Average complexity for linear operators over bounded domains

DOI10.1016/0885-064X(87)90005-7MaRDI QIDQ579854zbMATH OpenOpenAlexFDO

Authors H. Woźniakowski

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0885-064x(87)90005-7

zbMATH Keywords

approximation of functionsaverage complexityintegration of functionsWiener measureworst case complexity

Mathematics Subject Classification ID

Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Equations and inequalities involving linear operators, with vector unknowns (47A50) General theory of numerical analysis in abstract spaces (65J05)

Review text

The worst case and average complexities for approximation of linear operators whose domain is a ball of finite radius q are compared. One proves that the average complexities even for the modest q and for \(q=+\infty\) are closely related. The average complexity for normalized and relative errors is also analyzed. The paper is illustrated by integration of functions of one variable and by approximation of functions of d variables which are equipped with a Wiener measure. See also the papers of \textit{D. Lee} and \textit{G. W. Wasilkowski} [ibid. 2, 12-43 (1986; Zbl 0602.65036)] and \textit{G. W. Wasilkowski} [ibid. 2, 204- 228 (1986; Zbl 0615.94004)].

Recommendations

• On average case complexity of linear problems with noisy information
• scientific article; zbMATH DE number 1159686
• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure
• Integration and approximation of multivariate functions: Average case complexity with isotropic Wiener measure

Cites work

• Approximation of linear functionals on a Banach space with a Gaussian measure
• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Gaussian measures in Banach spaces
• Gaussian radon measures on locally convex spaces.
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 3716479 (Why is no real title available?)
• scientific article; zbMATH DE number 3755545 (Why is no real title available?)
• Information of varying cardinality
• On the average complexity of multivariate problems
• Probabilistic setting of information-based complexity
• The Brunn-Minkowski inequality in Gauss space

Cited in

(8)

• Complexity of approximation with relative error criterion in worst, average, and probabilistic settings
• Randomization for continuous problems
• Testing linear operators -- an average case study
• Average approximations and moments of measures
• Algorithms and complexity for functions on general domains
• Perspectives on information-based complexity
• Mixed settings for linear problems
• Probabilistic complexity analysis for linear problems in bounded domains

This page was built for publication: Average complexity for linear operators over bounded domains

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