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 ai are unknown constants and the ki are known constants such that hki > hki+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 tk0 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(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

such that

with .

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

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

Read more about this topic:  Richardson Extrapolation

Famous quotes containing the words general and/or formula:

    The general interest of the masses might take the place of the insight of genius if it were allowed freedom of action.
    Denis Diderot (1713–1784)

    Every formula which expresses a law of nature is a hymn of praise to God.
    Maria Mitchell (1818–1889)