Bulirsch–Stoer algorithm: Difference between revisions

Revision as of 05:11, 16 January 2009

Revision as of 17:20, 16 January 2009

Line 1:

In [[numerical analysis]], the '''Bulirsch–Stoer algorithm''' 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]], to obtain numerical solutions to [[ordinary differential equation|ordinary differential equations]] (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–Stoer Algorithm(GBS) algorithm''' because of the importance of a result about the error function of the modified midpoint method, due to [[William B. Gragg]].

{{orphan|date=November 2008}}

In [[numerical analysis]], the '''Bulirsch–Stoer algorithm''' is a method of [[numerical integration]] which combines three powerful ideas, [[Richardson extrapolation]], the use of [[rational function extrapolation]] in Richardson-type applications, and the [[modified midpoint method]], to obtain numerical solutions to [[ordinary differential equation|ordinary differential equations]] (ODEs) with high accuracy and comparatively little computational effort. It ist named after [[Roland Bulirsch]] and [[Josef Stoer]]. It is sometimes called '''Gragg–Bulirsch–Stoer Algorithm''' because of the importance of a result about the error function of the modified midpoint method, due to [[William B. Gragg]].

==Underlying ideas==

Line 10 ⟶ 8:

The modified midpoint method by itself is a second-order method, and therefore generally inferior to fourth-order methods like the [[Runge–Kutta methods|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.

{{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==

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

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

* {{Citation | last1=Press | first1=William H. | last2=Flannery | first2=Brian P. | last3=Teukolsky | first3=Saul A. | author3-link=Saul Teukolsky | last4=Vetterling | first4=William T. | title=[[Numerical Recipes|Numerical Recipes in C]] | publisher=[[Cambridge University Press]] | edition=2nd | isbn=978-0-521-43108-8 | year=1988 }}. (See chapter 15.)

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

==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.

[[Category:Numerical integration (quadrature)]]