| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
105 |
II |
2016 |
Numerical Analysis |
|
Paper 3, Section II, B |
2016 |
(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]$