Last modified: June 08, 2019
This article is written in: ๐บ๐ธ
Gaussian Elimination
Gaussian elimination is a fundamental algorithmic procedure in linear algebra used to solve systems of linear equations, find matrix inverses, and determine the rank of matrices. The procedure systematically applies elementary row operations to transform a given matrix into an upper-triangular form (row echelon form), from which the solution to the system (if it exists and is unique) can be readily determined by back substitution.
From a conceptual viewpoint, Gaussian elimination provides a structured approach to eliminating unknowns step-by-step. Geometrically, each linear equation represents a hyperplane in nn-dimensional space, and the solution of the system corresponds to the intersection point(s) of these hyperplanes. Gaussian elimination successively "clears out" the variables, enabling a direct path to the solution (or revealing inconsistencies or infinite solution sets if they exist).
Mathematical Formulation
Consider a system of nn linear equations with nn unknowns:
Ax=b,Ax=b, where
A=[a11a12โฏa1na21a22โฏa2nโฎโฎโฑโฎan1an2โฏann]
x=[x1 x2 โฏ xn]
b=[b1 b2 โฏ bn]
We form the augmented matrix [A|b]:
[A|b]=[a11a12โฏa1nb1a21a22โฏa2nb2โฎโฎโฑโฎโฎan1an2โฏannbn]
The goal of Gaussian elimination is to perform a series of row operations to transform [A|b] into an upper-triangular form:
[U|c]=[u11u12โฏu1nc10u22โฏu2nc2โฎโฎโฑโฎโฎ00โฏunncn]
where U is an upper-triangular matrix. Once in this form, the solution x can be found by back substitution.
Derivation
The derivation of Gaussian elimination closely mirrors the logic of systematic elimination of variables from a set of equations:
I. Elimination of x1 from equations 2 through n:
Suppose the first pivot (the leading element in the first row) is a11. By using row operations, we can eliminate the x1-term from all equations below the first. This is achieved by subtracting suitable multiples of the first row from subsequent rows.
II. Elimination of x2 from equations 3 through n:
After the first step, the second row now has a leading coefficient (pivot) in the second column. Using this pivot, we eliminate the x2-term from all equations below the second.
III. Continue this process until the last pivot ann (in the n-th row) is in place. If at any stage a pivot is zero, we interchange rows (partial pivoting) to bring a nonzero pivot into the pivot position.
The end result is an upper-triangular system that can be solved starting from the last equation and moving upward (back substitution).
Algorithm Steps
Input: An augmented matrix [A|b] representing the system Ax=b.
Output: A solution vector x if it exists, or detection of no solution or infinitely many solutions.
Step-by-Step Procedure:
I. Form the augmented matrix:
[A|b]=[a11a12โฏa1nb1a21a22โฏa2nb2โฎโฎโฑโฎโฎan1an2โฏannbn]
II. Forward Elimination (to reach upper-triangular form):
For i=1 to n:
II.I. Partial Pivoting (if desired): Find the row (pivotRow) below (and including) the current row i that has the largest absolute value in column i. Swap the current row i with pivotRow to reduce numerical instability.
II.II. Pivot Normalization: Divide the entire i-th row by aii (the pivot) to make the pivot element equal to 1.
III.III. Elimination: For each row j>i, subtract aji times the i-th row from the j-th row to make the elements below the pivot zero.
After these steps, the matrix is in row echelon form:
[U|c]=[1โโฏโโ01โฏโโโฎโฎโฑโฎโฎ00โฏ1โ]
where โ represents arbitrary numbers obtained during the process.
III. Back Substitution:
Starting from the last equation:
For i=n down to 1:
xi=ciโnโk=i+1uikxk.
Since uii=1 after normalization, xi can be directly computed. (If not normalized, divide by uii.)
This process yields the solution vector x.
Example
Given System:
2x+yโz=8,โ3xโy+2z=โ11,โ2x+y+2z=โ3.
I. Augmented Matrix:
[A|b]=[21โ18โ3โ12โ11โ212โ3]
II. Forward Elimination:
Pivot in first row is a11=2. Normalize the first row by dividing by 2:
[10.5โ0.54โ3โ12โ11โ212โ3]
Eliminate x-terms in row 2 and row 3 using row 1: For row 2: Add 3 times row 1:
(โ3)R1+R2โR2โนR2=[00.50.51]
For row 3: Add 2 times row 1:
(2)R1+R3โR3โนR3=[0215]
Now the matrix is:
[10.5โ0.5400.50.510215]
Next pivot is a22=0.5. Normalize the second row by dividing by 0.5:
[10.5โ0.5401120215]
Eliminate below the second pivot:
For row 3: subtract 2 times row 2 from row 3:
R3โ2R2โนR3=[00โ11]
Now the matrix is in upper-triangular form:
[U|c]=[10.5โ0.54011200โ11]
III. Back Substitution:
From the last equation: โ1โ z=1โนz=โ1. Substitute z=โ1 into second equation:
y+1(โ1)=2โนy=3.
Substitute y=3,z=โ1 into first equation:
x+0.5(3)โ0.5(โ1)=4โนx+1.5+0.5=4โนx=2.
The solution is x=(2,3,โ1)โค.
Advantages
- Gaussian elimination has general applicability to any nรn system of linear equations, and it can also identify cases where no solution or infinitely many solutions exist in non-square systems.
- The method serves as a foundation for advanced techniques like LU decomposition and QR decomposition, forming a building block for many numerical algorithms.
- It can be used to determine the rank of a matrix and to compute the inverse of a matrix when applicable by applying the procedure to the augmented matrix [A|I].
Limitations
- Numerical instability is a concern due to round-off errors, particularly without pivoting. Partial or full pivoting mitigates this issue but may require additional computational steps.
- The methodโs computational cost, proportional to O(n3) operations, can become prohibitive for large-scale systems, making it less efficient than iterative methods for such cases.
- A zero pivot element halts the process unless row interchanges are performed. Pivoting is necessary to avoid division by zero and to maintain algorithmic stability.