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

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

which can be simplified with Big O notation to be

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

Multiplying the second equation by t^k0 and subtracting the first equation gives

which can be solved for A to give

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

such that

A well-known practical use of Richardson extrapolation is Romberg integration, which applies Richardson extrapolation to the trapezium rule.

Example

Using Taylor's theorem,

so the derivative of f(x) is given by

If the initial approximations of the derivative are chosen to be

then k_i = i+1.

For t = 2, the first formula extrapolated for A would be

For the new approximation

we can extrapolate again to obtain