Cubature formulas for symmetric measures in higher dimensions with few points

Hinrichs, Aicke; Novak, Erich

doi:10.1090/S0025-5718-07-01974-6

Cubature formulas for symmetric measures in higher dimensions with few points
HTML articles powered by AMS MathViewer

by Aicke Hinrichs and Erich Novak PDF

Math. Comp. 76 (2007), 1357-1372 Request permission

Abstract:

We study cubature formulas for $d$-dimensional integrals with an arbitrary symmetric weight function of product form. We present a construction that yields a high polynomial exactness: for fixed degree $\ell =5$ or $\ell =7$ and large dimension $d$ the number of knots is only slightly larger than the lower bound of Möller and much smaller compared to the known constructions. We also show, for any odd degree $\ell = 2k+1$, that the minimal number of points is almost independent of the weight function. This is also true for the integration over the (Euclidean) sphere.

References

H. Berens, H. J. Schmid, and Y. Xu, Multivariate Gaussian cubature formulae, Arch. Math. (Basel) 64 (1995), no. 1, 26–32. MR 1305657, DOI 10.1007/BF01193547
Hans-Joachim Bungartz and Michael Griebel, Sparse grids, Acta Numer. 13 (2004), 147–269. MR 2249147, DOI 10.1017/S0962492904000182
Simon Capstick and B. D. Keister, Multidimensional quadrature algorithms at higher degree and/or dimension, J. Comput. Phys. 123 (1996), no. 2, 267–273. MR 1372373, DOI 10.1006/jcph.1996.0023
Ronald Cools, Constructing cubature formulae: the science behind the art, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 1–54. MR 1489255, DOI 10.1017/S0962492900002701
Ronald Cools, An encyclopaedia of cubature formulas, J. Complexity 19 (2003), no. 3, 445–453. Numerical integration and its complexity (Oberwolfach, 2001). MR 1984127, DOI 10.1016/S0885-064X(03)00011-6
Ronald Cools and Ann Haegemans, An imbedded family of cubature formulae for $n$-dimensional product regions, J. Comput. Appl. Math. 51 (1994), no. 2, 251–262. MR 1290241, DOI 10.1016/0377-0427(92)00007-V
Alan Genz, Fully symmetric interpolatory rules for multiple integrals, SIAM J. Numer. Anal. 23 (1986), no. 6, 1273–1283. MR 865956, DOI 10.1137/0723086
Alan Genz and B. D. Keister, Fully symmetric interpolatory rules for multiple integrals over infinite regions with Gaussian weight, J. Comput. Appl. Math. 71 (1996), no. 2, 299–309. MR 1399898, DOI 10.1016/0377-0427(95)00232-4
Thomas Gerstner and Michael Griebel, Numerical integration using sparse grids, Numer. Algorithms 18 (1998), no. 3-4, 209–232. MR 1669959, DOI 10.1023/A:1019129717644
Greg Kuperberg, Numerical cubature using error-correcting codes, SIAM J. Numer. Anal. 44 (2006), no. 3, 897–907. MR 2231848, DOI 10.1137/040615572
James Lu and David L. Darmofal, Higher-dimensional integration with Gaussian weight for applications in probabilistic design, SIAM J. Sci. Comput. 26 (2004), no. 2, 613–624. MR 2116364, DOI 10.1137/S1064827503426863
J. N. Lyness, Symmetric integration rules for hypercubes. I. Error coefficients, Math. Comp. 19 (1965), 260–276. MR 201067, DOI 10.1090/S0025-5718-1965-0201067-3
J. N. Lyness, Limits on the number of function evaluations required by certain high-dimensional integration rules of hypercubic symmetry, Math. Comp. 19 (1965), 638–643. MR 199961, DOI 10.1090/S0025-5718-1965-0199961-5
J. McNamee and F. Stenger, Construction of fully symmetric numerical integration formulas, Numer. Math. 10 (1967), 327–344. MR 219241, DOI 10.1007/BF02162032
H. M. Möller, Lower bounds for the number of nodes in cubature formulae, Numerische Integration (Tagung, Math. Forschungsinst., Oberwolfach, 1978) Internat. Ser. Numer. Math., vol. 45, Birkhäuser, Basel-Boston, Mass., 1979, pp. 221–230. MR 561295
I. P. Mysovskih, On the construction of cubature formulas with the smallest number of nodes, Dokl. Akad. Nauk SSSR 178 (1968), 1252–1254 (Russian). MR 0224284
I. P. Mysovskikh, Interpolyatsionnye kubaturnye formuly, “Nauka”, Moscow, 1981 (Russian). MR 656522
Erich Novak and Klaus Ritter, High-dimensional integration of smooth functions over cubes, Numer. Math. 75 (1996), no. 1, 79–97. MR 1417864, DOI 10.1007/s002110050231
Erich Novak and Klaus Ritter, Simple cubature formulas with high polynomial exactness, Constr. Approx. 15 (1999), no. 4, 499–522. MR 1702807, DOI 10.1007/s003659900119
Erich Novak, Klaus Ritter, Richard Schmitt, and Achim Steinbauer, On an interpolatory method for high-dimensional integration, J. Comput. Appl. Math. 112 (1999), no. 1-2, 215–228. Numerical evaluation of integrals. MR 1728461, DOI 10.1016/S0377-0427(99)00222-8
Knut Petras, Smolyak cubature of given polynomial degree with few nodes for increasing dimension, Numer. Math. 93 (2003), no. 4, 729–753. MR 1961886, DOI 10.1007/s002110200401
Hans Joachim Schmid, Interpolatorische Kubaturformeln, Dissertationes Math. (Rozprawy Mat.) 220 (1983), 122 (German). MR 735919
Smolyak, S. A. (1963): Quadrature and interpolation formulas for tensor products of certain classes of functions. Soviet Math. Dokl. 4, 240-243
A. H. Stroud, Approximate calculation of multiple integrals, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR 0327006
Nicolas Victoir, Asymmetric cubature formulae with few points in high dimension for symmetric measures, SIAM J. Numer. Anal. 42 (2004), no. 1, 209–227. MR 2051063, DOI 10.1137/S0036142902407952