Smolyak's algorithm for integration and L ₁-approximation of multivariate functions with bounded mixed derivatives of second order

We propose and analyze two algorithms for multiple integration and L ₁-approximation of functions f:[0,1] ^s → ℝ that have bounded mixed derivatives of order 2. The algorithms are obtained by applying Smolyak's construction (see [16]) to one-dimensional composite midpoint rules (for integration) and to one-dimensional piecewise linear interpolation algorithm (for L ₁-approximation). Denoting by n the number of function evaluations used, the worst case error of the obtained Smolyak's cubature is asymptotically bounded from above by 16π ²s/3(s-1)((s- 2)!) ³.(log ₂n) ^3(s-1)/n ².(1+o(1)) as n→∞. The error of the corresponding algorithm for L ₁-approximation is bounded by the same expression multiplied by 4 ^s-1.