Richardson extrapolation

From Wikipedia, the free encyclopedia

In numerical analysis, Richardson extrapolation is a method used to improve the rate of convergence of a limit typically depending on a parameter going to zero. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century.[1][2] In the words of Birkhoff and Rota, "... its usefulness for practical computations can hardly be overestimated."[3]

Contents

[edit] Example of Richardson extrapolation

Suppose that A(h) is an estimation of order n for A_0=\lim_{h\to 0}A(h), i.e. A_0-A(h) \sim h^n\, as h\to0. 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).

If A(h) - A_0= a_n h^n+O(h^m),~a_n\ne0,~m>n, then R(h) is an estimate of order greater than or equal to m for A.

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_0 - A(h)= a_1h^{k_1} + a_2h^{k_2} + \cdots

where the ai are nonzero constants and the ki are positive constants such that ki < ki+1.

Using big O notation, one has

A_0 = A(h)+ a_1h^{k_1} + O(h^{k_2}).\,

For a different step size h / t with some t>1 (to fix ideas), one gets a second formula for A0,

A_0 = A\!\left(\tfrac{h}{t}\right) + a_1\left(\tfrac{h}{t}\right)^{k_1} + O(h^{k_2}) .

Multiplying the second equation by tk1 and subtracting the first equation gives

(t^{k_1}-1)A_0 = t^{k_1}A\left(\tfrac{h}{t}\right) - A(h) + O(h^{k_1})

which can be solved for A to give

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

By this process, we have achieved a better approximation of A0 by subtracting the largest term in the error which was O(hk1). This process can be repeated to remove more error terms to get even better approximations. It should be noted, however, that the above expression is not necessarily an estimation of order k2, since several error terms could have disappeared at once. Also, a new error term of order larger than k2, could have been introduced. Thus, in order to re-iterate the method, the true order of the new estimate needs to be determined first.

A well-known practical use of Richardson extrapolation is Romberg integration, which applies Richardson extrapolation to the trapezium rule.

It should be noted that the Richardson extrapolation can be considered as a linear sequence transformation.

[edit] Example

Using Taylor's theorem,

f(x+h) = f(x) + f'(x)h + \frac{f''(x)}{2}h^2 + \cdots

the derivative of f(x) is given by

f'(x) = \frac{f(x+h) - f(x)}{h} - \frac{f''(x)}{2}h + \cdots.

If the initial approximations of the derivative are chosen to be

A_1(h) = \frac{f(x+h) - f(x)}{h}

then k1 = 1, unless f"(x) = 0.

For t = 2, the first formula extrapolated for A would be

A = 2A_1\!\left(\tfrac{h}{2}\right) - A_1(h) + O(h^2) .

For the new approximation

A_2(h) = 2A_1\!\left(\tfrac{h}{2}\right) - A_1(h) = \frac{4f(x+h/2)-f(x+h)-3f(x)}{h}

one could extrapolate again to obtain

A_0 = \frac{4A_1\!\left(\frac{h}{2}\right) - A_1(h)}{3} + O(h^3) .

[edit] See also

[edit] References

  1. ^ Richardson, L. F. (1910). "The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam". Philosophical Transactions of the Royal Society of London, Series A 210: 307–357. 
  2. ^ Richardson, L. F. (1927). "The deferred approach to the limit". Philosophical Transactions of the Royal Society of London, Series A 226: 299–349. 
  3. ^ Page 126 of Birkhoff, Garrett; Gian-Carlo Rota (1978). Ordinary differential equations, 3rd edition, John Wiley and sons. ISBN 047107411X. OCLC 4379402. 
  • Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.

[edit] External links