Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 2 / 38C / a

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.