The Poisson equation $\frac{d^{2} u}{d x^{2}}=f$ in the unit interval $[0,1]$, with $u(0)=u(1)=0$, is discretised with the formula

$$u_{i-1}-2 u_{i}+u_{i+1}=h^{2} f_{i}, \quad 1 \leqslant i \leqslant n,$$

where $u_{0}=u_{n+1}=0, h=(n+1)^{-1}$, the grid points are at $x=i h$ and $u_{i} \approx u(i h)$.

(a) Write the above system of equations in the vector form $A \boldsymbol{u}=\boldsymbol{b}$ and describe the relaxed Jacobi method with relaxation parameter $\omega$ for solving this linear system.

(b) For $\boldsymbol{x}^{*}$ and $\boldsymbol{x}^{(\nu)}$ being the exact and the iterated solution, respectively, let $\boldsymbol{e}^{(\nu)}:=\boldsymbol{x}^{(\nu)}-\boldsymbol{x}^{*}$ be the error and $H_{\omega}$ be the iteration matrix, so that

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

Express $H_{\omega}$ in terms of the matrix $A$ and the relaxation parameter $\omega$. Using the fact that for any $n \times n$ Toeplitz symmetric tridiagonal matrix, the eigenvectors $\boldsymbol{v}_{k}(k=1, \ldots, n)$ have the form:

$$\boldsymbol{v}_{k}=(\sin i k x)_{i=1}^{n}, \quad x=\frac{\pi}{n+1}$$

find the eigenvalues $\lambda_{k}(A)$ of $A$. Hence deduce the eigenvalues $\lambda_{k}(\omega)$ of $H_{\omega}$.

(c) For $A$ as above, let

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

be the expansion of the error with respect to the eigenvectors $\left(\boldsymbol{v}_{k}\right)$ of $H_{\omega}$.

Find the range of the parameter $\omega$ which provides convergence of the method for any $n$, and prove that, for any such $\omega$, the rate of convergence $e^{(\nu)} \rightarrow 0$ is not faster than $\left(1-c / n^{2}\right)^{\nu}$ when $n$ is large.

(d) Show that, for an appropriate range of $\omega$, the high frequency components $a_{k}^{(\nu)}$ $\left(\frac{n+1}{2} \leqslant k \leqslant n\right)$ of the error $e^{(\nu)}$ tend to zero much faster than the rate obtained in part (c). Determine the optimal parameter $\omega_{*}$ which provides the largest supression of the high frequency components per iteration, and find the corresponding attenuation factor $\mu_{*}$ assuming $n$ is large. That is, find the least $\mu_{\omega}$ such that $\left|a_{k}^{(\nu+1)}\right| \leqslant \mu_{\omega}\left|a_{k}^{(\nu)}\right|$ for $\frac{n+1}{2} \leqslant k \leqslant n$.