On the power of standard information for multivariate approximation in the worst case setting Original Research Article

We study multivariate approximation with the error measured in L∞L∞ and weighted L2L2 norms. We consider the worst case setting for a general reproducing kernel Hilbert space of functions of dd variables with a bounded or integrable kernel. Here dd can be arbitrarily large. We analyze algorithms that use standard information consisting of nn function values, and we are especially interested in the optimal order of convergence, i.e., in the maximal exponent bb for which the worst case error of such an algorithm is of order n−bn−b. We prove that b∈[2p2/(2p+1),p]b∈[2p2/(2p+1),p] for weighted L2L2 approximation and b∈[2p(p−1/2)/(2p+1),p−1/2]b∈[2p(p−1/2)/(2p+1),p−1/2] for L∞L∞ approximation, where pp is the optimal order of convergence for weighted L2L2 approximation among all algorithms that may use arbitrary linear functionals, as opposed to function values only. Under a mild assumption on the reproducing kernels we have p>1/2p>1/2. It was shown in our previous paper that the optimal order for L∞L∞ approximation and linear information is p−1/2p−1/2. We do not know if our bounds are sharp for standard information. We also study tractability of multivariate approximation, i.e., we analyze when the worst case error bounds depend at most polynomially on dd and n−1n−1. We present necessary and sufficient conditions on tractability and illustrate our results for the weighted Korobov spaces with arbitrary smoothness and for the weighted Sobolev spaces with the Wiener sheet kernel. Tractability conditions for these spaces are given in terms of the weights defining these spaces.