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 (17131784)
“Every formula which expresses a law of nature is a hymn of praise to God.”
—Maria Mitchell (18181889)