Abstract

In this paper, we prove the convergence of the multilevel iterative methods for solving linear equations that arise from elliptic partial differential equations. Our theory is presented entirely in terms of the generalized condition number K of the matrix A and the smoothing matrix B. This leads to a completely algebraic analysis of the method as in iterative technique for solving linear equations; the properties of the elliptic equation and the discretization procedure enter only when we seek to estimate K, just as in the case of 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 K using both Fourier analysis and standard finite element techniques. We compare the predictions of our theorems with the actual rate of convergence. Our analysis shows that accelerated iterative methods, both fixed (Chebyshev) and adaptive (conjugate gradients and conjugate residuals), are effective as smoothing procedures.