Worst case complexity of weighted approximation and integration over \(\mathbb{R}^d\) (Q1599206)

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.