Richardson extrapolation

From Wikipedia, the free encyclopedia

In numerical analysis, Richardson extrapolation is a method to improve an approximation that depends on a step size. It is named after Lewis Fry Richardson.

1 Simple definition
2 General formula
3 Example
4 References
5 See also

[edit] Simple definition

Suppose that A(h) is an estimation of order hⁿ for $A=\lim_{h\to 0}A(h)$ , i.e. $A-A(h) = a_n h^n+O(h^m),~a_n\ne0,~m>n$ . Then

$R(h) = A(h/2) + \frac{A(h/2)-A(h)}{2^n-1} = \frac{2^n\,A(h/2)-A(h)}{2^n-1}$

is called the Richardson extrapolate of A(h); it is an estimate of order h^m for A, with m>n.

More generally, the factor 2 can be replaced by any other factor, as shown below.

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).

[edit] 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

$A - A(h) = a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots$

where the a_i are unknown constants and the k_i are known constants such that h^k_i > h^k_i+1.

The exact value sought can be given by

$A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots$

which can be simplified with Big O notation to be

$A = A(h)+ a_0h^{k_0} + O(h^{k_1}). \,\!$

Using the step sizes h and h / t for some t, the two formulas for A are:

$A = A(h)+ a_0h^{k_0} + O(h^{k_1}) \,\!$

$A = A\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + O(h^{k_1}) .$

Multiplying the second equation by t^k0 and subtracting the first equation gives

$(t^{k_0}-1)A = t^{k_0}A\left(\frac{h}{t}\right) - A(h) + O(h^{k_1})$

which can be solved for A to give

$A = \frac{t^{k_0}A\left(\frac{h}{t}\right) - A(h)}{t^{k_0}-1} + O(h^{k_1}) .$

By this process, we have achieved a better approximation of A by subtracting the largest term in the error which was O(h^k₀). This process can be repeated to remove more error terms to get even better approximations.

A general recurrence relation can be defined for the approximations by

$A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1}$