An Algebraic Theory for Multigrid Methods for Variational Problems

Abstract

A convergence theory is developed for multigrid methods for symmetric, positive definite problems in a variational setting. The theory is based on a single algebraic approximation assumption, which is satisfied for finite element discretizations of elliptic boundary value problems, although the theory can be applied to problems without any continuous background as well. In contrast to previous results, we prove fast convergence with any positive number of smoothing steps for V- and W-cycles under discrete analogues of the $H^2 $ and $H^{1 + \alpha } $ regularity assumptions, respectively. We analyze a wide class of smoothers, including arbitrary symmetric and nonsymmetric preconditioned iterations, arbitrarily ordered Gauss–Seidel, steepest descent, Chebyshev iteration and conjugate gradients. Our estimates exhibit the usual asymptotic behavior for a large number of smoothing steps.