Line 22: Line 22:
  
 
Matrix form:
 
Matrix form:
* $\underbrace{\begin{bmatrix}
+
* <math>\underbrace{\begin{bmatrix}
 
1 & 2 & 1\\  
 
1 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
Line 31: Line 31:
 
\underbrace{\begin{bmatrix}
 
\underbrace{\begin{bmatrix}
 
2 \\ 12 \\ 2
 
2 \\ 12 \\ 2
\end{bmatrix}}_{\mathbf b}$
+
\end{bmatrix}}_{\mathbf b}</math>
  
  
Line 38: Line 38:
 
So, first let's see how elimination works  
 
So, first let's see how elimination works  
 
* i.e. concentrate only on the matrix $A$
 
* i.e. concentrate only on the matrix $A$
* $A = \begin{bmatrix}
+
* <math>A = \begin{bmatrix}
 
1 & 2 & 1\\  
 
1 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
  
  
Line 50: Line 50:
 
** s.t. there's 0 for the first column in all other rows
 
** 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$
 
** so we want to knock out the $x_i$ part of the equation, or "eliminate" $x_i$
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
\boxed 1 & 2 & 1\\  
 
\boxed 1 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$. $\boxed 1$ is the 1st pivot  
+
\end{bmatrix}</math>. $\boxed 1$ is the 1st pivot  
 
* step 2.1: clean cell $a_{21}$:
 
* step 2.1: clean cell $a_{21}$:
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
\boxed 1 & 2 & 1\\  
 
\boxed 1 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
Line 64: Line 64:
 
0 & 2 & -2\\  
 
0 & 2 & -2\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* multiplying row 1 by 3 will knock out $x$ from the 2nd equation
 
* multiplying row 1 by 3 will knock out $x$ from the 2nd equation
 
* step 3.1: clean cell $a_{21}$
 
* step 3.1: clean cell $a_{21}$
 
** already 0, continuing
 
** already 0, continuing
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
\boxed 1 & 2 & 1\\  
 
\boxed 1 & 2 & 1\\  
 
0 & \boxed 2 & -2\\  
 
0 & \boxed 2 & -2\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$, $\boxed 2$ is the 2nd pivot
+
\end{bmatrix}</math>, $\boxed 2$ is the 2nd pivot
 
* step 3.2
 
* step 3.2
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
\boxed 1 & 2 & 1\\  
 
\boxed 1 & 2 & 1\\  
 
0 & \boxed 2 & -2\\  
 
0 & \boxed 2 & -2\\  
Line 82: Line 82:
 
0 & \boxed 2 & -2\\  
 
0 & \boxed 2 & -2\\  
 
0 & 0 & \boxed 5
 
0 & 0 & \boxed 5
\end{bmatrix}$
+
\end{bmatrix}</math>
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
\boxed 1 & 2 & 1\\  
 
\boxed 1 & 2 & 1\\  
 
0 & \boxed 2 & -2\\  
 
0 & \boxed 2 & -2\\  
 
0 & 0 & \boxed 5
 
0 & 0 & \boxed 5
\end{bmatrix}$, $\boxed 5$ - it's 3rd pivot
+
\end{bmatrix}</math>, $\boxed 5$ - it's 3rd pivot
  
  
Line 93: Line 93:
  
  
=== When Does if Fails? ===
+
=== When does it fail? ===
 
Not always we are able to do the forward elimination
 
Not always we are able to do the forward elimination
  
 
0 at a Pivot position:
 
0 at a Pivot position:
 
* suppose the first pivot is 0:
 
* suppose the first pivot is 0:
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
\boxed 0 & 2 & 1\\  
 
\boxed 0 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* But here it doesn't mean that we can't solve the system: we can switch the rows and continue:
 
* But here it doesn't mean that we can't solve the system: we can switch the rows and continue:
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
\boxed 3 & 8 & 1\\  
 
\boxed 3 & 8 & 1\\  
 
0 & 2 & 1\\  
 
0 & 2 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* so, if there's a 0 at the pivot position, try to exchange rows
 
* 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
 
* if there's no rows with non-zero values at the pivot position - the elimination fails
Line 116: Line 116:
 
=== Augmented Matrix ===  
 
=== Augmented Matrix ===  
 
But we shouldn't forget about $\mathbf b$!
 
But we shouldn't forget about $\mathbf b$!
* $A$ augmented is $\begin{bmatrix}
+
* $A$ augmented is <math>\begin{bmatrix}
 
\mathop{a_1}\limits_|^| \mathop{a_2}\limits_|^|  ...  \mathop{a_n}\limits_|^| \ \Bigg| \ \mathop{\mathbf b}\limits_|^|  
 
\mathop{a_1}\limits_|^| \mathop{a_2}\limits_|^|  ...  \mathop{a_n}\limits_|^| \ \Bigg| \ \mathop{\mathbf b}\limits_|^|  
\end{bmatrix}$: matrix $A$ with column $\mathbf b$ stacked to the right
+
\end{bmatrix}</math>: matrix $A$ with column $\mathbf b$ stacked to the right
* $A$ augmented: $\left[\begin{array}{ccc|c}
+
* $A$ augmented: <math>\left[\begin{array}{ccc|c}
 
1 & 2 & 1 & 2\\  
 
1 & 2 & 1 & 2\\  
 
3 & 8 & 1 & 12\\  
 
3 & 8 & 1 & 12\\  
 
0 & 4 & 1 & 2
 
0 & 4 & 1 & 2
\end{array}\right]$
+
\end{array}\right]</math>
 
* the right part $\mathbf b$ also changes as we go through elimination
 
* the right part $\mathbf b$ also changes as we go through elimination
* $\left[\begin{array}{ccc|c}
+
* <math>\left[\begin{array}{ccc|c}
 
1 & 2 & 1 & 2\\  
 
1 & 2 & 1 & 2\\  
 
3 & 8 & 1 & 12\\  
 
3 & 8 & 1 & 12\\  
Line 137: Line 137:
 
0 & 2 & -6 & 6\\  
 
0 & 2 & -6 & 6\\  
 
0 & 0 & 5 & -10
 
0 & 0 & 5 & -10
\end{array}\right]$
+
\end{array}\right]</math>
 
* let $\mathbf c$ be the result of applying elimination to $\mathbf b$
 
* let $\mathbf c$ be the result of applying elimination to $\mathbf b$
  
Line 144: Line 144:
 
After we forward-eliminated variables of augmented $A$, we can do back substitution:
 
After we forward-eliminated variables of augmented $A$, we can do back substitution:
 
* Our matrix is  
 
* Our matrix is  
$\left[\begin{array}{ccc|c}
+
<math>\left[\begin{array}{ccc|c}
 
1 & 2 & 1 & 2\\  
 
1 & 2 & 1 & 2\\  
 
0 & 2 & -6 & 6\\  
 
0 & 2 & -6 & 6\\  
 
0 & 0 & 5 & -10
 
0 & 0 & 5 & -10
\end{array}\right]$
+
\end{array}\right]</math>
 
* It means that our system is  
 
* It means that our system is  
  
  
$\left\{\begin{array}{rl}
+
<math>\left\{\begin{array}{rl}
 
x + 2y + z & = 2\\  
 
x + 2y + z & = 2\\  
 
2y - 2z & = 6 \\  
 
2y - 2z & = 6 \\  
 
5z & = -10
 
5z & = -10
\end{array}\right.$
+
\end{array}\right.</math>
  
 
Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$
 
Now we just go backwards and solve: first for $z$, then for $y$, and finally for $x$
Line 165: Line 165:
 
=== Elimination: Matrix Form ===
 
=== Elimination: Matrix Form ===
 
We can write these elimination steps in matrix form
 
We can write these elimination steps in matrix form
* $\begin{bmatrix}
+
* <math>\begin{bmatrix}
 
1 & 2 & 1\\  
 
1 & 2 & 1\\  
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\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.  
 
* 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]]?
 
* Can we write it with [[Matrix Multiplication]]?
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
1 & 0 & 0\\  
 
1 & 0 & 0\\  
 
? & ? & ?\\  
 
? & ? & ?\\  
Line 180: Line 180:
 
3 & 8 & 1\\  
 
3 & 8 & 1\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
** The first and last rows remain unchanged - hence we have $\begin{bmatrix}
+
** The first and last rows remain unchanged - hence we have <math>\begin{bmatrix}
 
1\\  
 
1\\  
 
?\\  
 
?\\  
 
0
 
0
\end{bmatrix}$ and $\begin{bmatrix}
+
\end{bmatrix}</math> and <math>\begin{bmatrix}
 
0\\  
 
0\\  
 
?\\  
 
?\\  
 
1
 
1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
** what should we put instead of $[? \ ? \ ?]$ so multiplication takes us from one matrix to another?
 
** what should we put instead of $[? \ ? \ ?]$ so multiplication takes us from one matrix to another?
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
1 & 0 & 0\\  
 
1 & 0 & 0\\  
 
\boxed{-3} & 1 & 0\\  
 
\boxed{-3} & 1 & 0\\  
 
0 & 0 & 1
 
0 & 0 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
** we want to subtract 3 times row 1 from row 2:
 
** we want to subtract 3 times row 1 from row 2:
** $\begin{bmatrix}
+
** <math>\begin{bmatrix}
 
1 & 0 & 0\\  
 
1 & 0 & 0\\  
 
\boxed{-3} & 1 & 0\\  
 
\boxed{-3} & 1 & 0\\  
Line 209: Line 209:
 
0 & 2 & -2\\  
 
0 & 2 & -2\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* let $E_{21}$ be the matrix that's used for step 2,1 of the elimination
 
* let $E_{21}$ be the matrix that's used for step 2,1 of the elimination
** $E_{21} A = \begin{bmatrix}
+
** <math>E_{21} A = \begin{bmatrix}
 
1 & 2 & 1\\  
 
1 & 2 & 1\\  
 
0 & 2 & -2\\  
 
0 & 2 & -2\\  
 
0 & 4 & 1
 
0 & 4 & 1
\end{bmatrix}$
+
\end{bmatrix}</math>
 
* we continue this way until we transform $A$ to $U$
 
* we continue this way until we transform $A$ to $U$
 
** so we have $E_{21} (E_{21} A) = U$  
 
** so we have $E_{21} (E_{21} A) = U$  

Revision as of 18:52, 27 January 2017

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}$
    • already 0, continuing
  • [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 & -6 & 6\\ 0 & 4 & 1 & 2 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 2 & 1 & 2\\ 0 & 2 & -6 & 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:

  • Our matrix is

[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?


See Also

Sources

Machine Learning Bookcamp: Learn machine learning by doing projects. Get 40% off with code "grigorevpc".

Share your opinion