A polynomial interpolation process at quasi-Chebyshev nodes with the FFT

Abstract:

Interpolation polynomial $p_n$ at the Chebyshev nodes $\cos \pi j/n$ ($0\le j\le n$) for smooth functions is known to converge fast as $n\to \infty$. The sequence $\{p_n\}$ is constructed recursively and efficiently in $O(n\log _2n)$ flops for each $p_n$ by using the FFT, where $n$ is increased geometrically, $n=2^i$ ($i=2,3,\dots$), until an estimated error is within a given tolerance of $\varepsilon$. This sequence $\{2^j\}$, however, grows too fast to get $p_n$ of proper $n$, often a much higher accuracy than $\varepsilon$ being achieved. To cope with this problem we present quasi-Chebyshev nodes (QCN) at which $\{p_n\}$ can be constructed efficiently in the same order of flops as in the Chebyshev nodes by using the FFT, but with $n$ increasing at a slower rate. We search for the optimum set in the QCN that minimizes the maximum error of $\{p_n\}$. Numerical examples illustrate the error behavior of $\{p_n\}$ with the optimum nodes set obtained.