---
tag: 948A39DZDE
kind: statement
role: proposition
name: Adaptive quadrature
msc: [65D30, 65D32]
uses: [7HYF6YG0RS, ADSVMCY77A, MNXC26G3BQ]
about: [7HYF6YG0RS]
sources:
  - url: https://en.wikipedia.org/wiki/Adaptive_quadrature
same_as:
  wikidata: Q4680758
  wikipedia: Adaptive quadrature
---

## Statement

Let $f \colon [a, b] \to \R$ be integrable and let $\tau > 0$ be a tolerance.
For each closed subinterval $J$ of $[a, b]$, let $A(J)$ be a computable approximation of $I(J) = \int_J f(x) \, dx$, and let $E(J) \ge 0$ be a computable error estimate.
The *adaptive quadrature* procedure $\mathrm{ADAPT}(J, \tau_J)$ returns $A(J)$ if $E(J) \le \tau_J$; otherwise it splits $J$ at its midpoint into $J_1$ and $J_2$ and returns $\mathrm{ADAPT}(J_1, \tau_J / 2) + \mathrm{ADAPT}(J_2, \tau_J / 2)$.
Suppose that $\mathrm{ADAPT}([a, b], \tau)$ terminates, and let $J_1, \ldots, J_m$ be the intervals at which it accepted $A(J_i)$ with tolerance $\tau_i$.
Then:

1. the intervals $J_1, \ldots, J_m$ cover $[a, b]$ and overlap only at endpoints, and $\tau_1 + \cdots + \tau_m = \tau$;
2. if $\abs{I(J_i) - A(J_i)} \le E(J_i)$ for each $i$, then the result $S = \sum_{i=1}^m A(J_i)$ satisfies $\abs{\int_a^b f(x)\,dx - S} \le \tau$.

## 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|MNXC26G3BQ]]: 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$.

## Explanations

### L1 human

An adaptive integrator spends its effort where the function is hard.
It estimates the error on an interval; if the error is too big, it cuts the interval in half and treats each half with half of the allowed error.
Smooth regions are finished after a few steps, and only the difficult spots get cut many times.

### L2 human

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|E8QJJVC1KV]].
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.