Bulirsch–Stoer algorithm: Difference between revisions

Revision as of 16:38, 15 November 2008

Latest revision as of 21:00, 14 April 2025

(21 intermediate revisions by 17 users not shown)

Line 1:

In [[numerical analysis]], the '''Bulirsch-StoerBulirsch–Stoer Algorithmalgorithm''' is a method offor the [[numerical integrationordinary differential equations|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]],<ref>{{Cite web|url=http://www.xmds.org/bulirschStoer.html|title = Modified Midpoint Method — XMDS2 3.1.0 documentation}}</ref> to obtain numerical solutions to [[ordinary differential equation|ordinary differential equations]]s (ODEs) with high accuracy and comparatively little computational effort. It istis named after [[Roland Bulirsch]] and [[Josef Stoer]]. It is sometimes called the '''Gragg-Bulirsch-StoerGragg–Bulirsch–Stoer (GBS) Algorithmalgorithm''' because of the importance of a result about the error function of the modified midpoint method, due to [[William B. Gragg]].

==Underlying ideas==

The idea of Richardson extrapolation is to consider a numerical calculation whose accuracy depends on the used stepsize <math>''h</math>'' as an (unknown) [[analytic function]] of the stepsize <math>''h</math>'', performing the numerical calculation with various values of <math>''h</math>'', fitting a (chosen) analytic function to the resulting points, and then evaluating the fitting function for <math>''h ''&nbsp;= &nbsp;0</math>, thus trying to approximate the result of the calculation with infinitely fine steps.

Bulirsch and Stoer recognized that using [[rational function|rational functions]]s as fitting functions for Richardson extrapolation in numerical integration is superior to using [[polynomial function|polynomial functions]]s because rational functions are able to approximate functions with poles rather well (compared to polynomial functions), given that there are enough higher-power terms in the denominator to account for nearby poles. 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.

The modified midpoint method by itself is a second-order method, and therefore generally inferior to fourth-order methods like the [[Runge-KuttaRunge–Kutta methods|fourth-order Runge-KuttaRunge–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 <math>''H</math>'', consisting of <math>''n</math>'' substeps of size <math>''h'' = ''H''/''n</math>'' each, and expressed as a power series in <math>''h</math>'', contains only even powers of <math>''h</math>''. This makes the modified midpoint method extremely useful to the Bulirsch-StoerBulirsch–Stoer method as the accuracy increases two orders at a time when the results of separate attempts to cross the interval <math>''H</math>'' with increasing numbers of substeps are combined.

{{harvtxt|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 {{harv|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 {{harv|Shampine|Baca|1983}}.

==References==

{{Reflist}}

<references/>

* William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. ''[[Numerical Recipes|Numerical Recipes in C]]''. Cambridge University Press, 1988. (See chapter 15.)

* {{Citation | last1=Deuflhard | first1=Peter | title=Order and stepsize control in extrapolation methods | doi=10.1007/BF01418332 | year=1983 | journal=Numerische Mathematik | issn=0029-599X | volume=41 | issue=3 | pages=399–422| s2cid=121911947 }}.

* {{Citation | last1=Hairer | first1=Ernst | last2=Nørsett | first2=Syvert Paul | last3=Wanner | first3=Gerhard | title=Solving ordinary differential equations I: Nonstiff problems | publisher=[[Springer-Verlag]] | ___location=Berlin, New York | isbn=978-3-540-56670-0 | year=1993}}.

*{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | ___location=New York | isbn=978-0-521-88068-8 | chapter=Section 17.3. Richardson Extrapolation and the Bulirsch-Stoer Method | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=921 | access-date=2011-08-17 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=921 | url-status=dead }}

* {{Citation | last1=Shampine | first1=Lawrence F. | last2=Baca | first2=Lorraine S. | title=Smoothing the extrapolated midpoint rule | doi=10.1007/BF01390211 | year=1983 | journal=Numerische Mathematik | issn=0029-599X | volume=41 | issue=2 | pages=165–175| s2cid=121097742 }}.

==External links==

* [http://www.unige.ch/~hairer/prog/nonstiff/odex.f ODEX.F], implementation of the Bulirsch–Stoer algorithm by Ernst Hairer and Gerhard Wanner (for other routines and license conditions, see their [http://www.unige.ch/~hairer/software.html Fortran and Matlab Codes] page).

* [https://www.boost.org/doc/libs/1_55_0/boost/numeric/odeint/stepper/bulirsch_stoer.hpp BOOST library], implementation in C++.

* [https://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/org/apache/commons/math3/ode/nonstiff/GraggBulirschStoerIntegrator.html Apache Commons Math], implementation in Java.

{{Numerical integrators}}

{{DEFAULTSORT:Bulirsch-Stoer algorithm}}

[[Category:Numerical integration]]