Worst case complexity of weighted approximation and integration over \(\mathbb{R}^d\)
type: Item
instance of: scholarly article
title: Worst case complexity of weighted approximation and integration over \(\mathbb{R}^d\)
zbMATH Open document ID: 1005.41017
author: Youming Li
author: Grzegorz W. Wasilkowski
published in: Journal of Complexity
publication date: 2003-02-05T00:00:00Z
review text: The paper deals with approximation of differentiable real-valued functions defined on \({\mathbb R}^d\) in the weighted \(L_q({\mathbb R}^d)\) norm. For a given function \(f\) and an approximation algorithm \({\mathcal U}\), the error of approximation is defined as \(\|\rho(f-{\mathcal U}(f))\|_q\) where \(\rho\) is some non-negative weight function. If \(\psi\) is another weight function, the class of functions \(f\) satisfying \(\|\psi f^{(\alpha)} \|_p \leq 1\) for all partial derivatives of orders \(|\alpha|\leq r\) is denoted by \(F_{p,r,\psi}\). The supremum of errors of the algorithm over all \(f \in F_{p,r,\psi}\) is denoted by \(e({\mathcal U})\). The \(\varepsilon\)-complexity of \(\mathcal U\) is defined as the minimum number of function/derivative evaluations in order to achieve \(e({\mathcal U}) \leq \varepsilon\). The authors obtain necessary and sufficient conditions for the \(\varepsilon\)-complexity of \({\mathcal U}\) to be finite for every \(\varepsilon\). They also provide sufficient conditions for the \(\varepsilon\)-complexity to have the same order, when \(\varepsilon \to 0\), as it has in the case of functions defined on a compact domain in \({\mathbb R}^d\) with \(\rho=\psi=1_D\). A related problem of approximating the integral \(\int_{R^d}f({\mathbf x})\rho({\mathbf x}) d{\mathbf x}\) is also studied.
Mathematics Subject Classification ID: 41A65
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1750229
zbMATH Keywords: complexity of approximation
zbMATH Keywords: optimal algorithms
reviewed by: Yuly Makovoz
MaRDI profile type: Publication
full work available at URL: jcom.2001.0632
OpenAlex ID: W4213027339
cites work: Optimal integration of Lipschitz functions with a Gaussian weight
cites work: Delayed curse of dimension for Gaussian integration
cites work: A new optimal algorithm for weighted approximation and integration over R
cites work: Asymptotically optimal weighted numerical integration
cites work: Deterministic and stochastic error bounds in numerical analysis
cites work: Optimal quadrature algorithms in \(H_ p\) spaces
cites work: Q3673103
cites work: Q3993279
cites work: Complexity of weighted approximation over \(\mathbb{R}\)
cites work: Complexity of weighted approximation over \(\mathbb{R}^d\)
DOI: 10.1006/JCOM.2001.0632
description: scientific article; zbMATH DE number 1750229