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

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.

The normal equations for linear least squares areThe supplied QR decomposition gives full column rank because $R$ is invertible and $Q^{T}Q=I$. Hence, for every nonzero $u$, $u^T{A}^{T}Au=\Vert Au{\Vert }_2^2>0$. Thus $A^{T}A$ is a symmetric positive-definite matrix and the displayed square system is nonsingular.

Substitution gives $R^{T}Rx=R^T{Q}^{T}b$. Since $R^T$ is invertible, cancel it on the left to obtain the nonsingular triangular systemThis is the reduced QR least-squares solution. Its geometric justification is the orthogonal decompositionThe second term is independent of $x$, while invertibility of $R$ lets the first term be zero at exactly one point. Although $Q^{T}Q=I_M$, one must not replace $Q{Q}^T$ by $I_N$: $Q$ is tall and its product $Q{Q}^T$ is the orthogonal projection onto its column space.

The supplied factors give $Q^{T}b=(0,2{)}^T$. Back substitution in $Rx=Q^{T}b$ yields $2y=2$ and $10x+4y=0$, soMultiplying by the original matrix gives $(1,1,1,1{)}^T$, so this least-squares minimizer has residual zero: this particular overdetermined system is exactly consistent. Full column rank still guarantees uniqueness of the minimizer.