We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number $N$ of function evaluations used, cannot decrease faster than $O(N^{-1})$ for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence $O(N^{-\alpha})$ for $\alpha>1$ then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.
We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number N of function evaluations used, cannot decrease faster than O(N−1) for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence O(N−α) for α>1 then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.
We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number N of function evaluations used, cannot decrease faster than O(N^{-1}) in the case where several quasi-Monte Carlo rules are combined to a compound quasi-Monte Carlo rule. However, if the errors of the quadrature rules constituting the compound rule have an order of convergence O(N^{-a}) for a > 1 then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. We apply our results to the case of lattice sequences.
This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s , where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.
This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N, where N is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. doi:10.1017/S1446181112000077
Abstract This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s . It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/ N , where N is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets.
Numerical integration in log-Korobov and log-cosine spaces
QMC rules are equal weight quadrature rules for approximating integrals over [0,1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on [0,1]s with square integrable partial mixed derivatives of order α. Using Parseval's identity, this smoothness can be defined for all real numbers α>1/2. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with α arbitrarily close to 1/2. To obtain such estimates we introduce a log-scale for functions with smoothness close to 1/2, which we call log-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order O(N−1/2(logN)−μ(1−λ)/2) for any 1/μ<λ≤1, where μ>1 is a power in the log-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights (γj)j∈N. It is known that if ∑j=1∞γjτ<∞ for some 1/(2α)<τ≤1 one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where τ is close to 1/(2α), namely we show dimension independent error bounds under the condition that ∑j=1∞γjmax{1,logγj−1}μ(1−λ)<∞ for some 1/μ<λ≤1. The essential tool in our analysis is a log-scale Jensen's inequality. The results described above also apply to integration in log-cosine spaces using tent-transformed lattice rules.
High-dimensional integrals arise in a variety of areas, including quantum physics, the physics and chemistry of molecules, statistical mechanics and more recently, in financial applications. In order to approximate multidimensional integrals, one may use Monte Carlo methods in which the quadrature points are generated randomly or quasi-Monte Carlo methods, in which points are generated deterministically. One particular class of quasi-Monte Carlo methods for multivariate integration is represented by lattice rules. Lattice rules constructed throughout this thesis allow good approximations to integrals of functions belonging to certain weighted function spaces. These function spaces were proposed as an explanation as to why integrals in many variables appear to be successfully approximated although the standard theory indicates that the number of quadrature points required for reasonable accuracy would be astronomical because of the large number of variables. The purpose of this thesis is to contribute to theoretical results regarding the construction of lattice rules for multiple integration. We consider both lattice rules for integrals over the unit cube and lattice rules suitable for integrals over Euclidean space. The research reported throughout the thesis is devoted to finding the generating vector required to produce lattice rules that have what is termed a low weighted discrepancy . In simple terms, the discrepancy is a measure of the uniformity of the distribution of the quadrature points or in other settings, a worst-case error. One of the assumptions used in these weighted function spaces is that variables are arranged in the decreasing order of their importance and the assignment of weights in this situation results in so-called product weights . In other applications it is rather the importance of group of variables that matters. This situation is modelled by using function spaces in which the weights are general . In the weighted settings mentioned above, the quality of the lattice rules is assessed by the weighted discrepancy mentioned earlier. Under appropriate conditions on the weights, the lattice rules constructed here produce a convergence rate of the error that ranges from O(n−1/2) to the (believed) optimal O(n−1+δ) for any δ gt 0, with the involved constant independent of the dimension.