Iterative Methods Jacobi and Gauss-Seidel

Iterative methods Jacobi and Gauss-Seidel in numerical analysis are based on the idea of successive approximations. This iterative method begins with one or two initial approximations of the roots, with a sequence of approximations x₁, x₂, x₃, …, x_k, …, as k → ∞, this sequence of roots converges to exact root 𝛼. For a system of equations Ax = B, we begin with an initial approximation of solution vector x = x_o, by which we get a sequence of solution vector x₁, x₂, …, x_k, … as k → ∞, this sequence converges to the solution x = A^{– 1}B.

The general iterative formulas can be given as:

x _{k + 1} = Hx_k ; k = 1, 2, 3, …

Where x_{k + 1} and x_k are approximations for the exact root of Ax = B at (k + 1)th and kth iterations. H is an iteration matrix that depends on A and B.

Also, read Direct Method Gauss Elimination.

Convergence of Iterative Methods: The sequence of iterates {x_k} is said to be converging to the exact root x, if

Where 𝜀 is a very small positive quantity called error tolerance or error bound.

The criterion to terminate Iteration Process: As we cannot perform the iteration process infinitely, we need some criterion to stop the iteration; we may use one or both of the criteria:

• The approximated root satisfies the given system of linear equations to a given accuracy.
• The magnitude of the difference between two successive iterates is negligible or smaller than a given error bound 𝜀.

Jacobi Method

Jacobi method or Jacobian method is named after German mathematician Carl Gustav Jacob Jacobi (1804 – 1851). The main idea behind this method is,

For a system of linear equations:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂

⠇

a_n1x₁ + a_n2x₂ + … + a_nnx_n = b_n

To find the solution to this system of equations Ax = B, we assume that the system of equations have a unique solution and there is no zero entry among the diagonal or pivot elements of the coefficient matrix A.

Now, we shall begin to solve equation 1 for x₁, equation 2 for x₂ and so on equation n for x_n, we get

x₁ = 1/a₁₁ [b₁ – a₁₂x₂ – a₁₃x₃ – … – a_1nx_n]

x₂ = 1/a₂₂ [b₂ – a₂₁x₁ – a₂₃x₃ – … – a_2nx_n]

⠇

x_n = 1/a_nn [b_n – a_n1x₁ – a_n3x₃ – … – a_{n n – 1}x_{n – 1}]

By making an initial guess for the solution x⁽⁰⁾ = (x₁⁽⁰⁾, x₂⁽⁰⁾, …, x_n⁽⁰⁾) and substituting these values only to the right hand side of the above equations we get first approximations x⁽¹⁾ = (x₁⁽¹⁾, x₂⁽¹⁾, …, x_n⁽¹⁾). Continuing this process iteratively we get sequence of approximations {x^(k)} such that as k → ∞, this sequence converges to exact solution of the system of equation up to a given error tolerance.

Learn more about Jacobian method in matrix form.

Convergence of Approximations

The sufficient condition for the convergence of the approximations obtained by Jacobi method is that the system of equations is diagonally dominant, that is, the coefficient matrix A is diagonally dominant.

The matrix A is said to be diagonally dominant if |a_ii | ≥ ∑ⁿ_{j = 1} |a_ij | for i ≠ j. That means, the absolute value of of the diagonal element is greater than or equal to the sum of all elements of the corresponding row.

How to Decide Initial Approximations?

To initiate the iterative process, we must assume some initial approximation of the possible solution for the given system of equations. If the given system of equations are diagonally dominant, then any initial approximation will converge to the exact solution. Still, if no suitable approximations are not available, then we may take x⁽⁰⁾ = 0 where x_i⁽⁰⁾ = 0 for all i. Then, the first approximation becomes x_i = b_i/a_ii for all i.

Gauss-Seidel Method

The Guass-Seidel method is a improvisation of the Jacobi method. This method is named after mathematicians Carl Friedrich Gauss (1777–1855) and Philipp L. Seidel (1821–1896). This modification often results in higher degree of accuracy within fewer iterations.

In Jacobi method the value of the variables is not modified until next iteration, whereas in Gauss-Seidel method the value of the variables are modified as soon as new value is evaluated. For instance, in Jacobi method the value of x_i^(k) is not modified until the (k + 1)th iteration but in Gauss-Seidel method the value of x_i^(k) changes in in kth iteration only.

Related Articles:

• Newton Raphson Method
• Runge-Kutta RK4 Method
• Fixed Point Iteration
• Bisection Method

Solved Examples

Example 1:

Solve the system of equations using the Jacobi Method

26x₁ + 2x₂ + 2x₃ = 12.6

3x₁ + 27x₂ + x₃ = – 14.3

2x₁ + 3x₂ + 17x₃ = 6.0

Obtain the result correct to three decimal places.

Solution:

First, check for the convergence of approximations,

26 > 2 + 2

27 > 3 + 1

17 > 2 + 3

Hence, the given system of equations are strongly diagonally dominant, which ensures the convergence of approximations. Let us take the initial approximation, x₁⁽⁰⁾ = 0, x₂⁽⁰⁾ = 0 and

x₃⁽⁰⁾ = 0

First Iteration:

x₁⁽¹⁾ = 1/26[12.6 – 2 × 0 – 2 × 0 ] = 0.48462

x₂⁽¹⁾ = 1/27[ – 14.3 – 3 × 0 – 1 × 0 ] = – 0.52963

x₃⁽¹⁾ = 1/17[6 – 2 × 0 – 3 × 0] = 0.35294

Second Iteration:

x₁⁽²⁾ = 1/26[12.6 – 2 × (– 0.52963 + 0.35294)] = 0.49821

x₂⁽²⁾ = 1/27[ – 14.3 – 3 × 0.48462 – 1 × 0.35294] = – 0. 59655

x₃⁽²⁾ = 1/17[6 – 2 × 0.48462 – 3 ×(– 0.52963)] = 0.38939

Likewise there will be modification in approximation with each iteration.

After the fifth iteration, we get |x₁⁽⁵⁾ – x₁⁽⁴⁾| = |0.50001 – 0.50000| = 0.00001

|x₂⁽⁵⁾ – x₂⁽⁴⁾| = | – 0.6 + 0.59999| = 0.00001

|x₃⁽⁵⁾ – x₃⁽⁴⁾| = | 0.4 – 0.39989| = 0.00011

Since, all the errors in magnitude are less than 0.0005, the required solution is

x₁ = 0.5, x₂ = – 0.6, x₃ = 0.4.

Example 2:

Solve the system of equations using the Gauss-Seidel Method

45x₁ + 2x₂ + 3x₃ = 58

–3x₁ + 22x₂ + 2x₃ = 47

5x₁ + x₂ + 20x₃ = 67

Obtain the result correct to three decimal places.

Solution:

First, check for the convergence of approximations,

45 > 2 + 3

22 > – 3 + 2

20 > 5 + 1

Hence, the given system of equations are strongly diagonally dominant, which ensures the convergence of approximations. Let us take the initial approximation, x₁⁽⁰⁾ = 0, x₂⁽⁰⁾ = 0 and

x₃⁽⁰⁾ = 0

First Iteration:

x₁⁽¹⁾ = 1/45[58 – 2 × 0 – 3 × 0 ] = 1.28889

x₂⁽¹⁾ = 1/22[ 47 + 3 × 1.28889 – 2 × 0 ] = 2.31212

x₃⁽¹⁾ = 1/20[67 – 5 × 1.28889 – 1 × 2.31212] = 2.91217.

Second Iteration:

x₁⁽²⁾ = 1/45[58 – 2 × 2.31212 – 3 × 2.91217 ] = 0.99198

x₂⁽²⁾ = 1/22[ 47 + 3 × 0.99198 – 2 × 2.91217 ] = 2.00689

x₃⁽²⁾ = 1/20[67 – 5 × 0.99198 – 1 × 2.00689] = 3.00166.

Likewise there will be modification in approximation with each iteration.

After the fourth iteration, we get |x₁⁽⁴⁾ – x₁⁽³⁾| = |1.0000 – 0.99958| = 0.00042

|x₂⁽⁴⁾ – x₂⁽³⁾| = |1.99999 + 1.99979| = 0.00020

|x₃⁽⁴⁾ – x₃⁽³⁾| = | 3.0000 – 3.00012| = 0.00012

Since, all the errors in magnitude are less than 0.0005, the required solution is

x₁ = 1.0, x₂ = 1.99999, x₃ = 3.0.

Rounding to three decimal places, we get x₁ = 1.0, x₂ = 2.0, x₃ = 3.0.

Practice Problems

1. Solve the system of equations using both Jacobi and Gauss-Seidel Method

5x₁ – 2x₂ + 3x₃ = –1

–3x₁ + 9x₂ + x₃ = 2

2x₁ – x₂ – 7x₃ = 3

Obtain the result correct to three decimal places.

2. Solve the system of equations

x₁ – 5x₂ = –4

7x₁ – x₂ = 6.