Implementing Clenshaw-Curtis quadrature, I methodology and experience

ABSTRACT

Clenshaw-Curtis quadrature is a particularly important automatic quadrature scheme for a variety of reasons, especially the high accuracy obtained from relatively few integrand values. However, it has received little use because it requires the computation of a cosine transformation, and the arithmetic cost of this has been prohibitive. This paper is in two parts; a companion paper, “II Computing the Cosine Transformation,” shows that this objection can be overcome by computing the cosine transformation by a modification of the fast Fourier transform algorithm. This first part discusses the strategy and various error estimates, and summarizes experience with a particular implementation of the scheme.

REFERENCES

• 1: Casaletto, J., Pickett, M., and Rice, J. A comparison of some numerical integration programs. SIGNUM Newsletter 4, 3 (1969), 30-40.
• 2: Clenshaw, C. W., and Curtis, A. R. A method for numerical integration on an automatic computer. Num. Math. 2 (1960), 197- 205.
• 3: Algorithm 351: modified Romberg quadrature, Communications of the ACM, v.12 n.6, p.324-326, June 1969 [doi>10.1145/363011.363031]
• 4: Fraser, W., and Wilson, M.W. Remarks on the Clenshaw- Curtis quadrature scheme. SIAM Rev. 8 (1966), 322-327.
• 5: Gentleman, W.M. An error analysis of Goertzel's (Watt's) method for computing Fourier coefficients. Comput. J. 12 (1966), 160-165.
• 6: W. Morven Gentleman, Implementing Clenshaw-Curtis quadrature, II computing the cosine transformation, Communications of the ACM, v.15 n.5, p.343-346, May 1972 [doi>10.1145/355602.361311]
• 7: W. Morven Gentleman, Algorithm 424: Clenshaw-Curtis quadrature [D-1], Communications of the ACM, v.15 n.5, p.353-355, May 1972 [doi>10.1145/355602.355603]
• 8: Havie, T. On a modification of the Clenshaw-Curtis quadrature formula. BIT9 (1969), 338-350.
• 9: Kenneth Hillstrom, Certification of Algorithm 279: Chebyshev quadrature, Communications of the ACM, v.10 n.5, p.294, May 1967 [doi>10.1145/363282.363309]
• 10: F. R. A. Hopgood , C. Litherland, Algorithm 279: Chebyshev quadrature, Communications of the ACM, v.9 n.4, p.270, April 1966 [doi>10.1145/365278.365508]
• 11: Imhof, J.P. On the method for numerical integration of Clenshaw and Curtis. Numer. Math. 5 (1963), 138-141.
• 12: O'Hara, H., and Smith, F.J. Error estimation in the Clenshaw-Curtis quadrature formula. Comput. J. 11 (1968), 213-219.
• 13: Oliver, J. The evaluation of definite integrals using high-order formulae. Comput. J. 14, 3 (1971), 301-306.
• 14: Smith, F.J. Quadrature methods based on the Euler-Mac- Laurin formula and on the Clenshaw-Curtis method of integration. Numer. Math. 7 (1965), 406-411.
• 15: George C. Wallick, Remark on algorithm 351 [D1]: modified Romberg quadrature, Communications of the ACM, v.13 n.6, p.374-376, June 1970 [doi>10.1145/362384.362511]
• 16: Wright, K. Series methods for integration, Comput. J. 9 (1966), 191-199.

INDEX TERMS

Keywords:
Chebyshev series, Clenshaw Curtis, automatic quadrature, error estimates, numerical integration