Multigrid Methods - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 227

1.2 Corollary. After a few iterations of the Jacobi method (with ω = 1 ), the error

essentially contains only terms for which
k and m are both small, or
k and m are both close to n.
Terms of the latter type are strongly reduced if we use ω = 1 / 2 (instead of ω = 1 .)

This leaves only the low frequency terms; see Fig. 48.
Accordingly, in carrying out the iteration we will get a clear reduction in the
error as long as the error still contains highly oscillatory parts. However, as soon
as the error becomes smooth, the iteration will essentially stop, and subsequently
the error reduction per step will only be of order 1 − O (n − 2 ) .

We will show later in connection with the convergence theory that the Jacobi
method has a smoothing effect in general, and not just for the model problem, see
Lemma 2.4. The following methods are used in practice for smoothing:
the Jacobi method and the Richardson iteration,
the successive overrelaxation method (SOR),
the symmetric successive overrelaxation method (SSOR),
iteration with the incomplete Cholesky decomposition (ICC).
We now list a few suggestions for the choice of the smoother. If the entire matrix of
the system is to be stored, either the SOR or the SSOR method (with a small amount
of underrelaxation) is useful in the standard case. For parallel computations, Jacobi
relaxation is appropriate. Smoothing via ICC requires more work than the other
methods, but turns out to be more robust for anisotropic problems; see Hemker
[1980] and Wittum [1989b]. For example, we have a strongly anisotropic problem
if one direction in space is preferred, such as for the differential equation

100 u xx + u yy = f.

The Multigrid Idea

The above discussion suggests the following approach.
First we carry out several relaxation steps in order to strongly damp all os-
cillating components of the error. Then we go to a coarser grid, and approximate
the remaining smooth part. This is possible because smooth functions can be ap-
proximated well on coarse grids.
We then alternately repeat the smoothing step on the fine grid and the coarse-
grid correction . This results in an iterative method.
The system of equations corresponding to the problem on the coarse grid
is usually simpler to solve than the original problem. In particular, in the planar
case, if we go from a grid with mesh size h to one with mesh size 2 h , the number