(i) Define the Jacobi method with relaxation for solving the linear system $A \boldsymbol{x}=\boldsymbol{b}$.

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

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

Express $H_{\omega}$ in terms of the matrix $A$, its diagonal part $D$ and the relaxation parameter $\omega$, and find the eigenvectors $\boldsymbol{v}_{k}$ and the eigenvalues $\lambda_{k}(\omega)$ of $H_{\omega}$ for the $n \times n$ tridiagonal matrix

$$A=\left[\begin{array}{rrrrr} 2 & -1 & & & \\ -1 & 2 & -1 & & \\ & \ddots & \ddots & \ddots & \\ & & -1 & 2 & -1 \\ & & & -1 & 2 \end{array}\right]$$

[Hint: The eigenvectors and eigenvalues of $A$ are

$$\left.\left(\boldsymbol{u}_{k}\right)_{i}=\sin \frac{k i \pi}{n+1}, \quad i=1, \ldots, n, \quad \lambda_{k}(A)=4 \sin ^{2} \frac{k \pi}{2(n+1)}, \quad k=1, \ldots, n .\right]$$

(iii) 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 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}$.

(iv) Show that, for some $\omega$, the high frequency components $\left(\frac{n+1}{2} \leqslant k \leqslant n\right)$ of the error $e^{(\nu)}$ tend to zero much faster. 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)$.