5.7 The multigrid method

We assume there exists a series of regular (FE-) meshes/grids $\mathfrak{T}_q$ ( $q=\overline{1,\ell} \makebox[0pt]{}$) where the finer grid  $\mathfrak{T}_{q+1}$ was derived from the coarser one  $\mathfrak{T}_{q}$ (simplest case in 2D: subdivide all triangles in 4 congruent ones). For that hierarchy of grids the relation $\mathfrak{T}_{1} \subset \mathfrak{T}_{2} \subset \cdots \subset \mathfrak{T}_{\ell}$ should hold, i.e., the grids are nested.

Discretizing the given differential equation on each grid  $\mathfrak{T}_{q}$ results in a series of systems of equations

$$K_q \cdot \underline{u}_q \;=\; \underline{f}_q$$ (5.9)

with the symmetric and positive definite sparse stiffness matrices $K_q$.

When analyzing the (non-optimal) convergence behavior of iteration methods presented in Sec 5.3 and 5.4 by means of representing the error  $\underline{u}_q^{\ast}-\underline{u}_q^{k}$ as sum of the eigenfrequencies of matrix $K$ we achieve the following results :

 $&bull#bullet;$

Those parts of the error belonging to high eigenfrequencies are reduced very quickly.

 $&bull#bullet;$

Low frequency parts of the error yield to the slow convergence behavior of classical iterative solvers.

$\Longrightarrow$

There is a need for a method reducing the low frequency errors  $e_{\mathrm{low}}$ at low costs without losing the good convergence behavior for the high frequency errors  $e_{\mathrm{high}}$.

$\Longrightarrow$

Two grid idea :

Reduce  $e_{\mathrm{high}}$ on grid  $\mathfrak{T}_{\ell}$ (smoothing), project the remaining error onto coarse grid  $\mathfrak{T}_{\ell-1}$ and solve there exactly. Interpolate the coarse grid solution (named defect correction) back to the fine grid  $\mathfrak{T}_{\ell}$ and add it to the solution thereon. Usually an additional smoothing reduces the high frequency errors once more.

 $&bull#bullet;$

Die Multigrid idea substitutes the exact solver in the defect correction on the coarse grid $\ell-1$ recursively by a two grid method until the coarsest grid  $\mathfrak{T}_{1}$ is reached. There, we have to solve the remaining small system of equations exactly.