The Algorithm for The Jacobi Iteration Method

We will now look at the algorithm for the Jacobi Iteration method in solving the system $Ax = b$.

Obtain an $n \times n$ matrix $A$ and an $n \times 1$ matrix $b$. Let $x^{(0)} = \begin{bmatrix} x_1^{(0)}\\ x_2^{(0)}\\ \vdots \\ x_n^{(0)}\\ \end{bmatrix}$ be an initial approximation to the solution to the system $Ax = b$. Obtain a maximum number of iterations and a prescribed accuracy value $\epsilon$ ensuring that the maximum difference between corresponding components is less than $\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_{1n}x_n^{(k-1)} \right ]}{a_{11}} \\ x_2^{(k)} = \frac{b_2 - \left [ a_{21}x_1^{(k-1)} + a_{23}x_3^{(k-1)} + ... + a_{2n}x_n^{(k-1)} \right ]}{a_{22}} \\ \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-1)} + a_{n2}x_2^{(k-1)} + ... + a_{n,n-1}x_{n-1}^{(k-1)} \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.