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

§ 1. Multigrid Methods for Variational Problems

Smoothing Properties of Classical Iterative Methods
Multigrid methods are based on the observation that the classical iterative methods
result in smoothing. This is most easily seen by examining the model Example
II.4.3 involving the Poisson equation on a rectangle. This example was also dis-
cussed in connection with the Gauss-Seidel and Jacobi methods; cf. (IV.1.11).

1.1 Example. The discretization of the Poisson equation on the unit square using
the standard five-point stencil leads to the system of equations
4 x i,j − x i + 1 ,j − x i − 1 ,j − x i,j + 1 − x i,j − 1 = b ij for 1 ≤ i, j ≤ n − 1 . 1 . 1 )

0. We consider the iterative solution of (1.1)
using the Jacobi method with relaxation parameter ω :
x ν + 1

Here x i, 0 = x i,n = x 0 ,j = x n,j =

ω ω

4 b ij + ( 1 4 (x i + 1 ,j + x i − 1 ,j + x i,j + 1 + x i,j − 1 ) +

− ω)x i,j . = ( 1 . 2 )

i,j

By (IV.1.12), the eigenvectors z k,m of the iteration matrix defined implicitly in
(1.2) can be thought of as the discretizations of the eigenfunctions

sin ikπ
n

sin jmπ
n

(z k,m ) i,j =

, 1 ≤ i, j, k, m ≤ n − 1 , ( 1 . 3 )

of the Laplace operator, with corresponding eigenvalues

2 cos kπ

1 1

2 cos mπ

λ km =

n +

, if ω = 1 ,

n

and

1
2 .
In each step of the iteration, the individual spectral parts of the errors are multiplied
by the corresponding factors λ km . Thus, those terms corresponding to eigenvalues
whose moduli are near 1 are damped the least.

4 cos kπ

1 1

4 cos mπ

1
2 ,

λ km

=

n + n +

if ω =

Fig. 48. Replacing values on a one-dimensional grid by the average values of
their neighbors has only a minor effect on low frequency terms, but a substantial
effect on high frequency ones.