×

Efficient cubature rules. (English) Zbl 1431.65021

Summary: 67 new cubature rules are found for three standard multi-dimensional integrals with spherically symmetric regions and weight functions using direct search with a numerical zero-finder. 63 of the new rules have fewer integration points than known rules of the same degree, and 20 are within three points of Möller’s lower bound. Most have all positive coefficients, and most have some symmetry, including some supported by one or two concentric spheres. They include degree-7 formulas for the integration over the sphere and Gaussian-weighted integrals over the entire space, each in 6 and 7 dimensions, with 127 and 183 points, respectively.

MSC:

65D32 Numerical quadrature and cubature formulas
65D30 Numerical integration
41A55 Approximate quadratures
41A63 Multidimensional problems

Software:

HRMSYM; Maxima; PATSYM; Matlab
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] N. ADURTHI, P. SINGLA,ANDT. SINGH, The conjugate unscented transform—an approach to evaluate multi-dimensional expectation integrals, in Proc. 2012 American Control Conference (ACC), IEEE Conference Proceedings, Los Alamitos, 2012, pp. 5556-5561.
[2] I. ARASARATNAM ANDS. HAYKIN, Cubature Kalman filters, IEEE Trans. Automat. Control, 54 (2009), pp. 1254-1269. · Zbl 1367.93637
[3] T. BECKER, Konstruktion von interpolatorischen Kubaturformeln mit Anwendungen in der Finit-ElementMethode, PhD. Thesis, Technische Hochschule Darmstadt, Darmstadt, 1987.
[4] J. BOOHER, Continued fractions, Pell’s equation, and transcendental numbers, Preprint, University of Arizona, August 2011. http://math.arizona.edu/ jeremybooher/expos/continued_fractions.pdf ETNA Kent State University and Johann Radon Institute (RICAM) EFFICIENT CUBATURE RULES237 TABLE10.2 21 new cubature rules forEnr. New RuleSmallest Previous Rule NM LB nNd Shells Quality SymmetryNdSource 2116Pbilateral10127[40, VI] 2178Pbilateral15199[17] 3114Pbilateral10135[40, VII] 3236Pnone20277[39, Enr:7-1] 4164 1+10+5P4-simplex15245[39, Enr:5-2] 4164 1+6+9Px1, x315245[39, Enr:5-2] 42351+22Pvertex21245[39, Enr:5-2] 4456Pnone35497[39, Enr:7-1] 41038Nnone70none 41549Nnone91none 5224 1+6+15P5-simplex21425[39, Enr:5-2] 5806Pnone56837[39, Enr:7-1] 52308Nnone126none 62841+27Pvertex28575[30] 6445 12+32Pcentral43575[30] 7464Pnone36995[39, Enr:5-1] 72236Pnone1202277[39, Enr:7-1] 8594Pnone451295[39, Enr:5-1] 9784Pnone551635[39, Enr:5-1] 101074Pnone662015[39, Enr:5-1] 111334Pnone782435[39, Enr:5-1]
[5] A. CAYLEY, On the motion of rotation of a solid body, Cambridge Math. J., 3 (1843), pp. 224-232. Also: The Collected Mathematical Papers, Vol I., pp. 28-35, Cambridge Univ. Press, Cambridge, 1889.
[6] T. F. COLEMAN ANDY. LI, A reflective Newton method for minimizing a quadratic function subject to bounds on some of the variables, SIAM J. Optim., 6 (1996), pp. 1040-1058. · Zbl 0861.65053
[7] R. COOLS, Monomial cubature rules since “Stroud”: a compilation. II, J. Comput. Appl. Math., 112 (1999), pp. 21-27. · Zbl 0954.65021
[8] , Advances in multidimensional integration, J. Comput. Appl. Math., 149 (2002), pp. 1-12. · Zbl 1013.65019
[9] , An encyclopaedia of cubature formulas, J. Complexity, 19 (2003), pp. 445-453. · Zbl 1061.41020
[10] R. COOLS ANDP. RABINOWITZ, Monomial cubature rules since “Stroud”: a compilation, J. Comput. Appl. Math., 48 (1993), pp. 309-326. · Zbl 0799.65027
[11] M. EVANS ANDT. SWARTZ, Some integration strategies for problems in statistical inference, in Proceedings of the 24th Symposium on the Interface, H. J. Newton, ed., Computing Science and Statististics Vol. 24., Interface Foundation of North America, Fairfax Station, 1992, pp. 310-317.
[12] C. FAN ANDZ. YOU, Highly efficient sigma point filter for spacecraft attitude and rate estimation, Math. Probl. Eng., 2009 (2009), Article ID 507370, 23 pages. · Zbl 1185.93132
[13] G. B. FOLLAND, How to integrate a polynomial over a sphere, Amer. Math. Monthly, 108 (2001), pp. 446-448. · Zbl 1046.26503
[14] A. GENZ ANDB. D. KEISTER, Fully symmetric interpolatory rules for multiple integrals over infinite regions with Gaussian weight, J. Comput. Appl. Math., 71 (1996), pp. 299-309. · Zbl 0856.65011
[15] P. E. GILL, W. MURRAY,ANDM. H. WRIGHT, Practical Optimization, Academic Press, London, 1981. · Zbl 0503.90062
[16] A. HAEGEMANS ANDR. PIESSENS, Construction of cubature formulas of degree eleven for symmetric planar regions, using orthogonal polynomials, Numer. Math., 25 (1975/76), pp. 139-148. · Zbl 0319.65020
[17] , Construction of cubature formulas of degree seven and nine symmetric planar regions, using orthogonal polynomials, SIAM J. Numer. Anal., 14 (1977), pp. 492-508. · Zbl 0365.65015
[18] K. L. G. HEYDE, The Nuclear Shell Model, Springer, Berlin, 1990.
[19] N. ISGUR ANDG. KARL, p-wave baryons in the quark model, Phys. Rev. D, 18 (1978), pp. 4187-4205.
[20] T. JANKEWITZ, Personal communication to R. Cools, Aug. 1998. http://nines.cs.kuleuven.be/research/ecf/mtables.html, ETNA Kent State University and Johann Radon Institute (RICAM) 238J. R. VAN ZANDT TABLE10.3 21 new cubature rules forSn. A * indicates that a rule with fewer points was known. New RuleSmallest Previous Rule NM LB nNdShells QualitySymmetryNdSource 217∗8PObilateral15168[43] 22310PObilateral212511[16] 3104POx2, x310114[3] 3226PObilateral20277[39, Sn:7-1] 3428POnone35458[10] 416∗41+10+5NO4-simplex15164[7,32] 41540+6+9PBx1, x315164[7,32] 423∗51+22PIvertex21225[39, Sn:5-1] 4436NObilateral35497[39, Sn:7-1] 41058NOnone701939[39, Sn:9-1] 41479NOnone911939[39, Sn:9-1] 420810NObilateral12641711[39, Sn:11-1] 52241+6+15PI5-simplex21325[39, Sn:5-1] 5806NOnone56837[39, Sn:7-1] 52208NOnone1264219[39, Sn:9-1] 62841+27PIvertex28445[39, Sn:5-1] 612771+54+72 PBcentral1241377[39, Sn:7-1] 7384 1+8+8+21 NOsee text36575[39, Sn:5-1] 71837 1+56+126 PIcentral1822277[39, Sn:7-1] 9784NOnone551635[39, Sn:5-2] 10964NOnone662015[39, Sn:5-2] 111234NOnone782435[39, Sn:5-2]
[21] B. JIA, M. XIN,ANDY. CHENG, Sparse Gauss-Hermite quadrature filter with application to spacecraft attitude estimation, J. Guidance Control Dynam., 34 (2011), pp. 367-379.
[22] R. JONKER ANDA. VOLGENANT, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, 38 (1987), pp. 325-340. · Zbl 0607.90056
[23] S. J. JULIER, The spherical simplex unscented transformation, Proc. 2003 American Control Conference ACC 2003, IEEE Conference Proceedings, Los Alamitos, 2003, pp. 2430-2434.
[24] J. LI ANDJ. S. RACINE, Maxima: An open source computer algebra system, J. Appl. Econ., 23 (2008), pp. 515-523.
[25] J. LU ANDD. L. DARMOFAL, Higher-dimensional integration with Gaussian weight for applications in probabilistic design, SIAM J. Sci. Comput., 26 (2004), pp. 613-624. · Zbl 1075.65014
[26] J. N. LYNESS, Limits on the number of function evaluations required by certain high-dimensional integration rules of hypercubic symmetry, Math. Comp., 19 (1965), pp. 638-643. · Zbl 0142.12302
[27] J. N. LYNESS ANDD. JESPERSEN, Moderate degree symmetric quadrature rules for the triangle, J. Inst. Math. Appl., 15 (1975), pp. 19-32. · Zbl 0297.65018
[28] D. B. MALKOFF, Evaluation of the Jonker-Volgenant-Castanon (jvc) assignment algorithm for track association, in Signal Processing, Sensor Fusion, and Target Recognition VI, I. Kadar, ed., SPIE Proceedings Vol. 3068, SPIE, Bellingham, 1997, doi: 10.1117/12.280801, 12 pages.
[29] THEMATHWORKS, Matlab optimization toolbox, 2008.
[30] Z. MENG ANDZ. LUO, Constructing cubature formulae of degree 5 with few points, J. Comput. Appl. Math., 237 (2013), pp. 354-362. · Zbl 1250.41017
[31] H. M. MÖLLER, Lower bounds for the number of nodes in cubature formulae, in Numerische Integration, G. Hämmerlin, ed., Internat Ser. Numer. Math. 45, Birkhäuser, Basel, 1979, pp. 221-230. · Zbl 0416.65019
[32] J. MYSOVSKIH, Interpolatorische Kubaturformeln, Tech. Report 74, RWTH Aachen, Aachen 1992.
[33] P. O. OFFENHARTZ, Atomic and Molecular Orbital Theory, McGraw-Hill, New York, 1970.
[34] J. P. SIMONIS, Inexact Newton Methods Applied to Under-Determined Systems, PhD. Thesis, Worcester Polytechnic Institute, Worcester, May 2006. ETNA Kent State University and Johann Radon Institute (RICAM) EFFICIENT CUBATURE RULES239 TABLE10.4 Approximate values ofJ4in(10.1). nNdJ4EstimatesErrorSource 41543.4818127309-0.0005195508Table4.4 41643.4511488638-0.0311834178Table4.3 41643.48289282590.0005605442[7,32] 42253.4403244866-0.0420077951[37],[39, Sn:5-1] 42353.48386222520.0015299435Table5.1 43153.48271862400.0003863423[30] 44363.48235471830.0000224367Table10.3 44973.4823164472-0.0000158345[38],[39, Sn:7-1] 410583.4823287423-0.0000035394Table10.3 414793.4823311982-0.0000010835Table10.3 4208103.4823322804-0.0000000012Table10.3
[35] A. H. STROUD, Quadrature methods for functions of more than one variable, Ann. New York Acad. Sci., 86 (1960), pp. 776-791. · Zbl 0102.33703
[36] , Some fifth degree integration formulas for symmetric regions, Math. Comp., 20 (1966), pp. 90-97. · Zbl 0137.33704
[37] , Some fifth degree integration formulas for symmetric regions. II, Numer. Math., 9 (1967), pp. 460-468. · Zbl 0149.37202
[38] , Some seventh degree integration formulas for symmetric regions, SIAM J. Numer. Anal., 4 (1967), pp. 37-44. · Zbl 0149.37203
[39] , Approximate Calculation of Multiple Integrals, Prentice-Hall, Englewood Cliffs, 1971. · Zbl 0379.65013
[40] A. H. STROUD ANDD. SECREST, Approximate integration formulas for certain spherically symmetric regions, Math. Comp., 17 (1963), pp. 105-135. · Zbl 0112.35302
[41] V. TOTH, Tensor manipulation in GPL Maxima, Preprint on arXiv, March 2005. https://arxiv.org/abs/cs/0503073
[42] L. WAN-CHUN, W. PING,ANDX. XIAN-CI, A novel simplex unscented transform and filter, in 2007 International Symposium on Communications and Information Technologies, IEEE Conference Proceedings, Los Alamitos, 2007, pp. 926-931.
[43] J. W. WISSMANN ANDT. BECKER, Partially symmetric cubature formulas for even degrees of exactness, SIAM J. Numer. Anal., 23 (1986), pp. 676-685. · Zbl 0589.41024
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.