Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.
Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.
This paper discusses φ -weighted integration of functions over the s -dimensional Euclidean space using quasi-Monte Carlo (QMC) rules combined with an inversion method, where the probability density function (PDF) φ is of product form, i.e., a product of uni-variate PDFs φ i for each coordinate i in { 1 , … , s } . The space of integrands is specified by means of a γ -weighted p -norm, p ≥ 1 , which involves coordinate weights γ , the partial derivatives of order up to one of the integrands as well as additional weight functions ψ i and the PDFs φ i . The coordinate weights γ model the importance of different coordinates or groups of coordinates in the sense of Sloan and Woźniakowski, and the weight functions ψ i are additional parameters of the space which describe the decay of the partial derivatives of the integrands. Fast decaying weights ψ i ( x ) for x → ± ∞ enlarge the space of functions with finite norm, but decrease the convergence rate of the worst-case error of the proposed algorithms. Our algorithms for integration use digitally shifted digital nets in combination with an inversion method. We study the (root) mean squared worst-case error with respect to random digital shifts. The obtained error bounds depend on the choice of weight functions ψ i and coordinate weights γ . Under certain conditions on γ , these bounds hold uniformly for all dimensions s . Numerical experiments demonstrate the effectiveness of the proposed algorithms.
A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/2
In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n−α−1/2+ε), ε>0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness α>1/2. Compared to the optimal deterministic rate of O(n−α+ε), ε>0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0<α≤1/2. Also here we obtain the near optimal convergence of O(n−α−1/2+ε), ε>0; or in more detail, we obtain O(rn−α−1/2+1/(2r)+ε′) which holds for any choices of ε′>0 and r∈N with r>1/(2α).
Recent advances in quasi-Monte Carlo integration demonstrate that the median of linearly scrambled digital net estimators achieves near-optimal convergence rates for high-dimensional integrals without requiring a priori knowledge of the integrand’s smoothness. Building on this framework, we prove that the median estimator attains dimension-independent convergence, a property known as strong tractability in complexity theory, under tractability conditions characterized by low effective dimensionality. Using a probabilistic, integrand-specific error criterion, our analysis establishes both faster and dimension-independent convergence under weaker assumptions than previously possible in the worst-case setting.