The Gauss-Seidel Iteration Method

We recently saw The Jacobi Iteration Method for solving a system of linear equations $Ax = b$ where $A$ is an $n \times n$ matrix. We will now look at another method known as the Gauss-Seidel Iteration Method that is somewhat of an improvement of the Jacobi Iteration Method.

Once again, suppose that $x^{(0)} =\begin{bmatrix}x_1^{(0)}\\ x_2^{(0)}\\ \vdots\\ x_n^{(0)} \end{bmatrix}$ is an initial approximation to the solution $x$ of the following system of $n$ equations in $n$ unknowns:

(1)

\begin{align} \quad \begin{matrix} E(1): & a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & = & b_1\\ E(2): & a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & = & b_2\\ \vdots & \vdots & & \vdots & & \ddots & & \vdots & & \vdots\\ E(n): & a_{n1}x_1 & + & a_{n2}x_2 & + & \cdots & + & a_{nn}x_n & = & b_n & \end{matrix} \end{align}

For the Gauss-Seidel Method, we once again isolate the variable $x_i$ from equation $E(i)$ for $i = 1, 2, ..., n$.

(2)

\begin{align} \quad x_1 = \frac{b_1 - \left [ a_{12}x_2 + a_{13}x_3 + ... + a_{1n}x_n \right ]}{a_{11}} \\ x_2 = \frac{b_2 - \left [ a_{21}x_1 + a_{23}x_3 + ... + a_{2n}x_n \right ]}{a_{22}} \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x_n = \frac{b_n - \left [ a_{n1}x_1 + a_{n2}x_2 + ... + a_{n,n-1}x_{n-1} \right ]}{a_{nn}} \end{align}

We will now obtain a first approximation to the solution$x^{(1)}$ of the actual solution $x$ by using the Gauss-Seidel Iteration Method. We compute $x_1^{(1)}$ by plugging in the values of our initial solution approximation $x^{(0)}$. We then obtain an approximation to the entry $x_1^{(1)}$ of $x_1^{(1)}$. We use this entry and the remaining entries from $x^{(0)}$ to obtain an approximation of the entry $x_2^{(1)}$. We then use both $x_1^{(1)}$ and $x_2^{(1)}$ as well as the remaining entries from $x^{(0)}$ to obtain an approximation of the entry $x_3^{(1)}$ and so forth, and thus:

(3)

\begin{align} \quad x_1^{(1)} = \frac{b_1 - \left [ a_{12}x_2^{(0)} + a_{13}x_3^{(0)} + a_{14}x_4^{(0)} + ... + a_{1n}x_n^{(0)} \right ]}{a_{11}} \\ x_2^{(1)} = \frac{b_2 - \left [ a_{21}x_1^{(1)} + a_{23}x_3^{(0)} + a_{24}x_4^{(0)} + ... + a_{2n}x_n^{(0)} \right ]}{a_{22}} \\ x_3^{(1)} = \frac{b_3 - \left [ a_{31}x_1^{(1)} + a_{32}x_2^{(1)} + a_{34}x_4^{(0)} + ... + a_{3n}x_n^{(0)} \right ]}{a_{33}} \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x_n^{(1)} = \frac{b_n - \left [ a_{n1}x_1^{(1)} + a_{n2}x_2^{(1)} + a_{n3}x_3^{(1)} + ... + a_{n,n-1}x_{n-1}^{(1)} \right ]}{a_{nn}} \end{align}

In sigma notation we have that each component $x_i^{(1)}$ for $i = 1, 2, ..., n$ of $x^{(1)}$ is given by:

(4)

\begin{align} \quad x_i^{(1)} = \frac{b_i - \left [ \sum_{j=1}^{i-1} a_{ij}x_j^{(1)} + \sum_{j=i+1}^{n} a_{ij}x_j^{(0)} \right ]}{a_{ii}} \end{align}

To obtain the second approximation $x^{(2)}$ of $x$ using the Gauss-Seidel method, we would have that:

(5)

\begin{align} \quad x_1^{(2)} = \frac{b_1 - \left [ a_{12}x_2^{(1)} + a_{13}x_3^{(1)} + a_{14}x_4^{(1)} + ... + a_{1n}x_n^{(1)} \right ]}{a_{11}} \\ x_2^{(2)} = \frac{b_2 - \left [ a_{21}x_1^{(2)} + a_{23}x_3^{(1)} + a_{24}x_4^{(1)} + ... + a_{2n}x_n^{(1)} \right ]}{a_{22}} \\ x_3^{(2)} = \frac{b_3 - \left [ a_{31}x_1^{(2)} + a_{32}x_2^{(2)} + a_{34}x_4^{(1)} + ... + a_{3n}x_n^{(1)} \right ]}{a_{33}} \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x_n^{(2)} = \frac{b_n - \left [ a_{n1}x_1^{(2)} + a_{n2}x_2^{(2)} + a_{n3}x_3^{(2)} + ... + a_{n,n-1}x_{n-1}^{(2)} \right ]}{a_{nn}} \end{align}

In sigma notation we have that each component $x_i^{(2)}$ for $i = 1, 2, ..., n$ of $x^{(2)}$ is given by:

(6)

\begin{align} \quad x_i^{(2)} = \frac{b_i - \left [ \sum_{j=1}^{i-1} a_{ij}x_j^{(2)} + \sum_{j=i+1}^{n} a_{ij}x_j^{(1)} \right ]}{a_{ii}} \end{align}

We can continue approximating $x$ with these solutions in the hopes that the sequence of approximations with the Gauss-Seidel method converges to the true solution. Thus for $k ≥ 1$ and for $i = 1, 2, ..., n$, the $k^{\mathrm{th}}$ iteration of the Gauss-Seidel method yields:

(7)

\begin{align} \quad x_1^{(k)} = \frac{b_1 - \left [ a_{12}x_2^{(k-1)} + a_{13}x_3^{(k-1)} + a_{14}x_4^{(k-1)} + ... + a_{1n}x_n^{(k-1)} \right ]}{a_{11}} \\ x_2^{(k)} = \frac{b_2 - \left [ a_{21}x_1^{(k)} + a_{23}x_3^{(k-1)} + a_{24}x_4^{(k-1)} + ... + a_{2n}x_n^{(k-1)} \right ]}{a_{22}} \\ x_3^{(k)} = \frac{b_3 - \left [ a_{31}x_1^{(k)} + a_{32}x_2^{(k)} + a_{34}x_4^{(k-1)} + ... + a_{3n}x_n^{(k-1)} \right ]}{a_{33}} \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x_n^{(k)} = \frac{b_n - \left [ a_{n1}x_1^{(k)} + a_{n2}x_2^{(k)} + a_{n3}x_3^{(k)} + ... + a_{n,n-1}x_{n-1}^{(k)} \right ]}{a_{nn}} \end{align}

In sigma notation we have that each entry $x_i^{(k)}$ for $i = 1, 2, ..., n$ in the approximation $x^{(k)}$ of $x$ is given by:

(8)

\begin{align} \quad x_i^{(k)} = \frac{b_i - \left [ \sum_{j=1}^{i-1} a_{ij}x_j^{(k)} + \sum_{j=i+1}^{n} a_{ij}x_j^{(k-1)} \right ]}{a_{ii}} \end{align}