Complexity of Weighted Approximation over R

Grzegorz W. Wasilkowski, Henryk Woźniakowski

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


We study approximation of univariate functions defined over the reals. We assume that the rth derivative of a function is bounded in a weighted Lp norm with a weight ψ. 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 Lq norm with a weight ρ. We study the worst case (information) complexity of the weighted approximation problem, which is equal to the minimal number of function and derivative evaluations needed to obtain error ε. We provide necessary and sufficient conditions in terms of the weights ψ and ρ, as well as the parameters r, p, and q for the weighted approximation problem to have finite complexity. We also provide conditions which guarantee that the 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.

Original languageEnglish
Pages (from-to)223-251
Number of pages29
JournalJournal of Approximation Theory
Issue number2
StatePublished - Apr 2000

Bibliographical note

Funding Information:
1The authors were partially supported by the National Science Foundation under Grants CCR-9729971 and CRR-9731858, respectively.

ASJC Scopus subject areas

  • Analysis
  • Numerical Analysis
  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Complexity of Weighted Approximation over R'. Together they form a unique fingerprint.

Cite this