Richardson extrapolation

From Encyclopedia of Mathematics
Jump to: navigation, search

A method for accelerating the convergence of solutions of difference problems (see Approximation of a differential boundary value problem by difference boundary value problems). The principal idea of the method consists in regarding the solution of a convergent difference problem for fixed as a function of the vanishing parameter of the difference grid, choosing the appropriate interpolation function based on several values of the solution for different , and calculating which is an approximate value of the sought solution — the limit of the sequence as . Usually, the function is sought in the form of an interpolation polynomial in .

The method is called after L. Richardson [1] who was the first to apply it to improve the precision of the solution of difference problems and called it a deferred approach to the limit.

The theoretical basis of the applicability of this method is the existence of an expansion

where , the functions are independent of , and are the values of a grid function which is bounded when . There are several theoretical methods for finding out whether such expansions exist or not [4].

Usually, linear extrapolation is used: By values of at the same point for different parameters one calculates the extrapolated value by the formula

where the weights are defined by the following system of equations:

If among the there are no values which are too close to each other, then

where , i.e. the order of convergence of to as is , which is greater than — the order of convergence of to . In two special cases there exist algorithms for calculating without having to determine the coefficients :

a) in the case when , , , the method reduces to the interpolation of a polynomial in , and from the Lagrange interpolation formula it follows that



b) in the case when , , , formula (*) is replaced by

This algorithm, called Romberg's rule (W. Romberg, 1955), is widely applied in the construction of quadrature formulas (see [5]). In order that for different the grids (see Approximation of a differential operator by difference operators) have as many nodes as possible to carry out the Richardson extrapolation, the parameters are chosen as part of one of the following sequences: , ; , ; .

Linear extrapolation is not the only possible way. For instance, in case , , as the interpolation function one can take rational functions of the form , where , are polynomials in of degrees and , respectively. Then the result of the rational extrapolation can be calculated by the following recurrent procedure:

Richardson extrapolation is conveniently realized on a computer, since in order to achieve high accuracy it uses the repeated solution of simple difference problems (sometimes with little modifications) of low order of approximation for which standard methods of solution and computer programs are usually well developed.


[1] L.F. Richardson, "The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stress in a masonry dam" Philos. Trans. Roy. Soc. Ser. A , 210 (1910) pp. 307–357
[2] R. Bulirsh, J. Stoer, "Fehlerabschätzungen und Extrapolation mit rationaler Funktionen bei Verfahren vom Richardson-Typus" Numer. Math. , 6 : 5 (1964) pp. 413–427
[3] D.C. Joyce, "Survey of extrapolation processes in numerical analysis" SIAM Review , 13 : 4 (1971) pp. 435–490
[4] G.I. Marchuk, V.V. Shaidurov, "Difference methods and their extrapolations" , Springer (1983) (Translated from Russian)
[5] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)



[a1] T. Hivie, "Generalized Neville type extrapolation schemes" BIT , 9 (1979) pp. 204–213
How to Cite This Entry:
Richardson extrapolation. V.V. Shardurov (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098