Richardson Extrapolation
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 (i.e., extrapolate to the limit) to obtain an
approximation of higher-order accuracy. This module illustrates this
extrapolation process for the particular example of computing a finite
difference approximation to the derivative of a function.
The user first selects a function f(x)
and a point x0 at which its derivative
is to be approximated. The selected function is drawn in the left
panel in black and the point (x0,
f(x0)) is marked in red. Next the user
selects a finite difference formula, along with the coarser step size
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 (magenta) are drawn in the left
panel. The values of the finite difference approximations, denoted by
F(h) and F(h
⁄q), are displayed below and the points
(h, F(h)) and (h
⁄q, F(h ⁄q)) are marked
in the right panel using the same color scheme.
Let F(y) denote the value of the finite
difference approximation to
f′(x0) using step size
y. For the first-order accurate forward and backward difference
formulas, F(y) converges linearly to
f′(x0) as y goes to
zero, and for the second-order accurate, centered difference formula,
F(y) converges quadratically. In either
case, based on this knowledge of the theoretical behavior of
F(y) as y approaches zero, we can use
Richardson extrapolation to estimate F(0). The
interpolant F(y) to the two previous
approximations is drawn in the right panel and the extrapolated point
(0, F(0)) is marked in red. The estimated tangent
line of slope F(0) passing through
(x0, f(x0)) is
drawn in the left panel in red. The extrapolated value of
F(0) is displayed below for comparison with the
actual derivative f′(x0),
which is also plotted as a black point (possibly obscured by the red
point) in the right panel.
The user can experiment with the values of h and q.
As h becomes smaller and q larger, the finite difference
approximations F(h) and
F(h ⁄q) generally become more
accurate. The extrapolated estimate F(0) converges
to f′(x0) even more rapidly
than F(h) or F(h
⁄q), though the error still remains nonzero, in
general, for any nonzero step size.
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