L. Plaskota and G.W. Wasilkowski

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

---

Abstract.   We propose and analyze two algorithms for multiple integration and $L_1$-approximation of functions $f:[0,1]^s\to\R$ that have bounded mixed derivatives of order $2$. The algorithms are obtained by applying Smolyak's construction (see \cite{Smol63}) to one dimensional composite midpoint rules (for integration) and to one dimensional piecewise linear interpolation algorithm (for $L_1$-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 $$ \frac{16\pi^2s}{3(s-1)((s-2)!)^3}\cdot\frac{(\log_2n)^{3(s-1)}}{n^2}\cdot (1+o(1)) $$ as $n\to\infty$. The error of the corresponding algorithm for $L_1$-approximation is bounded by the same expression multiplied by $4^{s-1}$.

---