Gaussian Elimination Examples

You are not logged in.
If you are a current student, please Log In for full access to this page.

1) Example 1

In this section, we'll work through solving the set of linear equations described in this exercise's page. Our initial setup for that problem was as follows:

\left[\begin{array}{cc} 3 & 4\\ 5 & -2\end{array}\right] \left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 33\\ 3\end{array}\right]

1.1) Forward Elimination

To begin, we look at the first column (i = 0). We look for the row with the highest magnitude value in column 0, and swap it with the current row 0 (both in b and in A). In this case, we want the row with the leading 5 to be the top row. So after this swap, we have:

\left[\begin{array}{cc} 5 & -2\\ 3 & 4\end{array}\right] \left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 3\\ 33\end{array}\right]

(Note that this did not change the system of equations described at all, just the order in which we will consider them). Now, we want to subtract a scaled version of row 0 from row 1 in order to eliminate the value A_{10}. The right scaling factor for this is 3/5.

Subtracting 3/5 times row 0 from row 1, we have:

\left[\begin{array}{cc} 5 & -2\\ 3-\frac{3}{5}\left(5\right) & 4-\frac{3}{5}\left(-2\right)\end{array}\right] \left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 3\\ 33-\frac{3}{5}\left(3\right)\end{array}\right]

Simplifying:

\left[\begin{array}{cc} 5 & -2\\ 0 & 26/5\end{array}\right] \left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 3\\ 156/5\end{array}\right]

Now we have our matrix in row-echelon form, so we can move on to solving for the variables.

1.2) Back-Solving

We had our system in the following form:

\left[\begin{array}{cc} 5 & -2\\ 0 & 26/5\end{array}\right] \left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 3\\ 156/5\end{array}\right]

Note that the bottom row represents the equation

\frac{26}{5}y = \frac{156}{5}

Solving, we find that y = 6. Then, the next row up represents the equation 5x -2y = 3. Now that we know y, we can solve this equation as well:

5x - 2(6) = 3

5x = 15

x = 3

So our final solution is

\left[\begin{array}{c} x\\ y\end{array}\right] = \left[\begin{array}{c} 3\\ 6\end{array}\right]

1.3) Python Form

In this setup, we would represent our original A and b as:

A = [[3, 4], [5, -2]]
b = [33, 3]

We could then solve for x with:

print(gauss_solve(A, b))

which should print our solution, [3, 6].

The intermediate result after forward eliminination would have A = [[5, -2], [0, 5.2]] and b = [3, 31.2]

2) Example 2

Consider solving the following set of linear equations:

x + 3y + 7z = 18

3x + 6y + 9z = 33

3x + 9y + 15z = 48

In matrix form, this system can be represented as:

\left[\begin{array}{ccc} 1 & 3 & 7\\ 3 & 6 & 9\\ 3 & 9 & 15\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 18\\ 33\\ 48\end{array}\right]

2.1) Forward Elimination

To begin, we look at the first column (i = 0). We look for the row with the highest magnitude value in column 0, and swap it with the current row 0 (both in b and in A). In this case, we want either of the rows with the leading 3's to be the top row, so we'll pick the middle one. After swapping row 0 with row 1, we have:

\left[\begin{array}{ccc} 3 & 6 & 9\\ 1 & 3 & 7\\ 3 & 9 & 15\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 33\\ 18\\ 48\end{array}\right]

(Note that this did not change the system of equations described at all, just the order in which we will consider them). Now, we want to subtract a scaled version of row 0 from the other rows in order to eliminate the values A_{10} and A_{20}.

To do this, we need to subtract 1/3 times row 0 from row 1, and 1 times row 0 from row 2.

After this subtraction, we have:

\left[\begin{array}{ccc} 3 & 6 & 9\\ 0 & 1 & 4\\ 0 & 3 & 6\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 33\\ 7\\ 15\end{array}\right]

From here on out, row 0 will remain unchanged.

Now we are moving on to the second column (i=1). Again, if there is a row below this one that has a higher magnitude value in column 1, we want to swap those two rows in the matrix. In this case, the bottom row has value 3 in column 1, so we want to swap it with row 1. After swapping rows 1 and 2, we have:

\left[\begin{array}{ccc} 3 & 6 & 9\\ 0 & 3 & 6\\ 0 & 1 & 4\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 33\\ 15\\ 7\end{array}\right]

Now we need to eliminate column 2 from all rows below this one. We can do this by subtracting 1/3 times row 1 from row 2:

\left[\begin{array}{ccc} 3 & 6 & 9\\ 0 & 3 & 6\\ 0 & 0 & 2\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 33\\ 15\\ 2\end{array}\right]

Now we have our matrix in row-echelon form, so we can move on to solving for the variables.

2.2) Back-Solving

We had our system in the following form:

\left[\begin{array}{ccc} 3 & 6 & 9\\ 0 & 3 & 6\\ 0 & 0 & 2\end{array}\right] \left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 33\\ 15\\ 2\end{array}\right]

Note that the bottom row represents the equation

2z = 2

Solving, we find that z = 1. Then, the next row up represents the equation 3y + 2z = 15. Now that we know z, we can solve this equation as well:

3y + 6(1) = 15

3y = 9

y = 3

And our final equation is 3z+6y+9z = 33. Knowing values for y znd z, we can solve for x:

3x + 6(3) + 9(1) = 33

3x = 6

x = 2

So our final solution is

\left[\begin{array}{c} x\\ y\\ z\end{array}\right] = \left[\begin{array}{c} 2\\ 3\\ 1\end{array}\right]

2.3) Python Form

In Python, we could solve this set of equations with:

print(gauss_solve([[1, 3, 7], [3, 6, 9], [3, 9, 15]], [18, 33, 48]))

which should print our solution, [2, 3, 1].

The intermediate result after forward eliminination would have A = [[3, 6, 9], [0, 3.0, 6.0], [0.0, 0, 2.0]] and b = [33, 15.0, 2.0].