zbMATH — the first resource for mathematics

A fast algorithm for the evaluation of Legendre expansions. (English) Zbl 0726.65018
An algorithm is presented for the rapid evaluation of a Legendre expansion at Chebyshev nodes on the interval [-1,1], and conversely, for the evaluation of the coefficients of a Legendre expansion from a table of its values at Chebyshev nodes. The algorithm is based on replacing the Legendre expansion \(f(t)=\sum^{n-1}_{j=0}a_ jP_ j(t)\) with a Chebyshev expansion of the same length, with subsequent evaluation of the latter via the fast cosine transform.
Given the above Legendre expansion, the algorithm produces its values at the n Chebyshev nodes \(t_ 0,t_ 1,...,t_{n-1}\) for a cost proportional to \(n\cdot \log n.\) A detailed description of the algorithm and the analysis of its complexity are given. Several numerical experiments and an efficient scheme for the evaluation of the function \(\Gamma (x+1/2)/\Gamma (x+1)\), required by the algorithm, are also presented.

65D20 Computation of special functions and constants, construction of tables
65B10 Numerical summation of series
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
41A58 Series expansions (e.g., Taylor, Lidstone series, but not Fourier series)
Full Text: DOI