Smolyak's algorithm for weighted L-1-approximation of multivariate functions with bounded rth mixed derivatives over R-d

摘要

We are interested in numerical algorithms for weighted L-1 (approximation of functions defined on D = Rd. We consider the space F)(r,d) (which consists of multivariate functions f : D R whose all mixed derivatives of order r are bounded in L)(-norm. We approximate f F)(1)(r,d) (by an algorithm which uses evaluations of the function. The error is measured in the weighted L)(1)-norm with a weight function r. We construct and analyze Smolyak's algorithm for solving this problem. The algorithm is based on one-dimensional piecewise polynomial interpolation of degree at most r-1, where the interpolation points are specially chosen dependently on the smoothness parameter r and the weight r. We show that, under some condition on the rate of decay of r, the error of the proposed algorithm asymptotically behaves as O((ln n)(r+1)(d-1)n-r), where n denotes the number of function evaluations used. The asymptotic constant is known and it decreases to zero exponentially fast as d .