Module

for

Aitken's [Graphics:Images/AitkenSteffensenMod_gr_2.gif] 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  
[Graphics:Images/AitkenSteffensenMod_gr_3.gif]  exhibits linear convergence.  A technique called Aitken's  [Graphics:Images/AitkenSteffensenMod_gr_4.gif] 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 [Graphics:Images/AitkenSteffensenMod_gr_5.gif],  define the forward difference  [Graphics:Images/AitkenSteffensenMod_gr_6.gif]  by

        
[Graphics:Images/AitkenSteffensenMod_gr_7.gif]    for   [Graphics:Images/AitkenSteffensenMod_gr_8.gif].  

Higher powers  
[Graphics:Images/AitkenSteffensenMod_gr_9.gif]  are defined recursively by  

    
    [Graphics:Images/AitkenSteffensenMod_gr_10.gif]    for   [Graphics:Images/AitkenSteffensenMod_gr_11.gif].  

When  k=2  we have the useful formula  [Graphics:Images/AitkenSteffensenMod_gr_12.gif]  which simplifies to be:  
        
    [Graphics:Images/AitkenSteffensenMod_gr_13.gif]    for   [Graphics:Images/AitkenSteffensenMod_gr_14.gif].  

 

Theorem (Aitken's Acceleration).  Assume that the sequence  [Graphics:Images/AitkenSteffensenMod_gr_15.gif]  converges linearly to the limit p and that  [Graphics:Images/AitkenSteffensenMod_gr_16.gif]  for all  [Graphics:Images/AitkenSteffensenMod_gr_17.gif].   If there exists a real number A with  [Graphics:Images/AitkenSteffensenMod_gr_18.gif]   such that  

        
[Graphics:Images/AitkenSteffensenMod_gr_19.gif]  

then the sequence  
[Graphics:Images/AitkenSteffensenMod_gr_20.gif]  defined by  

        
[Graphics:Images/AitkenSteffensenMod_gr_21.gif]  

converges to
p faster than  [Graphics:Images/AitkenSteffensenMod_gr_22.gif],  in the sense that  

        
[Graphics:Images/AitkenSteffensenMod_gr_23.gif].  

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
[Graphics:Images/AitkenSteffensenMod_gr_24.gif], two steps of Newton's method are used to compute  [Graphics:Images/AitkenSteffensenMod_gr_25.gif]  and  [Graphics:Images/AitkenSteffensenMod_gr_26.gif],  then Aitken's  [Graphics:Images/AitkenSteffensenMod_gr_27.gif] process is used to compute  [Graphics:Images/AitkenSteffensenMod_gr_28.gif].   To continue the iteration set [Graphics:Images/AitkenSteffensenMod_gr_29.gif] 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).

[Graphics:Images/AitkenSteffensenMod_gr_30.gif]

Mathematica Subroutine (Steffensen's Method).

[Graphics:Images/AitkenSteffensenMod_gr_31.gif]

Example 1.   Use Newton's method to construct a linearly convergent sequence  [Graphics:Images/AitkenSteffensenMod_gr_32.gif]  which converges slowly to the multiple root  [Graphics:Images/AitkenSteffensenMod_gr_33.gif]  of  [Graphics:Images/AitkenSteffensenMod_gr_34.gif].  
Then use the Aitken  [Graphics:Images/AitkenSteffensenMod_gr_35.gif] process to construct  [Graphics:Images/AitkenSteffensenMod_gr_36.gif]   which converges faster to the root  [Graphics:Images/AitkenSteffensenMod_gr_37.gif].  
Solution 1.

 

Example 2.  Use Newton's method and Steffensen's acceleration method to find numerical approximations to the multiple root  [Graphics:Images/AitkenSteffensenMod_gr_58.gif]  of the function  [Graphics:Images/AitkenSteffensenMod_gr_59.gif].  
Show details of the computations for the starting value  [Graphics:Images/AitkenSteffensenMod_gr_60.gif].  Compare the number of iterations for the two methods.
Solution 2.

 

Example 3.  Use Newton's method to construct a linearly convergent sequence  [Graphics:Images/AitkenSteffensenMod_gr_112.gif]  which converges slowly to the multiple root  [Graphics:Images/AitkenSteffensenMod_gr_113.gif]  of  [Graphics:Images/AitkenSteffensenMod_gr_114.gif].  
Then use the Aitken  [Graphics:Images/AitkenSteffensenMod_gr_115.gif] process to construct  [Graphics:Images/AitkenSteffensenMod_gr_116.gif]   which converges faster to the root  [Graphics:Images/AitkenSteffensenMod_gr_117.gif].  
Solution 3.

 

Example 4.  Use Newton's method and Steffensen's acceleration method to find numerical approximations to the multiple root  [Graphics:Images/AitkenSteffensenMod_gr_138.gif]  of the function  [Graphics:Images/AitkenSteffensenMod_gr_139.gif].  
Show details of the computations for the starting value  [Graphics:Images/AitkenSteffensenMod_gr_140.gif].  Compare the number of iterations for the two methods.
Solution 4.

 

Example 5.  Use Newton's method to construct a linearly convergent sequence  [Graphics:Images/AitkenSteffensenMod_gr_192.gif]  which converges slowly to the multiple root  [Graphics:Images/AitkenSteffensenMod_gr_193.gif]  of  [Graphics:Images/AitkenSteffensenMod_gr_194.gif].  
Then use the Aitken  [Graphics:Images/AitkenSteffensenMod_gr_195.gif] process to construct  [Graphics:Images/AitkenSteffensenMod_gr_196.gif]   which converges faster to the root  [Graphics:Images/AitkenSteffensenMod_gr_197.gif].  
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  [Graphics:Images/AitkenSteffensenMod_gr_218.gif].  
Show details of the computations for the starting value  [Graphics:Images/AitkenSteffensenMod_gr_219.gif].  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