Bulirsch–Stoer algorithm: Difference between revisions

Revision as of 01:54, 3 March 2011

Revision as of 19:19, 11 August 2011

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]], to obtain numerical solutions to [[ordinary differential equation|ordinary differential equations]] (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.