Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions (Q843723)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions
scientific article

    Statements

    Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions (English)
    0 references
    0 references
    0 references
    15 January 2010
    0 references
    Let \(f:[0,1]^{d}\to {\mathbb R}\) be a function which are infinitely many times differentiable with respect to all variables and have the property that the sum of all normalized derivatives is bounded in the \(L_{p}\)-norm, for some \(p\in[1,\infty)\). The authors approximate such a function with respect to the Sobolev norm \(W_{p}^{\mathbf m}([0,1]^d)\). Here \({\mathbf m}=[m,m,\dots,m]\), \(d\) times, for some non-negative integer \(m\) and the norm of the target space is 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\geq 1\). This means that the order of convergence supplies incomplete information concerning the computational difficulty of a problem. For \(m=0\) and \(p=2\), the authors prove that the problem is not polynomially tractable, but that it is weakly tractable.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    tractability
    0 references
    curse of dimensionality
    0 references
    rate of convergence
    0 references
    approximation of smooth functions
    0 references
    0 references