I am studying for my last Qualifying exam and came across two related problems that I can't seem to solve, both are Iterative Methods for Linear Systems.

Given A is a strictly diagonally dominant matrix, then show that the Gauss Seidel and Jacobi methods converge.

Jacobi:

Let $\displaystyle A = D + R$ where

$\displaystyle D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\

0 & a_{22} & \cdots & 0 \\

\vdots & \vdots & \ddots & \vdots \\

0 & 0 & \cdots & a_{nn} \\\end{bmatrix}$

$\displaystyle R = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\

a_{21} & 0 & \cdots & a_{2n} \\

\vdots & \vdots & \ddots & \vdots \\

a_{n1} & a_{n2} & \cdots & 0 \\\end{bmatrix}$

Thus,

$\displaystyle Ax = b \Rightarrow (D+R)x = b \Rightarrow x = D^{-1}b - D^{-1}R x$

and the iterative method is given by

$\displaystyle x^{(k+1)} = D^{-1}b - D^{-1}R x^{(k)}$.

Gauss-Seidel:

Let $\displaystyle A = L + U$ where

$\displaystyle L = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\

a_{21} & a_{22} & \cdots & 0 \\

\vdots & \vdots & \ddots & \vdots \\

a_{n1} & a_{n2} & \cdots & a_{nn} \\\end{bmatrix}$

$\displaystyle U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\

0 & 0 & \cdots & a_{2n} \\

\vdots & \vdots & \ddots & \vdots \\

0 & 0 & \cdots & 0 \\\end{bmatrix}$

Thus,

$\displaystyle Ax = b \Rightarrow (L+U)x = b \Rightarrow x = L^{-1}b - L^{-1}U x$

and the iterative method is given by

$\displaystyle x^{(k+1)} = L^{-1}b - L^{-1}U x^{(k)}$.

I have proven that if we have an iterative method

$\displaystyle X^{(k+1)} = Q X^{(k)} + d$

converges if $\displaystyle \|Q\| < 1$ where $\displaystyle \|\cdot\|$ is a matrix norm. Thus, all I would have to do is prove that $\displaystyle \|-D^{-1}R\| < 1$ and $\displaystyle \|-L^{-1}U\| < 1$.

However, I have a theorem that says the following are equivalent:

1.$\displaystyle X^{(k+1)} = Q X^{(k)} + d$ converges

2. $\displaystyle \rho(Q) < 1$

So if I can prove that the spectral radius is less than one I have shown that the method converges. I don't really care which way I prove this, but I can't figure out how to do it.