Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

Authors: Hiroshi Sugiura and Takemitsu Hasegawa
Journal: Math. Comp. 80 (2011), 2169-2184
MSC (2010): Primary 65D05, 41A10; Secondary 42A15
Published electronically: March 31, 2011
MathSciNet review: 2813353
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D05, 41A10, 42A15

Retrieve articles in all journals with MSC (2010): 65D05, 41A10, 42A15

Additional Information

Hiroshi Sugiura
Affiliation: Department of Information Systems and Mathematical Sciences, Nanzan University, Seto, Aichi, 489-0863, Japan

Takemitsu Hasegawa
Affiliation: Department of Information Science, University of Fukui, Fukui, 910-8507, Japan

Keywords: Chebyshev interpolation, Chebyshev nodes, quasi-Chebyshev nodes, Chinese remainder theorem, FFT, error estimate, computational complexity, fast algorithm.
Received by editor(s): March 23, 2009
Received by editor(s) in revised form: September 21, 2010
Published electronically: March 31, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.