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?)

  • 1. Z. Battles, L. N. Trefethen, An extension of MATLAB to continuous functions and operators, SIAM J. Sci. Comput., 25 (2004), 1743-1770. MR 2087334 (2005e:41001)
  • 2. J. P. Berrut, L. N. Trefethen, Barycentric Lagrange interpolation, SIAM Rev., 46 (2004), 501-517. MR 2115059 (2005k:65018)
  • 3. J. P. Boyd, Computing zeros of a real interval through Chebyshev expansion and polynomial rootfinding, SIAM J. Numer. Anal., 40 (2003), 1666-1682. MR 1950617 (2003m:65071)
  • 4. J. P. Boyd, D. H. Gally, Numerical experiments on the accuracy of the Chbeyshev-Frobenius computation matrix method for finding the zeros of a truncated series of Chebyshev polynomials, J. Comput. Appl. Math., 205 (2007), 281-295. MR 2324840 (2008b:65065)
  • 5. M. Branders, R. Piessens, An extension of Clenshaw-Curtis quadrature, J. Comp. Appl. Math., 1 (1975), 55-65. MR 0371022 (51:7245)
  • 6. C. W. Clenshaw, A. R. Curtis, A method for numerical integration on an automatic computer, Numer. Math., 2 (1960), 197-205. MR 0117885 (22:8659)
  • 7. J. W. Cooley, J. W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp., 19 (1965), 297-301. MR 0178586 (31:2843)
  • 8. P. J. Davis, Interpolation and Approximation, Dover, New York, NY, 1963. MR 0157156 (28:393)
  • 9. W. M. Gentleman, Implementing Clenshaw-Curtis quadrature, II. Computing the cosine transformation, Comm. ACM, 15 (1972), 337-342. MR 0327001 (48:5343)
  • 10. T. Hasegawa, T. Torii, I. Ninomiya, Generalized Chebyshev interpolation and its application to automatic quadrature, Math. Comp., 41 (1983), 537-553. MR 717701 (84m:65037)
  • 11. T. Hasegawa, T. Torii, H. Sugiura, An algorithm based on the FFT for a generalized Chebyshev interpolation, Math. Comp., 54 (1990), 195-210. MR 990599 (91c:65009)
  • 12. J. C. Mason, D. C. Handscomb, Chebyshev Polynomials, Chapman & Hall, 2003. MR 1937591 (2004h:33001)
  • 13. H. J. Nussbaumer, Fast Fourier Transform and Convolution Algorithms, Springer, Berlin, 1981. MR 606376 (83e:65219)
  • 14. R. B. Platte, L. N. Trefethen, Chebfun: A new kind of numerical computing, Report No. 08/13, Oxford University Computing Laboratory, October (2008).
  • 15. D. Potts, G. Steidl, M. Tasche, Fast Algorithms for discrete polynomial transforms, Math. Comp., 224 (1998), 1577-1590. MR 1474655 (99b:65183)
  • 16. S. C. Reddy, J. A. C. Weideman, The accuracy of the Chebyshev differencing method for analytic functions, SIAM J. Numer. Anal., 42 (2005), 2176-2187. MR 2139243 (2006b:65026)
  • 17. I. H. Sloan, W. E. Smith, Product integration with the Clenshaw-Curtis points: Implementation and error estimates, Numer. Math., 34 (1980), 387-401. MR 577405 (81g:65030)
  • 18. G. Steidl, M. Tasche, A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms, Math. Comp., 56 (1991), 281-296. MR 1052103 (91h:65225)
  • 19. H. Sugiura, T. Torii, Polynomial interpolation on quasi-equidistributed nodes on the unit disk, SIAM J. Numer. Anal., 29 (1992), 1154-1165. MR 1173191
  • 20. P. N. Swarztrauber, Symmetric FFTs, Math. Comp., 175 (1986), 323-346. MR 842139 (88a:65157)
  • 21. L. N. Trefethen, Is Gauss quadrature better than Clenshaw-Curtis, SIAM Rev., 50 (2008), 67-87. MR 2403058 (2009c:65061)
  • 22. J. Waldvogel, Fast construction of the Fejér and Clenshaw-Curtis quadrature rules, BIT, 46 (2006), 195-202. MR 2214855 (2007k:65046)
  • 23. J. A. C. Weideman, L. N. Trefethen, The kink phenomenon in Fejér and Clenshaw-Curtis quadrature, Numer. Math. 107 (2007), 707-727. MR 2342649 (2008i:65048)

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