Module

for

Numerical Differentiation, Part II

Richardson's Extrapolation

 

Background.

    Numerical differentiation formulas can be derived by first constructing the Lagrange interpolating polynomial  [Graphics:Images/RichardsonExtrapMod_gr_1.gif] through three points, differentiating the Lagrange polynomial, and finally evaluating  [Graphics:Images/RichardsonExtrapMod_gr_2.gif]  at the desired point.  The truncation error is be investigated, but round off error from computer arithmetic using computer numbers will be studied in another lab.

Theorem  (Three point rule for [Graphics:Images/RichardsonExtrapMod_gr_3.gif]).  The central difference formula for  the first derivative, based on three points is  

    [Graphics:Images/RichardsonExtrapMod_gr_4.gif],  

and the remainder term is

    [Graphics:Images/RichardsonExtrapMod_gr_5.gif].

Together they make the equation  [Graphics:Images/RichardsonExtrapMod_gr_6.gif],  and the truncation error bound is  

    [Graphics:Images/RichardsonExtrapMod_gr_7.gif]  

where  [Graphics:Images/RichardsonExtrapMod_gr_8.gif].  This gives rise to the Big "O" notation for the error term for  [Graphics:Images/RichardsonExtrapMod_gr_9.gif]:

    [Graphics:Images/RichardsonExtrapMod_gr_10.gif].   

Proof  Richardson's Extrapolation  Richardson's Extrapolation

 

Theorem  (Five point rule for [Graphics:Images/RichardsonExtrapMod_gr_11.gif]).  The central difference formula for  the first derivative, based on five points is  

    [Graphics:Images/RichardsonExtrapMod_gr_12.gif],  

and the remainder term is

    [Graphics:Images/RichardsonExtrapMod_gr_13.gif].

Together they make the equation  [Graphics:Images/RichardsonExtrapMod_gr_14.gif],  and the truncation error bound is  

    [Graphics:Images/RichardsonExtrapMod_gr_15.gif]  

where  [Graphics:Images/RichardsonExtrapMod_gr_16.gif].  This gives rise to the Big "O" notation for the error term for  [Graphics:Images/RichardsonExtrapMod_gr_17.gif]:

    [Graphics:Images/RichardsonExtrapMod_gr_18.gif].  

Proof  Richardson's Extrapolation  Richardson's Extrapolation

 

Theorem  (Richardson's Extrapolation for [Graphics:Images/RichardsonExtrapMod_gr_19.gif]).  The central difference formula for  the first derivative, based on five points is a linear combination of  [Graphics:Images/RichardsonExtrapMod_gr_20.gif] and [Graphics:Images/RichardsonExtrapMod_gr_21.gif].

    [Graphics:Images/RichardsonExtrapMod_gr_22.gif],  

where  [Graphics:Images/RichardsonExtrapMod_gr_23.gif]  and  [Graphics:Images/RichardsonExtrapMod_gr_24.gif].

Proof  Richardson's Extrapolation  Richardson's Extrapolation

 

Animations (Numerical Differentiation  Numerical Differentiation).  Internet hyperlinks to animations.

 

Computer Programs  Richardson's Extrapolation  Richardson's Extrapolation

 

Richardson's Extrapolation.  

    Richardson's extrapolation relates the five point rule and the three point rule,  [Graphics:Images/RichardsonExtrapMod_gr_25.gif],  that was studied previously.  

    [Graphics:Images/RichardsonExtrapMod_gr_26.gif].  

Enter the three point formula for numerical differentiation.

 

[Graphics:Images/RichardsonExtrapMod_gr_27.gif]

[Graphics:Images/RichardsonExtrapMod_gr_28.gif]

Project III.  

    Investigate the numerical differentiation formulae  [Graphics:Images/RichardsonExtrapMod_gr_29.gif]  and error bound  [Graphics:Images/RichardsonExtrapMod_gr_30.gif]  where  [Graphics:Images/RichardsonExtrapMod_gr_31.gif].   
The truncation error is be investigated, but round off error from computer arithmetic using computer numbers will be studied in another lab.

Enter the five point formula for numerical differentiation.

 

[Graphics:Images/RichardsonExtrapMod_gr_32.gif]

[Graphics:Images/RichardsonExtrapMod_gr_33.gif]

Example 1.  Consider the function  [Graphics:Images/RichardsonExtrapMod_gr_34.gif].   Find the formula for the third derivative [Graphics:Images/RichardsonExtrapMod_gr_35.gif], it will be used in our explorations for the remainder term and the truncation error bound.  Graph  [Graphics:Images/RichardsonExtrapMod_gr_36.gif].  Find the bound  [Graphics:Images/RichardsonExtrapMod_gr_37.gif].  Look at it's graph and estimate the value  [Graphics:Images/RichardsonExtrapMod_gr_38.gif], be sure to take the absolute value if necessary.
Solution 1.

 

Example 2 (a).  Compute numerical approximations for the derivatives [Graphics:Images/RichardsonExtrapMod_gr_57.gif], using step sizes [Graphics:Images/RichardsonExtrapMod_gr_58.gif].  
2 (b).  Plot the numerical approximation [Graphics:Images/RichardsonExtrapMod_gr_59.gif] over the interval [Graphics:Images/RichardsonExtrapMod_gr_60.gif].  Compare it with the graph of [Graphics:Images/RichardsonExtrapMod_gr_61.gif] over the interval [Graphics:Images/RichardsonExtrapMod_gr_62.gif].  
Solution 2.

 

Example 3.  Plot the absolute error  [Graphics:Images/RichardsonExtrapMod_gr_95.gif]  over the interval  [Graphics:Images/RichardsonExtrapMod_gr_96.gif], and estimate the maximum absolute error over the interval.
Compute the error bound  [Graphics:Images/RichardsonExtrapMod_gr_97.gif]  and observe that  [Graphics:Images/RichardsonExtrapMod_gr_98.gif]  over  [Graphics:Images/RichardsonExtrapMod_gr_99.gif].  
Solution 3.

 

Example 4.  Investigate the behavior of  [Graphics:Images/RichardsonExtrapMod_gr_113.gif].  If the step size is reduced by a factor of  [Graphics:Images/RichardsonExtrapMod_gr_114.gif]  then the error bound is reduced by  [Graphics:Images/RichardsonExtrapMod_gr_115.gif].  This is the  [Graphics:Images/RichardsonExtrapMod_gr_116.gif]  behavior.
Solution 4.

 

Example 5.  Compare the error bounds for the three point and five point formulas.
5 (a).  Which is smaller [Graphics:Images/RichardsonExtrapMod_gr_139.gif]?  Can you justify it?  
5 (b).  Which is smaller [Graphics:Images/RichardsonExtrapMod_gr_140.gif]?   Can you justify it?  
Solution 5.

 

 

Project IV.  

    Investigate Richardson's extrapolation for numerical differentiation.

Example 6.  In general, show that  [Graphics:Images/RichardsonExtrapMod_gr_148.gif].  
Solution 6.

 

Example 7.  Consider the function  [Graphics:Images/RichardsonExtrapMod_gr_153.gif].   Find the approximations  [Graphics:Images/RichardsonExtrapMod_gr_154.gif], [Graphics:Images/RichardsonExtrapMod_gr_155.gif]  and then use the extrapolation formula  [Graphics:Images/RichardsonExtrapMod_gr_156.gif].  
Compute  [Graphics:Images/RichardsonExtrapMod_gr_157.gif]  directly.  Finally, compare these numerical approximations for the derivative with  [Graphics:Images/RichardsonExtrapMod_gr_158.gif].
Solution 7.

 

Various Scenarios and Animations for Richardson's Extrapolation and higher derivatives.

Example 8.  Given  [Graphics:Images/RichardsonExtrapMod_gr_172.gif], find numerical approximations to the derivative  [Graphics:Images/RichardsonExtrapMod_gr_173.gif], using five points and the central difference formula.
Solution 8.

 

Example 9.  Given  [Graphics:Images/RichardsonExtrapMod_gr_193.gif], find numerical approximations to the derivative  [Graphics:Images/RichardsonExtrapMod_gr_194.gif], using five points and the central difference formula.
Solution 9.

 

Example 10.  Given  [Graphics:Images/RichardsonExtrapMod_gr_214.gif], find numerical approximations to the derivative  [Graphics:Images/RichardsonExtrapMod_gr_215.gif], using five points and the central difference formula.
Solution 10.

 

Old Lab Project (Numerical Differentiation  Numerical Differentiation).  Internet hyperlinks to an old lab project.  

 

Research Experience for Undergraduates

Numerical Differentiation  Numerical Differentiation  Internet hyperlinks to web sites and a bibliography of articles.  

Richardson's Extrapolation  Richardson's Extrapolation  Internet hyperlinks to web sites and a bibliography of articles.  

 

Download this Mathematica Notebook Richardson's Extrapolation

 

Return to Numerical Methods - Numerical Analysis

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(c) John H. Mathews 2004