|
ABSTRACT:
The computation of Riemann definite integrals by means of Clenshaw-Curtis
quadrature sums or their extensions to oscillatory or hyperbolic weight
functions covers the most important numerical problems involving
observables which relate variables from the direct and the reciprocal
space.
From the numerical point of view, the use of an n-th degree truncated
Chebyshev series expansion for the approximation of the integrand over
the fundamental range [-1, 1] shows the advantage that it is close to
the minimax polynomial approximation: the deviations of the interpolatory
polynomial from the values of the integrand (assumed to be a Lipschitz
function) inbetween the quadrature abscissas are finite, and hence the
output reliability is substantially better as compared to other kinds of
quadrature rules (like the highest polynomial degree precision Gauss
quadrature which uses least squares polynomial expansions).
The computation of the n-column vector B of the expansion coefficients
is done from the matrix product B = T F, where T denotes a symmetric
matrix which stores the values of the Chebyshev polynomials at the
quadrature abscissas and F denotes a column vector storing the integrand
values at the quadrature abscissas.
Gentleman was the first to note that the computation of the coefficients
B within Clenshaw-Curtis quadrature can take advantage of the fast
Fourier technique (FFT). However, only solutions concerning particular
finite n-values of the polynomial degree have been reported so far.
In the present paper, a fast Chebyshev algorithm for the computation of
the coefficients B is discussed for expansion degrees n which are powers
of 2. The following three main results are reported:
(i) The set of irreducible positive abscissas over (0, 1) can be ordered
in a binary tree with heap ordering key. This allows their computation to
machine accuracy using relationships for siblings characterized by
complementary arguments.
(ii) The values of any line or column of coefficients of the matrix T
run over the fundamental set of quadrature abscissas. The heap ordering
allows the splitting of T into square l X l irreducible blocks, where l
denotes the depth level of the children inside the heap. This property
permits the exploitation of the FFT great factorization theorem,
resulting in a number of multiplications needed to compute B which is
smaller than the value n ln(n) specific to the FFT.
(iii) The internal structure of the irreducible l X l blocks shows
discrete symmetry properties which allow the definition of symmetry
stars of the elements belonging to specific irreducible domains inside
each block. The use of the occurring symmetry stars leads to the
straightforward identification of the matrix elements thus keeping to a
minimum the necessary computing effort.
back
|