The Poisson equation $u_{x x}=f$ in the unit interval $\Omega=[0,1], u=0$ on $\partial \Omega$ is discretised with the formula

$$u_{i-1}+u_{i+1}-2 u_{i}=h^{2} f_{i}$$

where $1 \leqslant i \leqslant n, u_{i} \approx u(i h)$ and $i h$ are the grid points.

(i) Define the above system of equations in vector form $A \mathbf{u}=\mathbf{b}$ and describe the relaxed Jacobi method with relaxation parameter $\omega$ for solving this linear system. For $\mathbf{x}^{*}$ and $\mathbf{x}^{(\nu)}$ being the exact solution and the iterated solution respectively, let $\mathbf{e}^{(\nu)}=\mathbf{x}^{(\nu)}-\mathbf{x}^{*}$ be the error and $H_{\omega}$ the iteration matrix, so that

$$\mathbf{e}^{(\nu+1)}=H_{\omega} \mathbf{e}^{(\nu)}$$

Express $H_{\omega}$ in terms of the matrix $A$, the diagonal part $D$ of $A$ and $\omega$, and find the eigenvectors $\mathbf{v}_{k}$ and the eigenvalues $\lambda_{k}(\omega)$ of $H_{\omega}$.

(ii) For $A$ as above, let

$$\mathbf{e}^{(\nu)}=\sum_{k=1}^{n} a_{k}^{(\nu)} \mathbf{v}_{k}$$

be the expansion of the error with respect to the eigenvectors of $H_{\omega}$. Derive conditions on $\omega$ such that the method converges for any $n$, and prove that, for any such $\omega$, the rate of convergence of $\mathbf{e}^{(\nu)} \rightarrow 0$ is not faster than $\left(1-c / n^{2}\right)^{\nu}$.

(iii) Show that, for some $\omega$, the high frequency components $\left(\frac{n+1}{2} \leqslant k \leqslant n\right)$ of the error $\mathbf{e}^{(\nu)}$ tend to zero much faster than $\left(1-c / n^{2}\right)^{\nu}$. Determine the optimal parameter $\omega_{*}$ which provides the largest suppression of the high frequency components per iteration, and find the corresponding attenuation factor $\mu_{*}$ (i.e., the least $\mu_{\omega}$ such that $\left|a_{k}^{(\nu+1)}\right| \leqslant \mu_{\omega}\left|a_{k}^{(\nu)}\right|$ for $\left.\frac{n+1}{2} \leqslant k \leqslant n\right)$.