Some estimates of the rate of convergence for the cascadic conjugate-gradient method

AbstractThe paper deals with a cascadic conjugate-gradient method (shortly called the CCG-algorithm) which was proposed by P. Deuflhard and can be considered as a simpler version of a multigrid (multilevel) method. We define it recurrently for discrete self-adjoint positive-definite problems on a sequence of grids. On the coarsest grid, the linear discrete algebraic system is solved directly. On the finer grids, the system is iteratively solved by the conjugate-gradient method where the starting guess is an interpolation of the approximated solution on the previous grid. Any preconditioning or restriction to coarser grids is not implemented. Nevertheless, the CCG-algorithm has the same optimal property compared to multigrid methods; namely, the algorithm converges with a rate which is independent of the number of unknowns and the number of grids. As an example, this property is proved for elliptic second order Dirichlet problems in two-dimensional, convex, polygonal bounded domains. For ensuring convergence, the number of iterations on each grid level has to increase from finer to coarser grids. The optimal dependence of these numbers is established with respect to the mesh size and the number of unknowns. The theory has been presented in an abstract setting which allows the application to both finite element and finite difference methods