Mathematics 371 – Numerical Analysis Discussion 3 – Numerical Differentiation and Extrapolation October 24-26, 2001

Background

On Monday, we introduced some basic techniques for numerical approximation of derivatives and derived the following error terms:

f′(x_{0}) = \{ \begin{matrix}\frac{f(x_{0}+h)−f(x_{0})}{h} − \frac{f′′(ξ_{f})}{2}h & (2 point forward difference) \\ \frac{−3f(x_{0}+2h)+4f(x_{0}+h)−f(x_{0})}{2h} + \frac{f′′′(ξ_{f})}{3}h^{2} & (3 point forward difference) \\ \frac{f(x_{0}+h)−f(x_{0}−h)}{2h} − \frac{f′′′(ξ_{c})}{6}h^{2} & (3 point centered difference) \end{matrix}

where ξ_{f} ∈ [x_{0}, x_{0} + h] for the 2-point formula, ξ_{f} ∈ [x_{0}, x_{0} + 2h] for the 3-point forward difference formula, and ξ_{b} ∈ [x_{0} − h, x_{0}], and ξ_{c} ∈ [x_{0} − h, x_{0} + h]. Because the error term for the centered difference approximation goes to zero faster as h → 0, to get a desired accuracy, we will not need to take h as small, and round-off problems will be correspondingly smaller!

Today, we want to think about a way to get more accurate approximations, without causing roundoff error problems by trying to use very small h values. The error for both the 2 point forward difference approximation above is O(h). The errors for 3 point forward difference and centered difference approximations are O(h^{2}).

There is a general way to combine several approximations derived from a particular method with a known error term that yields an improved error term. The name for the method in general is Richardson extrapolation. The idea is reminiscent of Aitken acceleration in some ways, but it is different. Here is the basic idea, in general terms. Suppose we have some way to produce approximations N(h) to some quantity M using different values of h, and suppose, for instance, that the error is O(h). Suppose we can expand the error in a power series in h as follows:

M = N(h) + c_{1}h + c_{2}h^{2} + c_{3}h^{3} + ⋯

Then if we combine the two approximations:

M = \{ \begin{matrix}N(h) + c_{1}h + c_{2}h^{2} + ⋯ \\ N(\frac{h}{2}) + c_{1} \frac{h}{2} + c_{2} (\frac{h}{2})^{2} + ⋯ \end{matrix}

by taking

M = 2M − M

= 2 (N (\frac{h}{2}) + c_{1} \frac{h}{2} + c_{2} (\frac{h}{2})^{2} + ⋯) − (N(h) + c_{1}h + c_{2}h^{2} + ⋯)

= (2N (\frac{h}{2}) − N(h)) + c′_{2}h^{2} + ⋯

then the h terms cancel! That is, using M ≐ (2N (\frac{h}{2}) − N(h)), we get an error term that is O(h^{2}) rather than O(h)!

Discussion Questions

A) Suppose the error term for the “N-method” was O(h^{2}) instead of O(h). How could you combine N(h) and N(h/2) to get an error term that is O(h^{3}) or better? Apply this to the three-point forward difference formula to derive an approximation to f′(x_{0}) with error O(h^{3}) or better.

B) Apply your method from part A to the 3-point centered difference formula to produce an approximation method for f′(x_{0}) with error O(h^{3}) or better. It can be shown, using Taylor series, that the error term for the centered difference approximation actually has the form c_{2}h^{2} + c_{4}h^{4} + ⋯ (only even powers of h). What does that say about the actual order of the error?

C) Generalizing part A, suppose the error term for the “N-method” was O(h^{k}) instead of O(h). How could you combine N(h) and N(h/2) to get an error term that is O(h^{k+1}) or better?

D) Use a degree 2 interpolating polynomial for f to derive a forward difference approximation to f′′(x_{0}). What is the error of your approximation? For which k is the error O(h^{k})?

E) Use your answer from C and Richardson extrapolation to derive an approximation

method for f′′(x_{0}) with error O(h^{2}) or better. F) There’s nothing magic about h and h/2 in Richardson Extrapolation. Do Exercise 9

from Section 4.2 in the text to see how the same sort of improvement of the order of the error could be done with h, h/3, h/9, etc.

Assignment

Write-ups due in class Wednesday, October 31.