Richardson Extrapolation - General Formula

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

where the a_i are unknown constants and the k_i are known constants such that hk_i > hk_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 tk₀ 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(hk₀). 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

with .

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

yields an approximate relationship

which can be solved numerically to estimate k₀.