×

Convergence analysis and adaptive strategy for the certified quadrature over a set defined by inequalities. (English) Zbl 1293.65036

Summary: This paper investigates the sufficient conditions for the asymptotic convergence of a generic branch and prune algorithm dedicated to the verified quadrature of a function in several variables. Quadrature over domains defined by inequalities, and adaptive meshing strategies are in the scope of this analysis. The framework is instantiated using certified quadrature methods based on Taylor models (i.e. Taylor approximations with rigorously bounded remainder), and reported experiments confirmed the analysis. They also show that the performances of the instantiated algorithm are comparable with current methods for certified quadrature.

MSC:

65D30 Numerical integration
65G40 General methods in interval analysis
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Moore, R.; Kearfott, R.; Cloud, M., Introduction to Interval Analysis (2009), SIAM · Zbl 1168.65002
[2] Malcolm, M. A.; Simpson, R. B., Local versus global strategies for adaptive quadrature, ACM Transactions on Mathematical Software, 1, 2, 129-146 (1975) · Zbl 0303.65019
[3] Chen, C.-Y., Verified computed peano constants and applications in numerical quadrature, BIT Numerical Mathematics, 47, 2, 297-312 (2007) · Zbl 1118.65007
[4] Chen, C.-Y., Bivariate product cubature using peano kernels for local error estimates, J. Sci. Comput., 36, 69-88 (2008) · Zbl 1203.65050
[5] Chen, C.-Y., On the properties of sard kernels and multiple error estimates for bounded linear functionals of bivariate functions with application to non-product cubature, Numer. Math., 122, 4, 603-643 (2012) · Zbl 1259.65052
[6] Chen, C.-Y., Computing interval enclosures for definite integrals by application of triple adaptive strategies, Computing, 78, 81-99 (2006), URL http://portal.acm.org/citation.cfm?id=1152729.1152734 · Zbl 1100.65017
[7] Huybrechs, D.; Cools, R., On generalized gaussian quadrature rules for singular and nearly singular integrals, SIAM Journal on Numerical Analysis, 47, 719-739 (2009) · Zbl 1190.65038
[8] Hale, N.; Trefethen, L. N., New quadrature formulas from conformal maps, SIAM Journal on Numerical Analysis, 46, 930-948 (2008), URL http://portal.acm.org/citation.cfm?id=1350722.1350741 · Zbl 1173.65020
[9] Kálovics, F., Zones and integrals, J. Comput. Appl. Math., 182, 243-251 (2005) · Zbl 1075.65036
[11] Moore, R., Interval Analysis (1966), Prentice-Hall · Zbl 0176.13301
[12] Alefeld, G.; Herzberger, J., (Introduction to Interval Computations. Introduction to Interval Computations, Computer Science and Applied Mathematics (1974))
[13] Neumaier, A., Interval Methods for Systems of Equations (1990), Cambridge Univ. Press · Zbl 0706.15009
[14] Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E., Applied Interval Analysis with Examples in Parameter and State Estimation, Robust Control and Robotics (2001), Springer-Verlag · Zbl 1023.65037
[15] Kearfott, R. B., Interval computations: introduction, uses, and resources, Euromath Bulletin, 2, 1, 95-112 (1996) · Zbl 1465.65041
[16] Knueppel, O., PROFIL/BIAS — a fast interval library, Computing, 53, 3-4, 277-287 (1994) · Zbl 0808.65055
[17] Griewank, A.; Juedes, D.; Utke, J., Algorithm 755: ADOL-C: A package for the automatic differentiation of algorithms written in C/C++, ACM Transactions on Mathematical Software, 22, 2, 131-167 (1996) · Zbl 0884.65015
[18] Charpentier, I.; Utke, J., Fast higher-order derivative tensors with Rapsodia, Optimization Methods Software, 24, 1, 1-14 (2009) · Zbl 1166.65009
[19] Bischof, C. H.; Hovland, P.; Norris, B., On the implementation of automatic differentiation tools, Higher-Order and Symbolic Computation, 21, 3, 311-331 (2008) · Zbl 1168.65324
[20] Berz, M., Forward algorithms for high orders and many variables with application to beam physics, (Griewank, A.; Corliss, G. F., Automatic Differentiation of Algorithms: Theory, Implementation, and Application (1991), SIAM: SIAM Philadelphia, PA), 147-156 · Zbl 0782.65018
[21] Neidinger, R. D., An efficient method for the numerical evaluation of partial derivatives of arbitrary order, ACM Transactions on Mathematical Software, 18, 2, 159-173 (1992) · Zbl 0892.65011
[22] Griewank, A.; Utke, J.; Walther, A., Evaluating higher derivative tensors by forward propagation of univariate Taylor series, Math. Comp., 69, 1117-1130 (2000) · Zbl 0952.65028
[23] Neidinger, R. D., Directions for computing truncated multivariate Taylor series, Math. Comp., 74, 249, 321-340 (2005) · Zbl 1052.65012
[24] Berz, M.; Makino, K., New methods for high-dimensional verified quadrature, Reliable Computing, 5, 13-22 (1999) · Zbl 0947.65026
[25] Berz, M.; Hoffstatter, G., Computation and application of Taylor polynomials with interval remainder bounds, Reliable Computing, 4, 83-97 (1998) · Zbl 0897.65005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.