Math 6610 • Analysis of Numerical Methods I

{Iterative Methods}

Consider the fixed-point iteration
\[
  u^{(k+1)}=Tu^{(k)}+c
\]
for finding a solution of the problem
\[
  u=Tu+c
\]
where \(T\) is an \(m\times m\) real matrix and \(c\) is a real \(m\)-vector. It is a
fact that the fixed-point iteration converges for any choice of starting point
\(u^{(0)}\) if and only if the spectral radius of \(T\), \(\rho(T)\), satisfies
\(\rho(T)<1\).

\partitem{a} Consider a linear system \(Ax=b\) where \(A\) is strictly diagonally
dominant (that is, \(a_{ii}>\sum_{j\ne i}|a_{ij}|\) for all \(i\)). Show that the
Gauss-Seidel iterative scheme converges for this problem. Describe a situation
in numerical analysis where a strictly diagonally-dominant matrix system arises.

\partitem{b} For convergence of fixed-point iteration from any starting point,
is it sufficient that \(\|T\|<1\) for some operator norm \(\|\cdot\|\)? Justify your
answer.

\newpage