Unit V: Gaussian Elimination, Gauss-Jordan, and Iterative Methods
Gaussian Elimination Method
Gaussian elimination is a direct method used to solve a system of linear equations by transforming the augmented matrix into an upper triangular matrix using elementary row operations, followed by back-substitution.
Steps for Gaussian Elimination
- Write the system of linear equations in the matrix form AX = B.
- Construct the augmented matrix [A | B].
- Apply elementary row operations to reduce the coefficient matrix A to an upper triangular form.
- Once the upper triangular form is achieved, use back-substitution to find the values of the variables starting from the last variable.
Elementary Row Operations
- Interchanging any two rows.
- Multiplying a row by a non-zero scalar.
- Adding a multiple of one row to another row.
Definition: An upper triangular matrix is a square matrix in which all the elements below the main diagonal are zero.
Practical Example: Consider the system:
- x + y + z = 6
- 2x + 3y + z = 11
- x + 2y + 3z = 14
The augmented matrix is:
[ 1 1 1 | 6 ]
[ 2 3 1 | 11 ]
[ 1 2 3 | 14 ]
Applying row operations R2 → R2 - 2R1 and R3 → R3 - R1:
[ 1 1 1 | 6 ]
[ 0 1 -1 | -1 ]
[ 0 1 2 | 8 ]
Applying R3 → R3 - R2:
[ 1 1 1 | 6 ]
[ 0 1 -1 | -1 ]
[ 0 0 3 | 9 ]
Now, using back-substitution:
- 3z = 9 → z = 3
- y - z = -1 → y - 3 = -1 → y = 2
- x + y + z = 6 → x + 2 + 3 = 6 → x = 1
Solution: x = 1, y = 2, z = 3.
Exam-Oriented Notes
Always verify your back-substitution step by substituting the computed values back into the original equations. Watch out for arithmetic sign errors during row scaling.
Gauss-Jordan Method
The Gauss-Jordan method is a variation of Gaussian elimination where the augmented matrix is reduced to a diagonal matrix (or identity matrix) instead of an upper triangular matrix.
Steps for Gauss-Jordan Method
- Construct the augmented matrix [A | B].
- Apply elementary row operations to transform the coefficient matrix A into an identity matrix (or diagonal matrix).
- Read the values of the variables directly from the final column without needing back-substitution.
Comparison: Gaussian Elimination vs Gauss-Jordan
| Feature | Gaussian Elimination | Gauss-Jordan Method |
|---|---|---|
| Final Matrix Form | Upper Triangular Matrix | Diagonal / Identity Matrix |
| Solution Extraction | Requires Back-Substitution | Directly from Final Column |
| Computational Work | Fewer operations | More operations |
Common Mistake: Stopping early when zeros are obtained below the diagonal, forgetting that Gauss-Jordan requires zeros above the main diagonal as well.
Pivoting Techniques
Pivoting is the process of selecting a strategic element as a pivot to avoid division by zero and to minimize round-off errors during numerical computation.
Types of Pivoting
- Without Pivoting: Uses diagonal elements strictly in their given order as pivots. Fails if a pivot element is zero.
- Partial Pivoting: Searches the current column from the diagonal element downward for the largest absolute value, then swaps that row with the current row.
- Complete Pivoting: Searches both the current row and column for the largest absolute element and performs both row and column swaps. (Rarely used in manual computations due to bookkeeping complexity).
Important Observation: Partial pivoting guarantees numerical stability in most practical engineering and scientific applications by keeping multiplier values ≤ 1 in magnitude.
Jacobi and Gauss-Seidel Iterative Methods
Iterative methods are indirect methods used for solving large sparse systems of linear equations. They start with an initial guess and successively improve the solution until convergence is reached.
Jacobi Iterative Method
In the Jacobi method, the value of each variable at the current iteration is calculated using only the values of the variables from the previous iteration.
Given a system rewritten for each variable:
x1(k+1) = (b1 - a12x2(k) - a13x3(k)) / a11
All updated values are held until a complete iteration cycle finishes.
Gauss-Seidel Iterative Method
The Gauss-Seidel method is an improvement over the Jacobi method. It uses the most recently computed values as soon as they are available within the same iteration cycle.
x1(k+1) = (b1 - a12x2(k) - a13x3(k)) / a11
x2(k+1) = (b2 - a21x1(k+1) - a23x3(k)) / a22
Notice how x1(k+1) is immediately used to calculate x2(k+1).
Comparison: Jacobi vs Gauss-Seidel
| Parameter | Jacobi Method | Gauss-Seidel Method |
|---|---|---|
| Value Usage | Uses old values for the entire iteration | Uses latest available updated values immediately |
| Convergence Rate | Slower convergence | Faster convergence (roughly twice as fast) |
| Memory Requirement | Requires two storage arrays (old and new) | Can be implemented in-place using a single array |
Convergence of Iterative Methods
An iterative method is said to converge if the successive approximations get closer and closer to the exact solution as the number of iterations increases.
Definition: A matrix A is strictly diagonally dominant if in every row, the magnitude of the diagonal element is strictly greater than the sum of the magnitudes of all other non-diagonal elements.
|aii| > ∑j ≠ i |aij|
Convergence Criteria
- A sufficient condition for the convergence of both Jacobi and Gauss-Seidel methods is that the coefficient matrix A must be strictly diagonally dominant.
- The Gauss-Seidel method converges if the Jacobi method converges, and it generally converges faster.
Practical Application: Iterative methods are heavily used in solving partial differential equations and large-scale finite element analysis models where direct methods consume excessive memory.