Clenshaw-Curtis quadrature
/ KLEN-shaw KER-tis /
Gauss-Legendre quadrature is brilliantly accurate but its nodes are awkward: they are irrational and not nested, so doubling the resolution throws away all your previous function values. Clenshaw-Curtis quadrature trades a touch of that peak accuracy for two big practical wins — nodes you can compute trivially, that nest beautifully, and an evaluation that piggybacks on the fast Fourier transform.
The idea: instead of Legendre roots, sample at the Chebyshev points, the projections onto the x-axis of equally spaced points on a semicircle, x_k = cos(k pi / n). These cluster toward the endpoints (which tames Runge's phenomenon) and, crucially, the n-point set is contained in the 2n-point set, so refinement REUSES every earlier evaluation. To integrate, you expand f in a Chebyshev polynomial series and integrate that series term by term; the weights for this can be computed in O(n log n) time by a discrete cosine transform (a cousin of the FFT). The rule is exact for polynomials up to degree n — only about half the degree of an n-point Gauss rule — yet on real smooth functions the two converge at very nearly the same rate.
Clenshaw-Curtis is a favourite for automatic, adaptive integrators (and for high-dimensional sparse-grid quadrature) precisely because its nested Chebyshev nodes let you reuse work as you refine and cheaply estimate the error by comparing successive levels. The honest comparison with Gauss is nuanced: in worst-case polynomial degree Gauss wins by a factor of two, but for typical analytic integrands the realized accuracies are remarkably close, and Clenshaw-Curtis's nesting and FFT-speed often make it the more convenient choice. Like all polynomial-based rules, it still assumes a reasonably smooth integrand.
On [-1, 1] the 3-point Clenshaw-Curtis rule uses nodes cos(0) = 1, cos(pi/2) = 0, cos(pi) = -1 with weights 1/3, 4/3, 1/3 — which is exactly composite Simpson on those points. Doubling to 5 points reuses all three old nodes (1, 0, -1 stay) and just adds +-0.707, so no earlier function value is wasted.
Chebyshev nodes nest, so refinement reuses every old sample.
Although its formal polynomial degree (about n) is half that of Gauss (about 2n), on smooth real integrands the two converge at nearly the same speed — the textbook degree comparison overstates Gauss's practical edge. Clenshaw-Curtis wins on nesting and FFT-based O(n log n) setup.