Mathematics 171 – Numerical Analysis 1 Discussion 4 – Numerical Differentiation and Extrapolation November 12, 1998

Background

On Tuesday, we introduced some basic techniques for numerical approximation of derivatives and derived the following error terms (h > 0):

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

where ξ_{f} ∈ [x_{0}, x_{0} + h], ξ_{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 two general ways to derive other numerical derivative methods of this type and analyze their error terms. To help us talk about the error terms, we will use the following terminology:

Definition. Let F be a function of h and k > 0. We say F is O(h^{k}) as h → 0 (in words: “F is big-Oh of h to the kth power as h goes to zero”) if there is a constant M such that |F (h)| ≤ M|h|^{k} for all sufficiently small h.

Bigger powers k correspond to faster rates of convergence to zero, since for example ℓ > m implies

lim_{h→0} \frac{h^{ℓ}}{h^{m}} = lim_{h→0} h^{ℓ−m} = 0,

so h^{ℓ} goes to zero faster than h^{m}.

The error for both the forward and backward difference approximations above is O(h). The error for the centered difference is O(h^{2}).

Discussion Questions

A) As we saw on Monday in the derivation of the centered difference formula, one way to try to derive this sort of approximation is to take several equations from Taylor approximations at different points and form a linear combination to cancel terms “behind” the first derivative terms. For example, find such a combination using the Taylor approximations:

\{ \begin{matrix}f(x_{0}) \\ f(x_{0} + h) = f(x_{0}) + f′(x_{0})h + \frac{f′′(x_{0})}{2!}h^{2} + \frac{f′′′(ξ_{1})}{3!}h^{3} \\ f(x_{0} + 2h) = f(x_{0}) + f′(x_{0})(2h) + \frac{f′′(x_{0})}{2!}(2h)^{2} + \frac{f′′′(ξ_{2})}{3!}(2h)^{3} \end{matrix}

and use it to derive a “three-point” forward difference formula. What is the error term? Show that the error can be written as \frac{f′′′(ξ)}{3}h^{2} for some ξ ∈ [x_{0}, x_{0} + 2h], so it is O(h^{2}) as h → 0. Ceteris paribus, which method is preferable: this 3-point formula or the centered difference approximation?

B) The same idea can also be used to derive formulas for approximating second and higher derivatives. For example, use

\{ \begin{matrix}f(x_{0} − h) = f(x_{0}) − f′(x_{0})h + \frac{f′′(x_{0})}{2!}h^{2} + \frac{f′′′(ξ_{1})}{3!}h^{3} \\ f(x_{0}) \\ f(x_{0} + h) = f(x_{0}) + f′(x_{0})h + \frac{f′′(x_{0})}{2!}h^{2} − \frac{f′′′(ξ_{2})}{3!}h^{3} \end{matrix}

to derive an approximation formula for f′′(x_{0}). What is the error term for this approximation? (Be careful: what happens if you use additional terms in the Taylor approximations?) Would you want to use this one with really small h’s? Why or why not?

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). In particular, 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)!

C) Use this extrapolation idea to derive a better approximation formula for second derivatives (one with error that is O(h^{4}) as h → 0).

D) 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 from question A.

Assignment

Group write-ups due in class Tuesday, November 17. (I will have them graded by Wednesday so you can pick them up before the exam on Thursday.)