Math 6610 • Analysis of Numerical Methods I

Fixed-point iteration for linear systems.
\begin{enumerate}

\item
For \(T \in \mathbb{R}^{m \times m}\) and any matrix norm, show that \(\|T^k\| \to 0\) as \(k \to \infty\) if and
only if \(\rho(T) < 1\) where \(\rho(T)\) is the spectral radius of \(T\). Do not assume that
the matrix \(T\) is diagonalizable.


\item
Suppose \(A \in \mathbb{R}^{m \times m}\) is nonsingular, that \(b \in \mathbb{R}^m\), and that \(Ax = b\). Suppose
that \(x = T x + c\) is a fixed point problem equivalent to this linear system. What
are the implications of part (a) for the convergence of the fixed-point iteration
\(x^{(k+1)} = T x^{(k)} + c\) to the solution \(x\) of the linear system?


\item
Suppose \(A\) is a symmetric, weakly diagonally dominant, and irreducible matrix.
Define the Jacobi iterative method for solving \(Ax = b\), and show that this
method converges to the solution of the linear system starting with any initial
vector \(x^{(0)}\). (Hint: You might find it helpful to use the fact that a matrix which
is both weakly diagonally dominant and irreducible is nonsingular.)

Recall that: An \(m \times m\) matrix \(A\) is irreducible iff for all
\(i,j \in \{1,2,\ldots,m\}\), \(i \ne j\), either \(a_{ij} \ne 0\) or there are
\(i_1,i_2,\ldots,i_s\), each between 1 and \(m\), such that
\(a_{i,i_1}a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_s,j} \ne 0\).
A symmetric \(m \times m\) matrix \(A\) is weakly diagonally dominant if
\(|a_{ii}| \ge \sum_{j\ne i}|a_{ij}|\) for all \(i\), and
\(|a_{ii}| > \sum_{j\ne i}|a_{ij}|\) for at least one \(i\).

\end{enumerate}