Richardson extrapolation

In numerical analysis, Richardson extrapolation is a sequence acceleration method used to improve the rate of convergence of a sequence of estimates of some value . In essence, given the value of for several values of , we can estimate by extrapolating the estimates to . It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century, though the idea was already known to Christiaan Huygens in his calculation of π. 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 trapezoid rule, and the Bulirsch–Stoer algorithm for solving ordinary differential equations. Let be an approximation of (exact value) that depends on a positive step size h with an error formula of the form where the are unknown constants and the are known constants such that . Furthermore, represents the truncation error of the approximation such that Similarly, in the approximation is said to be an approximation. Note that by simplifying with Big O notation, the following formulae are equivalent: Richardson extrapolation is a process that finds a better approximation of by changing the error formula from to Therefore, by replacing with the truncation error has reduced from to for the same step size . The general pattern occurs in which is a more accurate estimate than when . By this process, we have achieved a better approximation of by subtracting the largest term in the error which was . This process can be repeated to remove more error terms to get even better approximations. Using the step sizes and for some constant , the two formulas for are: To improve our approximation from to by removing the first error term, we multiply the second equation (2) by and subtract the first equation (1) to give usThis multiplication and subtraction was performed because is an approximation of .