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

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 ₁-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 ₁-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.