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

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.