Gaussian elimination method for solving systems of linear algebraic equations

What do you know about solving systems of linear equations? This type of tasks is often offered to students in linear algebra homework. In one of our videos we discussed that a system of linear equations can be solved using Cramer’s rule which involves finding determinants and it might get tricky when dealing with systems of 4, 5 or more equations. Luckily, there is another method which allows to avoid massive calculations.  And it is called Gaussian elimination (or row reduction).
Consider the system of $m$ linear equations with $n$ unknowns written in the next form:

\left\{ \begin{aligned}a_{11}x_1+a_{12}x_2+…+a_{1n}x_n =b_1\\a_{21}x_1+a_{22}x_2+…+a_{2n}x_n =b_2\\ …& & \\a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n =b_m\end{aligned}\right.
where $x_1, x_2, …, x_n$– unknowns,
$a_{ij}$- coefficients of the unknowns,
$b_i$- free terms (the right parts of the equations).

Here’s video version of this tutorial:

Let us think of it as of a set of conditions giving us information about unknowns. It can be spelled like… if we take, say, this much of this unknown noted as $x_1$ and this much of another unknown – $x_2$, then some amount of the next unknown and, say, sum them up – we’ll obtain this much of $b_1$. Of course, this information is not enough for defining all unknowns, so there are more equations. if we take that much of unknown $x_1$ and subtract that much of $x_2$, then add some other unknowns and subtract some another – we’ll obtain this much of $b_2$. And so on.
Ok, let’s move on. What else can we say about this system?

•  it is pretty obvious that we can swap any pair of equations in the set because the order in which we get this information is not important. The idea is to have enough information but not particularly ordered;
• another simple conclusion that comes to mind is that we can multiply both sides of any equation by any non-zero constant and that will not change the system, as well as adding to both sides of any of the equations corresponding parts of any another equation.

We can perform these elementary transformations as many times as we want. It will lead to equivalent system of equations because in fact doing so we are not producing or reducing information about the unknowns but just reorganizing it.

What we are going to do with all this? Obviously we’ll find these properties essential when solving a system of equations using Gaussian method.

Let’s consider some real life example of the system of linear equations:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\x_1-2x_2+5x_3+2x_4 =2\\2x_2-4x_3+5x_4 =-1\\2x_3+x_4 =-3 \end{aligned}\right.

It’s a good habit to form nice columns of variable first before solving any system of a kind. It should prevent us from making mistakes and we’ll proceed faster. Secondly, we’ll rearrange the system so that equations staffed with all unknowns are in the top. Now, let’s pick the first two equations from the system and eliminate the first unknown from one of them. It’s not important which equation and which unknown to choose, the only condition is that both equations must contain it :).  Let’s pick the first and the second ones and intend to eliminate the first unknown $x_1$. In a few steps we’ll form suitable notion of the system, you’ll see.

Ok, back to elimination. How can that be done? More than simple – first we multiply or divide one of the picked equations by some number in order to have as much of $x_1$ in it as in the other one but with opposite sign. Second – we add corresponding sides of these two equations and thus unknown $x_1$ is canceled out. It will make no difference of cause if we add the first equation to the second or vice versa.

So let’s multiply the first equation by the $\frac{1}{2}$, add it to the second and replace existing second equation with the new one. After performing all that we obtain a new equivalent system:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\2x_2-4x_3+5x_4 =-1\\2x_3+x_4 =-3 \end{aligned}\right.

As you can see we eliminated $x_1$ from the second row.

Let’s now multiply it by $\frac{1}{2}$, add the result to the equation in the third row, and then replace existing equation with the newly obtained one.

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\-\frac{3}{4}x_3+\frac{11}{2}x_4 =0\\2x_3+x_4 =-3 \end{aligned}\right.

We eliminated $x_2$ from the third equation. Our last move will be elimination of $x_3$ from the forth equation.

So let’s multiply it by $-\frac{3}{8}$, add to the third row equation and put the result into the forth row.

Our final equivalent system looks as follows:

\left\{ \begin{aligned}2x_1+4x_2-3x_3+2x_4 =0\\-4x_2+\frac{13}{2} x_3+x_4 =2\\-\frac{3}{4}x_3+\frac{11}{2}x_4 =0\\ \frac{41}{8}x_4 =\frac{9}{8} \end{aligned}\right.

We obtained a system in upper-triangular form.

Finding the unknowns of the triangular system is called the reverse course of Gauss method. Actually, it is fairly easy to see how to proceed from this point. First, we’ll find $x_4$ from the forth equation. Then we’ll just back-substitute $x_4$ into the third equation in order to find $x_3$. After that we’ll plug $x_4$ and $x_3$ into the second equation to find $x_2$. Then, finally, knowing $x_2$, $x_3$ and $x_4$, we can easily find $x_1$ from the first equation.

So, here is the answer to our system:

\left\{ \begin{aligned}x_1 =-\frac{88}{41}\\x_2=\frac{89}{41}\\x_3=\frac{66}{41}\\ x_4 =\frac{9}{41} \end{aligned}\right.

You can check it if you like.

In general, it may occur that during transformation of the system we obtain contradictory equation of the form  $0 = b$, where $b \neq 0$. This means that the system has no solutions. Such systems are called inconsistent.

It may also happen so that you follow the method correctly but fon’t get this nice triangular form and this last equation $\frac{41}{8}x_4 = \frac{9}{8}$ from where you can derive $x_4$ and solve the system. Instead you come against a case where you can only express some unknows in terms of another. It is nothing to be fear of, that’s normal 🙂 In one of the next sections we’ll pick an example showing that particular case.

Gauss elimination method is often even more usable than Cramer’s method (Cramer’s rule) which requires calculations of determinants and this operation is complicated for systems of high order. On the contrary, Gaussian elimination can be performed comparatively easy for systems of order higher than, say, 4 when calculating determinants gets complicated.

Summing up. When you want to solve a system of linear equations using Gaussian elimination, first you need to obtain your system in a triangular (or trapeziodal) form. For that you go down your system and step by step eliminate variables from the equations. After that you go up and gradually find variables (or express them through others). Don’t forget to check your answers by plugging them into the initial system, it helps to avoid mistakes and do your homework assignment correctly.

0 Shares
Filed under Math.