Richardson extrapolation

src: i.ytimg.com

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

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.

Video Richardson extrapolation

Example of Richardson extrapolation

Suppose that we wish to approximate ${\displaystyle A^{*}}$, and we have a method ${\displaystyle A(h)}$ that depends on a small parameter ${\displaystyle h}$, so that

${\displaystyle A(h)=A^{\ast }+Ch^{n}+O(h^{n+1})\;}$

Define a new method

${\displaystyle R(h,k):={\frac {k^{n}A(h)-A(k\,h)}{k^{n}-1}}}$

Then

${\displaystyle R(h,k)={\frac {k^{n}(A^{*}+Ch^{n}+O(h^{n+1}))-(A^{*}+Ck^{n}h^{n}+O(h^{n+1}))}{k^{n}-1}}=A^{*}+O(h^{n+1}).}$

${\displaystyle R(h,k)}$ is called the Richardson extrapolation of A(h), and has a higher-order error estimate ${\displaystyle O(h^{n+1})}$ compared to ${\displaystyle A(h)}$.

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

Maps Richardson extrapolation

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

${\displaystyle A-A(h)=a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{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

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots }$

which can be simplified with Big O notation to be

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}}).\,\!}$

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

${\displaystyle A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\,\!}$

${\displaystyle 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^k₀ and subtracting the first equation gives

${\displaystyle (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

${\displaystyle 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 beginning with ${\displaystyle A_{0}=A(h)}$ can be defined for the approximations by

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

where ${\displaystyle k_{i+1}}$ satisfies

${\displaystyle A=A_{i+1}(h)+O(h^{k_{i+1}})}$.

The Richardson extrapolation can be considered as a linear sequence transformation.

Additionally, the general formula can be used to estimate k₀ 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

${\displaystyle A={\frac {t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}+O(h^{k_{1}})={\frac {s^{k_{0}}A\left({\frac {h}{s}}\right)-A(h)}{s^{k_{0}}-1}}+O(h^{k_{1}})}$

yields an approximate relationship

${\displaystyle A\left({\frac {h}{t}}\right)+{\frac {A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}\approx A\left({\frac {h}{s}}\right)+{\frac {A\left({\frac {h}{s}}\right)-A(h)}{s^{k_{0}}-1}}}$

which can be solved numerically to estimate k₀.

src: nanohub.org

Example

Using Taylor's theorem about x=0,

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

the derivative of f(x) is given by

${\displaystyle 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

${\displaystyle 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

${\displaystyle A=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)+O(h^{2}).}$

For the new approximation

${\displaystyle A_{1}(h)=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)}$

we can extrapolate again to obtain

${\displaystyle A={\frac {4A_{1}\!\left({\frac {h}{2}}\right)-A_{1}(h)}{3}}+O(h^{3}).}$

src: i.ytimg.com

Example pseudocode code for Richardson extrapolation

The following pseudocode in MATLAB style demonstrates Richardson extrapolation to help solve the ODE ${\displaystyle y'(t)=-y^{2}}$, ${\displaystyle y(0)=1}$ with the Trapezoidal method. In this example we halve the step size ${\displaystyle h}$ each iteration and so in the discussion above we'd have that ${\displaystyle t=2}$. The error of the Trapezoidal method can be expressed in terms of odd powers so that the error over multiple steps can be expressed in even powers; this leads us to raise ${\displaystyle t}$ to the second power and to take powers of ${\displaystyle 4=2^{2}=t^{2}}$ in the pseudocode. We want to find the value of ${\displaystyle y(5)}$, which has the exact solution of ${\displaystyle {\frac {1}{5+1}}={\frac {1}{6}}=0.1666...}$ since the exact solution of the ODE is ${\displaystyle y(t)={\frac {1}{1+t}}}$. This pseudocode assumes that a function called 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.

src: nanohub.org

See also

• Aitken's delta-squared process
• Takebe Kenko
• Richardson iteration

src: i.ytimg.com

References

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

src: nanohub.org

External links

• Fundamental Methods of Numerical Extrapolation With Applications, mit.edu
• Richardson-Extrapolation
• Richardson extrapolation on a website of Robert Israel (University of British Columbia)

Source of the article : Wikipedia