Analysis of linear difference schemes in the sparse grid combination technique

Sparse grids (Zenger, C. (1990) Sparse grids. Parallel Algorithms for Partial Differential Equations (W. Hackbusch ed.) Notes on Numerical Fluid Dynamics 31. Proceedings of the Sixth GAMM-Seminar; Bungartz, H.-J. & Griebel, M. (2004) Sparse grids. Acta Numer., 13, 1-123.) are tailored to the approximation of smooth high-dimensional functions. On a d-dimensional tensor product space, the number of grid points is N = O(h(-1) vertical bar log h vertical bar(d-1)), where h is a mesh parameter. The so-called combination technique, based on hierarchical decomposition and extrapolation, requires specific multivariate error expansions of the discretization error on Cartesian grids to hold. We derive such error expansions for linear difference schemes through an error correction technique of semi-discretizations. We obtain overall error formulae of the type epsilon = O (h(p) vertical bar log h vertical bar(d-1)) and analyse the convergence, with its dependence on dimension and smoothness, by examples of linear elliptic and parabolic problems, with numerical illustrations in up to eight dimensions.