Product rules are optimal for numerical integration in classical smoothness spaces

DOI10.1016/J.JCO.2016.09.001zbMATH Open1354.65043arXiv1604.00261OpenAlexW3102262919MaRDI QIDQ346296FDOQ346296

Aicke Hinrichs, Mario Ullrich, H. Woźniakowski, Erich Novak

Publication date: 5 December 2016

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: We mainly study numerical integration of real valued functions defined on the $d$-dimensional unit cube with all partial derivatives up to some finite order $rge1$ bounded by one. It is well known that optimal algorithms that use $n$ function values achieve the error rate $n^{-r/d}$, where the hidden constant depends on $r$ and $d$. Here we prove explicit error bounds without hidden constants and, in particular, show that the optimal order of the error is $$, where now the hidden constant only depends on $r$, not on $d$. For $n=m^d$, this optimal order can be achieved by (tensor) product rules. We also provide lower bounds for integration defined over an arbitrary open domain of volume one. We briefly discuss how lower bounds for integration may be applied for other problems such as multivariate approximation and optimization.

Full work available at URL: https://arxiv.org/abs/1604.00261

Recommendations

• Cubature formulas for function spaces with moderate smoothness
• An application of tensor products of functionals in problems of numerical integration
• Optimal numerical integration on classes of smooth functions in several variables
• High dimensional integration of smooth functions over cubes
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands

zbMATH Keywords

optimizationerror boundintegrationmultivariate approximationoptimal error boundsproduct rules

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) Multidimensional problems (41A63) Approximate quadratures (41A55)

Cites Work

• Deterministic and stochastic error bounds in numerical analysis
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• On the optimality of linear methods for operator approximation in convex classes of functions
• Gaussian quadrature formulae -- second Peano kernels, nodes, weights and Bessel functions
• Some nonlinear problems are as easy as the approximation problem
• On the approximate calculation of multiple integrals
• The curse of dimensionality for numerical integration of smooth functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• ON THE BEST QUADRATURE FORMULA OF THE FORM $ \sum_{k=1}^np_kf(x_k)$ FOR SOME CLASSES OF DIFFERENTIABLE PERIODIC FUNCTIONS
• Title not available (Why is that?)
• Numerical Evaluation of Multiple Integrals

Cited In (13)

• Algorithms and complexity for functions on general domains
• Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods
• Uniform recovery of high-dimensional \(C^r\)-functions
• Approximation methods for piecewise deterministic Markov processes and their costs
• The convergence of interpolatory product integration rules
• On a Kantorovich-Rubinstein inequality
• Exponential tractability of \(L_2\)-approximation with function values
• The construction of numerical integration rules of degree three for product regions
• Cubature Formulas for Multisymmetric Functions and Applications to Stochastic Partial Differential Equations
• A Monte Carlo Method for Integration of Multivariate Smooth Functions
• Global error bounds for product cubature rules
• On the Wasserstein distance between classical sequences and the Lebesgue measure
• Tractability of sampling recovery on unweighted function classes

This page was built for publication: Product rules are optimal for numerical integration in classical smoothness spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346296)