This quadrature method comes from the scmutils package that inspired this library.
The idea is similar to Romberg integration:
use some simpler quadrature method like the Midpoint or Trapezoid method to approximate an integral with a successively larger number of integration slices
Fit a curve to the pairs Loading..., where Loading... is the width of an integration slice and Loading... is the integral estimator
Use the curve to extrapolate forward to Loading....
Romberg integration does this by fitting a polynomial to a geometric series of slices - Loading..., for example - using Richardson extrapolation.
The Bulirsch-Stoer algorithm is exactly this, but:
Here are the default step sizes:
The more familiar algorithm named "Bulirsch-Stoer" applies the same ideas to the solution of ODes, as described on Wikipedia. scmutils adapted this into the methods you see here.
NOTE - The Wikipedia page states that "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 (Deuflhard 1983)."
We can do this too! Passing {:bs-extrapolator :polynomial}
enables polynomial extrapolation in the sequence and integration functions implemented below.
One more detail is important to understand. You could apply the ideas above to any function that approximates an integral, but this namespace focuses on accelerating the midpoint and trapezoid methods.
As discussed in midpoint.cljc
and trapezoid.cljc
, the error series for these methods has terms that fall off as even powers of the integration slice width:
This means that the rational function approximation needs to fit the function to points of the form
Loading...to take advantage of the acceleration. This trick is baked into Richardson extrapolation through the ability to specify a geometric series. richardson_test.cljc
shows that Richardson extrapolation is indeed equivalent to a polynomial fit using Loading...... the idea here is the same.
The following two functions generate a sequence of NON-squared Loading... slice widths. bs-sequence-fn
below squares each entry.
The next group of functions generates open-sequence
and closed-sequence
methods, analagous to all other quadrature methods in the library.
This function exists because we wanted to provide an open-sequence
and closed-sequence
option below. The logic for both is the same, other than the underlying approximation sequence generator.
Finally, two separate functions that use the sequence functions above to converge quadrature estimates.