Richardson extrapolation

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. [cite journal | last=Richardson | first=L. F. | authorlink=Lewis Fry Richardson | title=The approximate arithmetical solution by finite differences of physical problems including differential equations, with an application to the stresses in a masonry dam | journal=Philosophical Transactions of the Royal Society of London, Series A | year=1910 | volume=210 | pages=307–357] [cite journal | last=Richardson | first=L. F. | authorlink=Lewis Fry Richardson | title=The deferred approach to the limit | journal=Philosophical Transactions of the Royal Society of London, Series A | year=1927 | volume=226 | pages=299–349 | doi=10.1098/rsta.1927.0008] In the words of Birkhoff and Rota, "... its usefulness for practical computations can hardly be overestimated." [Page 126 of cite book | last=Birkhoff | first=Garrett | authorlink=Garrett Birkhoff | coauthors=Gian-Carlo Rota | title=Ordinary differential equations | publisher=John Wiley and sons | year=1978 | edition=3rd edition | isbn=047107411X | oclc= 4379402]

Example of Richardson extrapolation

Suppose that "A"("h") is an estimation of order "hⁿ" for$A=lim\_\{h\; o\; 0\}A(h)$, i.e. $A-A(h)\; =\; a\_n\; h^n+O(h^m),~a\_n\; e0,~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)" ratherthan "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 :$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\}\; ight)\; +\; a\_0left(frac\{h\}\{t\}\; ight)^\{k\_0\}\; +\; O(h^\{k\_1\})\; .$

Multiplying the second equation by "t"^"k"₀ and subtracting the first equation gives:$(t^\{k\_0\}-1)A\; =\; t^\{k\_0\}Aleft(frac\{h\}\{t\}\; ight)\; -\; A(h)\; +\; O(h^\{k\_1\})$which can be solved for "A" to give:$A\; =\; frac\{t^\{k\_0\}Aleft(frac\{h\}\{t\}\; ight)\; -\; 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\_ileft(frac\{h\}\{t\}\; ight)\; -\; A\_i(h)\}\{t^\{k\_i\}-1\}$such that :$A\; =\; A\_\{i+1\}(h)\; +\; O(h^\{k\_\{i+1)$with $A\_0=A(h)$.

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.

Example

Using Taylor's theorem,:$f(x+h)\; =\; f(x)\; +\; f\text{'}(x)h\; +\; frac\{f"(x)\}\{2\}h^2\; +\; cdots$the derivative of "f"("x") is given by:$f\text{'}(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\_0(h)\; =\; frac\{f(x+h)\; -\; f(x)\}\{h\}$then "k_i" = "i"+1.

For "t" = 2, the first formula extrapolated for "A" would be:$A\; =\; 2A\_0!left(frac\{h\}\{2\}\; ight)\; -\; A\_0(h)\; +\; O(h^2)\; .$

For the new approximation :$A\_1(h)\; =\; 2A\_0!left(frac\{h\}\{2\}\; ight)\; -\; A\_0(h)$we can extrapolate again to obtain:$A\; =\; frac\{4A\_1!left(frac\{h\}\{2\}\; ight)\; -\; A\_1(h)\}\{3\}\; +\; O(h^3)\; .$

ee also

* Aitken's delta-squared process

References

*"Extrapolation Methods. Theory and Practice" by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.

External links

* [http://math.fullerton.edu/mathews/n2003/RichardsonExtrapMod.html Module for Richardson's Extrapolation] , fullerton.edu
* [http://ocw.mit.edu/NR/rdonlyres/Mathematics/18-304Spring-2006/D69D4111-2100-443D-A75D-5D5BE7B4FAA2/0/xtrpltn_liu_xpnd.pdf Fundamental Methods of Numerical Extrapolation With Applications] , mit.edu
* [http://www.math.ubc.ca/~feldman/m256/richard.pdf Richardson-Extrapolation]
* [http://www.math.ubc.ca/~israel/m215/rich/rich.html Richardson extrapolation on a website of Robert Israel (Unversity of British Columbia) ]