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

Since $B$ is upper triangular, its eigenvalues are its diagonal entries. Equivalently, its characteristic polynomial is $\lambda (\lambda -3/8)$. Hence

For eigenvalue zero take $s_1=(1,0{)}^T$. For eigenvalue $3/8$, the first row of $(B-3I/8)s_2=0$ gives $x=-2y$, so take $s_2=(-2,1{)}^T$. These are linearly independent eigenvectors, givingThe identities $B{s}_i={\lambda }_i{s}_i$ give $BS=SD$, hence the required diagonalization $S^{-1}BS=D$.

The Gauss-Seidel method solves each component using the already updated components from the same iteration. In the splitting $A=D-L-U$, those updated diagonal and lower-triangular terms stay on the left, while upper-triangular terms use the previous iterate. ThusHere $D-L$ is lower triangular with nonzero diagonal, so each new iterate is obtained by forward substitution, starting from the specified zero vector.

As $x_0=0$, solve $(D-L)x_1=b$. Its first row gives $4(x_1{)}_1=1$; its second gives $(x_1{)}_1+2(x_1{)}_2=-1$. ThereforeThe second component uses the new first component $1/4$, distinguishing Gauss-Seidel iteration from Jacobi iteration.

The exact solution obeys $(D-L)x=Ux+b$. Subtract this from the iteration to get $(D-L)e_n=U{e}_{n-1}$. Hence the stationary iteration matrix isThis is exactly the matrix $B$ from part (a); the sign follows the given $A=D-L-U$ convention.

Yes. Part (a) diagonalizes $G=B$, whose spectral radius is $3/8<1$. Thusand every initial error converges to zero. For the specified initial vector, solving $Ax=b$ gives $x=(1,-1{)}^T$ and $e_0=(-1,1{)}^T$. In fact,The special formula is not asserted for $n=0$, because the zero-eigenvalue component disappears only after the first step.