Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 2 / 39C (Numerical Analysis)

Let ${\theta }_k=k\pi h=k\pi /(m+1)$ and define $q_j^{(k)}=\sin (j{\theta }_k)$. The artificial boundary values are $q_0^{(k)}=q_{m+1}^{(k)}=0$. For the symmetric tridiagonal Toeplitz matrix $H=[\beta ,\alpha ,\beta ]$, the sine addition formula givesThus all such matrices have the same discrete sine transform eigenvectors, with eigenvaluesThe sine vectors are mutually orthogonal vectors and nonzero, so the matrix $Q=(\sin (ij\pi h){)}_{i,j=1}^m$ is invertible. If $D=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_m)$, then $HQ=QD$ and therefore

Let $u_j=(u_{1,j},\dots ,u_{m,j}{)}^T$ collect the unknowns in grid column $j$, and define $b_j=h^2(f_{1,j},\dots ,f_{m,j}{)}^T$. The terms within one column form the blockwhile coupling to either adjacent column contributesThe zero boundary values remove all blocks outside the displayed range, so the nine-point finite-difference stencil becomes the block tridiagonal matrix system

The simultaneous diagonalization from part (a) applies to both $B$ and $C$. With ${\theta }_k=k\pi h$,andMultiplying the $j$th block equation by $Q^{-1}$ and writing $v_j=Q^{-1}{u}_j$ and $c_j=Q^{-1}{b}_j$ giveswith the absent boundary terms omitted. This is exactly system (3).

Each coordinate of the transformed vectors evolves independently because $D$ and $E$ are diagonal matrices. Reorder the unknowns by collecting the $k$th components across all grid columns:Then system (3) splits into the $m$ uncoupled systemswhereThus the original $m^2\times m^2$ problem reduces to one discrete sine transform followed by $m$ independent tridiagonal solves and an inverse sine transform.