Richardson extrapolation
Encyclopedia
In numerical analysis
, Richardson extrapolation is a sequence acceleration
method, used to improve the rate of convergence
of a sequence
. It is named after Lewis Fry Richardson
, who introduced the technique in the early 20th century. In the words of Birkhoff
and Rota
, "... its usefulness for practical computations can hardly be overestimated."
Practical applications of Richardson extrapolation include Romberg integration, which applies Richardson extrapolation to the trapezium rule, and the Bulirsch–Stoer algorithm
for solving ordinary differential equations.
is an estimation of order 
for
, i.e. 
. Then
is called the Richardson extrapolate
of A(h);
it is an estimate of order hm for A, with m>n.
More generally, the factor 2 can be replaced by any other factor, as shown below.
Very often, it is much easier to obtain a given precision by using R(h) rather
than A(h') with a much smaller h' , which can cause problems due to limited precision (rounding errors) and/or due to the increasing number of calculations needed (see examples below).
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.
,
the derivative of f(x) is given by
If the initial approximations of the derivative are chosen to be
then ki = i+1.
For t = 2, the first formula extrapolated for A would be
For the new approximation
we can extrapolate again to obtain
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, Richardson extrapolation is a sequence acceleration
Series acceleration
In mathematics, series acceleration is one of a collection of sequence transformations for improving the rate of convergence of a series. Techniques for series acceleration are often applied in numerical analysis, where they are used to improve the speed of numerical integration...
method, used to improve the rate of convergence
Rate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
of a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
. It is named after Lewis Fry Richardson
Lewis Fry Richardson
Lewis Fry Richardson, FRS was an English mathematician, physicist, meteorologist, psychologist and pacifist who pioneered modern mathematical techniques of weather forecasting, and the application of similar techniques to studying the causes of wars and how to prevent them...
, who introduced the technique in the early 20th century. In the words of Birkhoff
Garrett Birkhoff
Garrett Birkhoff was an American mathematician. He is best known for his work in lattice theory.The mathematician George Birkhoff was his father....
and Rota
Gian-Carlo Rota
Gian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...
, "... its usefulness for practical computations can hardly be overestimated."
Practical applications of Richardson extrapolation include Romberg integration, which applies Richardson extrapolation to the trapezium rule, and the Bulirsch–Stoer algorithm
Bulirsch–Stoer algorithm
In numerical analysis, the Bulirsch–Stoer algorithm is a method for the numerical solution of ordinary differential equations which combines three powerful ideas: Richardson extrapolation, the use of rational function extrapolation in Richardson-type applications, and the modified midpoint method,...
for solving ordinary differential equations.
Example of Richardson extrapolation
Suppose that is an estimation of order for, i.e. . Thenis called the Richardson extrapolate
Extrapolation
In mathematics, extrapolation is the process of constructing new data points. It is similar to the process of interpolation, which constructs new points between known points, but the results of extrapolations are often less meaningful, and are subject to greater uncertainty. It may also mean...
of A(h);
it is an estimate of order hm for A, with m>n.
More generally, the factor 2 can be replaced by any other factor, as shown below.
Very often, it is much easier to obtain a given precision by using R(h) rather
than A(h') with a much smaller h' , which can cause problems due to limited precision (rounding errors) and/or due to the increasing number of calculations needed (see examples below).
General formula
Let A(h) be an approximation of A that depends on a positive step size h with an errorApproximation error
The approximation error in some data is the discrepancy between an exact value and some approximation to it. An approximation error can occur because#the measurement of the data is not precise due to the instruments...
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
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
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
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....
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
Rate of convergence
In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...
. 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.
Example
Using Taylor's theoremTaylor's theorem
In calculus, Taylor's theorem gives an approximation of a k times differentiable function around a given point by a k-th order Taylor-polynomial. For analytic functions the Taylor polynomials at a given point are finite order truncations of its Taylor's series, which completely determines the...
,
the derivative of f(x) is given by
If the initial approximations of the derivative are chosen to be
then ki = i+1.
For t = 2, the first formula extrapolated for A would be
For the new approximation
we can extrapolate again to obtain