research-article

Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants

Author:

Pedro GonnetAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 37, Issue 3

Article No.: 26, Pages 1 - 32

https://doi.org/10.1145/1824801.1824804

Published: 01 September 2010 Publication History

Abstract

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 improper divergent integrals, and how they estimate the integration error. The main focus of these improvements is to increase the reliability of the algorithms without significantly impacting their efficiency. Both algorithms are implemented in MATLAB and tested using both the “families” suggested by Lyness and Kaganove and the battery test used by Gander and Gautschi and Kahaner. They are shown to be more reliable, albeit in some cases less efficient, than other commonly-used adaptive integrators.

References

[1]

}}Bauer, F. L., Rutishauser, H., and Stiefel, E. 1963. New aspects in numerical quadrature. In Proceedings of the 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.

[2]

}}Berntsen, J. and Espelid, T. O. 1991. Error estimation in automatic quadrature routines. ACM Trans. Math. Softw. 17, 2, 233--252.

Digital Library

[3]

}}Björck, Å . and Pereyra, V. 1970. Solution of Vandermonde systems of equations. Math. Comput. 24, 112, 893--903.

[4]

}}Casaletto, J., Pickett, M., and Rice, J. 1969. A comparison of some numerical integration programs. SIGNUM Newslett. 4, 3, 30--40.

Digital Library

[5]

}}Clenshaw, C. W. and Curtis, A. R. 1960. A method for numerical integration on an automatic computer. Numer. Math. 2, 197--205.

Digital Library

[6]

}}Davis, P. J. and Rabinowitz, P. 1984. Numerical Integration 2nd Ed. Blaisdell Publishing Company, Waltham, MA.

[7]

}}de Boor, C. 1971. CADRE: An algorithm for numerical quadrature. In Mathematical Software, J. R. Rice, Ed. Academic Press, New York, 201--209.

[8]

}}de Doncker, E. 1978. An adaptive extrapolation algorithm for automatic integration. SIGNUM Newsl. 13, 2, 12--18.

Digital Library

[9]

}}Eaton, J. W. 2002. GNU Octave Manual. Network Theory Limited.

[10]

}}Espelid, T. O. 2007. Algorithm 868: Globally doubly adaptive quadrature---Reliable Matlab codes. ACM Trans. Math. Softw. 33, 3, 21.

Digital Library

[11]

}}Favati, P., Lotti, G., and Romani, F. 1991. Interpolatory integration formulas for optimal composition. ACM Trans. Math. Softw. 17, 2, 207--217.

Digital Library

[12]

}}Forsythe, G. E., Malcolm, M. A., and Moler, C. B. 1977. Computer Methods for Mathematical Computations. Prentice-Hall, Inc., Englewood Cliffs, NJ 07632.

Digital Library

[13]

}}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.

Digital Library

[14]

}}Gallaher, L. J. 1967. Algorithm 303: An adaptive quadrature procedure with random panel sizes. Comm. ACM 10, 6, 373--374.

Digital Library

[15]

}}Gander, W. and Gautschi, W. 1998. Adaptive quadrature---Revisited. Tech. rep. 306, Department of Computer Science, ETH Zurich, Switzerland.

[16]

}}Gander, W. and Gautschi, W. 2001. Adaptive quadrature---Revisited. BIT 40, 1, 84--101.

[17]

}}Gautschi, W. 1975. Norm estimates for inverses of Vandermonde matrices. Numer. Math. 23, 337--347.

Digital Library

[18]

}}Gautschi, W. 1997. Numerical Analysis, An Introduction. Birkhäuser Verlag, Basel.

Digital Library

[19]

}}Gentleman, W. M. 1972. Implementing Clenshaw-Curtis quadrature, II computing the cosine transformation. Comm. ACM 15, 5, 343--346.

Digital Library

[20]

}}Golub, G. H. and Welsch, J. H. 1969. Calculation of Gauss quadrature rules. Math. Comput. 23, 106, 221--230.

[21]

}}Gonnet, P. G. 2009a. Adaptive quadrature re-revisited. Ph.D. thesis, ETH Zürich, Switzerland.

[22]

}}Gonnet, P. G. 2009b. Efficient construction, update and downdate of the coefficients of interpolants based on polynomials satisfying a three-term recurrence relation. arxiv:1003.4628v2 {cs.NA}.

[23]

}}Henriksson, S. 1961. Contribution no. 2: Simpson numerical integration with variable length of step. BIT Numer. Math. 1, 290.

[24]

}}Higham, N. J. 1988. Fast solution of Vandermonde-like systems involving orthogonal polynomials. IMA J. Numer. Anal. 8, 473--486.

[25]

}}Higham, N. J. 1990. Stability analysis of algorithms for solving confluent Vandermonde-like systems. SIAM J. Matrix Anal. Appl. 11, 1, 23--41.

Digital Library

[26]

}}Hillstrom, K. E. 1970. Comparison of several adaptive Newton-Cotes quadrature routines in evaluating definite integrals with peaked integrands. Comm. ACM 13, 6, 362--365.

Digital Library

[27]

}}Kahaner, D. K. 1971. 5.15 Comparison of numerical quadrature formulas. In Mathematical Software, J. R. Rice, Ed. Academic Press, New York and London, 229--259.

[28]

}}Krommer, A. R. and Ü berhuber, C. W. 1998. Computational Integration. SIAM, Philadelphia, PA.

[29]

}}Kronrod, A. S. 1965. Nodes and Weights of Quadrature Formulas---Authorized Translation from the Russian. Consultants Bureau, New York.

[30]

}}Kuncir, G. F. 1962. Algorithm 103: Simpson’s rule integrator. Comm. ACM 5, 6, 347.

Digital Library

[31]

}}Laurie, D. P. 1983. Sharper error estimates in adaptive quadrature. BIT 23, 258--261.

[32]

}}Laurie, D. P. 1992. Stratified sequences of nested quadrature formulas. Quaestiones Mathematicae 15, 364--384.

[33]

}}Lyness, J. N. 1970. Algorithm 379: SQUANK (Simpson quadrature used adaptively -- noise killed). Comm. ACM 13, 4, 260--262.

Digital Library

[34]

}}Lyness, J. N. and Kaganove, J. J. 1977. A technique for comparing automatic quadrature routines. Comput. J. 20, 2, 170--177.

[35]

}}Malcolm, M. A. and Simpson, R. B. 1975. Local versus global strategies for adaptive quadrature. ACM Trans. Math. Softw. 1, 2, 129--146.

Digital Library

[36]

}}McKeeman, W. M. 1962. Algorithm 145: Adaptive numerical integration by Simpson’s rule. Comm. ACM 5, 12, 604.

Digital Library

[37]

}}McKeeman, W. M. 1963. Algorithm 198: Adaptive integration and multiple integration. Comm. ACM 6, 8, 443--444.

Digital Library

[38]

}}McKeeman, W. M. and Tesler, L. 1963. Algorithm 182: Nonrecursive adaptive integration. Comm. ACM 6, 6, 315.

Digital Library

[39]

}}Morrin, H. 1955. Integration subroutine -- Fixed point. Tech. rep. 701 Note #28, U.S. Naval Ordnance Test Station, China Lake, California.

[40]

}}Ninham, B. W. 1966. Generalised functions and divergent integrals. Numer. Math. 8, 444--457.

[41]

}}Ninomiya, I. 1980. Improvements of adaptive Newton-Cotes quadrature methods. J. Inform. Porc. 3, 3, 162--170.

[42]

}}O’Hara, H. and Smith, F. J. 1968. Error estimation in Clenshaw-Curtis quadrature formula. Comput. J. 11, 2, 213--219.

[43]

}}O’Hara, H. and Smith, F. J. 1969. The evaluation of definite integrals by interval subdivision. Comput. J. 12, 2, 179--182.

[44]

}}Oliver, J. 1972. A doubly-adaptive Clenshaw-Curtis quadrature method. Comput. J. 15, 2, 141--147.

[45]

}}Patterson, T. N. L. 1973. Algorithm 468: Algorithm for automatic numerical integration over a finite interval. Comm. ACM 16, 11, 694--699.

Digital Library

[46]

}}Piessens, R. 1973. An algorithm for automatic integration. Angewandte Inf. 9, 399--401.

[47]

}}Piessens, R., de Doncker-Kapenga, E., Überhuber, C. W., and Kahaner, D. K. 1983. QUADPACK A Subroutine Package for Automatic Integration. Springer-Verlag, Berlin.

[48]

}}Ralston, A. and Rabinowitz, P. 1978. A First Course in Numerical Analysis. McGraw-Hill Inc., New York.

[49]

}}Rice, J. R. 1975. A metalgorithm for adaptive quadrature. J. ACM 22, 1, 61--82.

Digital Library

[50]

}}Robinson, I. 1979. A comparison of numerical integration programs. J. Comput. Appl. Math. 5, 3, 207--223.

[51]

}}Rowland, J. H. and Varol, Y. L. 1972. Exit criteria for Simpson’s compound rule. Math. Comput. 26, 119, 699--703.

[52]

}}Rutishauser, H. 1976. Vorlesung über Numerische Mathematik. Birkhäuser Verlag, Basel.

[53]

}}Schwarz, H. R. 1997. Numerische Mathematik. B. G. Teubner, Stuttgart.

[54]

}}Stiefel, E. 1961. Einführung in Die Numerische Mathematik. B. G. Teubner Verlagsgesellschaft, Stuttgart.

[55]

}}Sugiura, H. and Sakurai, T. 1989. On the construction of high-order integration formulae for the adaptive quadrature method. J. Comput. Appl. Math. 28, 367--381.

Digital Library

[56]

}}The Mathworks. 2003. MATLAB 6.5 Release Notes. The Mathworks, Natick, MA.

[57]

}}Trefethen, L. N. 2008. Is Gauss quadrature better than Clenshaw-Curtis? SIAM Rev. 50, 1, 67--87.

Digital Library

[58]

}}Venter, A. and Laurie, D. P. 2002. A doubly adaptive integration algorithm using stratified rules. BIT 42, 1, 183--193.

[59]

}}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.

[60]

}}Waldvogel, J. 2009. Towards a general error theory of the trapezoidal rule. In Approximation and Computation, W. Gautschi and G. Mastroianni and Th.M. Rassias, To appear. Preprint Eds. Springer. http://www.math.ethz.ch/waldvoge/Projects/nisJoerg.pdf.

Cited By

Fuseau DSeoane LRamillien GDarrozes JPlazolles BRouxel DSchmitt TSalaün C(2024)Efficiency of Optimized Approaches for Gravity Operator ModelingRemote Sensing10.3390/rs1621403116:21(4031)Online publication date: 30-Oct-2024
https://doi.org/10.3390/rs16214031
Pal A(2024)Coarse graining with control points: a cubic-Bézier based approach to modeling athermal fibrous materialsInternational Journal for Computational Methods in Engineering Science and Mechanics10.1080/15502287.2024.235830925:5(347-356)Online publication date: 3-Jun-2024
https://doi.org/10.1080/15502287.2024.2358309
Núñez Fernández YJeannin MDumitrescu PKloss TKaye JParcollet OWaintal X(2022)Learning Feynman Diagrams with Tensor TrainsPhysical Review X10.1103/PhysRevX.12.04101812:4Online publication date: 16-Nov-2022
https://doi.org/10.1103/PhysRevX.12.041018
Show More Cited By

Index Terms

Increasing the Reliability of Adaptive Quadrature Using Explicit Interpolants
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

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 ...
Orthogonality, interpolation and quadratures on the unit circle and the interval [-1,1]

Given a weight function @s(x) on [-1,1], or more generally a positive Borel measure, the Erdos-Turan theorem assures the convergence in L"2^@s-norm to a function f of its sequence of interpolating polynomials at the zeros of the orthogonal polynomials ...
Szegö quadrature formulas for certain Jacobi-type weight functions

In this paper we are concerned with the estimation of integrals on the unit circle of the form ∫₀^2π f(e^iθ)ω(θ)dθ by means of the so-called Szegö quadrature formulas, i.e., formulas of the type Σ_j=1ⁿ λ_jf(x_j) with distinct nodes on the unit circle, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 37, Issue 3

September 2010

296 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/1824801

Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 2010

Accepted: 01 January 2010

Revised: 01 January 2010

Received: 01 December 2008

Published in TOMS Volume 37, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
493
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)4

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fuseau DSeoane LRamillien GDarrozes JPlazolles BRouxel DSchmitt TSalaün C(2024)Efficiency of Optimized Approaches for Gravity Operator ModelingRemote Sensing10.3390/rs1621403116:21(4031)Online publication date: 30-Oct-2024
https://doi.org/10.3390/rs16214031
Pal A(2024)Coarse graining with control points: a cubic-Bézier based approach to modeling athermal fibrous materialsInternational Journal for Computational Methods in Engineering Science and Mechanics10.1080/15502287.2024.235830925:5(347-356)Online publication date: 3-Jun-2024
https://doi.org/10.1080/15502287.2024.2358309
Núñez Fernández YJeannin MDumitrescu PKloss TKaye JParcollet OWaintal X(2022)Learning Feynman Diagrams with Tensor TrainsPhysical Review X10.1103/PhysRevX.12.04101812:4Online publication date: 16-Nov-2022
https://doi.org/10.1103/PhysRevX.12.041018
Pal A(2021)Fast and accurate computation of interactions between linear fiber segmentsEngineering Computations10.1108/EC-06-2020-034538:7(3061-3076)Online publication date: 10-Jun-2021
https://doi.org/10.1108/EC-06-2020-0345
Kloss TWeston JGaury BRossignol BGroth CWaintal X(2021)Tkwant: a software package for time-dependent quantum transportNew Journal of Physics10.1088/1367-2630/abddf723:2(023025)Online publication date: 17-Feb-2021
https://doi.org/10.1088/1367-2630/abddf7
Cambareri PDi Rienzo L(2021)Complete analytic integrations for the 2D BEM representation of the Laplace equation with linear shape functionsEngineering Analysis with Boundary Elements10.1016/j.enganabound.2021.07.017132(481-488)Online publication date: Nov-2021
https://doi.org/10.1016/j.enganabound.2021.07.017
Epperson J(2021)Numerical IntegrationAn Introduction to Numerical Methods and Analysis 3e10.1002/9781119604754.ch5(269-336)Online publication date: 16-Jul-2021
https://doi.org/10.1002/9781119604754.ch5
Liu ZLi CZhong YLesselier D(2020)Electromagnetic modeling of damaged fiber-reinforced laminatesJournal of Computational Physics10.1016/j.jcp.2020.109318409(109318)Online publication date: May-2020
https://doi.org/10.1016/j.jcp.2020.109318
Aragon‐Angel AZürn MRovira‐Garcia A(2019)Galileo Ionospheric Correction Algorithm: An Optimization Study of NeQuick‐GRadio Science10.1029/2019RS00687554:11(1156-1169)Online publication date: 24-Nov-2019
https://doi.org/10.1029/2019RS006875
Johnson R(2018)Algorithm 988ACM Transactions on Mathematical Software10.1145/315773544:3(1-19)Online publication date: 11-Apr-2018
https://dl.acm.org/doi/10.1145/3157735
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents