## Weighted compound integration rules with higher order convergence for all $$N$$.(English)Zbl 1240.65002

The subject of this paper is an improvement of the quasi-Monte-Carlo (QMC) integration rule $$Q_{qmc}(f)=\frac{1}{N}\sum_{k=0}^{N-1}f(x_k)$$ used for approximating a multivariate integral $$\int_{[0,1]^s}f(x)dx$$. It is known that its convergence is close to order $$1/N$$ (better than the convergence $$1/\sqrt{N}$$ assured by simple Monte-Carlo algorithms). The authors prove two important results:
(1) If the $$QMC$$ rule uses $$N$$ sampling points from an infinite sequence $$x_0,x_1,\dots$$, then the best convergence possible is $$1/N$$.
(2) If the points are selected with different weights, then it is possible to improve the performance of the $$QMC$$ rule.
The next result is proved and verified by examples: If the $$N$$ sampling points are partitioned into $$M$$ sets with $$N=\sum_{i=1}^MN_i$$, and for each set of size $$N_i$$ an integration rule $$Q_i$$ is used with a $${\mathcal O}(N_i^{-\alpha})$$ convergence rate $$(\alpha >1)$$, then the integration rule $$Q(f)=\sum_{i=1}^Mw_iQ_i(f)$$, where the weights $$w_i=N_i^a/(N_1^a+\dots+N_M^a)$$ are defined for $$a\geq \alpha$$ assures a $${\mathcal O}(N^{-\alpha})$$ convergence rate for all the values of $$N$$.
As a remark, this paper improves old results presented by H. Niederreiter [Diophantine Approx. Appl., Proc. Conf. Washington 1972, 129–199 (1973; Zbl 0268.65014)] and is a completion of similar current research [see for example J. Baldeaux, J. Dick, G. Leobacher, D. Nuyens and F. Pillichshammer, “Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules”, arXiv:1105.2599]).

### MSC:

 65C05 Monte Carlo methods 11H06 Lattices and convex bodies (number-theoretic aspects) 11K45 Pseudo-random numbers; Monte Carlo methods 26B15 Integration of real functions of several variables: length, area, volume

Zbl 0268.65014

QSIMVN
Full Text:

### 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) · Zbl 0171.38503  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) · Zbl 1244.65002  Boyle, P.P., Lai, T., Tan, K.S.: Pricing options using lattice rules. N. Amer. Actuarial J. 9(3), 50–76 (2005) · Zbl 1141.91419  Cools, R., Kuo, F.Y., Nuyens, D.: Constructing embedded lattice rules for multivariate integration. SIAM J. Sci. Comput. 28(6), 2162–2188 (2006) · Zbl 1126.65002  Dick, J.: On the convergence rate of the component-by-component construction of good lattice rules. J. Complex. 20(4), 493–522 (2004) · Zbl 1344.65034  Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010) · Zbl 1282.65012  Dick, J., Pillichshammer, F., Waterhouse, B.J.: The construction of good extensible rank-1 lattices. Math. Comput. 77(264), 2345–2374 (2008) · Zbl 1211.11092  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) · Zbl 1178.11053  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) · Zbl 0920.65010  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) · Zbl 0974.65004  Hickernell, F.J., Niederreiter, H.: The existence of good extensible rank-1 lattices. J. Complex. 19(3), 286–300 (2003) · Zbl 1029.65004  Jensen, J.L.W.V.: Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Math. 30, 175–193 (1906) · JFM 37.0422.02  Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley, New York (1974) · Zbl 0281.10001  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) · Zbl 1027.41031  Kuo, F.Y., Sloan, I.H.: Lifting the curse of dimensionality. Not. Am. Math. Soc. 52(11), 1320–1328 (2005) · Zbl 1080.65020  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) · Zbl 0268.65014  Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, Number 63. SIAM, Philadelphia (1992) · Zbl 0761.65002  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) · Zbl 1094.65004  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) · Zbl 1092.65002  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) · Zbl 0855.65013  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) · Zbl 1037.65005  Sugihara, M., Murota, K.: A note on Hasselgrove’s method for numerical integration. Math. Comput. 39(160), 549–554 (1982) · Zbl 0502.65009  Vandewoestyne, B., Cools, R.: On obtaining higher order convergence for smooth periodic functions. J. Complex. 24(3), 328–340 (2008) · Zbl 1151.65019  Vandewoestyne, B., Cools, R., Warnock, T.: On obtaining quadratic and cubic error convergence using weighted Kronecker-sequences. Comput. 80(1), 75–94 (2007) · Zbl 1117.65007
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.