Past exam of the mathematics course of the University of Cambridge / 2015 / ii / Paper 2 / 37E (Numerical Analysis)

Order the interior grid values into a vector. The coefficient matrix has diagonal $4+c{h}^2$ and off-diagonal entries $-1$ at horizontal and vertical neighbours, with boundary values already zero. Every row is strictly diagonally dominant because $c>0$. The standard convergence theorem for strict diagonal dominance gives convergence of both the Jacobi method and the Gauss-Seidel method. The matrix is also symmetric positive definite.

For $D=(4+c{h}^2)I$, the weighted Jacobi method is $u^{(r+1)}=u^{(r)}+\omega D^{-1}(b-A{u}^{(r)})$, with iteration matrix $H_{\omega }=I-\omega D^{-1}A$. The sine-product grid eigenvectors giveThese weighted Jacobi eigenvalues for a square Dirichlet grid determine convergence. All eigenvalues of $A$ are positive. Thus for fixed $h$ convergence requires $0<\omega <2(4+c{h}^2)/a_{\max }$, where $a_{\max }=8{\cos }^2(\pi h/2)+c{h}^2$. As $h\downarrow 0$, this upper bound tends to $1$ from above. Any fixed $\omega >1$ therefore fails on sufficiently fine grids; $\omega \le 0$ also fails. Consequently $0<\omega \le 1$ is necessary for all mesh sizes, and it is sufficient, since $a_{\max }<2(4+c{h}^2)$ for every finite grid.

A multigrid method combines a fine-grid smoother with a coarse-grid correction. Starting with $u_h$, apply a few smoothing iterations, compute $r_h=b_h-A_h{u}_h$, restrict this residual to a coarser grid, and approximately solve $A_H{e}_H=R{r}_h$. Prolong the coarse error and update $u_h\leftarrow u_h+P{e}_H$, then post-smooth. The coarse solve is itself performed recursively, with a direct solve at the coarsest level; visiting each coarser level once gives a V-cycle. The smoother damps rapidly varying error, while error smooth on the fine grid is efficiently represented and corrected on the coarse grid.

For ordinary Jacobi, $\omega =1$, the highest-frequency sine-product error has eigenvalue approaching $-1$, not zero. In particular for the discrete Poisson equation it is $-\cos (\pi h)$, whose magnitude approaches one. This nearly alternating error changes sign between sweeps but is barely damped, and ordinary coarse-grid restriction does not represent it well. Thus with the standard point-Jacobi smoother and coarse-grid transfers one chooses $\omega \ne 1$, usually $0<\omega <1$, for fast multigrid convergence. For example $\omega =2/3$ makes the extreme high-frequency eigenvalue approach $-1/3$. Convergence of Jacobi as a standalone iteration is therefore insufficient to guarantee that it is an effective smoother. This conclusion concerns that standard multigrid choice; other smoothers or specially designed transfers can change it.