Complexity of weighted approximation over R-1

We study approximation of univariate functions defined over the reals. We a ssume that the,th derivative of a function is bounded in a weighted L-p nor m with a weight psi. Approximation algorithms use the values of a function and its derivatives up to order r - 1. The worst case error of an algorithm is defined in a weighted L-q norm with a weight p. We study the worst case (information) complexity of the weighted approximation problem, which is e qual to the minimal number of function and derivative evaluations needed to obtain error epsilon. We provide necessary and sufficient conditions in te rms of the weights psi and rho, as well as the parameters r, p, and q for t he weighted approximation problem to have finite complexity. We also provid e conditions which guarantee that the complexity of weighted approximation is of the same order as the complexity of the classical approximation probl em over a finite interval. Such necessary and sufficient conditions are als o provided for a weighted integration problem since its complexity is equiv alent to the complexity of the weighted approximation problem for q = 1. (C ) 2000 Academic Press.