Peter Kritzer, Frances Y. Kuo, Dirk Nuyens, Mario Ullrich,
"Lattice rules with random n achieve nearly the optimal {\cal O} (n - \alpha - 1/2 ) error independently of the dimension"
, in Journal of Approximation Theory, 2019
Original Titel:
Lattice rules with random n achieve nearly the optimal {\cal O} (n - \alpha - 1/2 ) error independently of the dimension
Sprache des Titels:
Englisch
Original Kurzfassung:
We analyze a random algorithm for numerical integration of d-variate functions from weighted
Sobolev spaces with dominating mixed smoothness ? ? 0 and product weights 1 ? ?1 ? ?2 ? ... > 0. The algorithm is based on rank-1 lattice
rules with a random number of points n. For the case ? > 1/2, we prove that the algorithm achieves almost the optimal order of convergence
of O(n???1/2), where the implied constant is independent of d if the weights satisfy sum j=1 ? ?j 1/? < ?.
The same rate of convergence holds for the more general case ? > 0 by adding a random shift to the lattice rule with random n. This shows,
in particular, that the exponent of strong tractability in the randomized setting equals 1/(?+1/2), if the weights decay fast enough.
We obtain a lower bound to indicate that our results are essentially optimal.
Forschungs-