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

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.

American Mathematical Society