| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
107 |
II |
2012 |
Numerical Analysis |
|
Paper 1, Section II, D |
2012 |
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)$.