Clenshaw–Curtis quadrature

Clenshaw–Curtis quadrature and Fejér quadrature are methods for numerical integration, or 'quadrature', that are based on an expansion of the integrand in terms of Chebyshev polynomials. Equivalently, they employ a change of variables x = cos ⁡ θ {displaystyle x=cos heta } and use a discrete cosine transform (DCT) approximation for the cosine series. Besides having fast-converging accuracy comparable to Gaussian quadrature rules, Clenshaw–Curtis quadrature naturally leads to nested quadrature rules (where different accuracy orders share points), which is important for both adaptive quadrature and multidimensional quadrature (cubature). Briefly, the function f ( x ) {displaystyle f(x)} to be integrated is evaluated at the N {displaystyle N} extrema or roots of a Chebyshev polynomial and these values are used to construct a polynomial approximation for the function. This polynomial is then integrated exactly. In practice, the integration weights for the value of the function at each node are precomputed, and this computation can be performed in O ( N log ⁡ N ) {displaystyle O(Nlog N)} time by means of fast Fourier transform-related algorithms for the DCT. A simple way of understanding the algorithm is to realize that Clenshaw–Curtis quadrature (proposed by those authors in 1960) amounts to integrating via a change of variable x = cos(θ). The algorithm is normally expressed for integration of a function f(x) over the interval (any other interval can be obtained by appropriate rescaling). For this integral, we can write: That is, we have transformed the problem from integrating f ( x ) {displaystyle f(x)} to one of integrating f ( cos ⁡ θ ) sin ⁡ θ {displaystyle f(cos heta )sin heta } . This can be performed if we know the cosine series for f ( cos ⁡ θ ) {displaystyle f(cos heta )} :