Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Digital systems, linear algebra, introduction to formal proof / 6 / c

At $u_0=0$, the linear-system residual is $r_0=b=(1,1{)}^T$. Here $A{r}_0=r_0$, so the steepest-descent step size isConsequently $u_1=(1,1{)}^T$, and $A{u}_1=b$ gives residual zero. The stated exact-arithmetic stopping test with $ϵ=0$ is met after one iteration. Stop there rather than trying to evaluate the next, undefined $0/0$ step. This is the special case where the initial residual is an eigenvector.

No, except when started at the exact solution. Merely failing the usual symmetric positive-definite matrix hypothesis would not by itself prove divergence. For this particular matrix one can prove that every defined nonzero-residual step increases the linear-system residual norm.

Write $r=(x,y{)}^T$, put $D=r^{T}Ar=2x^2-2xy-2y^2$ and $B=5x^2+4xy+3y^2$. For $D\ne 0$, direct substitution into the stated iteration givesFor $r\ne 0$, bothare strictly positive; completing squares gives $7(x+y/7{)}^2+6y^2/7$ and $3(x+y{)}^2+2y^2$. Hence $B>|D|$ and the residual norm strictly increases at every defined step. If $D=0$ before the residual vanishes, the algorithm is instead undefined. Neither behavior converges to residual zero. The matrix is invertible, so this also rules out convergence of the iterates to its unique solution.

For example, from the zero starting guess the first two step sizes are $37/11$ and $-37/11$, giving $r_1=(42,30{)}^T$ and $r_2=(1380/11)r_0$. This demonstrates the failure without treating a sufficient convergence theorem as a necessary one. The general calculation is residual growth in an indefinite steepest-descent iteration.