Welcome, Guest. Please login or register.

July 17, 2019, 11:24:26 am

Author Topic: Gaussian Elimination (with some tricks)  (Read 103 times)

0 Members and 1 Guest are viewing this topic.

RuiAce

  • HSC Lecturer
  • Moderator
  • Great Wonder of ATAR Notes
  • *****
  • Posts: 8403
  • "All models are wrong, but some are useful."
  • Respect: +2283
Gaussian Elimination (with some tricks)
« on: June 17, 2019, 01:57:33 pm »
+3
Remember to register here for FREE to ask any questions you may come across in your QCE studies!

The classic methods of elimination and substitution in simultaneous equations become more annoying when we have more than two variables. Whilst we can keep track of things, usually we don't want to because it is easy to get lost in it all. So we use Gaussian elimination as a more 'systematic' approach when we have lots of linear equations.

The system of equations are presented in their corresponding augmented matrix form. There are three different row operations we can then use on each row.
- Multiply an entire row by a constant: \( R_i = \alpha R_i \). However don't multiply the entire row by 0 - that wrecks everything!
- Swap two rows: \( R_i \leftrightarrow R_j \).
- Add a multiple of one row, to another row: \( R_i = R_i + \alpha R_j \).

For an example, I purposely picked one where the numbers would not be nice. I personally like performing my Gaussian elimination in 'clever' ways, but there are still some important rules of thumb you're recommended to follow. We will attempt to solve the system
\begin{align*}
3x+y+5z&=10\\
-x+4y+7z&=-7\\
9x+2y+3z&=19\end{align*}
The augmented matrix for this system is
\[ \left(\begin{array}{c c c|c}
3 & 1 & 5 & 10\\
-1 & 4 & 7 & -7\\
9 & 2 & 3 & 19
\end{array}\right)\]
Here I do something convenient at the start. I see that the leading entry in the second row is already \(-1\). When some other row's leading entry is \(1\) or \(-1\), and the one in the first row is not, I like to swap it there. That way I have to deal with less fractions for as long as possible - I only have to put up with them for the easy bit.

Note: In a row, the leading entry is the first entry that's not a 0, when you read from left to right.
\[ \xrightarrow{R_2\leftrightarrow R_1} \left(\begin{array}{c c c|c}
-1 & 4 & 7 & -7\\
3 & 1 & 5 & 10\\
9 & 2 & 3 & 19
\end{array}\right) \]
Your teacher might disagree with me here now, and that's fair enough. If he/she does, listen to them. But personally when my leading entry on the highest row I require is \(-1\), I just leave it there. Some teachers would recommend multiplying by -1 to it right now (because ultimately we want 1's down the diagonal), but I'll just do it later to save writing.

Now we wish for the first column to be filled with as many 0's as possible, excluding for in the first row. To do this, our leading entries are
- \(-1\) in row 1.
- \(3\) in row 2.
- \(9\) in row 3.

So to eliminate row 2, we can add \(3\) lots of row 1. In the first column, we'd be computing \(3 + 3\times(-1)\), which is \(0\)! Similarly, we add \(0\) lots of row 1 to row 3.
\[
\xrightarrow[R_3 = R_3 + 9R_1]{R_2 = R_2+9R_1} \left( \begin{array}{c c c|c}
-1 & 4 & 7 & -7\\
0 & 13 & 26 & -11/13\\
0 & 38 & 66 & -44
\end{array}\right)
\]
Now we move onto the second row. At this point, the standard thing to do is to multiply a number, so that the leading entry of row 2 becomes 1. Here, the leading entry is \(13\) - remember that we look at the first non-zero value! So we multiply \(R_2\) by \( \frac1{13} \).

But I will also use a trick again. Just by looking at \(R_3\), I can clearly see that \(2\) is a common factor of every term! So I'll halve every term in \(R_3\) as well for some simplification.
\[
\xrightarrow[R_3 = \frac12 R_3]{R_2 = \frac1{19}R_2} \left( \begin{array}{c c c|c}
-1 & 4 & 7 & -7\\
0 & 1 & 2 & -11/13\\
0 & 19 & 33 & -22
\end{array}\right)
\]
Now we do the same thing to cut away as many 0's as possible in the second column. See if you can figure out why this works by yourself. Note how the leading entry in \(R_2\) is now \(1\), instead of \(-1\)!
\[
\xrightarrow{R_3 = R_3 - 19R_2} \left( \begin{array}{c c c|c}
-1 & 4 & 7 & -7\\
0 & 1 & 2 & -11/13\\
0 & 0 & -5 & -77/13
\end{array}\right)
\]
Once we're here, there's nothing else to eliminate. Here, I multiply whatever rows need to be multiplied, so that their leading entries will all be 1's.
\[
\xrightarrow[R_3 = -\frac15 R_3]{R_1 = -R_1} \left( \begin{array}{c c c|c}
1 & -4 & -7 & 7\\
0 & 1 & 2 & -11/13\\
0 & 0 & 1 & 77/65
\end{array}\right)
\]
This augmented matrix is now in a row-echelon form. When this occurs, the entries down the main diagonal are all 1's, and everything to the left/below the diagonal is 0. Note that a matrix can have multiple row-echelon forms, so don't panic if you get a different one along the way. The important thing is that the final answer is the same.

Once we are in a row-echelon form, we can perform back substitution. This involves converting each row back into a Cartesian equation, but we go from bottom to top due to the convenient form we have now. Here, we start with \(R_3\):
\[ \boxed{z = \frac{77}{65}}. \]
Basically, the key is to remember that the numbers are actually the coefficients of \(x\), \(y\) and \(z\)! Gaussian elimination does what substitution and (old) elimination did - the idea is that the manipulations are only done on the coefficients to help keep track of everything! So in a similar way, when we equate \(R_2\) we have:
\[ y + 2z = -\frac{11}{13}. \]
Of course, we already know what \(z\) is, so subbing that in:
\[ y + \frac{144}{65} = -\frac{11}{13} \implies \boxed{y = -\frac{209}{65}} \]
Then we do the same thing in \(R_1\):
\[ x - 4y - 7z = 7. \]
Since we know what \(y\) and \(z\) are, upon subbing them both in:
\[ x + \frac{836}{65} - \frac{539}{65} = 7 \implies \boxed{x=\frac{158}{65}} \]
Hence our solutions are \( x = \frac{158}{65} \), \(y = -\frac{209}{65} \) and \(z = \frac{77}{65}\).

Of course, if you want to do it without clever tricks, that's still alright. Possibly recommended if you don't mind writing out more working, because it's even more systematic at least. Just look up some random row-echelon form calculator and sub your numbers in! Note that some calculators are programmed to find reduced row-echelon forms.
« Last Edit: June 17, 2019, 02:29:07 pm by RuiAce »