How well do fast discrete trigonometric transforms work for parametric numerical integration?

Abstract

The fast Fourier transform (FFT) and its real counterparts, the fast algorithms of the discrete cosine transform (DCT) and the discrete sine transform (DST), are frequently employed for the numerical evaluation of the Fourier cosine and Fourier sine transform, thereby acting as parametric quadrature rules based on finitely many samples of a given continuous function. But how accurate are the obtained results? In this paper we study the error occurring if the DCT of type I (DCT-I) and the DST of type I (DST-I) are applied to compute $\int_0^{\infty} f(x)\cos(2πxv)\d x$ and $\int_0^{\infty} f(x)\sin(2πxv)\d x$ for $f \in L^1(\Rp) \cap C(\Rp)$ and $v \in \Rp$, as well as the error occurring if the Chebyshev coefficients $\frac{2}π\int_0^π h(\cosθ)\,\cos(nθ)\dθ$, $n \in \Np$, of a function $h\in C(I)$ on $I:=[-1,1]$ are computed by the DCT-I. We present practicable, explicit error estimates under polynomial, exponential, and mixed decay conditions. For the Fourier cosine and sine transform, rational functions lead to a geometric decay in the frequency parameter $P$ combined with an algebraic plateau of order $L^{-3/2}$ in the sampling parameter $L$, while for meromorphic functions such as $\mathrm{sech}(\pi \cdot )$ the critical geometric rate is attained in both parameters. For Chebyshev approximation of a rational function with simple poles in $\C \setminus I$, the quadrature error has the critical geometric rate ${\rho }_0^{-P}$ with an explicit constant, where ${\rho }_0>1$ is the parameter of the largest Bernstein ellipse of analyticity. Several numerical examples illustrate the theory.