Sharp Estimates for Multigrid Rates of Convergence with General Smoothing and Acceleration

Abstract

In this paper, we prove the convergence of the multilevel iterative method for solving linear equations that arise from elliptic partial differential equations. Our theory is presented entirely in terms of the generalized condition number $\kappa $ of the matrix A and the smoothing matrix B. This leads to a completely algebraic analysis of the method as an iterative technique for solving linear equations; the properties of the elliptic equation and discretization procedure enter only when we seek to estimate $\kappa $, just as in the case of most standard iterative methods. Here we consider the fundamental two-level iteration, and the V and W cycles of the j-level iteration ($j > 2$). We prove that the V and W cycles converge even when only one smoothing iteration is used. We present several examples of the computation of $\kappa $ using both Fourier analysis and standard finite element techniques. We compare the predictions of our theorems with the actual rate of convergence. Our analysis also shows that accelerated iterative methods, both fixed (Chebyshev) and adaptive (conjugate gradients and conjugate residuals), are effective as smoothing procedures.