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