Module

for

Aitken's Process and Steffensen's Acceleration Method

Background for Aitken's Process

We have seen that Newton’s method converges slowly at a multiple root and the sequence of iterates
exhibits linear convergence.  A technique called Aitken's   process can be used to speed up convergence of any sequence that is linearly convergent.  In order to proceed, we will need a definition.

Definition (Forward Difference).  Given the sequence ,  define the forward difference    by

for   .

Higher powers
are defined recursively by

for   .

When  k=2  we have the useful formula    which simplifies to be:

for   .

Theorem (Aitken's Acceleration).  Assume that the sequence    converges linearly to the limit p and that    for all  .   If there exists a real number A with     such that

then the sequence
defined by

converges to
p faster than  ,  in the sense that

.

Steffensen's Acceleration

When Aitken's process is combined with the fixed point iteration in Newton’s method, the result is called Steffensen's acceleration.  Starting with
, two steps of Newton's method are used to compute    and  ,  then Aitken's   process is used to compute  .   To continue the iteration set and repeat the previous steps.

Mathematica Subroutine (Newton-Raphson Iteration).

``````
``````

Mathematica Subroutine (Steffensen's Method).

``````
``````

Example 1.   Use Newton's method to construct a linearly convergent sequence    which converges slowly to the multiple root    of  .
Then use the Aitken   process to construct     which converges faster to the root  .
Solution 1.

Example 2.  Use Newton's method and Steffensen's acceleration method to find numerical approximations to the multiple root    of the function  .
Show details of the computations for the starting value  .  Compare the number of iterations for the two methods.
Solution 2.

Example 3.  Use Newton's method to construct a linearly convergent sequence    which converges slowly to the multiple root    of  .
Then use the Aitken   process to construct     which converges faster to the root  .
Solution 3.

Example 4.  Use Newton's method and Steffensen's acceleration method to find numerical approximations to the multiple root    of the function  .
Show details of the computations for the starting value  .  Compare the number of iterations for the two methods.
Solution 4.

Example 5.  Use Newton's method to construct a linearly convergent sequence    which converges slowly to the multiple root    of  .
Then use the Aitken   process to construct     which converges faster to the root  .
Solution 5.

Example 6.  Use Newton's method and Steffensen's acceleration method to find numerical approximations to the multiple root near  x = 2  of the function  .
Show details of the computations for the starting value  .  Compare the number of iterations for the two methods.
Solution 6.

Aitken's Method and Steffensen's Acceleration  Aitken's Method and Steffensen's Acceleration  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2004