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

Choose a matrix splitting $A=M-N$ with $M$ invertible. Then $Ax=b$ is equivalent toand the associated stationary iterative method for a linear system isFor the Jacobi method, write $A=D+L+U$ with $D$ diagonal and $L,U$ strictly lower and upper triangular, and takeThusThe iteration converges for every initial vector exactly when the spectral radius of its iteration matrix satisfies

Here $D=I$, so the Jacobi iteration matrix isThe all-ones vector is an eigenvector with eigenvalue $-2\alpha$. On its two-dimensional orthogonal complement, the coordinates sum to zero and $Hv=\alpha v$, so the other eigenvalue is $\alpha$ with multiplicity two. ThereforeBy Jacobi convergence for a three-by-three equicorrelation matrix, convergence occurs exactly forAt either endpoint the spectral radius is one, so convergence for arbitrary initial data fails.

The Householder-John theorem states: if $A=M-N$ is Hermitian positive definite and $M^{\ast }+N$ is also Hermitian positive definite, then $M$ is invertible and

Now let $A=D+L+L^T$ be real symmetric positive definite and tridiagonal. For the Jacobi splitting, $M=D$ and $N=-(L+L^T)$. Positive definiteness of $A$ implies every diagonal entry is positive, so $D$ is positive definite. Introduce the alternating-sign diagonal matrixTridiagonality givesSince $S$ is orthogonal, $SAS$ is positive definite whenever $A$ is. Both hypotheses of the Householder-John theorem hold, and hence the Jacobi iteration matrix satisfies $\rho (M^{-1}N)<1$. Therefore the Jacobi convergence for a symmetric positive-definite tridiagonal matrix follows.