| fl(x) | = +/-.x1.....xd 10e |
| = +/-(x1/10 +.......+xd/10d) 10e. |
This is a floating point number with base equal to 10 where x1 is not equal to zero, xi are integers between 0 and 9, the exponent e is also a bounded integer and d is an integer called the precision of the floating point system.
 |
| Figure: Number Systems |
The above figure depicts the relationship of the complex numbers C, the real
numbers R, the rational numbers Q, and the floating point numbers FP. The
numbers i = sqrt(-1), sqrt(2) and eps indicate that the sets are proper
subsets. The imaginary number i is not a real number because
- 2 q12....qm2 =
p12.....pn2,
and this is a contradiction to the uniqueness of a prime factorization. The eps is any small positive rational number which is less than the minimum of all positive floating point numbers.
Associated with each real number, x, and its floating point number, fl(x), is the floating point error, fl(x) -x. In general, this error decreases as the precision, d, increases. Each calculation has some floating point or roundoff error. Moreover, as additional calculations are done, there is an accumulation of these roundoff errors.
Example. x = -1.5378 and fl(x) = -0.154 101 where d = 3. The roundoff error is
- fl(x) -x = -.0022 .
- fl(x)2 = .237 10-1
| accumulation error | = fl(x)2 - x2 |
| = .237 101 - 1.53782 | |
| = 2.37 - 2.36482884 | |
| = -.00517116. |
1.1.2. Applied Area.
The accumulation of roundoff errors can be an important consideration in calculations concerning money. For example, the national debt has about 15 digits, and so floating point numbers that use 64 bits will tend to have significant roundoff errors.
Application to Time Value of Money. The following is a model of money for a loan that is being paid off by making a payment every month. The initial loan amount is y0, and the monthly interest rate is assumed to be constant. We wish to calculate the amount of the loan for any month k given a fixed interest rate, r, compounded monthly.
| Let | yk be the amount in an account at month k, |
| r equal the interest rate compounded monthly, and | |
| p equal the monthly payment. |
The amount at the end of the next month will be the old amount plus the interest on the old amount minus the payment. In terms of the above variables this has the form
-
yk+1 = yk + yk r/12 - p = a yk + b where a = 1 + r/12 and b = -p.
Since |a| > 1, we must be very careful about the effects of roundoff error either for large values of k or large roundoff errors. Later we shall return to this application.
Many problems have the same formulation, and another model is a to heat transfer.
Application to Discrete Form of Newton's Law of Cooling. This problem concerns the cooling of a well-stirred liquid such as a cup of coffee. Here we want to predict the temperature of the liquid based on some initial observations.
Newton's law of cooling is based on the observation that for small changes of time, h, the change in the temperature is nearly equal to the product of the c, the h and the difference in the room temperature and the present temperature of the coffee.
| Let | yk equal the temperature of a well stirred cup of coffee at time tk. |
| ysur equal the surrounding room temperature, and | |
| c measure the insulation ability of the cup. |
The symbolic form of Newton's law of cooling has the form
- yk+1 - yk = ch(ysur - yk).
Or,
-
yk+1 = (1 - ch) yk + chysur = a yk + b where a = 1 - ch and b = chysur .
The long run solution should be the room temperature; that is, yk should converge to ysur as k increases. This does happen if we impose the |ch| < 1 condition on the time step h. If h is such that |a| > 1, then this does not happen!
1.1.3. Model.
The model in this case appears to be very simple. It consists of three constants y0 , a, b and the formula
- yk+1 = a yk + b.
The formula must be used repeatedly, but with different yk being put into the right side. Often a and b are derived from formulating how yk changes as k increases (k reflects the time step.). The change in the amount yk is often modeled by dyk + b
- yk+1 - yk = dyk + b
where a = 1 + d.
1.1.4. Method.
This can be descibed in the following general notation which is independent of a particular computing tool.
First Order Finite Difference Algorithm.
- choose y0, a and b
- for k = 0, maxit
y(k+1) = a*y(k) + b (1) - endloop.
- for k = 0, maxit
The method for solving the above problem is a direct calculation of the work given in the loop in (1). An alternative is to use the following "telescoping" calculation and the geometric summation. Recall the geometric summation
- (1 + r + r2 +...+ rk )(1 - r) = 1 - rk+1.
- (1 + r + r2 +...+ rk ) = (1 - rk+1)/(1 - r).
Consequently, if |r| < 1, then 1+ r + r2 +... = 1/(1 - r).
In (1) we can compute yk by decreasing k by 1 so that
-
yk+1 = a (a yk-1 + b) + b = a2 yk-1 + a b + b = a2 (a yk-2 + b) + a b + b = a3 yk-2 + a2 b + a b + b . . . = ak+1y0 + b (ak +...+ a2 + a + 1) = ak+1y0 + b (1 - ak+1)/(1 - a). (2)
1.1.5. Implementation.
The Maple implementation of the first order finite difference algorithm (1) for the time value of money problem is as follows. Here an a savings plan extending over ten years with monthly payments of $100 is studied. The first computation assumes the interest rate is 12% compounded monthly. In this case the amount after ten years is $23,667. In the second computation we use 6% compounded monthly, and the amount is considerably less $16,753.
> x(0):=1:
> y(0):=100:
> h:=1:
> n:= 120:
> a:=1.010:
> b:=100
> for i from 0 to n do
> y(i+1) := a*y(i) + b;
> x(i+1) := x(i) + h;
> od:
> plot([seq([x(i),y(i)],i=0..n)],style = point);
 |
| Figure: Amount versus Months, 12% |
 |
| Figure: Amount versus Months, 6% |
The next computation involves a retirement plan that spans forty years, assumes an interest rate of 12% compounded monthly and a monthly payment of $100. In the figure below the top curve uses 10 digits for the floating point numbers and accumulates to $1,188,342.026. The bottom curve uses 3 digits and accumulates to $1,000,000. Notice that the difference between the calculations continues to increase. This is because the magnitude of a is greater than one, and this will be discussed later in more detail.
 |
| Figure: Amount versus Months, Digits = 3, 10 |
The application to heat transfer is as follows. Consider a cup of coffee,
which is initially at 200 degrees and is in a room with temperature equal to
70, and after 5 minutes it cools to 190 degrees. By using
- a = 1 - c h = 64/65 and
- b = c h 70 = 70/65.
The figure indicates the expected monotonic decrease to the steady state room temperature.
 |
| Figure: Temp. versus Time, a = 64/65 |
The next calculation is for a larger c = 2/13 which is computed from a
new second observed temperature of 100 after 5 minutes. In this case for
larger time step
- a = 1 - (2/13)10 = -7/13 and
- b = c h 70 = (2/13) 10 70 = 1400/13.
Notice that the computed solution no longer is montonic, but it does converge to the steady state solution. This indicates that our model for this large a time step is not very good.
 | ||
| Figure: Temp. versus Time, a = -7/13 |
 |
| Figure: Temp. versus Time, a = -17/13 |
The following is a Matlab code for Newton's law of cooling, and it compares the computed solution, uk, with the exact solution of the continuum model, uex. The reader should experiment with the number of time steps, kk, and observe the size of the error relative to kk. The form of the exact solution requires the use of calculus and will not be discussed here.
kk=20;
T =1.0;
dt =T/kk;
u0 = 200.;
c = 1.0;
usur = 70.;
uk = u0;
for k = 1:kk
uk = uk +dt*c*(usur -uk);
uex = usur + (u0 -usur)*exp(-c*(k)*dt);
error = abs(uk - uex);
vec(k) = error;
vecdt(k) = k*dt;
end
plot(vecdt,vec)
 |
| Figure: Discrete Error versus Time |
1.1.6. Assessment.
The time value of money model has a fixed interest rate and fixed deposit or payment. Both of these are not true; however, over shorter time intervals they are close to fixed values.
In the case of the heat transfer problem, the constants can be controled, but the formula for the temperature at the next time step is only an approximation which gets better as the time step h decreases. Moreover there are other modes of transfering heat such as diffusion and radiation.
Both applications may suffer from accumulation of roundoff error as was illustrated in the above calculations using Maple. On a computer (1) is not done with real numbers. At each step there is some new roundoff error Rk+1 .
-
Let Y0 = fl(y0), A = fl(a) and B = fl(b).
- for k = 0, maxit
Yk+1 = A Yk + B + Rk+1 (3) - endloop.
Next, we want to estimate the
- accumulation errors = Yk+1 - yk+1
under the assumption that the roundoff errors are uniformly bounded
.
-
Yk+1 - yk+1 = a (Yk - yk ) + Rk+1 = a[a (Yk-1 - yk-1 ) + Rk] + Rk+1 = a2 (Yk-1 - yk-1 ) + a Rk + Rk+1 . . . = ak+1 (Y0 - y0 ) + ak R1 +...+ Rk+1 . (4)
Now let r = |a| and R be the uniform bound on the roundoff error. Also, note
- (rk +...+1)(r - 1) = rk+1 - 1.
Thus, by using the triangle inequality
|Yk+1 - yk+1 | < rk+1 |Y0 - y0 | + R(rk+1 - 1)/(r - 1). (5)
Either r is less than one, or greater, or equal to one. An analysis of (4) and (5) immediately proves the next theorem.
Accumulation Error Theorem. Consider the first order finite difference algorithm, (1).
- If |a| < 1 and the roundoff errors are uniformly bounded, then the
accumulation error is uniformly bounded. If the roundoff error decreases,
then the accumulation error decreases.
- If |a| = 1 and the roundoff errors are uniformly bounded away from zero,
then the accumulation error will blowup.
- If |a| > 1 and Y0 - y0 is not zero, then the
accumulation error will also blowup.
1.1.7. Homework Problems.
- Use (2) to determine the amount aquired by depositing $100 each month in
an account which gets 12% compounded monthly.
- Consider the application to Newton's discrete law of cooling. Use (2) to
verify that if |hc| < 1, then yk+1 converges to the room
temperature.
- Write a computer code for the first order difference algorithm and apply
it to the applications.
- Consider the current national debt. Assume an interest rate of 9%
compounded monthly. If each of 200 million people pays $200 per month and no
additional debt is taken on, accurately compute when the debt will be paid
off. Experiment with different levels of precision (use Digits in Maple).
- Show (5) follows from (4).
- Fill in the remaining details of the proof of theorem.