Richardson extrapolation

Richardson extrapolation is a method in numerical analysis for estimating the limit of a quantity that depends on a step size h as h approaches zero, when the truncation error is known to have a power-series expansion at h equal to zero. It is most often applied as a sequence acceleration method, improving the rate of convergence of iterative methods. The technique is named after Lewis Fry Richardson, who introduced it in the early twentieth century, although a form of the idea was already known to Christiaan Huygens in the seventeenth century, who used it in his calculation of pi. Practical applications include Romberg integration, which applies Richardson extrapolation to the trapezoid rule, and the Bulirsch-Stoer algorithm for solving ordinary differential equations. In the words of Birkhoff and Rota, its usefulness for practical computations can hardly be overestimated.