Abstract
Quasi-Monte Carlo integration rules, which are equal-weight sample averages of function values, have been popular for approximating multivariate integrals due to their superior convergence rate of order close to 1/N or better, compared to the order \(1/\sqrt{N}\) of simple Monte Carlo algorithms. For practical applications, it is desirable to be able to increase the total number of sampling points N one or several at a time until a desired accuracy is met, while keeping all existing evaluations. We show that although a convergence rate of order close to 1/N can be achieved for all values of N (e.g., by using a good lattice sequence), it is impossible to get better than order 1/N convergence for all values of N by adding equally-weighted sampling points in this manner. We then prove that a convergence of order N − α for α > 1 can be achieved by weighting the sampling points, that is, by using a weighted compound integration rule. We apply our theory to lattice sequences and present some numerical results. The same theory also applies to digital sequences.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abramowitz, M., Stegun, I.A. (eds.): Handbook of Mathematical Functions with Formulas, Graphs and Mathematical Tables. National Bureau of Standards Applied Mathematics Series, vol. 55. U.S. Government Printing Office, Washington, D.C. (1964)
Baldeaux, J., Dick, J., Leobacher, G., Nuyens, D., Pillichshammer, F.: Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules. (2011, submitted)
Boyle, P.P., Lai, T., Tan, K.S.: Pricing options using lattice rules. N. Amer. Actuarial J. 9(3), 50–76 (2005)
Cools, R., Kuo, F.Y., Nuyens, D.: Constructing embedded lattice rules for multivariate integration. SIAM J. Sci. Comput. 28(6), 2162–2188 (2006)
Dick, J.: On the convergence rate of the component-by-component construction of good lattice rules. J. Complex. 20(4), 493–522 (2004)
Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010)
Dick, J., Pillichshammer, F., Waterhouse, B.J.: The construction of good extensible rank-1 lattices. Math. Comput. 77(264), 2345–2374 (2008)
Genz, A.: Numerical computation of multivariate normal probabilities. J. Comput. Graph Stat. 1, 141–149 (1992)
Gill, S.H., Lemieux, C.: Searching for extensible Korobov rules. J. Complex. 23(4–6), 603–613 (2007)
Hammersley, J.M., Handscomb, D.C.: Monte Carlo Methods. Methuen & Co. Ltd., London (1964)
Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge University Press, Cambridge (1934)
Hickernell, F.J.: Lattice rules: how well do they measure up? In: Hellekalek, P., Larcher, G. (eds.) Random and Quasi-Random Point Sets, pp. 109–166. Springer, Berlin (1998)
Hickernell, F.J., Hong, H.S., L’Ecuyer, P., Lemieux, C.: Extensible lattice sequences for quasi-Monte Carlo quadrature. SIAM J. Sci. Comput. 22, 1117–1138 (2001)
Hickernell, F.J., Niederreiter, H.: The existence of good extensible rank-1 lattices. J. Complex. 19(3), 286–300 (2003)
Jensen, J.L.W.V.: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math. 30, 175–193 (1906)
Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley, New York (1974)
Kuo, F.Y.: Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces. J. Complex. 19, 301–320 (2003)
Kuo, F.Y., Sloan, I.H.: Lifting the curse of dimensionality. Not. Am. Math. Soc. 52(11), 1320–1328 (2005)
Niederreiter, H.: Application of diophantine approximations to numerical integration. In: Osgood, C.F. (ed.) Diophantine Approximation and its Applications, pp. 129–199. Academic, New York (1973)
Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, Number 63. SIAM, Philadelphia (1992)
Nuyens, D., Cools, R.: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75(2), 903–920 (2006)
Nuyens, D., Cools, R.: Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points. J. Complex. 22(1), 4–28 (2006)
Nuyens, D., Cools, R.: Higher order quasi-Monte Carlo methods: a comparison. AIP Conference Proceedings 1281, 553–557 (2010)
Sobol′, I.M.: On quasi-Monte Carlo integrations. Math. Comput. Simul. 47(2), 103–112 (1998)
Sidi, A.: A new variable transformation for numerical integration. In: Brass, H., Hämmerlin, G. (eds.) Numerical integration. IV. Proceedings of the Fourth Conference held in Oberwolfach, 8–14 Nov 1992, pp. 359–373. Birkhäuser Verlag, Basel (1993)
Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Clarendon Press, Oxford (1994)
Sloan, I.H., Kuo, F.Y., Joe, S.: Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40(5), 1650–1665 (2002)
Sugihara, M., Murota, K.: A note on Hasselgrove’s method for numerical integration. Math. Comput. 39(160), 549–554 (1982)
Vandewoestyne, B., Cools, R.: On obtaining higher order convergence for smooth periodic functions. J. Complex. 24(3), 328–340 (2008)
Vandewoestyne, B., Cools, R., Warnock, T.: On obtaining quadratic and cubic error convergence using weighted Kronecker-sequences. Comput. 80(1), 75–94 (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hickernell, F.J., Kritzer, P., Kuo, F.Y. et al. Weighted compound integration rules with higher order convergence for all N . Numer Algor 59, 161–183 (2012). https://doi.org/10.1007/s11075-011-9482-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-011-9482-5