Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2007 / A / 3

A multigrid method alternates local error damping with correction on coarser grids. For clarity write $A_h=h^{-2}$ times the five-point stencil and $A_h{u}_h=f_h$, incorporating Dirichlet boundary data into the right side. One two-grid cycle proceeds as follows.

The coarse solve is performed recursively, with a direct solve on the smallest grid, giving a V-cycle. Smoothing treats oscillations that are cheap for local relaxation to remove; coarse-grid correction treats errors that appear smooth on the fine grid. The scaling of the residual and coarse operator must agree if one instead uses the paper's unscaled stencil.

For homogeneous error boundary values, the tensor-product sine vectors $U_{j,k}=\sin (r\pi jh)\sin (s\pi kh)$ form a basis. The sine addition formula gives $U_{j+1,k}+U_{j-1,k}=2\cos (r\pi h)U_{j,k}$, and similarly in the other coordinate. Hence the five-point matrix hasThere is a printing error in the displayed iteration. Taken literally, its error multiplier is $1/20-(2/5)(\cos (r\pi h)+\cos (s\pi h))$, and its fixed-point equation is $(19/4)U_{j,k}+{\sum }_{\mathrm{neighbors}}U=h^2{f}_{j,k}$, rather than the stated Poisson equation. Thus the printed affine update cannot be used as a consistent relaxation for this system.

The intended weighted Jacobi iteration with $\omega =4/5$ isIts iteration matrix is $I-(\omega /4)A$, whose mode multiplier isIf at least one of the two cosines is negative, their sum lies strictly between $-2$ and $1$, so $-3/5<{\mu }_{r,s}<3/5$. Thus every such high-frequency mode contracts by at most $\boxed{3/5}$ per sweep, uniformly in grid spacing. This weighted Jacobi smoothing bound for the square Poisson problem justifies the corrected method as a smoother. The literal printed update also damps modes, but toward the wrong fixed-point equation.