Past exam of the numerical linear algebra and approximation course of the University of Oxford / 2008 / 2 / c / Solution

Order points along each $j$-line before moving to the next $k$-line. The splitting hasand $N$ couples the two neighboring $k$-lines. Factor $T_n$ once with the Thomas algorithm; each iteration then needs $n$ tridiagonal solves and the neighboring-line right sides, costing $\boxed{O(n^2)}$ for $n^2$ unknowns. Known boundary values are moved to the right side; the error eigenmodes have homogeneous boundary values.

The generalized eigenvalue problem iswith $U=0$ at the boundary indices. Put ${\theta }_r=r\pi /(n+1)$, ${\theta }_s=s\pi /(n+1)$. The sine addition formula gives $U_{j+1,k}+U_{j-1,k}=2\cos {\theta }_r{U}_{j,k}$ and the corresponding identity in $k$. ThusThese tensor-product sine vectors form a basis, so they give the whole spectrum. With $c=\cos (\pi /(n+1))\in [0,1)$,The iteration therefore converges.

It is not a uniformly effective multigrid smoother. Take $r=1$ and $s=n$: the error is slowly varying along a line but highly oscillatory between lines, and its multiplier is $-c/(2-c)\to -1$ as the grid is refined. It changes sign at each step while retaining almost its full amplitude. This line-Jacobi Fourier spectrum distinguishes convergence on each fixed grid from the high-frequency damping needed by the multigrid method.