How does an adaptive integrator know the error if it does not know the answer?

It estimates the local error by comparing two approximations of differing accuracy on the same subinterval — for example a higher-order and a lower-order rule. Their difference approximates the error and guides where to refine, even though the true integral is unknown.

When does adaptive quadrature struggle?

It can be misled by integrands that are smooth at the sample points but have hidden features between them, by strongly oscillatory integrands, or by non-integrable singularities. Specialized rules, transformations, or oscillatory-integration methods are then needed.

Adaptive Quadrature

Adaptive quadrature automatically subdivides the integration interval where the integrand is difficult, using local error estimates to meet a requested accuracy with as few function evaluations as possible.

Definition

Adaptive quadrature is any numerical integration strategy that uses estimates of the local approximation error to decide where and how finely to subdivide the integration domain so that a prescribed overall error tolerance is achieved efficiently.

Scope

This topic covers local error estimation by comparing rules of different orders or refinement levels, recursive interval bisection (adaptive Simpson and adaptive Gauss-Kronrod), global error budgets and stopping criteria, the handling of singularities and sharp features, and the design of production automatic integrators such as those in the QUADPACK library.

Core questions

How is the local error of a quadrature estimate computed without knowing the exact integral?
How does recursive subdivision concentrate effort where the integrand varies most?
What stopping criteria reliably achieve the requested tolerance while avoiding wasted work?
How are integrable singularities and discontinuities detected and handled robustly?

Key theories

Local error estimation and subdivision: Comparing a coarse and a finer (or higher-order) estimate on a subinterval yields an estimate of the local error; if it exceeds the share of the tolerance allotted to that subinterval, the subinterval is split and the procedure recurses, otherwise its contribution is accepted.
Globally adaptive strategies: Rather than treating subintervals independently, globally adaptive integrators keep a queue of subintervals ordered by estimated error and always refine the worst one, which handles localized singularities efficiently and underlies the QUADPACK routines.

Mechanisms

On each subinterval the integrator evaluates an embedded rule pair — for example a Gauss-Kronrod pair or two Simpson estimates at different refinements — whose difference estimates the local error. A locally adaptive method recurses by bisecting any subinterval whose estimated error is too large. A globally adaptive method maintains a priority queue of subintervals keyed by estimated error and repeatedly subdivides the current worst offender until the summed error estimate meets the tolerance. Extrapolation and specialized weight handling are added to cope with endpoint singularities and oscillatory integrands.

Clinical relevance

Adaptive quadrature is what general-purpose integration routines in scientific software rely on to deliver a result to a user-specified accuracy without the user having to analyze the integrand; it is essential for integrands with peaks, boundary-layer behaviour, or integrable singularities that would defeat a fixed rule, and it underlies the automatic integrators in widely used numerical and statistical packages.

History

Automatic, error-controlled integration matured in the 1970s and early 1980s, culminating in the QUADPACK package (1983), whose adaptive Gauss-Kronrod routines with extrapolation became the de facto standard and were later adopted, ported, or re-implemented in many numerical and statistical software systems.

Key figures

Robert Piessens
Philip J. Davis
Philip Rabinowitz

Seminal works

davis1984
piessens1983

Frequently asked questions

How does an adaptive integrator know the error if it does not know the answer?: It estimates the local error by comparing two approximations of differing accuracy on the same subinterval — for example a higher-order and a lower-order rule. Their difference approximates the error and guides where to refine, even though the true integral is unknown.
When does adaptive quadrature struggle?: It can be misled by integrands that are smooth at the sample points but have hidden features between them, by strongly oscillatory integrands, or by non-integrable singularities. Specialized rules, transformations, or oscillatory-integration methods are then needed.