Search

It is known from the analysis by Sloan and Woz´niakowski that under appropriate conditions on the weights, the optimal rate of convergence for multivariate integration in weighted Korobov spaces is O(n−α/2+δ) where α>1 is some parameter of the spaces, δ is an arbitrary positive number, and the implied constant in the big O notation depends only on δ, and is independent on the number of variables. Similarly, the optimal rate for weighted Sobolev spaces is O(n−1+δ). However, their work did not show how to construct rules achieving these rates of convergence. The existing theory of the component-by-component constructions developed by Sloan, Kuo and Joe for the Sobolev case yields the rules achieving O(n−1/2) error bounds. Here we present theorems which show that those lattice rules constructed by the component-by-component algorithms in fact achieve the optimal rate of convergence under appropriate conditions on the weights. [Copyright &y& Elsevier]

Shifted rank-1 lattice rules, a special class of quasi-Monte Carlo methods, have recently been proposed by the present authors for the integration of functions belonging to certain "weighted" Sobolev spaces. The shifts in these rules were generated in a deterministic manner. In contrast, in this paper we generate these shifts randomly. This allows probabilistic estimates for the error in a given integral. It also reduces the number of operations required to find the generating vectors for the underlying lattice rules component-by-component. The rules thus constructed achieve a worst-case strong tractability error bound in an average or probabilistic sense. [ABSTRACT FROM AUTHOR]