Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings. (Chinese. English summary) Zbl 1499.46072
Summary: This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes \(B(W^r_p([0,1]^d))\) in the deterministic, randomized and average case settings, and obtains the exact orders of the \(n\)-th minimal error of these problems in all three settings. The results show that in the case of \(B(W^r_p([0,1]^d))\) being not imbedded into the space of continuous functions \(C([0, 1]^d)\), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor \(n^{-1+\varepsilon}\) for any \(\varepsilon>0\), and for integration problem the gain is up to factor \(n^{-1}\) which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.
MSC:
46E35 | Sobolev spaces and other spaces of “smooth” functions, embedding theorems, trace theorems |
41A55 | Approximate quadratures |
65D30 | Numerical integration |
41A25 | Rate of convergence, degree of approximation |
41A63 | Multidimensional problems |