Aitkin’s extrapolation.

Aitkin’s extrapolation is discussed in Hildebrand and also in Carnahan, Luther Wilkes, Applied Numerical Methods section 3.5 under the heading “Method of Successive Substitutions”. ..\Progdet\References.htm

                Begin with Newton's method

but rewrite this as an iterative procedure

               

where the function F is defined in terms of f to be

The solution to the iterative procedure is given by

.

Subtract the solution from the iterative procedure and expand F about a.

and we see that F¢(a) is the convergence factor.  If F¢(a) is less than 1, successive substitutions will

 

come closer to a, if larger than 1 they will diverge.

                Now iterate one more time to find

This is two equations and two unknowns.  Divide these to eliminate F’(a) and solve for a.

Note that the projected solution is the ratio of the geometric mean and the algebraic mean, both of which are approaching zero.  The method thus needs to keep the denominator from numerically going to zero which as a practical matter means an if statement to avoid using it if the denominator is less than 10-10 ci.  Aitkin’s method converges even when the sequence of iterations is diverging away from the solution.  The method does not require one dimension to work.  In the common integral differential equation

               

which is frequently solved by assuming a value for g and iterating to self consistency the method, frequently called the Broyle’s method, is applied to each value of r independently of the others.  Note however that ci and ci+1 must both be calculated using the same function F(c).  One must always skip at least one iterative step between extrapolations and most of us skip two.

Mixing

                A few more interesting things can come about from looking closely at the general iterative method.  The first iterative procedure can be made into

               

a slightly different procedure which does not change the solution

               

though beware of l=1

               

It is fairly logical to guess that l=0.5 which is usually called mixing would improve the situation in the case

and in the case of extreme instability one might not be surprised to find l=0.99, the surprise is that it frequently pays to make l negative and/or much greater than 1 which is called over-relaxation.  One could in principle solve for l in the three step method that allows the calculation of a, but I have never found this to help.