Complexity of weighted approximation over \(\mathbb{R}\) (Q1976271)

This paper investigates approximation of univariate functions defined over the line. Assume that the \(r\)-th derivative of a function is bounded in a weighted \(L_w^p\) norm with a weight \(w\). Approximation algorithms use the values of a function and its derivatives up to the order \(r-1\). The worst case error of an algorithm is defined in a weighted \(L_u^q \) norm with a weight \(u\). This paper investigates the worst case (information) complexity of the weighted approximation problem, which is equal to the minimal number of functions and derivative evaluations needed to obtain the error \(\varepsilon\). This paper provides necessary and sufficient conditions in term of the weights \(w\) and \(u\), as well as the parameters \(r,p\), and \(q\) for the weighted approximation problem to have finite complexity. This paper also provides conditions which guarantee that complexity of weighted approximation is of the same order as the complexity of the classical approximation problem over a finite interval. Such necessary and sufficient conditions are also provided for a weighted integration problem since its complexity is equivalent to the complexity of the weighted approximation problem for \(q=1\).