Integration and approximation in arbitrary dimensions. (English) Zbl 0939.41004

Multivariate integration and approximation for various classes of functions of \(d\) variables (with arbitrary \(d\)) was studied. Algorithms are considered that use a finite number of function evaluations as the information about the function. As for approximation, arbitrary continuous linear functionals are considered as the information. The problem is studied when integration and approximation are tractable (minimal number of function evaluations needed to reduce the initial error by a factor \(\varepsilon\) is bounded by \(C(d)\varepsilon^{-p}\) for some exponent \(p\) independent of \(d\)) and strongly tractable (\(C(d)\) can be made independent of \(d\)). It was proved that integration is strongly tractable for some Korobov and Sobolev and Hilbert spaces. Bounds for \(\varepsilon\)-exponents in some cases were found. The \(\varepsilon\)-exponents are the same for general and function evaluations.


41A05 Interpolation in approximation theory
41A63 Multidimensional problems
65D05 Numerical interpolation
41A25 Rate of convergence, degree of approximation
Full Text: DOI