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 / b

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.