Bulirsch–Stoer algorithm
In
Underlying ideas
The idea of Richardson extrapolation is to consider a numerical calculation whose accuracy depends on the used stepsize h as an (unknown) analytic function of the stepsize h, performing the numerical calculation with various values of h, fitting a (chosen) analytic function to the resulting points, and then evaluating the fitting function for h = 0, thus trying to approximate the result of the calculation with infinitely fine steps.
Bulirsch and Stoer recognized that using
The modified midpoint method by itself is a second-order method, and therefore generally inferior to fourth-order methods like the fourth-order Runge–Kutta method. However, it has the advantage of requiring only one derivative evaluation per substep (asymptotically for a large number of substeps), and, in addition, as discovered by Gragg, the error of a modified midpoint step of size H, consisting of n substeps of size h = H/n each, and expressed as a power series in h, contains only even powers of h. This makes the modified midpoint method extremely useful to the Bulirsch–Stoer method as the accuracy increases two orders at a time when the results of separate attempts to cross the interval H with increasing numbers of substeps are combined.
Hairer, Nørsett & Wanner (1993, p. 228), in their discussion of the method, say that rational extrapolation in this case is nearly never an improvement over polynomial interpolation (Deuflhard 1983). Furthermore, the modified midpoint method is a modification of the regular midpoint method to make it more stable, but because of the extrapolation this does not really matter (Shampine & Baca 1983).
References
- Deuflhard, Peter (1983), "Order and stepsize control in extrapolation methods", Numerische Mathematik, 41 (3): 399–422, S2CID 121911947.
- Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems, Berlin, New York: ISBN 978-3-540-56670-0.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 17.3. Richardson Extrapolation and the Bulirsch-Stoer Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Archived from the originalon 2011-08-11. Retrieved 2011-08-17.
- Shampine, Lawrence F.; Baca, Lorraine S. (1983), "Smoothing the extrapolated midpoint rule", Numerische Mathematik, 41 (2): 165–175, S2CID 121097742.
External links
- ODEX.F, implementation of the Bulirsch–Stoer algorithm by Ernst Hairer and Gerhard Wanner (for other routines and license conditions, see their Fortran and Matlab Codes page).
- BOOST library, implementation in C++.
- Apache Commons Math, implementation in Java.