Adaptive Quadrature

Numerical integration that automatically refines where the integrand varies rapidly and coarsens where it is smooth.

One rule does not fit all integrands

A fixed quadrature rule wastes effort on smooth regions of an integrand and under-resolves regions with peaks, kinks, or rapid oscillation. Adaptive quadrature estimates the local error and subdivides only where needed, concentrating function evaluations where the integrand is difficult and using few elsewhere. This delivers a requested accuracy with far fewer evaluations than a uniform rule of the same tolerance.

The recursion

The basic strategy applies a quadrature rule to an interval, then applies the same rule to each half. If the sum of the two halves agrees with the whole to within the local tolerance, the result is accepted; otherwise each half is subdivided recursively with a proportionally tightened tolerance. The difference between the coarse and refined estimates serves as the error estimate, a form of Richardson extrapolation.

def adaptive_simpson(f, a, b, tol):
    def simpson(a, b):
        c = (a + b) / 2
        return (b - a) / 6 * (f(a) + 4*f(c) + f(b))
    def recurse(a, b, whole, tol):
        c = (a + b) / 2
        left, right = simpson(a, c), simpson(c, b)
        if abs(left + right - whole) <= 15 * tol:
            return left + right + (left + right - whole) / 15
        return recurse(a, c, left, tol/2) + recurse(c, b, right, tol/2)
    return recurse(a, b, simpson(a, b), tol)

Gauss-Kronrod pairs

High-quality adaptive integrators (as in QUADPACK) use Gauss-Kronrod rules: a Gauss rule and a higher-order Kronrod extension that reuses the same points, so the error estimate comes almost for free. The interval with the largest estimated error is subdivided first, a globally adaptive strategy that is more efficient than blind recursion.

Handling hard integrands

Adaptive quadrature copes with integrable singularities, sharp peaks, and localized features, but oscillatory or highly singular integrands may need specialized transformations or rules. Knowing the integrand's structure, and setting both absolute and relative tolerances sensibly, is key to reliable results. Adaptive integration underlies the evaluation of the many one-dimensional integrals in cross-section averaging and reaction-rate calculations.