The curse of dimensionality for numerical integration of smooth functions
HTML articles powered by AMS MathViewer
- by A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski PDF
- Math. Comp. 83 (2014), 2853-2863 Request permission
Abstract:
We prove the curse of dimensionality for multivariate integration of $C^r$ functions: The number of needed function values to achieve an error $\epsilon$ is larger than $c_r (1+\gamma )^d$ for $\epsilon \le \epsilon _0$, where $c_r,\gamma >0$. The proofs are based on volume estimates for $r=1$ together with smoothing by convolution. This allows us to obtain smooth fooling functions for $r>1$.References
- Milton Abramowitz and Irene A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR 0167642
- N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275
- Aicke Hinrichs, Erich Novak, and Henryk Woźniakowski, The curse of dimensionality for the class of monotone functions and for the class of convex functions, J. Approx. Theory 163 (2011), no. 8, 955–965. MR 2832759, DOI 10.1016/j.jat.2011.02.009
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Vol. 1: Linear information, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR 2455266, DOI 10.4171/026
- Erich Novak and Henryk Woźniakowski, Approximation of infinitely differentiable multivariate functions is intractable, J. Complexity 25 (2009), no. 4, 398–404. MR 2542039, DOI 10.1016/j.jco.2008.11.002
- Erich Novak and Henryk Woźniakowski, Tractability of multivariate problems. Volume II: Standard information for functionals, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR 2676032, DOI 10.4171/084
- A. G. Suharev, Optimal formulas of numerical integration for some classes of functions of several variables, Dokl. Akad. Nauk SSSR 246 (1979), no. 2, 282–285 (Russian). MR 533623
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
- Jakub Onufry Wojtaszczyk, Multivariate integration in $C^\infty ([0,1]^d)$ is not strongly tractable, J. Complexity 19 (2003), no. 5, 638–643. MR 2003236, DOI 10.1016/S0885-064X(03)00069-4
Additional Information
- A. Hinrichs
- Affiliation: Institut für Mathematik, Universität Rostock, Ulmenstraße 69, 18051 Rostock, Germany
- Email: aicke.hinrichs@uni-rostock.de, a.hinrichs@uni-jena.de
- E. Novak
- Affiliation: Mathematisches Institut, Universität Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany
- Email: erich.novak@uni-jena.de
- M. Ullrich
- Affiliation: Dipartimento di Matematica, Università Roma Tre, Largo San Leonardo Murialdo 1, 00146 Roma, Italy
- MR Author ID: 1042925
- Email: ullrich.mario@gmail.com
- H. Woźniakowski
- Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 – and – Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
- Email: henryk@cs.columbia.edu
- Received by editor(s): November 5, 2012
- Received by editor(s) in revised form: April 16, 2013
- Published electronically: June 20, 2014
- Additional Notes: The first author was partially supported by the DFG-Priority Program 1324.
The third author was supported by DFG GRK 1523 and ERC Advanced Grant PTRELSS
The fourth author was partially supported by the National Science Foundation - © Copyright 2014 American Mathematical Society
- Journal: Math. Comp. 83 (2014), 2853-2863
- MSC (2010): Primary 65D30, 65Y20, 41A63, 41A55
- DOI: https://doi.org/10.1090/S0025-5718-2014-02855-X
- MathSciNet review: 3246812