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

One form of the Householder-John theorem is as follows. Suppose $A=A^{\ast }$ and $A=M-N$, with $M$ invertible and $W=M+M^{\ast }-A$ positive definite. Then the stationary iteration $M{x}^{(k+1)}=N{x}^{(k)}+b$ converges for every initial vector exactly when $A$ is positive definite; its iteration matrix is $B=M^{-1}N$ and convergence means spectral radius below one.

For a known positive definite system, design a splitting with $M$ easy to solve, such as diagonal or triangular, and arrange $M+M^{\ast }-A>0$. The theorem then guarantees convergence. For example $M=sI$ has $W=2sI-A>0$ when $2s$ exceeds the largest eigenvalue of $A$. In the converse direction, the discrete energy identity $A-B^{\ast }AB=(I-B{)}^{\ast }W(I-B)$ explains the criterion: stable $B$ gives $A$ as a convergent sum of positive matrices, while positive $A,W$ force every iteration eigenvalue inside the unit disk.

Divide the supplied scheme by $\omega$ and takeThen $A=M-N$, and $M$ is invertible because it is lower triangular with positive diagonal $D/\omega$. Symmetry gives $U=L^T$, soThe Householder-John theorem therefore gives convergence.

For a direct spectral proof, let $B=M^{-1}N=I-M^{-1}A$. Expansion verifies $A-B^{\ast }AB=(I-B{)}^{\ast }W(I-B)$. If $Bv=\lambda v$ with $v\ne 0$, thenThe value $\lambda =1$ is impossible since $(I-B)v=M^{-1}Av$ and $A$ is invertible. Both quadratic forms are positive, hence $|\lambda |<1$. The error obeys $e^{(k+1)}=B{e}^{(k)}$ and tends to zero, proving convergence to the unique solution $A^{-1}b$ for every initial iterate. This is the successive-over-relaxation iteration, with no assertion of convergence at the excluded endpoints.