Bulirsch–Stoer algorithm: Difference between revisions

Revision as of 17:20, 16 January 2009

Latest revision as of 21:00, 14 April 2025

(14 intermediate revisions by 13 users not shown)

Line 1:

In [[numerical analysis]], the '''Bulirsch–Stoer algorithm''' is a method for the [[numerical ordinary 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 is named after [[Roland Bulirsch]] and [[Josef Stoer]]. 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]].

==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 <math>''h</math>'', fitting a (chosen) analytic function to the resulting points, and then evaluating the fitting function for ''h'' &nbsp;= &nbsp;0, thus trying to approximate the result of the calculation with infinitely fine steps.

Bulirsch and Stoer recognized that using [[rational function]]s as fitting functions for Richardson extrapolation in numerical integration is superior to using [[polynomial function]]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.

Line 12:

==References==

{{Reflist}}

* {{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}}.

* {{CitationCite book | last1=Press | first1=William H.WH | last2=FlanneryTeukolsky | first2=Brian P.SA | last3=TeukolskyVetterling | first3=Saul A.WT | author3-linklast4=Saul TeukolskyFlannery | last4first4=VetterlingBP | first4year=William T.2007 | title=[[Numerical Recipes|Numerical: RecipesThe inArt C]]of Scientific Computing | edition=3rd | publisher=[[Cambridge University Press]] | edition___location=2ndNew York | isbn=978-0-521-4310888068-8 | yearchapter=1988Section }}17.3. (SeeRichardson Extrapolation and the Bulirsch-Stoer Method | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=921 15| 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.

[[Category:{{Numerical integration (quadrature)]]integrators}}

{{DEFAULTSORT:Bulirsch-Stoer algorithm}}

[[Category:Numerical integration]]