|
|||||
|
|
Approximation of infinitely differentiable multivariate functions is intractable |
|
| Authors: | Erich Novak Henryk Wo niakowski |
| Institution: | aMathematisches Institut, Universität Jena, Ernst-Abbe-Platz 2, 07740 Jena, Germany;bDepartment of Computer Science, Columbia University, New York, NY 10027, USA;cInstitute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland |
| Abstract: | We prove that L∞-approximation of C∞-functions defined on 0,1]d is intractable and suffers from the curse of dimensionality. This is done by showing that the minimal number of linear functionals needed to obtain an algorithm with worst case error at most ε (0,1) is exponential in d. This holds despite the fact that the rate of convergence is infinite. |
| Keywords: | Tractability Curse of dimensionality Rate of convergence Approximation of smooth functions |
| 本文献已被 ScienceDirect 等数据库收录！ | |