Adaptive quadrature

Remarks

Clause 1 holds by induction on the recursion: a split replaces one interval with tolerance $\tau_J$ by its two halves with tolerances adding up to $\tau_J$. Clause 2 then follows from the triangle inequality, since $\abs{\int_a^b f - S} \le \sum_i \abs{I(J_i) - A(J_i)} \le \sum_i \tau_i$. The usual example is adaptive Simpson's rule: with $S(J)$ the Simpson value on $J$, one takes $A(J) = S(J_1) + S(J_2)$ and $E(J) = \abs{S(J_1) + S(J_2) - S(J)}/15$. This estimate is justified for $f \in C^4$ and small $J$: the Simpson error on an interval of length $\ell$ is $-\frac{\ell^5}{2880} f^{(4)}(\xi)$, so halving the interval divides the error by about $16$. The hypothesis of clause 2 is essential, and the estimate $E$ can be fooled. For $f(x) = \big(x (x - \tfrac14)(x - \tfrac12)(x - \tfrac34)(x - 1)\big)^2$ on $[0, 1]$, all the Simpson sample points of the first test are zeros of $f$, so $E([0,1]) = 0$ and the procedure returns $0$, while $\int_0^1 f > 0$. Real programs also bound the depth of the recursion, since termination is not guaranteed for every $f$.

Going deeper

For a student

Compared with a fixed composite rule, adaptivity can save many function evaluations when $f$ has a peak, a kink or an endpoint singularity. The error estimate comes from comparing two rules on the same interval, such as Simpson's rule on one and on two panels, or a Gauss rule with its Gauss–Kronrod extension. The guarantee is only as good as the estimate: it is a heuristic, not a proof, for a function known only through samples. Global variants keep a list of all intervals and always split the one with the largest estimated error.