Gauss-Seidel iteration

This is a better method compared to Jacobi but at the cost of additional complexity.

$$\begin{array}{c}A=D-L-U\\ (D-L)x^{(k+1)}=b+U{x}^{(k)}\end{array}$$

Again this method belongs to the class of splitting methods.

Algorithm

for k = 1:maxiter
    for i = 1:n
        sigma = 0.
        for j = 1:n
            if j != i
                sigma += A[i,j] * x[j]
            end
        end
        x[i] = (b[i] - sigma)/A[i,i]
    end
end

Gauss-Seidel uses the most recent estimate of x[i], whereas Jacobi uses the previous x to compute xnew.

Convergence of Gauss-Seidel

Theorem 1. If $A$ is strictly row diagonally dominant

$$|a_{ii}|>\sum _{j\ne i}|a_{ij}|$$

then both Jacobi and Gauss-Seidel always converge. An analogous result holds if $A$ is strictly column diagonally dominant.

Theorem 2. If $A$ is a symmetric positive definite matrix, then Gauss-Seidel always converges.

• Gauss-Seidel typically converges faster than Jacobi.
• In many cases, the number of iterations with GS is about half that of Jacobi. See details in the textbook.
• However, GS is less parallel than Jacobi because of the additional data dependency.

Proof of Theorem 1.

Before proving the theorem we prove that diagonally dominant matrices cannot be singular. Consider matrix $A$ a strictly row diagonally dominant matrix. Assume that $A$ is singular. Then there exists $x\ne 0$ such that $Ax=0$. This implies, with $A=D-L-U,$ that

$$x=D^{-1}(L+U)x$$

So $D^{-1}(L+U)$ has eigenvalue 1. But from diagonal dominance, we also have that

$$\Vert D^{-1}(L+U){\Vert }_{\infty }<1$$

This is a contradiction. So $A$ cannot be singular.

We get a similar result for a strictly column diagonally dominant matrix. We show that $(L+U)D^{-1}$ has eigenvalue 1. But $\Vert (L+U)D^{-1}{\Vert }_1<1$, which is a contradiction.

Let us now prove our result for Gauss-Seidel. The iteration matrix in Gauss-Seidel is

$$G=(D-L{)}^{-1}U$$

Consider $\lambda$ an eigenvalue of $G$. Then there exists $x\ne 0$ such that

$$Ux=\lambda (D-L)x$$

So $\lambda D-\lambda L-U$ is singular. If $|\lambda |\ge 1$, then $\lambda D-\lambda L-U$ is (row or column) diagonally dominant. This is a contradiction. So

$$|\lambda |<1$$

So Gauss-Seidel converges for (row or column) diagonally dominant matrices.