×

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

Citations:

Zbl 0268.65014

Software:

QSIMVN
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 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
[2] 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
[3] 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
[4] 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
[5] 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
[6] Dick, J., Pillichshammer, F.: Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010) · Zbl 1282.65012
[7] 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
[8] Genz, A.: Numerical computation of multivariate normal probabilities. J. Comput. Graph Stat. 1, 141–149 (1992)
[9] Gill, S.H., Lemieux, C.: Searching for extensible Korobov rules. J. Complex. 23(4–6), 603–613 (2007) · Zbl 1178.11053
[10] Hammersley, J.M., Handscomb, D.C.: Monte Carlo Methods. Methuen & Co. Ltd., London (1964)
[11] Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge University Press, Cambridge (1934)
[12] 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
[13] 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
[14] Hickernell, F.J., Niederreiter, H.: The existence of good extensible rank-1 lattices. J. Complex. 19(3), 286–300 (2003) · Zbl 1029.65004
[15] 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
[16] Kuipers, L., Niederreiter, H.: Uniform Distribution of Sequences. Wiley, New York (1974) · Zbl 0281.10001
[17] 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
[18] Kuo, F.Y., Sloan, I.H.: Lifting the curse of dimensionality. Not. Am. Math. Soc. 52(11), 1320–1328 (2005) · Zbl 1080.65020
[19] 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
[20] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. Regional Conference Series in Applied Mathematics, Number 63. SIAM, Philadelphia (1992) · Zbl 0761.65002
[21] 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
[22] 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
[23] Nuyens, D., Cools, R.: Higher order quasi-Monte Carlo methods: a comparison. AIP Conference Proceedings 1281, 553–557 (2010)
[24] Sobol’, I.M.: On quasi-Monte Carlo integrations. Math. Comput. Simul. 47(2), 103–112 (1998)
[25] 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)
[26] Sloan, I.H., Joe, S.: Lattice Methods for Multiple Integration. Clarendon Press, Oxford (1994) · Zbl 0855.65013
[27] 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
[28] Sugihara, M., Murota, K.: A note on Hasselgrove’s method for numerical integration. Math. Comput. 39(160), 549–554 (1982) · Zbl 0502.65009
[29] Vandewoestyne, B., Cools, R.: On obtaining higher order convergence for smooth periodic functions. J. Complex. 24(3), 328–340 (2008) · Zbl 1151.65019
[30] 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.