In numerical analysis, Richardson extrapolation is a sequence acceleration method, used to improve the rate of convergence of a sequence. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century. In the words of Birkhoff and Rota, "its usefulness for practical computations can hardly be overestimated."
Contents
- Example of Richardson extrapolation
- General formula
- Example
- Example pseudocode code for Richardson extrapolation
- References
Practical applications of Richardson extrapolation include Romberg integration, which applies Richardson extrapolation to the trapezoid rule, and the Bulirsch–Stoer algorithm for solving ordinary differential equations.
Example of Richardson extrapolation
Suppose that we wish to approximate
Define a new method
Then
Very often, it is much easier to obtain a given precision by using R(h) rather than A(h') with a much smaller h' , which can cause problems due to limited precision (rounding errors) and/or due to the increasing number of calculations needed (see examples below).
General formula
Let A(h) be an approximation of A that depends on a positive step size h with an error formula of the form
where the ai are unknown constants and the ki are known constants such that hki > hki+1.
The exact value sought can be given by
which can be simplified with Big O notation to be
Using the step sizes h and h / t for some t, the two formulas for A are:
Multiplying the second equation by tk0 and subtracting the first equation gives
which can be solved for A to give
By this process, we have achieved a better approximation of A by subtracting the largest term in the error which was O(hk0). This process can be repeated to remove more error terms to get even better approximations.
A general recurrence relation beginning with
where
The Richardson extrapolation can be considered as a linear sequence transformation.
Additionally, the general formula can be used to estimate k0 when neither its value nor A is known a priori. Such a technique can be useful for quantifying an unknown rate of convergence. Given approximations of A from three distinct step sizes h, h / t, and h / s, the exact relationship
yields an approximate relationship
which can be solved numerically to estimate k0.
Example
Using Taylor's theorem about h=0,
the derivative of f(x) is given by
If the initial approximations of the derivative are chosen to be
then ki = i+1.
For t = 2, the first formula extrapolated for A would be
For the new approximation
we can extrapolate again to obtain
Example pseudocode code for Richardson extrapolation
The following pseudocode in MATLAB style demonstrates Richardson extrapolation to help solve the ODE Trapezoidal(f, tStart, tEnd, h, y0)
exists which attempts to computes y(tEnd)
by performing the trapezoidal method on the function f
, with starting point y0
and tStart
and step size h
.
Note that starting with too small an initial step size can potentially introduce error into the final solution. Although there are methods designed to help pick the best initial step size, one option is to start with a large step size and then to allow the Richardson extrapolation to reduce the step size each iteration until the error reaches the desired tolerance.