Algorithms and complexity for functions on general domains

DOI10.1016/J.JCO.2020.101458MaRDI QIDQ1996873zbMATH OpenOpenAlexWikidataFDO

Authors Erich Novak

Publication date 26 February 2021

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

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

zbMATH Keywords

error boundsbounded Lipschitz domaincomplexity analysisfunctions on general domains

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical integration (65D30) Algorithms for approximation of functions (65D15)

Abstract: Error bounds and complexity bounds in numerical analysis and information-based complexity are often proved for functions that are defined on very simple domains, such as a cube, a torus, or a sphere. We study optimal error bounds for the approximation or integration of functions defined on $D_{d}subset{R}^d$ and only assume that $D_d$ is a bounded Lipschitz domain. Some results are even more general. We study three different concepts to measure the complexity: order of convergence, asymptotic constant, and explicit uniform bounds, i.e., bounds that hold for all $n$ (number of pieces of information) and all (normalized) domains. It is known for many problems that the order of convergence of optimal algorithms does not depend on the domain $D_{d}subset{R}^d$. We present examples for which the following statements are true: 1) Also the asymptotic constant does not depend on the shape of $D_d$ or the imposed boundary values, it only depends on the volume of the domain. 2) There are explicit and uniform lower (or upper, respectively) bounds for the error that are only slightly smaller (or larger, respectively) than the asymptotic error bound.

Recommendations

• Average complexity for linear operators over bounded domains
• Worst case complexity of weighted approximation and integration over \(\mathbb{R}^d\)
• Product rules are optimal for numerical integration in classical smoothness spaces
• ``Curse of dimensionality for complexity of approximation for classes of functions satisfying Lipschitz condition
• Probabilistic complexity analysis for linear problems in bounded domains

Cites work

• scientific article; zbMATH DE number 5297651 (Why is no real title available?)
• scientific article; zbMATH DE number 3663806 (Why is no real title available?)
• scientific article; zbMATH DE number 3675205 (Why is no real title available?)
• scientific article; zbMATH DE number 898099 (Why is no real title available?)
• scientific article; zbMATH DE number 3215519 (Why is no real title available?)
• A note on coverings
• Approximation numbers of Sobolev embeddings-sharp constants and tractability
• Approximation of infinitely differentiable multivariate functions is intractable
• Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
• Asymptotic behavior of the spectrum of differential equations
• Ausfüllung und Überdeckung konvexer Körper durch konvexe Körper
• Bases in function spaces, sampling, discrepancy, numerical integration
• Degree-independent Sobolev extension on locally uniform domains
• Deterministic and stochastic error bounds in numerical analysis
• Distribution of the eigenvalues for differential operators with constant coefficients
• Function spaces and wavelets on domains
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• High dimensional polynomial interpolation on sparse grids
• Leading term in the asymptotic spectral formula for nonsmooth elliptic problems
• On the Schrödinger equation and the eigenvalue problem
• On the complexity of computing the \(L_q\) norm
• On weak tractability of the Clenshaw-Curtis Smolyak algorithm
• On weak tractability of the Smolyak algorithm for approximation problems
• Optimal approximation of elliptic problems by linear and nonlinear mappings. I
• Optimal approximation of multivariate periodic Sobolev functions in the sup-norm
• Optimal method of constructing best uniform approximations for functions of a certain class
• Optimal recovery of isotropic classes of twice-differentiable multivariate functions
• Optimum quantization and its applications
• Product rules are optimal for numerical integration in classical smoothness spaces
• Randomized approximation of Sobolev embeddings. II
• Randomized approximation of Sobolev embeddings. III
• Sampling numbers and function spaces
• Sharp estimates for approximation numbers of non-periodic Sobolev embeddings
• Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting
• Tensor power sequences and the approximation of tensor product operators
• The curse of dimensionality for numerical integration of smooth functions
• The curse of dimensionality for numerical integration of smooth functions. II
• The curse of dimensionality for numerical integration on general domains
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Tractability of multivariate problems. Volume III: Standard information for operators
• Tractability results for weighted Banach spaces of smooth functions
• Uniform recovery of high-dimensional C^r-functions
• Upper bounds for the Neumann eigenvalues on a bounded domain in Euclidean space
• Wavelet para-bases and sampling numbers in function spaces on domains
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
• Widths of embeddings in function spaces

Cited in

(6)

• How anisotropic mixed smoothness affects the decay of singular numbers for Sobolev embeddings
• scientific article; zbMATH DE number 1534573 (Why is no real title available?)
• Optimal recovery and volume estimates
• Recovery of Sobolev functions restricted to iid sampling
• Lower bounds of cowidths and widths of multiplier operators
• scientific article; zbMATH DE number 3637838 (Why is no real title available?)

This page was built for publication: Algorithms and complexity for functions on general domains

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