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  

        .  

Proof  Aitken's & Steffensen's acceleration  Aitken's & Steffensen's acceleration  

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.  

Proof  Aitken's & Steffensen's acceleration  Aitken's & Steffensen's acceleration  

Computer Programs  Aitken's & Steffensen's acceleration  Aitken's & Steffensen's acceleration  

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.

Research Experience for Undergraduates

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

Download this Mathematica Notebook Aitken's Process and Steffensen's Acceleration

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004