Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

The curse of dimensionality for numerical integration of smooth functions


Authors: A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski
Journal: Math. Comp. 83 (2014), 2853-2863
MSC (2010): Primary 65D30, 65Y20, 41A63, 41A55
Published electronically: June 20, 2014
MathSciNet review: 3246812
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D30, 65Y20, 41A63, 41A55

Retrieve articles in all journals with MSC (2010): 65D30, 65Y20, 41A63, 41A55


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
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

DOI: https://doi.org/10.1090/S0025-5718-2014-02855-X
Keywords: Curse of dimensionality, numerical integration, high dimensional numerical problems
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
Article copyright: © Copyright 2014 American Mathematical Society