Liberating the dimension (Q708310): Difference between revisions

The authors address the problem of integration over the \(d\)-dimensional unit cube of a function \(f\) of \(d\) variables, \[ I_d(f) = \int_{[0,1]^d} f({\mathbf{x}}) d{\mathbf{x}}. \] It is possible to design an algorithm for which the error is bounded polynomially in \(d\), or independently of \(d\) under suitable conditions on the weighted function space [\textit{I. H. Sloan} and \textit{H. Woźniakowski}, J. Complexity 14, No.~1, 1--33 (1998; Zbl 1032.65011)]. The key challenge which is addressed in this paper is the integration problem with infinitely many variables (\(d\rightarrow \infty\)) and a search for algorithms with small error and minimal cost. As a result, a number of lower and upper estimates of the minimal cost for the product and the finite-order weights is presented. It is demonstrated that in some cases the bounds are sharp. Lower and upper bounds are obtained on the worst case \(\varepsilon\)-complexity (that is, on the minimal cost of all algorithms whose worst case errors are at most \(\varepsilon\)), and conditions for polynomial tractability and weak tractability are provided. Polynomial tractability means that the \(\varepsilon\)-complexity is bounded polynomially in \(\varepsilon^{-1}\); weak tractability means that the \(\varepsilon\)-complexity is not an exponential function of \(\varepsilon^{-1}\). The authors assume that a point evaluation of the integrands is possible only at points with finitely many non-zero components. It is to be noted that an intensive development of the theory of numerical integration has started in the second half of XX century. \textit{S. L. Sobolev} was one of the founders of this modern direction of computational mathematics. His first papers concerning the theory of approximate integration were published at the beginning of the 60s and promoted the use of ideas and methods of functional analysis in the theory of computations. One of the key monographs of \textit{S. L. Sobolev} is `Introduction to the theory of cubature formulas' [Nauka, Moscow, Russian (1974; Zbl 0294.65013)]. An abridged English translation of the book was published in 1992 only as `Cubature formulas and modern analysis: An introduction' [Montreux: Gordon and Breach Science Publishers (1992; Zbl 0784.65016)].