Two Proofs of Convergence for the Combination Technique for the
             Efficient Solution of Sparse Grid Problems

        H.-J. Bungartz, M. Griebel, D. R\"oschke, and C. Zenger

   Institut fuer Informatik der TU Muenchen, D-80290 Muenchen, Germany


                 
                       A  b  s  t  r  a  c  t  

For a simple model problem --- the Laplace equation on the unit square with
a Dirichlet boundary function vanishing for x=0, x=1, and y=1, and
equaling some suitable g(x) for y=0 --- we present a proof of convergence
for the combination technique, a modern, efficient, and easily
parallelizable sparse grid solver for elliptic partial differential equations
that recently gained importance in fields of applications like computational
fluid dynamics. For full square grids with meshwidth h and O(h^{-2})
grid points, the order O(h^2) of the discretization error using finite
differences was shown in [Hofmann, 1967 (see refs.)], if g(x) in C^2[0,1]. 
In this paper, we show that the finite difference discretization error
of the solution produced by the combination technique on a sparse grid with
only O(h^{-1} log_2(h^{-1})) grid points is of the order
O(h^{2} log_2(h^{-1})), if the Fourier coefficients b_k of the 2-periodic
and 0-symmetric extension of g fulfill b_k <= c_g/k^{-3-epsilon} for some 
arbitrary small positive epsilon. If 0<epsilon<=1, this is vaild for
for C^4[0,1] functions g with g(0)=g(1)=g''(0)=g''(1)=0, e.g.. A simple
transformation even shows that C^4[0,1] is sufficient. We present
results of numerical experiments with functions g of varying smoothness.