ClenshawCurtis

Clenshaw-Curtis quadrature is a numerical integration method based on Chebyshev points of the second kind. For a chosen number of points n+1, the nodes are x_k = cos(kπ/n) for k = 0,1,...,n, lying in the interval [-1,1]. The integral of a function f on [-1,1] is approximated by a weighted sum ∑_{k=0}^n w_k f(x_k), where the weights w_k are chosen so that polynomials up to a certain degree are integrated exactly. The endpoint nodes x_0 = 1 and x_n = -1 are included, and the weights can be computed efficiently using a discrete cosine transform, yielding an overall O(n log n) implementation.

The method is particularly effective for smooth functions. If f is analytic on [-1,1], the approximation error decays exponentially as n increases (spectral convergence); for functions with finite differentiability, the decay is algebraic with a rate determined by the regularity. Clenshaw-Curtis quadrature can be extended to arbitrary intervals [a,b] via a linear change of variables: ∫_a^b f(x) dx ≈ (b-a)/2 ∑_{k=0}^n w_k f((b-a)/2 x_k + (a+b)/2). It also serves as a basis for high-dimensional quadrature through tensor product grids or sparse grids.

Origin and use: The rule was introduced in the 1960s by Clenshaw and Curtis. It has become prominent in numerical analysis and spectral methods due to its accuracy, simplicity, and the FFT-based efficiency of weight computation, features emphasized in modern treatments of spectral collocation and polynomial approximation.