Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Richardson extrapolation
Summary
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 .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.