The Algorithm for The Gauss-Seidel Iteration Method

We will now look at the algorithm for the Gauss-Seidel Iteration method for solving the system of equations $Ax = b$.

Let $A$ be an $n \times n$ matrix and let $b$ be an $n \times 1$ matrix. Suppose that a solution exists to the linear system $Ax = b$. Obtain an initial approximation $x^{(0)} = \begin{bmatrix} x_1^{(0)}\\ x_2^{(0)}\\ \vdots \\ x_n^{(0)}\\ \end{bmatrix}$ of the solution to this system, as well as a maximum number of iterations for the Gauss-Seidel method and a desired level of accuracy $\epsilon$.

For each $k = 1, 2, ...$ up to the maximum number of iterations prescribed:

Step 1: Obtain the approximations $x^{(k)}$ component wise by:

(1)

\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 \quad \vdots \quad \quad \quad \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}

Step 2: Check the accuracy of the approximations. Check to see if:

(2)

\begin{align} \quad \| x^{(k)} - x^{(k-1)} \|_{\infty} = \max_{1 ≤ i ≤ n} \mid x_i^{(k)} - x_i^{(k-1)} \mid \: < \: \epsilon \end{align}

If the above is true, then stop the iteration process. $x^{(n)}$ is an approximation of the solution with the desired accuracy. If no, then continue the iterations to obtain successive approximations of the solution. If after the maximum number of iterations, the accuracy $\epsilon$ is not achieved, then stop the iteration process and print out a failure message.