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

Update the unknowns in row order, immediately using newly computed components. The component equations areThus $G=\left(\begin{array}{ccc}0& 1& -1\\ 0& -1/2& 0\\ 0& -3/4& 1/2\end{array}\right)$ and $c=(-1,3/2,1/4{)}^T$. Using only old values in all three row equations would instead describe the Jacobi method, not the Gauss-Seidel method.

From zero, the first update is $x_1=(-1,3/2,1/4{)}^T$. For the next update, the first component is $-1+3/2-1/4=1/4$, the second is $3/2-(1/2)(3/2)=3/4$, and the third is $1/4-(3/4)(3/2)+(1/2)(1/4)=-3/4$. Therefore $x_2=(1/4,3/4,-3/4{)}^T$.

For the spectral error bound for a diagonalizable fixed-point iteration, the exact solution $x$ is a fixed point: $x=Gx+c$. Subtracting it from the iteration gives the error recurrence $e_n=G{e}_{n-1}$, with $e_n=x_n-x$. Multiplying by $S^{-1}$ and using $G=SD{S}^{-1}$ givesIterating proves $f_n=D^n{f}_0$, including $n=0$ because $D^0=I$. This argument does not assume $S$ is orthogonal; it simply expresses the error in an eigenbasis.

Write $D=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_m)$ and let $|\Lambda |={\max }_i|{\lambda }_i|$. The stated Euclidean norm givesTaking nonnegative square roots proves $\Vert f_n\Vert \le |\Lambda {|}^n\Vert f_0\Vert$. At $n=0$ this is equality. This is a contraction bound in the transformed coordinates; an arbitrary nonorthogonal $S$ does not give the same unit-constant bound for the original error norm.

The iteration matrix has eigenvalues $0,-1/2,1/2$: expanding its characteristic polynomial down the first column leaves the triangular two-by-two block with diagonal entries $-1/2,1/2$. The distinct eigenvalues ensure diagonalizability. Thus its spectral radius is $1/2<1$.

The previous bound gives $\Vert f_n\Vert \le 2^{-n}\Vert f_0\Vert \to 0$, so the Gauss-Seidel iteration converges for every initial guess under the stated diagonalization. Its limit is the exact solution $(1,1,-1{)}^T$. Since $e_n=S{f}_n$, a fixed matrix also sends this transformed error to zero; its operator norm can account for any amplification in the original coordinates.

Rotate the specified line onto the horizontal axis, stretch horizontally by two while leaving the orthogonal component unchanged, then rotate back. With $\theta =\pi /3$ and counterclockwise rotation matrix $R(\theta )$, the requested product isThe rightmost rotation acts first. In particular, $R(\theta )=\left(\begin{array}{cc}1/2& -\sqrt{3}/2\\ \sqrt{3}/2& 1/2\end{array}\right)$ and $R(-\theta )=R(\theta {)}^T$. For the unit direction $u=(1/2,\sqrt{3}/2{)}^T$, the same transformation is $T=I+u{u}^T$. It sends $u$ to $2u$ and fixes every orthogonal vector, verifying that the product is a directional stretch rather than a shear mapping or scaling in every direction. The constructed second panel in the geometric figure in Question 5 illustrates this separation.