Treffer: Complexity of deterministic and randomized methods for multivariate integration problems for the class HpΛ(Id): Complexity of deterministic and randomized methods for multivariate integration problems for the class \(H_p^\Lambda(I^d)\)

The authors consider the problem of multi-dimensional integration in a randomized setting and investigate the computational complexity of this problem. The computational complexity of such a problem is roughly defined as the smallest number of integrand evaluations needed to compute an approximation of the integral, with the error at most \(\epsilon\). Based on \(p\)-th Lebesgue spaces \(L_p(I^d)\), \(1 \geq p \geq \infty, I^d = [0, 1]^d\), isotropic (classical) Sobolev classes of functions are introduced. What is already known is that the isotropic Sobolev classes are suitable for the average case and randomized setting. The problem arising within this paper is to find some classes of functions on which the error bounds of the integration problem, in the average case or randomized setting, to be significantly improved in comparison to the error bounds in the worst case setting. The authors introduce a new class of multivariate functions, called the generalized Hölder-Nikolskii class, as subclasses that are also continuously embedded in the newly generalized Hölder-Nikolskii class. The main results of the paper consist in proving that, for \(p > 1\), the \(\epsilon\)-complexity of the multi-dimensional integration problem in the randomized setting as well as in the average case setting is significantly smaller than that in the worst case deterministic setting. More precisely, in the randomized setting, the lower estimate of the integration error for the generalized Hölder-Nikolskii new class can be reduced to the generalized Sobolev class, while the upper estimate is reduced to the anisotropic Hölder-Nikolskii class. The estimates of the average error setting are outlined using similar arguments as those for the randomized setting.