Gauss-Seidel Method

Iterative Methods for Linear Algebraic Systems

Let where they are respectively: lower triangle, diagonal and upper triangle.
We take
We obtain the next iteration by solving:

So

Note that there is no need to calculate the inverse explicitly,
because we can calculate the components of by forward substitution.

Theorem

If is Strictly diagonally dominant, then the Gauss-Seidel method converges.

Proof

Note so
Thus we need to prove
Let be an eigenvalue of .
Then

where the second line is obtained by multiplying by
Let
Suppose
Then is also strictly diagonally dominant.
So has evals with strictly positive real part by Gershgorin Theorem.
This is a contradiction, thus
So .

Theorem

If is symmetric positive definite, then the Gauss-Seidel method converges.

Proof

Note
Now is also symmetric positive definite as
Use The Householder-John Theorem to find