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

For a tridiagonal matrix with subdiagonal $a_i$, diagonal $b_i$ and superdiagonal $c_i$, banded Gaussian elimination introduces no fill beyond the original band. The Thomas algorithm usesUpdate the right side by $d_1=f_1$, $d_i=f_i-{\ell }_i{d}_{i-1}$. Then back substitution givesEach row requires only a fixed number of arithmetic operations, so both work and storage are $\boxed{O(n)}$. The assumed absence of a need for pivoting includes nonzero elimination pivots $p_i$.

Write $G=M^{-1}N$. Subtracting the exact equation $Mx=Nx+b$ from the iteration gives $e_{\ell +1}=G{e}_{\ell }$, where $e_{\ell }=x-x^{(\ell )}$. Hence $e_{\ell }=G^{\ell }{e}_0$. Alsoso the stated scalars are precisely the eigenvalues of the iteration matrix $G$.

The spectral radius criterion for matrix powers states that $G^{\ell }\to 0$ if and only if all its eigenvalues have modulus strictly less than one. Applying that theorem gives $e_{\ell }\to 0$ for every initial vector. Therefore $\boxed{x^{(\ell )}\to A^{-1}b}$.

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.