An algorithm based on the FFT for a generalized Chebyshev interpolation

Hasegawa, Takemitsu; Torii, Tatsuo; Sugiura, Hiroshi

doi:10.1090/S0025-5718-1990-0990599-0

An algorithm based on the FFT for a generalized Chebyshev interpolation
HTML articles powered by AMS MathViewer

by Takemitsu Hasegawa, Tatsuo Torii and Hiroshi Sugiura PDF

Math. Comp. 54 (1990), 195-210 Request permission

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

Maria Branders and Robert Piessens, An extension of Clenshaw-Curtis quadrature, J. Comput. Appl. Math. 1 (1975), 55–65. MR 371022, DOI 10.1016/0771-050x(75)90009-1
William L. Briggs, Further symmetries of in-place FFTs, SIAM J. Sci. Statist. Comput. 8 (1987), no. 4, 644–654. MR 892311, DOI 10.1137/0908057

The Fast Fourier Transform and its applications

Roland Bulirsch, Bemerkungen zur Romberg-Integration, Numer. Math. 6 (1964), 6–16 (German). MR 165688, DOI 10.1007/BF01386048
C. W. Clenshaw and A. R. Curtis, A method for numerical integration on an automatic computer, Numer. Math. 2 (1960), 197–205. MR 117885, DOI 10.1007/BF01386223
Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
Elise de Doncker-Kapenga, Asymptotic expansions and their applications in numerical integration, Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 203, Reidel, Dordrecht, 1987, pp. 141–151. MR 907116
David Elliott, Truncation errors in two Chebyshev series approximations, Math. Comp. 19 (1965), 234–248. MR 181084, DOI 10.1090/S0025-5718-1965-0181084-2
H. Engels, Numerical quadrature and cubature, Computational Mathematics and Applications, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1980. MR 587486

An investigation of Romberg quadrature

4

Fast Fourier transform for fun and profit

W. Morven Gentleman, Implementing Clenshaw-Curtis quadrature. I. Methodology and experience, Comm. ACM 15 (1972), 337–342. MR 0327001, DOI 10.1145/355602.361310
W. Morvin Gentleman, Implementing Clenshaw-Curtis quadrature. II. Computing the cosine transformation, Comm. ACM 15 (1972), 343–346. MR 0327002, DOI 10.1145/355602.361311
Takemitsu Hasegawa, Tatsuo Torii, and Ichizo Ninomiya, Generalized Chebyshev interpolation and its application to automatic quadrature, Math. Comp. 41 (1983), no. 164, 537–553. MR 717701, DOI 10.1090/S0025-5718-1983-0717701-6
Takemitsu Hasegawa and Tatsuo Torii, Indefinite integration of oscillatory functions by the Chebyshev series expansion, J. Comput. Appl. Math. 17 (1987), no. 1-2, 21–29. MR 884258, DOI 10.1016/0377-0427(87)90035-5
J. N. Lyness, The calculation of Fourier coefficients by the Möbius inversion of the Poisson summation formula. I. Functions whose early derivatives are continuous, Math. Comp. 24 (1970), 101–135. MR 260230, DOI 10.1090/S0025-5718-1970-0260230-8
H. O’Hara and Francis J. Smith, Error estimation in the Clenshaw-Curtis quadrature formula, Comput. J. 11 (1968/69), 213–219. MR 230469, DOI 10.1093/comjnl/11.2.213

Doubly-adaptive Clenshaw-Curtis quadrature method

15

Robert Piessens and Maria Branders, Numerical solution of integral equations of mathematical physics, using Chebyshev polynomials, J. Comput. Phys. 21 (1976), no. 2, 178–196. MR 458972, DOI 10.1016/0021-9991(76)90010-3
Robert Piessens, Elise de Doncker-Kapenga, Christoph W. Überhuber, and David K. Kahaner, QUADPACK, Springer Series in Computational Mathematics, vol. 1, Springer-Verlag, Berlin, 1983. A subroutine package for automatic integration. MR 712135, DOI 10.1007/978-3-642-61786-7
R. Piessens, Modified Clenshaw-Curtis integration and applications to numerical computation of integral transforms, Numerical integration (Halifax, N.S., 1986) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 203, Reidel, Dordrecht, 1987, pp. 35–51. MR 907110

A comparison of numerical integration programs

5

Ian H. Sloan and W. E. Smith, Product-integration with the Clenshaw-Curtis and related points. Convergence properties, Numer. Math. 30 (1978), no. 4, 415–428. MR 494863, DOI 10.1007/BF01398509
Ian H. Sloan and William E. Smith, Product integration with the Clenshaw-Curtis points: implementation and error estimates, Numer. Math. 34 (1980), no. 4, 387–401. MR 577405, DOI 10.1007/BF01403676
Ian H. Sloan and William E. Smith, Properties of interpolatory product integration rules, SIAM J. Numer. Anal. 19 (1982), no. 2, 427–442. MR 650061, DOI 10.1137/0719027
Paul N. Swarztrauber, Symmetric FFTs, Math. Comp. 47 (1986), no. 175, 323–346. MR 842139, DOI 10.1090/S0025-5718-1986-0842139-3