Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 40D (Numerical Analysis)

The Householder-John theorem states the following. Letbe a splitting in which $A$ is Hermitian positive definite. Ifis also Hermitian positive definite, then $M$ is nonsingular and every eigenvalue of $H=M^{-1}N$ has modulus less than one. Hence the associated stationary iteration converges.

First, $M$ must be nonsingular. If $Mx=0$ for some nonzero $x$, then $Nx=-Ax$, and thereforecontradicting the positive definiteness of $B$.

Now let $Hx=\lambda x$ with $x\ne 0$. Then $Nx=\lambda Mx$, soPut $a=x^{\ast }Ax>0$ and $m=x^{\ast }Mx$. Since $\lambda \ne 1$,Consequently,It follows that $|\lambda |<1$. Thus $\rho (H)<1$, proving the theorem.

Writewhere $D=\mathrm{diag}(a_1,\dots ,a_n)$ and $L,U$ are the strict lower and upper triangular parts. The Jacobi method iswith iteration matrix

Here $A$ is symmetric, so $U=L^T$. Regard the iteration as the splittingLetBecause $A$ is tridiagonal, changing alternating signs reverses the sign of every off-diagonal entry while preserving every diagonal entry. ThereforeSince $S^T=S=S^{-1}$ and $A$ is positive definite, $SAS$ is positive definite. The Householder-John theorem now givesThe Jacobi iterates therefore converge to the unique solution $A^{-1}b$ for every starting vector, which is the jacobi convergence for a symmetric positive-definite tridiagonal matrix.