Error estimation in automatic quadrature routines

ABSTRACT

A new algorithm for estimating the error in quadrature approximations is presented. Based on the same integrand evaluations that we need for approximating the integral, one may, for many quadrature rules, compute a sequence of null rule approximations. These null rule approximations are then used to produce an estimate of the local error. The algorithm allows us to take advantage of the degree of precision of the basic quadrature rule. In the experiments we show that the algorithm works satisfactorily for a selection of different quadrature rules on all test families of integrals.

REFERENCES

• 1: BER~rTSEN, J. A test of some well known quadrature routines. Reports in Informatics 20, Dept. of Informatics, Univ. of Bergen, 1986.
• 2: J. Berntsen, Practical error estimation in adaptive multidimensional quadrature routines, Journal of Computational and Applied Mathematics, v.25 n.3, p.327-340, May 1989 [doi>10.1016/0377-0427(89)90036-8]
• 3: BERNTSEN, J., ESPELU), T. O., AND GENZ, A. A test of ADMINT. Reports in Informatics 31, Dept. of Informatics, Univ. of Bergen, 1988.
• 4: Jarle Berntsen , Terje O. Espelid , Alan Genz, An adaptive algorithm for the approximate calculation of multiple integrals, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.437-451, Dec. 1991 [doi>10.1145/210232.210233]
• 5: DAVIS, P. J., AND RABINOWITZ, P. Methods of Numerica! Integration. Academic Press, 1984.
• 6: DE BOOR, C. On writing an automatic integration algorithm. In Mathematical Software., J. R. Rice, Ed., Academic Press, 1971.
• 7: ESPELID, T.O. Integration rules, null rules and error estimation. Reports in Informatics 33, Dept. of Informatics, Univ. of Bergen, 1988.
• 8: T. O. Espelid , T. Sørevik, A discussion of a new error estimate for adaptive quadrature, BIT, v.29 n.2, p.283-294, 1989 [doi>10.1007/BF01952683]
• 9: GENZ, A C., AND MALIK, A.A. An adaptive algorithm for numerical integration over an N-dimenmonal rectangular region. J. Comput. Appl. Math. 6 (1980), 295-302.
• 10: ISAACSON, E., AND KELLER, I-I B. Analys~s of Numerzcal Methods. North Oxford Academic, 1966
• 11: LAURIE, D.P. Sharper error estimate in adaptive quadrature. BIT 23 (1983), 258-261
• 12: LAURIE, D. P. Practical error estimation in numerical integration. J. Comput. Appl. Math. 12 & 13 (1985), 425 431.
• 13: LYNESS, J.N. Symmetric integration rules for hypercubes III Construction of integration rules using null rules. Math. Comput. 19 (1965), 625-637.
• 14: J. N. Lyness , J. J. Kaganove, Comments on the Nature of Automatic Quadrature Routines, ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.65-81, March 1976 [doi>10.1145/355666.355671]
• 15: LYNESS, J. N., AND KAGANOVE, J. J. A technique for comparing automatic quadrature routines. Comput J. 20 (1977), 170-177.
• 16: Wm. M. McKeeman, Certification of algorithm 145: adaptive numerical integration by Simpson's rule, Communications of the ACM, v.6 n.4, p.167-168, April 1963 [doi>10.1145/366349.366535]
• 17: PIESSENS, R., DE DONCKER KAPENGA, E., UBERHUBER, C W , AND KAHANER, D K QUAD- PACK, a subroutine package for automatic integration. Series in Corrlplttational Ma{h. 1. Springer-Verlag, 1983.
• 18: SOREVIK, T. Reliable and efficient algorithms for adaptive quadrature Tech. Rep. Thesis for the degree Doctor Scientiarum, Dept. of Informatics, Univ. of Bergen, 1988.
• 19: VAN DOOREN, P., AND DE RIDDER, L. An adaptive algorithm for numerical integration over an N-dimensional cube. J. Comput. Appl. Math. 2 (1976), 207-217

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Adaptive and iterative quadrature

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Experimentation

Keywords:
reliability