Optimal Order of Convergence and (In)Tractability of Multivariate Approximation of Smooth Functions

摘要

We study the approximation problem for C∞ functions f : [0, 1]d →R with respect to a Wm p -norm. Here, m = [m,m,. . . ,m], d times, with the norm of the target space defined in terms of up to m partial derivatives with respect to all d variables. The optimal order of convergence is infinite, hence excellent, but the problem is still intractable and suffers from the curse of dimensionality if m ≥ 1. This means that the order of convergence supplies incomplete information concerning the computational difficulty of a problem. For m = 0 and p = 2, we prove that the problem is not polynomially tractable, but that it is weakly tractable.