Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

An algorithm based on the FFT for a generalized Chebyshev interpolation


Authors: Takemitsu Hasegawa, Tatsuo Torii and Hiroshi Sugiura
Journal: Math. Comp. 54 (1990), 195-210
MSC: Primary 65D05; Secondary 41A55, 42A15, 65D30, 65T20
DOI: https://doi.org/10.1090/S0025-5718-1990-0990599-0
MathSciNet review: 990599
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: An algorithm for a generalized Chebyshev interpolation procedure, increasing the number of sample points more moderately than doubling, is presented. The FFT for a real sequence is incorporated into the algorithm to enhance its efficiency. Numerical comparison with other existing algorithms is given.


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

  • [1] M. Branders and R. Piessens, An extension of Clenshaw-Curtis quadrature, J. Comput. Appl. Math. 1 (1975), 55-65. MR 0371022 (51:7245)
  • [2] W. L. Briggs, Further symmetries of in-place FFTs, SIAM J. Sci. Statist. Comput. 8 (1987), 644-654. MR 892311 (88i:65167)
  • [3] E. O. Brigham, The Fast Fourier Transform and its applications, Prentice-Hall, Englewood Cliffs, NJ, 1988.
  • [4] R. Bulirsch, Bemerkung zur Romberg-Integration, Numer. Math. 6 (1964), 6-16. MR 0165688 (29:2968)
  • [5] C. W. Clenshaw and A. R. Curtis, A method for numerical integration on an automatic computer, Numer. Math. 2 (1960), 197-205. MR 0117885 (22:8659)
  • [6] P. J. Davis and P. Rabinowitz, Methods of numerical integration, 2nd ed., Academic Press, Orlando, FL, 1984. MR 760629 (86d:65004)
  • [7] E. deDoncker-Kapenga, Asymptotic expansions and their applications in numerical integration, Numerical Integration, Recent Developments, Software and Applications (P. Keast and G. Fairweather, eds.), Reidel, Dordrecht, 1987, pp. 141-151. MR 907116 (88i:65027)
  • [8] D. Elliott, Truncation errors in two Chebyshev series approximations, Math. Comp. 19 (1965), 234-248. MR 0181084 (31:5313)
  • [9] H. Engels, Numerical quadrature and cubature, Academic Press, London, 1980. MR 587486 (83g:65002)
  • [10] G. Fairweather and P. Keast, An investigation of Romberg quadrature, ACM Trans. Math. Software 4 (1978), 316-322.
  • [11] W. M. Gentleman and G. Sande, Fast Fourier transform for fun and profit, 1966, Fall Joint Computer Conference, AFIPS Conference Proceedings, vol. 29, 1966, pp. 563-578.
  • [12] W. M. Gentleman, Implementing Clenshaw-Curtis quadrature, I. Methodology and experience, Comm. ACM 15 (1972), 337-342. MR 0327001 (48:5343)
  • [13] -, Implementing Clenshaw-Curtis quadrature, II. Computing the cosine transformation, Comm. ACM 15 (1972), 343-346. MR 0327002 (48:5344)
  • [14] T. Hasegawa, T. Torii, and I. Ninomiya, Generalized Chebyshev interpolation and its application to automatic quadrature, Math. Comp. 41 (1983), 537-553. MR 717701 (84m:65037)
  • [15] T. Hasegawa and T. Torii, Indefinite integration of oscillatory functions by the Chebyshev series expansion, J. Comput. Appl. Math. 17 (1987), 21-29. MR 884258 (88d:65039)
  • [16] J. N. Lyness, The calculation of Fourier coefficients by the Möbius inversion of the Poisson summation formula, Part I. Functions whose early derivatives are continuous, Math. Comp. 24 (1970), 101-135. MR 0260230 (41:4858)
  • [17] H. O'Hara and F. J. Smith, Error estimation in the Clenshaw-Curtis quadrature formula, Comput. J. 11 (1968), 213-219. MR 0230469 (37:6031)
  • [18] J. Oliver, Doubly-adaptive Clenshaw-Curtis quadrature method, Comput. J. 15 (1972), 141-147.
  • [19] R. Piessens and M. Branders, Numerical solution of integral equations of mathematical physics using Chebyshev polynomials, J. Comput. Phys. 21 (1976), 178-196. MR 0458972 (56:17171)
  • [20] R. Piessens, E. deDoncker-Kapenga, C. W. Überhuber and D. K. Kahaner, QUADPACK, A subroutine package for automatic integration, Springer-Verlag, Berlin, 1983. MR 712135 (85b:65022)
  • [21] R. Piessens, Modified Clenshaw-Curtis integration and application to numerical computation of integral transforms, Numerical Integration, Recent Developments, Software and Applications (P. Keast and G. Fairweather, eds.), Reidel, Dordrecht, 1987, pp. 35-51. MR 907110 (88j:65050)
  • [22] I. Robinson, A comparison of numerical integration programs, J. Comput. Appl. Math. 5 (1979), 207-223.
  • [23] I. H. Sloan and W. E. Smith, Product-integration with the Clenshaw-Curtis and related points. Convergence properties, Numer. Math. 30 (1978), 415-428. MR 0494863 (58:13646)
  • [24] -, Product integration with the Clenshaw-Curtis points: implementation and error estimates, Numer. Math. 34 (1980), 387-401. MR 577405 (81g:65030)
  • [25] -, Properties of interpolatory product integration rules, SIAM J. Numer. Anal. 19 (1982), 427-442. MR 650061 (83e:41032)
  • [26] P. N. Swarztrauber, Symmetric FFTs, Math. Comp. 47 (1986), 323-346. MR 842139 (88a:65157)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D05, 41A55, 42A15, 65D30, 65T20

Retrieve articles in all journals with MSC: 65D05, 41A55, 42A15, 65D30, 65T20


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-0990599-0
Keywords: Chebyshev interpolation, approximate integration, FFT
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society