Ékstrapolasi Richardson

Dina analisis numeris, **ékstrapolasi Richardson** nyaéta métode akselerasi runtuyan, nu digunakeun pikeun ngabebenah rarata konvergénsi tina runtuyan. Dingaranan sanggeus kapanggih ku Lewis Fry Richardson, nu manggihan téhnik ieu dina mangsa awal abad ka-20.

## Définisi basajan 
Suppose that *A*(*h*) is an estimation of order *hn* 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  *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 éasier 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 incréasing number of calculations needed (see examples below).

## Rumus umum 
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 *ai* are unknown constants and the *ki* are known constants such that *hki* > *hki+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 *tk*0 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''0).  This process can be repéated 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} 
such that 
: A = A_{i+1}(h) + O(h^{k_{i+1}}) .

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 linéar sequence transformation.

## Conto 
Using Taylor's theorem,
:f(x+h) = f(x) + f'(x)h + \frac{f*(x)}{2}h^2 + \cdots
so 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_0(h) = \frac{f(x+h) - f(x)}{h}
then *ki* = *i*+1.

For *t* = 2, the first formula extrapolated for *A* would be
:A = 2A_0\left(\frac{h}{2}\right) - A_0(h) + O(h^2) .

For the new approximation 
:A_1(h) = 2A_0\left(\frac{h}{2}\right) - A_0(h) 
we can extrapolate again to obtain
: A = \frac{4A_1\left(\frac{h}{2}\right) - A_1(h)}{3} + O(h^3) .

## Rujukan 
**Extrapolation Methods. Theory and Practice'' ku C. Brezinski jeung M. Redivo Zaglia, North-Holland, 1991.

## Tempo ogé 
* Aitken's delta-squared process
* Nyungsi 'Richardson extrapolation' di google