Scientific Computing

This module illustrates Richardson extrapolation, which is a process
for obtaining increased accuracy in a discretized approximation by
extrapolating results from coarse discretizations to an aribtrarily
fine one. If we have approximate results for two different values of
the discretization parameter *h* (e.g, a step size or mesh
spacing) and we know the functional form (e.g., linear or quadratic) of
the error in the approximation as *h* goes to zero (e.g., from a
Taylor series analysis), then we can interpolate the given results with
the appropriate function and evaluate the interpolant for
*h* = 0

The user first selects a function *f*(*x*)*x*_{0}*x*_{0},
*f*(*x*_{0}))*h* and the ratio *q* between the two step sizes to be used.
The two resulting secant lines corresponding to finite difference
approximations computed with step sizes *h* (blue) and
*h* ⁄*q**F*(*h*)*F*(*h*
⁄*q*)*h*, *F*(*h*))*h*
⁄*q*, *F*(*h* ⁄*q*))

Let *F*(*y*)*f*′(*x*_{0})*y*. For the first-order accurate forward and backward difference
formulas, *F*(*y*)*f*′(*x*_{0})*y* goes to
zero, and for the second-order accurate, centered difference formula,
*F*(*y*)*F*(*y*)*y* approaches zero, we can use
Richardson extrapolation to estimate *F*(0)*F*(*y*)*F*(0))*F*(0)*x*_{0}, *f*(*x*_{0}))*F*(0)*f*′(*x*_{0})

The user can experiment with the values of *h* and *q*.
As *h* becomes smaller and *q* larger, the finite difference
approximations *F*(*h*)*F*(*h* ⁄*q*)*F*(0)*f*′(*x*_{0})*F*(*h*)*F*(*h*
⁄*q*)

**Reference:** Michael T. Heath, *Scientific Computing,
An Introductory Survey*, 2nd edition, McGraw-Hill, New York,
2002. See Section 8.7, especially Example 8.8 and Figure 8.6.

**Developers:** Evan VanderZee and Michael Heath