Clenshaw–Curtis quadrature and Fejér quadrature are methods for
numerical integration
In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral.
The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for "numerical integr ...
, or "quadrature", that are based on an expansion of the
integrand in terms of
Chebyshev polynomials
The Chebyshev polynomials are two sequences of orthogonal polynomials related to the cosine and sine functions, notated as T_n(x) and U_n(x). They can be defined in several equivalent ways, one of which starts with trigonometric functions:
...
. Equivalently, they employ a
change of variables
In mathematics, a change of variables is a basic technique used to simplify problems in which the original variables are replaced with functions of other variables. The intent is that when expressed in new variables, the problem may become si ...
and use a
discrete cosine transform
A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequency, frequencies. The DCT, first proposed by Nasir Ahmed (engineer), Nasir Ahmed in 1972, is a widely ...
(DCT) approximation for the
cosine series. Besides having fast-converging accuracy comparable to
Gaussian quadrature
In numerical analysis, an -point Gaussian quadrature rule, named after Carl Friedrich Gauss, is a quadrature rule constructed to yield an exact result for polynomials of degree or less by a suitable choice of the nodes and weights for .
Th ...
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 to be integrated is evaluated at the
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
time by means of
fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
-related algorithms for the DCT.
[W. Morven Gentleman, "Implementing Clenshaw-Curtis quadrature I: Methodology and experience," ''Communications of the ACM'' 15(5), p. 337-342 (1972).][Jörg Waldvogel,]
Fast construction of the Fejér and Clenshaw-Curtis quadrature rules
" ''BIT Numerical Mathematics'' 46 (1), p. 195-202 (2006).
General method
A simple way of understanding the algorithm is to realize that Clenshaw–Curtis quadrature (proposed by those authors in 1960)
[C. W. Clenshaw and A. R. Curtis]
A method for numerical integration on an automatic computer
''Numerische Mathematik'' 2, 197 (1960). amounts to integrating via a
change of variable . The algorithm is normally expressed for integration of a function over the interval
��1,1(any other interval can be obtained by appropriate rescaling). For this integral, we can write:
That is, we have transformed the problem from integrating
to one of integrating
. This can be performed if we know the
cosine series for
:
in which case the integral becomes:
Of course, in order to calculate the cosine series coefficients
one must again perform a numeric integration, so at first this may not seem to have simplified the problem. Unlike computation of arbitrary integrals, however, Fourier-series integrations for
periodic functions
A periodic function, also called a periodic waveform (or simply periodic wave), is a function that repeats its values at regular intervals or periods. The repeatable part of the function or waveform is called a ''cycle''. For example, the tr ...
(like
, by construction), up to the
Nyquist frequency
In signal processing, the Nyquist frequency (or folding frequency), named after Harry Nyquist, is a characteristic of a Sampling (signal processing), sampler, which converts a continuous function or signal into a discrete sequence. For a given S ...
, are accurately computed by the
equally spaced and equally weighted points
for
(except the endpoints are weighted by 1/2, to avoid double-counting, equivalent to the
trapezoidal rule
In calculus, the trapezoidal rule (or trapezium rule in British English) is a technique for numerical integration, i.e., approximating the definite integral:
\int_a^b f(x) \, dx.
The trapezoidal rule works by approximating the region under the ...
or the
Euler–Maclaurin formula
In mathematics, the Euler–Maclaurin formula is a formula for the difference between an integral and a closely related sum. It can be used to approximate integrals by finite sums, or conversely to evaluate finite sums and infinite series using ...
). That is, we approximate the cosine-series integral by the type-I
discrete cosine transform
A discrete cosine transform (DCT) expresses a finite sequence of data points in terms of a sum of cosine functions oscillating at different frequency, frequencies. The DCT, first proposed by Nasir Ahmed (engineer), Nasir Ahmed in 1972, is a widely ...
(DCT):