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

For independent columns $a_1,\dots ,a_k$ in a real inner product space, the Gram-Schmidt process recursively formsEach $u_j$ subtracts the orthogonal projections onto earlier normalized vectors. Their independence ensures $u_j\ne 0$. The resulting $q_i$ are orthonormal and preserve the span of every initial column set. Putting $Q=(q_1\cdots q_k)$ and $r_{ij}=⟨q_i,a_j⟩$ for $i\le j$, with zeros below the diagonal, gives a QR decomposition $A=QR$ with $Q^{T}Q=I$. Dependent input columns require omitting a zero residual or treating rank deficiency separately.

The first column has norm two, giving $q_1=(1,-1,1,-1{)}^T/2$. Its inner products with the second and third columns are both one. Subtracting $q_1$ from the second column leaves $(3,3,3,3{)}^T/2$, of norm three, so $q_2=(1,1,1,1{)}^T/2$. The inner product of $q_2$ with the third column is one. Subtracting $q_1+q_2$ from that column leaves $(1,1,-1,-1{)}^T$, of norm two. Thus the Gram-Schmidt process givesThe columns of $Q$ have unit norm and pairwise zero inner products, so $Q^{T}Q=I_3$. Direct multiplication verifies $QR=A$.

A unit vector along the line is $v=(3,4{)}^T/5$. Reflection fixes its component parallel to $v$ and negates its perpendicular component, so the reflection matrix isIndeed $H(3,4{)}^T=(3,4{)}^T$, $H(-4,3{)}^T=-(-4,3{)}^T$ and $H^2=I$. These characterize the orthogonal reflection in that line.

The line passes through $p=(0,1{)}^T$ and has the same direction as in part (i). Translate by $-p$, reflect by $H$, then translate back. In homogeneous coordinates the affine reflection isAct on column $(x,y,1{)}^T$, reading the product from right to left. Every point with $y=4x/3+1$ is fixed. The translation column is $p-Hp$, as for any reflection in an affine hyperplane.

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.