Pedro Gonnet
Skip Abstract Section
Abstract
The most critical component of any adaptive numerical quadrature routine is the estimation of the integration error. Since the publication of the first algorithms in the 1960s, many error estimation schemes have been presented, evaluated, and discussed. This article presents a review of existing error estimation techniques and discusses their differences and their common features. Some common shortcomings of these algorithms are discussed, and a new general error estimation technique is presented.
- Aitken, A. 1926. On Bernoulli's numerical solution of algebraic equations. Proc. Royal Soc. Edinburgh 46, 289--305.Google Scholar
Cross Ref
- Balles, Z. and Trefethen, L. N. 2004. An extensions of MATLAB to continuous functions and operators. SIAM J. Sci. Comput. 25, 5, 1743--1770. Google ScholarDigital Library
- Bauer, F. L., Rutishauser, H., and Stiefel, E. 1963. New aspects in numerical quadrature. In Experimental Arithmetic, High Speed Computing and Mathematics, N. C. Metropolis, A. H. Taub, J. Todd, and C. B. Tompkins, Eds. American Mathematical Society, Providence, RI, 199--217.Google Scholar
- Berntsen, J. and Espelid, T. O. 1984. On the use of Gauss quadrature in adaptive automatic integration schemes. BIT Numer. Math. 24, 239--242.Google ScholarCross Ref
- Berntsen, J. and Espelid, T. O. 1991. Error estimation in automatic quadrature routines. ACM Trans. Math. Softw. 17, 2, 233--252. Google ScholarDigital Library
- Björck, Å. and Pereyra, V. 1970. Solution of Vandermonde systems of equations. Math. Comput. 24, 112, 893--903.Google Scholar
- Casaletto, J., Pickett, M., and Rice, J. 1969. A comparison of some numerical integration programs. SIGNUM Newsl. 4, 3, 30--40. Google ScholarDigital Library
- Clenshaw, C. W. and Curtis, A. R. 1960. A method for numerical integration on an automatic computer. Numerische Mathematik 2, 197--205.Google ScholarDigital Library
- Davis, P. J. and Rabinowitz, P. 1967. Numerical Integration. Blaisdell Publishing Company, Waltham, MA.Google Scholar
- de Boor, C. 1971. CADRE: An algorithm for numerical quadrature. In Mathematical Software, J. R. Rice, Ed. Academic Press, New York, NY, 201--209.Google Scholar
- de Doncker, E. 1978. An adaptive extrapolation algorithm for automatic integration. SIGNUM Newsl. 13, 2, 12--18. Google ScholarDigital Library
- Eaton, J. W. 2002. GNU Octave Manual. Network Theory Limited, U.K.Google Scholar
- Espelid, T. O. 1992. DQUAINT: An algorithm for adaptive quadrature over a collection of finite intervals. In Numerical Integration, T. O. Espelid and A. Genz, Eds. Kluwer Academic Publishers, Netherlands, 341--342.Google Scholar
- Espelid, T. O. 2002. Doubly adaptive quadrature routines based on Newton-Cotes rules. Tech. rep. 229, Department of Informatics, University of Bergen, Norway.Google Scholar
- Espelid, T. O. 2003. Doubly adaptive quadrature routines based on Newton-Cotes rules. BIT Numer. Math. 43, 319--337.Google ScholarCross Ref
- Espelid, T. O. 2004a. Extended doubly adaptive quadrature routines. Tech. rep. 266, Department of Informatics, University of Bergen, Norway.Google Scholar
- Espelid, T. O. 2004b. A test of QUADPACK and four doubly adaptive quadrature routines. Tech. rep. 281, Department of Informatics, University of Bergen, Norway.Google Scholar
- Espelid, T. O. 2007. Algorithm 868: Globally doubly adaptive quadrature—reliable MATLAB codes. ACM Trans. Math. Softw. 33, 3, Article 21. Google ScholarDigital Library
- Espelid, T. O. and Sørevik, T. 1989. A discussion of a new error estimate for adaptive quadrature. BIT Numer. Math. 29, 293--294. Google ScholarDigital Library
- Favati, P., Lotti, G., and Romani, F. 1991a. Interpolatory integration formulas for optimal composition. ACM Trans. Math. Softw. 17, 2, 207--217. Google ScholarDigital Library
- Favati, P., Lotti, G., and Romani, F. 1991b. Local error estimates in quadrature. BIT Numer. Math. 31, 102--111. Google ScholarDigital Library
- Forsythe, G. E., Malcolm, M. A., and Moler, C. B. 1977. Computer Methods for Mathematical Computations. Prentice-Hall, Inc., Englewood Cliffs, NJ. Google ScholarDigital Library
- Galassi, M., Davies, J., Theiler, J., Gough, B., Jungman, G., Alken, P., Booth, M., and Rossi, F. 2009. GNU Scientific Library Reference Manual, 3rd Ed. Network Theory Ltd., U.K. Google ScholarDigital Library
- Gallaher, L. J. 1967. Algorithm 303: An adaptive quadrature procedure with random panel sizes. Commun. ACM 10, 6, 373--374. Google ScholarDigital Library
- Gander, W. 2006. Generating numerical algorithms using a computer algebra system. BIT Numer. Math. 46, 491--504.Google ScholarCross Ref
- Gander, W. and Gautschi, W. 2001. Adaptive quadrature—revisited. BIT 40, 1, 84--101.Google ScholarCross Ref
- Garribba, S., Quartapelle, L., and Reina, G. 1978. SNIFF: Efficient self-tuning algorithm for numerical integration. Computing 20, 363--375.Google ScholarCross Ref
- Gautschi, W. 1975. Norm estimates for inverses of Vandermonde matrices. Numerische Mathematik 23, 337--347.Google ScholarDigital Library
- Gautschi, W. 1997. Numerical Analysis, An Introduction. Birkhäuser Verlag, Boston, MA. Google ScholarDigital Library
- Gautschi, W. 2004. Orthogonal Polynomials: Computation and Approximation. Oxford University Press, Oxford.Google ScholarCross Ref
- Gonnet, P. 2009. Adaptive quadrature re-revisited. Ph.D. dissertation, ETH Zürich.Google Scholar
- Gonnet, P. 2010a. Efficient construction, update and downdate of the coefficients of interpolants based on polynomials satisfying a three-term recurrence relation. arXiv:1003.4628.Google Scholar
- Gonnet, P. 2010b. Increasing the reliability of adaptive quadrature using explicit interpolants. ACM Trans. Math. Softw. 37, 26:1--26:32. Google ScholarDigital Library
- Hasegawa, T., Hibino, S., Hosoda, Y., and Ninomiya, I. 2007. An extended doubly-adaptive quadrature method based on the combination of the Ninomiya and the FLR schemes. Numer. Algorithms 45, 1--4, 101--112.Google ScholarCross Ref
- Henrici, P. 1982. Essentials of Numerical Analysis, with Pocket Calculator Demonstrations. John Wiley & Sons, Inc., New York, NY. Google ScholarDigital Library
- Henriksson, S. 1961. Contribution no. 2: Simpson numerical integration with variable length of step. BIT Numer. Math. 1, 290.Google Scholar
- Higham, N. J. 1988. Fast solution of Vandermonde-like systems involving orthogonal polynomials. IMA J. Numer. Anal. 8, 473--486.Google ScholarCross Ref
- Higham, N. J. 1990. Stability anal. of algorithms for solving confluent Vandermonde-like systems. SIAM J. Matrix Anal. Appli. 11, 1, 23--41. Google ScholarDigital Library
- Hillstrom, K. E. 1970. Comparison of several adaptive Newton-Cotes quadrature routines in evaluating definite integrals with peaked integrands. Commun. ACM 13, 6, 362--365. Google ScholarDigital Library
- Kahaner, D. K. 1971. 5.15 Comparison of numerical quadrature formulas. In Mathematical Software, J. R. Rice, Ed. Academic Press, New York, NY, 229--259.Google Scholar
- Kahaner, D. K. 1972. Numberical quadrature by the ϵ-algorithm. Math. Comput. 26, 119, 689--693.Google Scholar
- Krommer, A. R. and Überhuber, C. W. 1998. Computational Integration. SIAM, Philadelphia, PA.Google Scholar
- Kronrod, A. S. 1965. Nodes and Weights of Quadrature Formulas—Authorized Translation from the Russian. Consultants Bureau, New York, NY.Google Scholar
- Kuncir, G. F. 1962. Algorithm 103: Simpson's rule integrator. Commun. ACM 5, 6, 347. Google ScholarDigital Library
- Laurie, D. P. 1983. Sharper error estimates in adaptive quadrature. BIT Numer. Math. 23, 258--261.Google ScholarCross Ref
- Laurie, D. P. 1985. Practical error estimation in numerical integration. J. Comput. Appl. Math. 12--13, 425--431.Google ScholarCross Ref
- Laurie, D. P. 1992. Stratified sequences of nested quadrature formulas. Quaestiones Mathematicae 15, 364--384.Google ScholarCross Ref
- Lyness, J. N. 1965. Symmetric integration rules for hypercubes III: Construction of integration rules using null rules. Math. Comput. 19, 625--637.Google Scholar
- Lyness, J. N. 1969. Notes on the adaptive Simpson quadrature routine. J. ACM 16, 3, 483--495. Google ScholarDigital Library
- Lyness, J. N. 1970. Algorithm 379: SQUANK (Simpson Quadrature Used Adaptively -- Noise Killed). Commun. ACM 13, 4, 260--262. Google ScholarDigital Library
- Lyness, J. N. and Kaganove, J. J. 1976. Comments on the nature of automatic quadrature routines. ACM Trans. Math. Softw. 2, 1, 170--177. Google ScholarDigital Library
- Lyness, J. N. and Kaganove, J. J. 1977. A technique for comparing automatic quadrature routines. Comput. J. 20, 2, 170--177.Google ScholarCross Ref
- Malcolm, M. A. and Simpson, R. B. 1975. Local versus global strategies for adaptive quadrature. ACM Trans. Math. Softw. 1, 2, 129--146. Google ScholarDigital Library
- McKeeman, W. M. 1962. Algorithm 145: Adaptive numerical integration by Simpson's rule. Commun. ACM 5, 12, 604. Google ScholarDigital Library
- McKeeman, W. M. 1963. Algorithm 198: Adaptive integration and multiple integration. Commun. ACM 6, 8, 443--444. Google ScholarDigital Library
- McKeeman, W. M. and Tesler, L. 1963. Algorithm 182: Nonrecursive adaptive integration. Commun. ACM 6, 6, 315. Google ScholarDigital Library
- Morrin, H. 1955. Integration subroutine -- fixed point. Tech. rep. 701 Note #28, U.S. Naval Ordnance Test Station, China Lake, CA.Google Scholar
- Ninomiya, I. 1980. Improvements of adaptive Newton-Cotes quadrature methods. J. Info. Process. 3, 3, 162--170.Google Scholar
- O'Hara, H. and Smith, F. J. 1968. Error estimation in Clenshaw-Curtis quadrature formula. Comput. J. 11, 2, 213--219.Google ScholarCross Ref
- O'Hara, H. and Smith, F. J. 1969. The evaluation of definite integrals by interval subdivision. Comput. J. 12, 2, 179--182.Google ScholarCross Ref
- Oliver, J. 1971. A practical strategy for the Clenshaw-Curtis quadrature method. J. Inst. Math. Appl. 8, 53--56.Google ScholarCross Ref
- Oliver, J. 1972. A doubly-adaptive Clenshaw-Curtis quadrature method. Comput. J. 15, 2, 141--147.Google ScholarCross Ref
- Pachón, R., Platte, R., and Trefethen, L. N. 2009. Piecewise smooth chebfuns. IMA J. Numer. Anal., in Press.Google Scholar
- Patterson, T. N. L. 1973. Algorithm 468: Algorithm for automatic numerical integration over a finite interval. Commun. ACM 16, 11, 694--699. Google ScholarDigital Library
- Piessens, R. 1973. An algorithm for automatic integration. Angewandte Informatik 9, 399--401.Google Scholar
- Piessens, R., de Doncker-Kapenga, E., Überhuber, C. W., and Kahaner, D. K. 1983. QUADPACK A Subroutine Package for Automatic Integration. Springer-Verlag, Berlin.Google Scholar
- Ralston, A. and Rabinowitz, P. 1978. A First Course in Numerical Analysis. McGraw-Hill Inc., New York, NY.Google Scholar
- Robinson, I. 1979. A comparison of numerical integration programs. J. Comput. Appl. Math. 5, 3, 207--223.Google ScholarCross Ref
- Romberg, W. 1955. Vereinfachte numerische Integration. Det Kongelige Norske Videnskabers Selskab Forhandlinger 28, 7, 30--36.Google Scholar
- Rowland, J. H. and Varol, Y. L. 1972. Exit criteria for Simpson's compound rule. Math. Comput. 26, 119, 699--703.Google Scholar
- Rutishauser, H. 1976. Vorlesungen über numerische Mathematik, Band 1. Birkhäuser Verlag, Basel and Stuttgart.Google Scholar
- Schwarz, H. R. 1997. Numerische Mathematik 4th Ed. B. G. Teubner, Stuttgart. With a contribution by Jörg Waldvogel.Google Scholar
- Shampine, L. 2008. Vectorized adaptive quadrature in MATLAB. J. Comput. and Appl. Math. 211, 2, 131--140. Google ScholarDigital Library
- Skeel, R. D. and Keiper, J. B. 1993. Elementary Numerical Computing with Mathematica. McGraw-Hill, Inc., New York, NY. Google ScholarDigital Library
- Stiefel, E. 1961. Einführung in die numerische Mathematik. B. G. Teubner Verlagsgesellschaft, Stuttgart.Google Scholar
- The Mathworks 2005. MATLAB 7.0 Release Notes. The Mathworks, Natick, MA.Google Scholar
- Venter, A. and Laurie, D. P. 2002. A doubly adaptive integration algorithm using stratified rules. BIT Numer. Math. 42, 1, 183--193.Google ScholarCross Ref
- Villars, D. S. 1956. Use of the IBM 701 computer for quantum mechanical calculations II. overlap integral. Tech. rep. 5257, U.S. Naval Ordnance Test Station, China Lake, CA.Google Scholar
- Wynn, P. 1956. On a device for computing the em(sn) transformation. Math. Tables Other Aids Comput. 10, 54, 91--96.Google ScholarCross Ref
Index Terms
- A review of error estimation in adaptive quadrature
Recommendations
Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants
We present two new adaptive quadrature routines. Both routines differ from previously published algorithms in many aspects, most significantly in how they represent the integrand, how they treat nonnumerical values of the integrand, how they deal with ...
Adaptive, Self-Validating Numerical Quadrature
Integrals of a function of a single variable can be expressed as the sum of a numerical quadrature rule and a remainder term. The quadrature rule is a linear combination of function values and weights, or the integral of a Taylor polynomial, while the ...
Computing Cauchy principal value integrals using a standard adaptive quadrature
We investigate the possibility of fast, accurate and reliable computation of the Cauchy principal value integrals a b f ( x ) ( x - ) - 1 d x ( a < < b ) using a standard adaptive quadrature. In order to properly control the error tolerance for the ...
Comments