Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 1 / 39A (Numerical Analysis)

The Householder-John theorem says that, for a splitting $A=M-N$ with $A$ Hermitian positive definite, positivity of $H=M^{\ast }+N=M^{\ast }+M-A$ implies $M$ is invertible and $\rho (M^{-1}N)<1$. Invertibility follows since $Mx=0$ for $x\ne 0$ would give $x^{\ast }Hx=-x^{\ast }Ax<0$.

For clarity, the spectral-radius conclusion follows from a useful energy identity. Put $T=M^{-1}N=I-M^{-1}A$. Direct multiplication givesIf $Tv=\lambda v$, thenThe eigenvalue one is impossible because $A$ is invertible. Both quadratic forms are positive, so $|\lambda |<1$. The splitting iteration $M{x}^{(k+1)}=N{x}^{(k)}+b$ propagates its error by $T$; spectral radius less than one therefore gives convergence from every initial vector.

Write $A=D+L+U$, with $D$ diagonal and $L,U$ the strict triangular parts. The Jacobi method updates all coordinates using the preceding iterate:For a symmetric positive definite matrix, $D$ has positive diagonal entries. In its splitting take $M=D$, $N=D-A$. The theorem requires $M^{\ast }+N=2D-A$ to be positive definite, which need not hold for every positive definite matrix.

For this tridiagonal matrix, let $S=\mathrm{diag}((-1{)}^1,\dots ,(-1{)}^n)$. Neighboring indices have opposite signs, so $SAS=2D-A$: the diagonal stays fixed and every nonzero off-diagonal entry changes sign. ThusThe Householder-John theorem now applies and proves Jacobi convergence for every initial vector. This is precisely why the tridiagonal structure matters.