Complexity of weighted approximation over ℝd

G. W. Wasilkowski, H. Woźniakowski

Research output: Contribution to journalArticlepeer-review

19 Scopus citations

Abstract

We study approximation of multivariate functions defined over δrd. We assume that all rth order partial derivatives of the functions considered are continuous and uniformly bounded. Approximation algorithms U(f) only use the values of f or its partial derivatives up to order r. We want to recover the function f with small error measured in a weighted Lq norm with a weight function p. We study the worst case (information) complexity which is equal to the minimal number of function and derivative evaluations needed to obtain error e. We provide necessary and sufficient conditions in terms of the weight p and the parameters q and r for the weighted approximation problem to have finite complexity. We also provide conditions guaranteeing that the complexity is of the same order as the complexity of the classical approximation problem over a finite domain. Since the complexity of the weighted integration problem is equivalent to the complexity of the weighted approximation problem with q = 1, the results of this paper also hold for weighted integration. This paper is a continuation of [7], where weighted approximation over δr was studied.

Original languageEnglish
Pages (from-to)722-740
Number of pages19
JournalJournal of Complexity
Volume17
Issue number4
DOIs
StatePublished - 2001

Bibliographical note

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

Keywords

  • Integration
  • Weighted multivariate approximation
  • Worst case complexity

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • Mathematics (all)
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Complexity of weighted approximation over ℝd'. Together they form a unique fingerprint.

Cite this