Gaussian Elimination
Gaussian Elimination or Row Reduction is a method for solving a System of Linear Equations
- it corresponds to elimination of variables in the system
- if a matrix $A$ that we reduce is non-singular and invertible, then we always have a solution
- a by-product of Gaussian Elimination is LU Factorization
Row Elimination
- First, do the forward elimination to reduce the matrix to triangular
- Then we do the back-substitution to find the solution
- When we multiply a row on some constant $c$ and subtract from any other row, we get an equivalent system
Elimination by Example
We have the following system with 3 equations and 3 unknowns:
$\left\{\begin{array}{l}
x + 2y + z = 2\\
3x + 8y + z = 12 \\
4y + z = 2
\end{array}\right.$
Matrix form:
- [math]\underbrace{\begin{bmatrix}
1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}}_{A} \cdot \underbrace{\begin{bmatrix}
x \\ y \\ z
\end{bmatrix}}_{\mathbf x} =
\underbrace{\begin{bmatrix}
2 \\ 12 \\ 2
\end{bmatrix}}_{\mathbf b}[/math]
Forward elimination
So, first let's see how elimination works
- i.e. concentrate only on the matrix $A$
- [math]A = \begin{bmatrix}
1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]
Let's proceed
- at each step
- multiply the $i$th equation by the right number and subtract it from the equations below
- s.t. there's 0 for the first column in all other rows
- so we want to knock out the $x_i$ part of the equation, or "eliminate" $x_i$
- [math]\begin{bmatrix}
\boxed 1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]. $\boxed 1$ is the 1st pivot
- step 2.1: clean cell $a_{21}$:
- [math]\begin{bmatrix}
\boxed 1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix} \sim \begin{bmatrix}
\boxed 1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}[/math]
- multiplying row 1 by 3 will knock out $x$ from the 2nd equation
- step 3.1: clean cell $a_{21}$
- [math]\begin{bmatrix}
\boxed 1 & 2 & 1\\
0 & \boxed 2 & -2\\
0 & 4 & 1
\end{bmatrix}[/math], $\boxed 2$ is the 2nd pivot
- step 3.2
- [math]\begin{bmatrix}
\boxed 1 & 2 & 1\\
0 & \boxed 2 & -2\\
0 & 4 & 1
\end{bmatrix} \sim \begin{bmatrix}
\boxed 1 & 2 & 1\\
0 & \boxed 2 & -2\\
0 & 0 & \boxed 5
\end{bmatrix}[/math]
- [math]\begin{bmatrix}
\boxed 1 & 2 & 1\\
0 & \boxed 2 & -2\\
0 & 0 & \boxed 5
\end{bmatrix}[/math], $\boxed 5$ - it's 3rd pivot
The matrix is now in the upper-triangular form $U$
When does it fail?
Not always we are able to do the forward elimination
0 at a Pivot position:
- suppose the first pivot is 0:
- [math]\begin{bmatrix}
\boxed 0 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]
- But here it doesn't mean that we can't solve the system: we can switch the rows and continue:
- [math]\begin{bmatrix}
\boxed 3 & 8 & 1\\
0 & 2 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]
- so, if there's a 0 at the pivot position, try to exchange rows
- if there's no rows with non-zero values at the pivot position - the elimination fails
- there's no solution to the system
Augmented Matrix
But we shouldn't forget about $\mathbf b$!
- $A$ augmented is [math]\begin{bmatrix}
\mathop{a_1}\limits_|^| \mathop{a_2}\limits_|^| ... \mathop{a_n}\limits_|^| \ \Bigg| \ \mathop{\mathbf b}\limits_|^|
\end{bmatrix}[/math]: matrix $A$ with column $\mathbf b$ stacked to the right
- $A$ augmented: [math]\left[\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
3 & 8 & 1 & 12\\
0 & 4 & 1 & 2
\end{array}\right][/math]
- the right part $\mathbf b$ also changes as we go through elimination
- [math]\left[\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
3 & 8 & 1 & 12\\
0 & 4 & 1 & 2
\end{array}\right] \to \left[\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 4 & 1 & 2
\end{array}\right] \to \left[\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -2 & 6\\
0 & 0 & 5 & -10
\end{array}\right][/math]
- let $\mathbf c$ be the result of applying elimination to $\mathbf b$
Back Substitution
After we forward-eliminated variables of augmented $A$, we can do back substitution:
[math]\left[\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
0 & 2 & -6 & 6\\
0 & 0 & 5 & -10
\end{array}\right][/math]
- It means that our system is
[math]\left\{\begin{array}{rl}
x + 2y + z & = 2\\
2y - 2z & = 6 \\
5z & = -10
\end{array}\right.[/math]
Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$
- we get $z = -2, y = -1, x =2$
- it's easy to solve because the matrix is triangular
Elimination: Matrix Form
We can write these elimination steps in matrix form
- [math]\begin{bmatrix}
1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]
- the first step of the elimination was to take first and last rows unchanged, and subtract 3 times 1st row from the second.
- Can we write it with Matrix Multiplication?
- [math]\begin{bmatrix}
1 & 0 & 0\\
? & ? & ?\\
0 & 0 & 1
\end{bmatrix} \times \begin{bmatrix}
1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix}[/math]
- The first and last rows remain unchanged - hence we have [math]\begin{bmatrix}
1\\
?\\
0
\end{bmatrix}[/math] and [math]\begin{bmatrix}
0\\
?\\
1
\end{bmatrix}[/math]
- what should we put instead of $[? \ ? \ ?]$ so multiplication takes us from one matrix to another?
- [math]\begin{bmatrix}
1 & 0 & 0\\
\boxed{-3} & 1 & 0\\
0 & 0 & 1
\end{bmatrix}[/math]
- we want to subtract 3 times row 1 from row 2:
- [math]\begin{bmatrix}
1 & 0 & 0\\
\boxed{-3} & 1 & 0\\
0 & 0 & 1
\end{bmatrix} \times \begin{bmatrix}
1 & 2 & 1\\
3 & 8 & 1\\
0 & 4 & 1
\end{bmatrix} = \begin{bmatrix}
1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}[/math]
- let $E_{21}$ be the matrix that's used for step 2,1 of the elimination
- [math]E_{21} A = \begin{bmatrix}
1 & 2 & 1\\
0 & 2 & -2\\
0 & 4 & 1
\end{bmatrix}[/math]
- we continue this way until we transform $A$ to $U$
- so we have $E_{21} (E_{21} A) = U$
- or $\underbrace{(E_{21} E_{21})}_E A = EA = U $
- This a part of $LU$ Factorization
What if we need to exchange rows?
Implementations
Python
Simple elimination with no permutation:
A = np.array([[60, 91, 26], [60, 3, 75], [45, 90, 31]], dtype='float')
b = np.array([1, 0, 0])
Ab = np.hstack([A, b.reshape(-1, 1)])
n = len(b)
for i in range(n):
a = Ab[i]
for j in range(i + 1, n):
b = Ab[j]
m = a[i] / b[i]
Ab[j] = a - m * b
for i in range(n - 1, -1, -1):
Ab[i] = Ab[i] / Ab[i, i]
a = Ab[i]
for j in range(i - 1, -1, -1):
b = Ab[j]
m = a[i] / b[i]
Ab[j] = a - m * b
x = Ab[:, 3]
See Also
Sources