Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions (Q843723): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q346289 |
||
Property / author | |||
Property / author: Henryk Woźniakowski / rank | |||
Revision as of 16:10, 13 February 2024
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
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
tractability
0 references
curse of dimensionality
0 references
rate of convergence
0 references
approximation of smooth functions
0 references