Analysis of a multigrid method as an iterative technique for solving linear systems

A general class of iterative methods is introduced for solving symmetric, positive definite linear systems. These methods use two different approximations to the inverse of the matrix of the problem, one of which involves the inverse of a smaller matrix. It is shown that the methods of this class reduce the error by a constant factor at each step and that under ideal circumstances this constant is equal to (k' - 1)/(k' + 1), where k' is the ratio of the largest eigenvalue to the (J + 1)st eigenvalue of the matrix, J being the dimension of the smaller matrix involved. A multigrid method is presented as an example of a method of this class, and it is shown that while the multigrid method does not quite achieve this optimal rate of convergence, it does reduce the error at each step by a constant factor independent of the mesh spacing h. The size of this constant factor and properties of the differential equation and the discretization that affect it are also discussed. 5 references, 1 table