(a) Define the Jacobi and Gauss-Seidel iteration schemes for solving a linear system of the form $A \mathbf{u}=\mathbf{b}$, where $\mathbf{u}, \mathbf{b} \in \mathbb{R}^{M}$ and $A \in \mathbb{R}^{M \times M}$, giving formulae for the corresponding iteration matrices $H_{J}$ and $H_{G S}$ in terms of the usual decomposition $A=L_{0}+D+U_{0}$.

Show that both iteration schemes converge when $A$ results from discretization of Poisson's equation on a square with the five-point formula, that is when

$$A=\left[\begin{array}{rrrrr} S & I & & & \\ I & S & I & & \\ & \ddots & \ddots & \ddots & \\ & & I & S & I \\ & & & I & S \end{array}\right], \quad S=\left[\begin{array}{rrrrr} -4 & 1 & & & \\ 1 & -4 & 1 & & \\ & \ddots & \ddots & \ddots & \\ & & 1 & -4 & 1 \\ & & & 1 & -4 \end{array}\right] \in \mathbb{R}^{m \times m}$$

and $M=m^{2}$. [You may state the Householder-John theorem without proof.]

(b) For the matrix $A$ given in $(*)$ :

(i) Calculate the eigenvalues of $H_{J}$ and deduce its spectral radius $\rho\left(H_{J}\right)$.

(ii) Show that each eigenvector $\mathbf{q}$ of $H_{G S}$ is related to an eigenvector $\mathbf{p}$ of $H_{J}$ by a transformation of the form $q_{i, j}=\alpha^{i+j} p_{i, j}$ for a suitable value of $\alpha$.

(iii) Deduce that $\rho\left(H_{G S}\right)=\rho^{2}\left(H_{J}\right)$. What is the significance of this result for the two iteration schemes?

[Hint: You may assume that the eigenvalues of the matrix $A$ in $(*)$ are

$$\lambda_{k, \ell}=-4\left(\sin ^{2} \frac{x}{2}+\sin ^{2} \frac{y}{2}\right), \quad \text { where } x=\frac{k \pi h}{m+1}, y=\frac{\ell \pi h}{m+1}, \quad k, \ell=1, \ldots, m,$$

with corresponding eigenvectors $\left.\mathbf{v}=\left(v_{i, j}\right), \quad v_{i, j}=\sin i x \sin j y, \quad i, j=1, \ldots, m . \quad\right]$