Richardson Extrapolation

In numerical analysis, Richardson extrapolation is a method to improve an approximation that depends on a step size. 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 tk0 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(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
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.

Example

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

 

<< PreviousWord BrowserNext >>
prosper garnot
kenneth j. hsu
mycin
stu irwin
mall of arabia
tobas hernndez
two factor theory
margaret d. tutwiler
parmenio
fifa series
johnny paredes
ticto barb
redhouse
quilombo
cory hobbs
anquan boldin
yuan cheng fung
protected areas of the united states
dixie cup
scott simms
everett, ontario
christian century
claudio ranieri
gallery
paget's disease of bone
francis kenrick
poor management
the willows at chillico woods, guelph, ontario
south pointe, innisfil, ontario
paget's disease
sunflowers, barrie, ontario
central league (football)
creditvalley, mississauga, ontario
the call
the call (television)
lakelands village, brampton, ontario
al pedrique
gro par
bahia de todos os santos
vanguard progressive unionist party
loch lubnaig
katie leung
viceroyalty of brazil
contour line