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

The characteristic polynomial isThus the eigenvalues are 1 and 11. Corresponding eigenvectors are $(3,-1{)}^T$ and $(1,3{)}^T$. Their dot product is zero and each has Euclidean norm $\sqrt{10}$. Normalizing givesThe columns are orthonormal, so $P^{T}P=I$. The eigenvector equations give $AP=PD$ and hence $P^{T}AP=D$, proving the claimed orthogonal diagonalization of a real symmetric matrix.

Set $y=P^{T}x$. Because $P$ is an orthogonal matrix, $x=Py$ and $x=0$ exactly when $y=0$. The preceding diagonalization givesConsequently $x^{T}Ax\ge 0$, with equality only when $x=0$. The matrix is a symmetric positive-definite matrix, not merely positive semidefinite. In the original coordinates the same identity iswhich also makes positivity transparent.

Real symmetry and positive definiteness are sufficient, and the preceding parts establish both properties for this matrix. If a residual becomes zero, stop: the solution has been reached and the displayed step quotient should not be evaluated as $0/0$.

For a convergence justification, let $x_{\ast }$ solve $A{x}_{\ast }=b$, let $e=x_{\ast }-x$, and let $r=Ae$. The quadratic energy error is $E=e^{T}Ae/2$. Moving by $\alpha r$, with $\alpha =(r^{T}r)/(r^{T}Ar)$, is exact line search for a positive-definite quadratic and givesWriting ${\lambda }_{\min },{\lambda }_{\max }>0$ for the extreme eigenvalues, one has $r^{T}Ar\le {\lambda }_{\max }{r}^{T}r$ and $r^{T}r=e^T{A}^{2}e\ge {\lambda }_{\min }{e}^{T}Ae$. ThereforeThe factor lies below one, so the energy tends to zero and positive definiteness forces $x\to x_{\ast }$. Here the bound is $E_{\mathrm{new}}\le (10/11)E$, since the eigenvalues are 1 and 11. This proves convergence for every initial vector, rather than merely checking one numerical iteration.

From the zero initial vector, the linear-system residual is $r_0=(1,1{)}^T$. Then $r_0^T{r}_0=2$, $A{r}_0=(5,13{)}^T$, and $r_0^{T}A{r}_0=18$. The step is ${\alpha }_0=1/9$, givingAs a check, the new residual is $(4/9,-4/9{)}^T$, orthogonal to the preceding residual as expected after this exact line search. It is nonzero, so one iteration has not already solved the system.