In numerical analysis, the Bulirsch–Stoer algorithm is a method for the numerical solution of ordinary differential equations which combines three powerful ideas: Richardson extrapolation, the use of rational function extrapolation in Richardson-type applications, and the modified midpoint method,[1] to obtain numerical solutions to ordinary differential equations (ODEs) with high accuracy and comparatively little computational effort.
It is sometimes called the Gragg–Bulirsch–Stoer (GBS) algorithm because of the importance of a result about the error function of the modified midpoint method, due to William B. Gragg.
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.
While a polynomial interpolation or extrapolation only yields good results if the nearest pole is rather far outside a circle around the known data points in the complex plane, rational function interpolation or extrapolation can have remarkable accuracy even in the presence of nearby poles.
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).