EXPLANATION FILE OF PROGRAM AITKEN
==================================
Aitken Acceleration
-------------------
In this section, we return to an examination of the fundamental iteration
form:
x = g(x)
Recall that in applying this equation numerically. the iteration sequence is
x = g(x )
n+1 n
When convergence occurs, the result is called a fixed point. However, as de-
monstrated in the earlier discussion and examples, convergence is assured only
if |dg/ dx| < 1 in the range of the iteration sequence. The doser dg/ dx is to
zero, the faster the convergence will be.
The convergence properties of the above iteration formula can be improved on
by using the Aitken D² method. This technique is, in essence, based on accoun-
ting for the curvature of the function as the root is approached. As shown in
the previous section for the Newton and secant algorithrns, the curvature of
the function can greatly affect convergence if the iteration is not dose to a
root. itken has provided a means for accelerating the convergence by develo-
ping an algorithm that employs three earlier calculated values to parabolical-
ly predict an improved position. The acceleration formula is
(xn - xn-1)²
x'n = xn - ---------------- (6.11.1)
xn - 2xn-1 +xn-2
It is important to note that this formula requires three previous Xn+1 = g(xn)
iteration steps to be calculated before the acceleration can be performed.
Once the accelerated vaIue is determined, it is used as the first guess in
another sequence of three iterations.
To apply this methodology to the problem of finding the locations of the ze-
ros of y(x), we will again examine the following form:
x = g(x) = x + cy(x)
We found previously that the Newton, secant, and false-position formulae could
be derived if c = -l/(dy/dx). However, this form requires knowledge of dy/dx,
which we will not resort to. Instead, a constant value will be used for c. ln
principle, we can always find values of c that are sufficiently small (and of
sign opposite to dy/dx) to assure convergence if the iteration is near a root,
However, the resulting convergence may be slow. Therefore, c can be considered
an empirically chosen convergence factor. This will be discussed more in asso-
ciation with later examples.
A subroutine that applies the concept of Aitken acceleration to finding the
roots of a function, y(x), has been implemented in program Aitken. This sub-
routine requires as input the converge factor, c, and an error goal that
causes a return when the iterative change in x. is less than E. The subroutine
also requires an initial guess, XO, and an iteration limit, M. Two values are
returned: X and N. X is the estimate of the position of the zero, and N is the
number of iterations used to obtain that estimate. The last value calculated
for Y is also available.
Aitken acceleration can be very effective. For example, consider the follo-
wing functions which were used in previous examples:
A) y(x) = x - 2 sin x (initial guess xO = pi/2)
B) y(x) = Xl + 2X2 - X - 2 (initial guess xO = -1.5)
C) y(x) = sin x (initial guess xO = 20)
Sample results are shown below. lncluded in the last column of each tabulation
are the results obtained using c = l/(dy/dx), Newton's method coupled with
Aitken acceleration.
Example A)
----------
Convergence Factor, c
E -0.1 +0.1 -1 1 -l/dy/dx
0.1 1.9829056(3) 2.0200624(3) 1.9999994(2) -0.083621(5) 2.0006853
0.0001 1.8783217(5) 1.9056554(7) 1.8954142(7) -0.001450537(6) 1.8955769
0.0000001 1.8954973(15) 1.8954979(19) 1.8954940(11) 0.00000045(8) 1.8954937
True Value 1.8954943 1.8954943 1.8954943 0 1.8954943
Example B)
----------
Convergence Factor, c
E -0.1 +0.1 -1 1 -l/dy/dx
0.1 0.167656(4) 0.0533662(3) -2.0119023(4) -0.875(2) 1(2)
0.0001 -2.0038728(15) -1.43(17) -2.0001375(8) -0.99989661(8) 1(2)
0.0000001 -1.9999989(25) -2.0000013(97) -2.(16) -0.99999989(14) 1(2)
True Value -2 -2 -2 -1 -1
Example C)
----------
Convergence Factor, c
E -0.1 +0.1 -1 1 -l/dy/dx
0.1 17.967623(3) 17.504558(9) 19.087055(2) 46.180888(3) 18.790797
0.0001 21.952955(9) 12.505906(5) 18.649192(7) 47.123642(7) 18.849757
0.0000001 21.99113(19) 12.566314(9) 18.849556(12) 47.12389(10) 18.849556
True Value 21.99115 12.566371 18.849556 47.12389 18.849556
There are several observations to be made. First, using a constant for c in-
stead of the Newton form leads to mixed results in terms of the number of ite-
rations required for a given E. ln the first table (Example A), the conver-
gence is somewhat slower for high-precision results when the Newton form for c
is used rather than employing a constant. ln the second table (Example B), the
reverse is true. The two are comparable in the third table (Example C).
The second observation is that the accuracy of the results should be viewed
with caution. The accuracy is not E; it can be much better or much worse. How-
ever, E can be used to roughly estima te the error.
It has been suggested by Hamming that instead of specifying an error limit
E, the number of iterations should be used as the iteration termination crite-
rion. However, by doing this, you would have no idea of the resulting accura-
cy. But, as a counterargument, fatal loops (possibly due to round-off error)
could be avoided by setting the number of iterations (M). Here, we use both
methods by employing E as the termination criterion and M to avoid infinite
loops.
The third observation is that there appears to be considerable freedom in
the choice of values for the convergence factor, c. It is usuaIly the case
that the smaIler c is, the slower the convergence. However, large values of c
can result in leaps in the iteration, which in turn lead to different roots.
This is evident in aIl of the tables. Also, the sign of c may or may not af-
fect which root is converged on, but can affect convergence rate.
The power of the Aitken acceleration method rests in its stable convergence
properties. Initial guesses for the locations of the zeros need not be as ac-
curate as those required for the Newton and secant methods. Also, the number
of iterations required is reasonably constant. As with any root-seeking me-
thod, however, there are limitations.
The numerical implementation of Aitken's method suffers from a potential
round-off error problem associated with the denominator of the acceleration
formula: xn - 2xn-1 + xn-2. When the iteration nears completion, this factor
aproaches zero, although the individual values, xn, xn-1 and xn-2, are nonzero
(i.e., they are aIl nearly equal). This can lead to a round-off error problem
at the very least, and perhaps a divide-by-zero overflow error. The subroutine
as written guards against the overflow problern, but the potential round-off
error can result in a reduction in the efficiency of the routine.
Another complication is the choice of the convergence factor, c. As discus-
sed earlier, if c is chosen so that convergence occurs, however slowly, the
accuracy test (the difference between successive values being less than E) may
not work weIl. That is, successive values may be close to one another but not
close to the root, and termination may occur far from the root. Also, choosing
too large a value for c can lead to convergence difficulties. Unfortunately,
you have no a priori knowledge of what the appropria te range for c is! Fortu-
nately, the algorithm is forgiving.
Another more general difficulty exists in the evaluation of y(x) itself.
There are some ways to evaluate y(x) that are better than others. For example,
consider the function y(x) = (x + 1)^5. Two distinctly different computational
ways of writing this equation are
y1 = (x + l)(x + l)(x + l)(x + l)(x + 1)
and y2 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1
The first form is more compact and faster in execution. It is also less prone
to round-off error in evaluation. This can be demonstrated as foIlows.
Consider the evaluation of y(x) near its root, say x = -1 + E. Under ideal
conditions (i.e., no round-off), the two computations become
y1 = E^5
5 4 3 2
and y2 = (1 - E) + 5(1 - E) - 10(1 - E) + 10(1 - E) - 5(1 - E) + 1
Mathematically, both expressions give y = 0 when E = O. However, when evalua-
ting the these forms numerically, y1 will evaluate to zero when E = 0, but y2
may not because of round-off error. Because we know that there must be values
of E that numerically lead to y2 = 0, it is apparent that round-off error may
(and very likely does) create a "root" that differs from the "true" or mathe-
matical root by some small amount. ln effect, by choosing a particular way to
evaluate y(x), fa Ise roots may unknowingly be introduced. Example 3 shows how
extreme the effect can be.
Given the above discussion, we can order what may go wrong with the Aitken
acceleration algorithm. First, the iteration may diverge or jump around if c
is too large, or if it is of the wrong sign. Second, the iteration may conver-
ge, but slowly, and the convergence test |Xn - Xn-1| < E may prematurely ter-
minate the iteration. Third, the convergence may be fast, but the result may
be a false root caused by round-off error. This last problem is not limited to
just the Aitken acceleration subroutine.
Despite all these potential problems, Aitken acceleration is a very useful
technique. In another section, we will consider a variation of this method
(see file Steffen.txt).
From [BIBLI 01].
--------------------------------------------------
End of file Aitken.txt