This short article studies a deterministic quasi-Monte Carlo lattice rule in weighted unanchored Sobolev spaces of smoothness 1 . Building on the error analysis by Kazashi and Sloan, we prove the existence of unshifted rank-1 lattice rules that achieve a worst-case error of O ( n − 1 / 4 ( log n ) 1 / 2 ) , with the implied constant independent of the dimension, under certain summability conditions on the weights. Although this convergence rate is inferior to the one achievable for the shifted-averaged root mean squared worst-case error, the result does not rely on random shifting or transformation and holds unconditionally without any conjecture, in contrast to the result of Kazashi and Sloan.
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.
We develop and justify an algorithm for the construction of quasi–Monte Carlo (QMC) rules for integration in weighted Sobolev spaces; the rules so constructed are shifted rank-1 lattice rules. The parameters characterising the shifted lattice rule are found “component-by-component”: the ( d + 1 d+1 )-th component of the generator vector and the shift are obtained by successive 1 1 -dimensional searches, with the previous d d components kept unchanged. The rules constructed in this way are shown to achieve a strong tractability error bound in weighted Sobolev spaces. A search for n n -point rules with n n prime and all dimensions 1 to d d requires a total cost of O ( n 3 d 2 ) O(n^3d^2) operations. This may be reduced to O ( n 3 d ) O(n^3d) operations at the expense of O ( n 2 ) O(n^2) storage. Numerical values of parameters and worst-case errors are given for dimensions up to 40 and n n up to a few thousand. The worst-case errors for these rules are found to be much smaller than the theoretical bounds.
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L ∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1 / 2 < α ≤ 1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α > 1 / 2 . Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L 2 error, while retaining the same tractability property.
In the present paper we study quasi-Monte Carlo rules for approximating integrals over the
d-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number
n of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.
We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness
α≥2 defined over the
s-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over
Fb with
α consecutive sizes of nodes,
bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of
α approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order
(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order
sαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
We study quasi-Monte Carlo (QMC) integration of smooth functions defined over the multidimensional unit cube. Inspired by a recent work of Pan and Owen, we study a new construction-free median QMC rule which can exploit the smoothness and the weights of function spaces adaptively. For weighted Korobov spaces, we draw a sample of
r independent generating vectors of rank-1 lattice rules, compute the integral estimate for each, and approximate the true integral by the median of these
r estimates. For weighted Sobolev spaces, we use the same approach but with the rank-1 lattice rules replaced by high-order polynomial lattice rules. A major advantage over the existing approaches is that we do not need to construct good generating vectors by a computer search algorithm, while our median QMC rule achieves almost the optimal worst-case error rate for the respective function space with any smoothness and weights, with a probability that converges to 1 exponentially fast as
r increases. Numerical experiments illustrate and support our theoretical findings.