16.5 Gaussian Elimination

  • Row Echelon Form • Gaussian Elimination • Number of Possible Solutions • Consistent and Inconsistent Systems

We now show a general method that can be used to solve a system of linear equations. The procedure used in this method is similar to that used in finding the inverse of a matrix in Section 16.3. It is known as Gaussian elimination, and as noted in the chapter introduction, it was developed in the early 1800s by Karl Gauss. Today, it is commonly used in computer programs for the solutions of systems of linear equations.

When using this method, we use certain row operations to convert the system of equations to row echelon form. Then the solution can be found by substituting back into the equations from the bottom up. The following examples illustrate this method.

EXAMPLE 1 Row echelon form

The system of equations to the left is said to be in row echelon form. We see that the third equation directly gives us the value z = 2. Since the second equation contains only y and z, we can now substitute z = 2 into the second equation to get y = 1. Then we can find x by substituting y = 1 and z = 2 into the first equation, and get x = 6. Therefore, after writing the system of equations in the form to the left, the solution is completed by substituting back, starting with the last equation.

The method of Gaussian elimination is based on first rewriting the given system of equations in row echelon form like in Example 1, so that the last equation shows the value of one of the unknowns, and the others are found by substituting back. The method to obtain the proper form is based on the use of any of the following three operations on the equations of the original system of equations.

Using three linear equations in three unknowns as an example, by using the above operations, we can change the system

a1x + b1y + c1z = d1a2x + b2y + c2z = d2a3x + b3y + c3z = d3
(16.10)

into the equivalent system in row echelon form

x + b4y + c4z = d4y + c5z = d5z = d6
(16.11)

The solution is completed by substituting the value of z into the second equation, and then substituting the values of y and z into the first equation, as in Example 1.

EXAMPLE 2 Gaussian elimination with two equations

Solve the following system of equations using Gaussian elimination:

2x + y = 43x − 2y = 3

The steps are given below, with the necessary row operations shown in red:

this is in the formof Eq. ( 16.10) make coefficient of x infirst equation 1eliminate x fromsecond equationmake coefficient of yin second equation 12x + y = 43x − 2y = 3→ 12R1x + 12y = 23x − 2y = 3→ − 3R1+ R2x + 12y = 2 − 72y =  − 3→ − 27R2x + 12y = 2y = 67

To find the value of x, we substitute y = 67 into the first equation: x + 12(67) = 2 ,  or x = 117 . 

Thus, the solution is x = 117 , y = 67 ,  which checks when substituted into the original equations.

EXAMPLE 3 Gaussian elimination with three equations

Solve the following system of equations using Gaussian elimination:

x + 3y − 2z =  − 52x − y + 4z = 7 − 3x + 2y − 3z =  − 1

In this example, we will perform the row operations on the augmented matrix, which includes the coefficients and constant terms, but not the variables. The equal signs are replaced with dotted lines. The steps are shown below.

top left entryis already 1make other entriesin first column 0make second entryin middle row 1 [ 13 − 2 − 52 − 147 − 32 − 3 − 1 ] → − 2R1+ R2→ 3R1+ R3 [ 13 − 2 − 50 − 7817011 − 9 − 16 ] → − 17R2 [ 13 − 2 − 501 − 87 − 177011 − 9 − 16 ] make second entryin bottom row 0make third entryin bottom row 1→ − 11R2+ R3 [ 13 − 2 − 501 − 87 − 17700257757 ] → 725R3 [ 13 − 2 − 501 − 87 − 1770013 ] → z = 3

The last line above shows that z = 3. This can be substituted into the second equation to find y, and then the values of x and y can be substituted into the first equation to find x.

y − 87(3) =  − 177x + 3(1) − 2(3) =  − 5y = 1x =  − 2

Thus, the solution is x =  − 2 , y = 1 , z = 3. This solution checks in the original equations.

Note that in this example, it is possible to continue performing row operations until the left side of the augmented matrix is the identity matrix. This is called reduced row echelon form (rref). In this form, the system is completely solved and there is no need to back-substitute from the bottom up. Many calculators have a rref feature that can be used to solve systems of equations (see Example 3 in Section 5.5). Figure 16.16 shows the calculator solution for this example.

A calculator screen.

Fig. 16.16

Graphing calculator keystrokes: bit.ly/2QShWf1

EXAMPLE 4 Gaussian elimination leading to infinite solutions

Solve the following system of equations using Gaussian elimination:

4y + z = 22x + 6y − 2z = 34x + 8y − 5z = 4

We will again work with the augmented matrix. Since the first equation doesn’t contain x, we start by interchanging the first two equations. The steps are shown below.

interchange the first-two equationsmake top leftentry 1make other entriesin first column 0 [ 26 − 23041248 − 54 ] → 12R1 [ 13 − 132041248 − 54 ] → − 4R1+ R3 [ 13 − 13204120 − 4 − 1 − 2 ] make second entryin middle row 1make second entryin bottom row 0→ 14R2 [ 13 − 1320114120 − 4 − 1 − 2 ] → 4R2+ R3 [ 13 − 1320114120000 ] 0= 0 is true, so there are an→ infinite number of solutions

The last row of zeros indicates that z can be any number. But it is still possible to express both x and y in terms of z. We first solve the equation in the second row for y in terms of z, which results in y = 12 − 14z .  Then this expression can be substituted into the equation in the top row to solve for x in terms of z.

x + 3(12 − 14z) − z = 32x = 74z

Therefore, the solution is given by x = 74z and y = 12 − 14z ,  where z can be any number.

NOTE

[This means there are an infinite number of solutions.]

For example, if z = 4 ,  then x = 7 and y =  − 12 . 

NOTE

[Note that the original matrix of coefficients on the left of the dotted line has a determinant of zero, and therefore its inverse does not exist. Thus, the method described in Section 16.4 cannot be used to solve this system. This underscores the importance of Gaussian elimination.]

POSSIBLE NUMBER OF SOLUTIONS

When we solved systems of linear equations in Chapter 5, we found that not all systems have unique solutions, as they do in Examples 2 and 3. In Example 4, we illustrated the use of Gaussian elimination on a system of equations for which the solution is not unique.

In Example 4, one of the equations became 0 = 0 ,  and there was an unlimited number of solutions. If any of the equations of a system becomes 0 = a , a ≠ 0 ,  then the system is inconsistent and there is no solution. Example 5 illustrates such a system.

If a system has more unknowns than equations, or it can be written this way, as in Example 4, it usually has an unlimited number of solutions. It is possible, however, that such a system is inconsistent.

If a system has more equations than unknowns, it is inconsistent unless enough equations become 0 = 0 such that at least one solution is found. The following example illustrates two systems in which there are more equations than unknowns.

EXAMPLE 5 Consistent and inconsistent systems

Solve the following systems of equations by Gaussian elimination.

The solutions are shown at the left. We note that each system has three equations and two unknowns.

In the solution of the first system, the third equation becomes 0 = 0 ,  and only two equations are needed to find the solution x = 1 , y = 2.

In the solution of the second system, the third equation becomes 0 =  − 4 ,  which means the system is inconsistent and there is no solution.

Graphing the systems, note that in Fig. 16.17, each of the lines passes through the point (1, 2), whereas in Fig. 16.18, there is no point common to the three lines.

Three graphs intersect at (1, 2). The line x plus 2 y = 5 falls to (5, 0). The line 4 x plus y = 6 falls through (0, 6). The line 3 x minus y = 1 rises through (0, negative 1).

Fig. 16.17

Three graphs.

Fig. 16.18

EXERCISES 16.5

In Exercises 1 and 2, make the given changes in the indicated examples of this section, and then solve the resulting systems using Gaussian elimination.

  1. In Example 2, interchange the two equations and then solve the system with the equations in this order.

  2. In Example 5, change the third equation of the second system to 5x + 3y = 11.

In Exercises 3–24, solve the given systems of equations by Gaussian elimination. If there is an unlimited number of solutions, find two of them.

  1. x + 2y = 43x − y = 5

  2. 2x + y = 15x + 2y = 1

  3. 4x − 3y = 2 − 2x + 4y = 3

  4.  − 3x + 2y = 44x + y =  − 5

  5. 2x − 3y + z = 46y − 4x − 2z = 9

  6. 3s + 4t − u =  − 52u − 6s − 8t = 10

  7. x + 3y + 3z =  − 32x + 2y + z =  − 5 − 2x − y + 4z = 6

  8. 9x − 3y + 6z = 94x − 2y + z = 36x + 6y + 3z = 4

  9. w + 2x − y + 3z = 122w − 2y − z = 33x − y − z =  − 1 − w + 2x + y + 2z = 3

  10. 3x − 2y =  − 115x + y =  − 12x + 3y = 10x − 5y =  − 21

  11. x − 4y + z = 52x − y + 3z = 4

  12. 4x + z = 62x − y − 2z =  − 2

  13. 2x − y + z = 53x + 2y − 2z = 45x + 8y − 8z = 5

  14. 3u + 6v + 2w =  − 2u + 3v − 4w = 22u − 3v − 2w =  − 2

  15. x + 3y + z = 42x − 6y − 3z = 104x − 9y + 3z = 4

  16. 30x + 20y − 10z = 304x − 2y − 6z = 4 − 5x + 20y − 25z =  − 5

  17. 2x − 4y = 73x + 5y =  − 69x − 7y = 15

  18. 4x − y = 58x + 8y = 126x − 4y = 72x + y = 4

  19. 6x + 10y =  − 424x − 18y = 1315x − 33y = 196x + 68y =  − 33

  20. x + 3y − z = 13x − y + 4z = 4 − 2x + 2y + 3z = 173x + 7y + 5z = 23

  21. 4x − 8y − 8z = 1210x + 5y + 15z = 20 − 6x − 3y − 3z = 153x + 3y − 2z = 2

  22. 2x − y − 2z − t = 44x + 2y + 3z + 2t = 3 − 2x − y + 4z =  − 2

In Exercises 25–28, solve the given system of equations by using the rref feature on a calculator.

  1. 7x + 5y − 3z = 163x − 5y + 2z =  − 85x + 3y − 7z = 0

  2. x + y + z = 62y + 5z =  − 42x + 5y − z = 27

  3.  − 2r + 3t + 5u = 1 − 4r + s − 2t + u = 0r − 4s + 2t + u = 4 − 5r − 3s + 8u = 0

  4. 2x + 5y − 9z + 3w = 1515x + 6y − 4z + 2w = 1033x − 4y + 2z + 7w = 1611x + 7y + 4z − 8w =  − 32

In Exercises 29 and 30, solve the given problems using Gaussian elimination.

  1. Solve the system a1x + b1y = c1 , a2x + b2y = c2 and show that the result is the same as that obtained using Cramer’s rule as in Section 5.4. See page 160.

  2. Solve the system x + 2y = 6 , 2x + ay = 4 and show that the solution depends on the value of a. What value of a does the solution show may not be used?

In Exercises 31–34, set up systems of equations and solve by Gaussian elimination.

  1. Two jets are 2370 km apart and traveling toward each other, one at 720 km/h and the other at 860 km/h. How far does each travel before they pass?

  2. The voltage across an electric resistor equals the current (in A) times the resistance (in Ω). If a current of 3.00 A passes through each of two resistors, the sum of the voltages is 10.5 V. If 2.00 A passes through the first resistor and 4.00 A passes through the second resistor, the sum of the voltages is 13.0 V. Find the resistances.

  3. Three machines together produce 650 parts each hour. Twice the production of the second machine is 10 parts/h more than the sum of the production of the other two machines. If the first operates for 3.00 h and the others operate for 2.00 h, 1550 parts are produced. Find the production rate of each machine.

  4. A business bought three types of computer programs to be used in offices at different locations. The first costs $35 each and uses 190 MB of memory; the second costs $50 each and uses 225 MB of memory; and the third costs $60 each and uses 130 MB of memory. If as many of the third type were purchased as the other two combined, with a total cost of $2600 and total memory requirement of 8525 MB, how many of each were purchased?

Answer to Practice Exercise

  1. x = 2 , y =  − 3

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.135.198.49