2023/04/20 by Frances Y. Kuo, Dirk Nuyens, Kuo, Frances Y. +3
Mathematics · Engineering · #Mathematical Approximation and Integration #Advanced Numerical Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2304.10413
We show that a very simple randomised algorithm for numerical integration can produce a near optimal rate of convergence for integrals of functions in the d-dimensional weighted Korobov space. This algorithm uses a lattice rule with a fixed generating vector and the only random element is the choice of the number of function evaluations. For a given computational budget n of a maximum allowed number of function evaluations, we uniformly pick a prime p in the range n/2 < p ≤ n. We show error bounds for the randomised error, which is defined as the worst case expected error, of the form O(n-α- 1/2 + δ), with δ> 0, for a Korobov space with smoothness α> 1/2 and general weights. The implied constant in the bound is dimension-independent given the usual conditions on the weights. We present an algorithm that can construct suitable generating vectors offline ahead of time at cost O(d n4 / ln n) when the weight parameters defining the Korobov spaces are so-called product weights. For this case, numerical experiments confirm our theory that the new randomised algorithm achieves the near optimal rate of the randomised error.