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 language | English |
---|---|
Pages (from-to) | 722-740 |
Number of pages | 19 |
Journal | Journal of Complexity |
Volume | 17 |
Issue number | 4 |
DOIs | |
State | Published - 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