A piecewise constant algorithm for weighted L 1 approximation over bounded or unbounded regions in ℝ s

Fred J. Hickernell*, Ian H. Sloan, Grzegorz W. Wasilkowski

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)
4 Downloads (Pure)

Abstract

Using Smolyak's construction [S.A. Smolyak, Dokl. Akad. Nauk SSSR, 4 (1963), pp. 240-243], we derive a new algorithm for approximating multivariate functions over bounded or unbounded regions in ℝ s with the error measured in a weighted L 1-norm. We provide upper bounds for the algorithm's cost and error for a class of functions whose mixed first order partial derivatives are bounded in the L 1-norm. In particular, we prove that the error and the cost (measured in terms of the number of function evaluations) satisfy the relation error ≤ s exp(1/12(s-1)/(s-1)π (e ln(cost)/(s-1)√2 ln(2)) 2(s-1) 1/cost whenever the cost is sufficiently large relative to the number s of variables. More specifically, the inequality holds when q ≥ 2(s -1), where g is a special parameter defining the refinement level in Smolyak's algorithm, and hence the number of function evaluations used by the algorithm. We also discuss extensions of the results to the spaces with the derivatives bounded in L p-norms.

Original languageEnglish
Pages (from-to)1003-1020
Number of pages18
JournalSIAM Journal on Numerical Analysis
Volume43
Issue number3
DOIs
Publication statusPublished - Jan 2005
Externally publishedYes

Scopus Subject Areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Banach spaces
  • Mixed first order partial derivatives
  • Multivariate functions
  • Smolyak's construction

Fingerprint

Dive into the research topics of 'A piecewise constant algorithm for weighted L 1 approximation over bounded or unbounded regions in ℝ s'. Together they form a unique fingerprint.

Cite this