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.[1][2] In the words of Birkhoff and Rota, "... its usefulness for practical computations can hardly be overestimated."[3]
Contents |
Simple definition
Suppose that A(h) is an estimation of order hn for <math>A=\lim_{h\to 0}A(h)</math>, i.e. <math>A-A(h) = a_n h^n+O(h^m),~a_n\ne0,~m>n</math>. Then
- <math>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} </math>
is called the Richardson extrapolate of A(h); it is an estimate of order hm 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).
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
- <math> A - A(h) = a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots </math>
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
- <math> A = A(h) + a_0h^{k_0} + a_1h^{k_1} + a_2h^{k_2} + \cdots </math>
which can be simplified with Big O notation to be
- <math> A = A(h)+ a_0h^{k_0} + O(h^{k_1}). \,\!</math>
Using the step sizes h and h / t for some t, the two formulas for A are:
- <math> A = A(h)+ a_0h^{k_0} + O(h^{k_1}) \,\!</math>
- <math> A = A\left(\frac{h}{t}\right) + a_0\left(\frac{h}{t}\right)^{k_0} + O(h^{k_1}) .</math>
Multiplying the second equation by tk0 and subtracting the first equation gives
- <math> (t^{k_0}-1)A = t^{k_0}A\left(\frac{h}{t}\right) - A(h) + O(h^{k_1}) </math>
which can be solved for A to give
- <math>A = \frac{t^{k_0}A\left(\frac{h}{t}\right) - A(h)}{t^{k_0}-1} + O(h^{k_1}) .</math>
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 can be defined for the approximations by
- <math> A_{i+1}(h) = \frac{t^{k_i}A_i\left(\frac{h}{t}\right) - A_i(h)}{t^{k_i}-1} </math>
such that
- <math> A = A_{i+1}(h) + O(h^{k_{i+1}}) .</math>
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,
- <math>f(x+h) = f(x) + f'(x)h + \frac{f(x)}{2}h^2 + \cdots</math>
so the derivative of f(x) is given by
- <math>f'(x) = \frac{f(x+h) - f(x)}{h} - \frac{f(x)}{2}h + \cdots.</math>
If the initial approximations of the derivative are chosen to be
- <math>A_0(h) = \frac{f(x+h) - f(x)}{h}</math>
then ki = i+1. For t = 2, the first formula extrapolated for A would be
- <math>A = 2A_0\left(\frac{h}{2}\right) - A_0(h) + O(h^2) .</math>
For the new approximation
- <math>A_1(h) = 2A_0\left(\frac{h}{2}\right) - A_0(h) </math>
we can extrapolate again to obtain
- <math> A = \frac{4A_1\left(\frac{h}{2}\right) - A_1(h)}{3} + O(h^3) .</math>
References
- ^ 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.
- ^ Richardson, L. F. (1927). "The deferred approach to the limit". Philosophical Transactions of the Royal Society of London, Series A 226: 299–349.
- ^ 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.
