Gauss-Jacobi and Gauss-Seidel Methods: Theory and a Detailed Example
The Gauss-Jacobi and Gauss-Seidel methods are fundamental iterative algorithms used in numerical linear algebra to solve systems of linear equations. They are particularly useful for very large systems where direct methods (like Gaussian elimination) would be too slow or require too much memory. This is common when solving partial differential equations in engineering and physics.
Methods
Both methods aim to solve a system of linear equations in the form \(Ax = b\), where \(A\) is the coefficient matrix, \(x\) is the vector of variables, and \(b\) is the vector of constants. Instead of solving directly, they start with an initial guess (often all zeros) and iteratively refine it until the solution converges.
To do this, we rewrite each equation from the system to solve for one variable:
\[ \begin{align*} x_1 &= \frac{1}{a_{11}} (b_1 - a_{12}x_2 - a_{13}x_3) \\ x_2 &= \frac{1}{a_{22}} (b_2 - a_{21}x_1 - a_{23}x_3) \\ x_3 &= \frac{1}{a_{33}} (b_3 - a_{31}x_1 - a_{32}x_2) \end{align*} \]The difference between the two methods lies in how they use the results from each step. Let's use the superscript \( (k) \) to denote the iteration number.
-
The Gauss-Jacobi Method
The Rule: In each iteration, calculate the new value for every variable using only the values from the previous iteration, \(x^{(k)}\).
The Formula:
\[ \begin{align*} x_1^{(k+1)} &= \frac{1}{a_{11}} (b_1 - a_{12}x_2^{(k)} - a_{13}x_3^{(k)}) \\ x_2^{(k+1)} &= \frac{1}{a_{22}} (b_2 - a_{21}x_1^{(k)} - a_{23}x_3^{(k)}) \\ x_3^{(k+1)} &= \frac{1}{a_{33}} (b_3 - a_{31}x_1^{(k)} - a_{32}x_2^{(k)}) \end{align*} \] -
The Gauss-Seidel Method
The Rule: In each iteration, use the most recently computed values for the variables as soon as they are available within the current iteration, \(x^{(k+1)}\).
The Formula:
\[ \begin{align*} x_1^{(k+1)} &= \frac{1}{a_{11}} (b_1 - a_{12}x_2^{(k)} - a_{13}x_3^{(k)}) \\ x_2^{(k+1)} &= \frac{1}{a_{22}} (b_2 - a_{21}\mathbf{x_1^{(k+1)}} - a_{23}x_3^{(k)}) \\ x_3^{(k+1)} &= \frac{1}{a_{33}} (b_3 - a_{31}\mathbf{x_1^{(k+1)}} - a_{32}\mathbf{x_2^{(k+1)}}) \end{align*} \]
A Worked Example
Problem Setup
1. Problem Statement
Solve the following system of linear equations starting with an initial guess of \(x_1=0, x_2=0, x_3=0\).
\[ \begin{align*} 26x_1 + 2x_2 + 2x_3 &= 12.6 \\ 3x_1 + 27x_2 + 1x_3 &= -14.3 \\ 2x_1 + 3x_2 + 17x_3 &= 6.0 \end{align*} \]2. Convergence Check
The system is strictly diagonally dominant, which guarantees convergence for both methods.
- Row 1: \(|26| > |2| + |2| \implies 26 > 4\) (True)
- Row 2: \(|27| > |3| + |1| \implies 27 > 4\) (True)
- Row 3: \(|17| > |2| + |3| \implies 17 > 5\) (True)
Method 1: Gauss-Jacobi Method (Complete Workings)
Step-by-Step Workings
First Iteration (k=1)
- \(x_1^{(1)} = (12.6 - 2(0) - 2(0)) / 26 = \mathbf{0.48462}\)
- \(x_2^{(1)} = (-14.3 - 3(0) - 0) / 27 = \mathbf{-0.52963}\)
- \(x_3^{(1)} = (6.0 - 2(0) - 3(0)) / 17 = \mathbf{0.35294}\)
Second Iteration (k=2)
- \(x_1^{(2)} = (12.6 - 2(-0.52963) - 2(0.35294)) / 26 = \mathbf{0.49821}\)
- \(x_2^{(2)} = (-14.3 - 3(0.48462) - 0.35294) / 27 = \mathbf{-0.59655}\)
- \(x_3^{(2)} = (6.0 - 2(0.48462) - 3(-0.52963)) / 17 = \mathbf{0.38939}\)
Third Iteration (k=3)
- \(x_1^{(3)} = (12.6 - 2(-0.59655) - 2(0.38939)) / 26 = \mathbf{0.50055}\)
- \(x_2^{(3)} = (-14.3 - 3(0.49821) - 0.38939) / 27 = \mathbf{-0.59941}\)
- \(x_3^{(3)} = (6.0 - 2(0.49821) - 3(-0.59655)) / 17 = \mathbf{0.39960}\)
Fourth Iteration (k=4)
- \(x_1^{(4)} = (12.6 - 2(-0.59941) - 2(0.39960)) / 26 = \mathbf{0.49999}\)
- \(x_2^{(4)} = (-14.3 - 3(0.50055) - 0.39960) / 27 = \mathbf{-0.60005}\)
- \(x_3^{(4)} = (6.0 - 2(0.50055) - 3(-0.59941)) / 17 = \mathbf{0.39983}\)
Fifth Iteration (k=5)
- \(x_1^{(5)} = (12.6 - 2(-0.60005) - 2(0.39983)) / 26 = \mathbf{0.50002}\)
- \(x_2^{(5)} = (-14.3 - 3(0.49999) - 0.39983) / 27 = \mathbf{-0.59999}\)
- \(x_3^{(5)} = (6.0 - 2(0.49999) - 3(-0.60005)) / 17 = \mathbf{0.40001}\)
Conclusion for Gauss-Jacobi: The method has converged. The final solution is (0.5, -0.6, 0.4).
Method 2: Gauss-Seidel Method (Complete Workings)
Step-by-Step Workings
First Iteration (k=1)
- \(x_1^{(1)} = (12.6 - 2(0) - 2(0)) / 26 = \mathbf{0.48462}\)
- \(x_2^{(1)} = (-14.3 - 3(\boldsymbol{0.48462}) - 0) / 27 = \mathbf{-0.58348}\)
- \(x_3^{(1)} = (6.0 - 2(\boldsymbol{0.48462}) - 3(\boldsymbol{-0.58348})) / 17 = \mathbf{0.39890}\)
Second Iteration (k=2)
- \(x_1^{(2)} = (12.6 - 2(-0.58348) - 2(0.39890)) / 26 = \mathbf{0.49881}\)
- \(x_2^{(2)} = (-14.3 - 3(\boldsymbol{0.49881}) - 0.39890) / 27 = \mathbf{-0.59983}\)
- \(x_3^{(2)} = (6.0 - 2(\boldsymbol{0.49881}) - 3(\boldsymbol{-0.59983})) / 17 = \mathbf{0.40011}\)
Third Iteration (k=3)
- \(x_1^{(3)} = (12.6 - 2(-0.59983) - 2(0.40011)) / 26 = \mathbf{0.49998}\)
- \(x_2^{(3)} = (-14.3 - 3(\boldsymbol{0.49998}) - 0.40011) / 27 = \mathbf{-0.60000}\)
- \(x_3^{(3)} = (6.0 - 2(\boldsymbol{0.49998}) - 3(\boldsymbol{-0.60000})) / 17 = \mathbf{0.40000}\)
Conclusion for Gauss-Seidel: The method converged much faster. The final solution is (0.5, -0.6, 0.4).
