# 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 hq (magenta) are drawn in the left panel. The values of the finite difference approximations, denoted by F(h) and F(hq), are displayed below and the points (h, F(h)) and (hq, F(hq)) 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(hq) generally become more accurate. The extrapolated estimate F(0) converges to f′(x0) even more rapidly than F(h) or F(hq), 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