Bulirsch–Stoer algorithm: Difference between revisions

Revision as of 05:10, 16 January 2009

Revision as of 05:11, 16 January 2009

Line 5:

==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'' = 0</math>, 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.