Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence. (English) Zbl 1312.65002
The authors study the numerical integration of functions depending on an infinite number of variables. Lower error bounds are provided for general deterministic algorithms and matching upper error bounds are given with the help of suitable multilevel algorithms. Two cost models for function evaluations and two classes of weights, namely product and order-dependent weights and the newly introduced finite projective dimension weights are discussed. It is shown that for these classes of weights multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing-dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, the authors discuss the anchored Sobolev space with smoothness parameter and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing-dimension algorithms based on higher-order polynomial lattice rules.
Reviewer: T. C. Mohan (Chennai)
MSC:
| 65C05 | Monte Carlo methods |
| 11K38 | Irregularities of distribution, discrepancy |
| 46E22 | Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) |
Keywords:
path integration; multilevel algorithms; changing-dimension algorithms; quasi-Monte Carlo methods; polynomial lattice rules; reproducing kernel Hilbert spaces; numerical integration; error bound; convergence; numerical exampleReferences:
| [1] | K. Appel, W. Haken, Every planar map is four colorable, I. Discharging, Illinois J. Math. 21 (1977), 429-490. · Zbl 0387.05009 |
| [2] | K. Appel, W. Haken, Every planar map is four colorable, II. Reducibility, Illinois J. Math. 21 (1977), 491-567. · Zbl 0387.05010 |
| [3] | N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337-404. · Zbl 0037.20701 · doi:10.1090/S0002-9947-1950-0051437-7 |
| [4] | J. Baldeaux, Scrambled polynomial lattice rules for infinite-dimensional integration, in: L. Plaskota, H. Woźniakowski (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2010, 255-263, Springer, Heidelberg, 2012. · Zbl 1271.65043 |
| [5] | J. Baldeaux, J. Dick, G. Leobacher, D. Nuyens, F. Pillichshammer, Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules, Numer. Algorithms 59 (2012), 403-431. · Zbl 1244.65002 · doi:10.1007/s11075-011-9497-y |
| [6] | J. Baldeaux, J. Dick, J. Greslehner, F. Pillichshammer, Construction algorithms for higher order polynomial lattice rules, J. Complexity 27 (2011), 281-299. · Zbl 1218.65003 · doi:10.1016/j.jco.2010.06.002 |
| [7] | J. Baldeaux, M. Gnewuch, Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. arXiv:1209.0882v1 [math.NA], Preprint 2012. To appear. In: SIAM J. Numer. Anal. · Zbl 1318.65002 |
| [8] | J. M. Borwein, D. M. Bradley, D. J. Broadhurst, Evaluations of k-fold Euler/Zagier sums: a compendium of results for arbitrary k. The Wilf Festschrift (Philadelphia, PA, 1996), Electron. J. Combin. 4 (1997), no. 2, Research Paper 5, approx. 21 pp. · Zbl 0884.40004 |
| [9] | H.E. Chrestenson, A class of generalized Walsh functions, Pacific J. Math. 5 (1955), 17-31. · Zbl 0065.05302 · doi:10.2140/pjm.1955.5.17 |
| [10] | J. Creutzig, S. Dereich, T. Müller-Gronbach, K. Ritter, Infinite-dimensional quadrature and approximation of distributions, Found. Comput. Math. 9 (2009), 391-429. · Zbl 1177.65011 · doi:10.1007/s10208-008-9029-x |
| [11] | J. Dick, Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. Numer. Anal. 46 (2008), 1519-1553. · Zbl 1189.42012 · doi:10.1137/060666639 |
| [12] | J. Dick, The decay of the Walsh coefficients of smooth functions, Bull. Austral. Math. Soc. 80 (2009), 430-453. · Zbl 1183.42027 · doi:10.1017/S0004972709000392 |
| [13] | J. Dick, M. Gnewuch, Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. J. Approx. Theory (2013, to appear). · Zbl 1296.41025 |
| [14] | J. Dick, F. Y. Kuo, F. Pillichshammer, I. H. Sloan, Construction algorithms for polynomial lattice rules for multivariate integration, Math. Comp. 74 (2005), 1895-1921. · Zbl 1079.65007 · doi:10.1090/S0025-5718-05-01742-4 |
| [15] | J. Dick, F. Pillichshammer, Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, J. Complexity 23 (2007), 436-453. · Zbl 1130.65005 · doi:10.1016/j.jco.2007.02.001 |
| [16] | J. Dick, F. Pillichshammer, Digital nets and sequences. Discrepancy Theory and quasi-Monte Carlo integration, Cambridge University Press, Cambridge, 2010. · Zbl 1282.65012 |
| [17] | J. Dick, I. H. Sloan, X. Wang, H. Woźniakowski, Good lattice rules in weighted Korobov spaces with general weights, Numer. Math. 103 (2006), 63-97. · Zbl 1097.65004 · doi:10.1007/s00211-005-0674-6 |
| [18] | R. Diestel, Graph Theory, Springer Verlag, Berlin, Heidelberg, 3rd Edition, 2005. · Zbl 1074.05001 |
| [19] | N. J. Fine, On the Walsh functions, Trans. Amer. Math. Soc. 65 (1949), 372-414. · Zbl 0036.03604 · doi:10.1090/S0002-9947-1949-0032833-2 |
| [20] | M. B. Giles, Multilevel Monte Carlo path simulation, Oper. Res. 56 (2008), 607-617. · Zbl 1167.65316 · doi:10.1287/opre.1070.0496 |
| [21] | M. B. Giles. Improved multilevel Monte Carlo convergence using the Milstein scheme, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, 343-358, Springer, Berlin, 2008. · Zbl 1141.65321 |
| [22] | M. B. Giles, B. J. Waterhouse, Multilevel quasi-Monte Carlo path simulation, Radon Ser. Comput. Appl. Math. 8 (2009), 165-181. · Zbl 1181.91335 |
| [23] | M. Gnewuch, Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces, J. Complexity 28 (2012), 2-17. · Zbl 1333.11073 · doi:10.1016/j.jco.2011.02.003 |
| [24] | M. Gnewuch, Infinite-dimensional integration on weighted Hilbert spaces, Math. Comp. 81 (2012), 2175-2205. · Zbl 1284.65044 · doi:10.1090/S0025-5718-2012-02583-X |
| [25] | M. Gnewuch. Lower error bounds for randomized multilevel and changing dimension algorithms. In: J. Dick, F. Y. Kuo, G. W. Peters, I. H. Sloan (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2012, 399-415, Springer, Heidelberg, 2013. · Zbl 1302.65006 |
| [26] | M. Gnewuch, S. Mayer, K. Ritter, On weighted Hilbert spaces and integration of functions of infinitely many variables, J. Complexity 30 (2014), 29-47. · Zbl 1286.65039 · doi:10.1016/j.jco.2013.05.004 |
| [27] | M. Gnewuch, H. Woźniakowski, Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information, J. Complexity 23 (2007), 262-295. · Zbl 1118.65001 · doi:10.1016/j.jco.2006.06.006 |
| [28] | M. Griebel, M. Holtz, Dimension-wise integration of high-dimensional functions with applications to finance, J. Complexity 26 (2010), 455-489. · Zbl 1203.65056 · doi:10.1016/j.jco.2010.06.001 |
| [29] | S. Heinrich, Monte Carlo complexity of global solution of integral equations, J. Complexity 14 (1998), 151-175. · Zbl 0920.65090 · doi:10.1006/jcom.1998.0471 |
| [30] | S. Heinrich, E. Sindambiwe. Monte Carlo complexity of parametric integration, J. Complexity 15 (1999), 317-341. · Zbl 0958.68068 · doi:10.1006/jcom.1999.0508 |
| [31] | F. J. Hickernell, T. Müller-Gronbach, B. Niu, K. Ritter, Multi-level Monte Carlo algorithms for infinite-dimensional integration on \[\mathbb{R}^{\mathbb{N}}\] RN, J. Complexity 26 (2010), 229-254. · Zbl 1207.65005 · doi:10.1016/j.jco.2010.02.002 |
| [32] | F. J. Hickernell, X. Wang, The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension, Math. Comp. 71 (2001), 1641-1661. · Zbl 1032.65006 · doi:10.1090/S0025-5718-01-01377-1 |
| [33] | F. Y. Kuo, Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces, J. Complexity 19 (2003), 301-320. · Zbl 1027.41031 · doi:10.1016/S0885-064X(03)00006-2 |
| [34] | F. Y. Kuo, C. Schwab, I. H. Sloan, Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients, SIAM J. Numer. Anal. 50 (2012), 3351-3374. · Zbl 1271.65017 · doi:10.1137/110845537 |
| [35] | F. Y. Kuo, C. Schwab, I. H. Sloan, Multi-level quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients, preprint 2012. · Zbl 1271.65017 |
| [36] | F. Y. Kuo, I. H. Sloan, G. Wasilkowski, H. Woźniakowski, Liberating the dimension, J. Complexity 26 (2010), 422-454. · Zbl 1203.65057 · doi:10.1016/j.jco.2009.12.003 |
| [37] | F. Y. Kuo, I. H. Sloan, G. Wasilkowski, H. Woźniakowski, On decompositions of multivariate functions, Math. Comp. 79 (2010), 953-966. · Zbl 1196.41022 · doi:10.1090/S0025-5718-09-02319-9 |
| [38] | H. Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields, Czechoslovak Math. J. 42 (1992), 143-166. · Zbl 0757.11024 |
| [39] | H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods. No. 63 in CBMS-NSF Series in Applied Mathematics. SIAM, Philadelphia, 1992. · Zbl 0761.65002 |
| [40] | B. Niu, F. J. Hickernell, Monte Carlo simulation of stochastic integrals when the cost of function evaluations is dimension dependent, in: P. L’Ecuyer, A. B. Owen (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2008, 545-560, Springer, Heidelberg, 2009. · Zbl 1182.91205 |
| [41] | B. Niu, F. J. Hickernell, T. Müller-Gronbach, K. Ritter, Deterministic multi-level algorithms for infinite-dimensional integration on \[\mathbb{R}^nRn\], J. Complexity 27 (2011), 331-351. · Zbl 1218.65005 · doi:10.1016/j.jco.2010.08.001 |
| [42] | E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I, European Mathematical Society, Zürich, 2008. · Zbl 1156.65001 |
| [43] | E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume II, European Mathematical Society, Zürich, 2010. · Zbl 1241.65025 |
| [44] | L. Plaskota, G. W. Wasilkowski, Tractability of infinite-dimensional integration in the worst case and randomized settings, J. Complexity 27 (2011), 505-518. · Zbl 1230.65037 · doi:10.1016/j.jco.2011.01.006 |
| [45] | I. H. Sloan, X. Wang, H. Woźniakowski, Finite-order weights imply tractability of multivariate integration, J. Complexity 20 (2004), 46-74. · Zbl 1067.65006 · doi:10.1016/j.jco.2003.11.003 |
| [46] | I. H. Sloan, H. Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), 1-33. · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463 |
| [47] | V. N. Temlyakov, Cubature formulas, discrepancy, and nonlinear approximation. Numerical integration and its complexity (Oberwolfach, 2001). J. Complexity 19 (2003), 352-391. · Zbl 1031.41016 · doi:10.1016/S0885-064X(02)00025-0 |
| [48] | J. F. Traub, G. W. Wasilkowski, H. Woźniakowski, Information-Based Complexity, Academic Press, New York, 1988. · Zbl 0654.94004 |
| [49] | J.L. Walsh, A closed set of normal orthogonal functions, Amer. J. Math. 55 (1923), 5-24. · JFM 49.0293.03 · doi:10.2307/2387224 |
| [50] | G. W. Wasilkowski, Liberating the dimension for \[L_2\] L2-approximation, J. Complexity 28 (2012), 304-319. · Zbl 1247.65013 · doi:10.1016/j.jco.2011.12.002 |
| [51] | G. W. Wasilkowski, H. Woźniakowski, On tractability of path integration, J. Math. Physics 37 (1996), 2071-2088. · Zbl 0863.65006 · doi:10.1063/1.531493 |
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.
