Math 438 Activity 2:



Math 438 Activity 2: Solving Systems of Equations by Gauss-Jordan Elimination

WHY: This activity is designed to help you understand the process of solving systems of equations using Gauss-Jordan Elimination on the augmented coefficient matrix. We will use this process repeatedly throughout the course, not only to solve systems of equations but also to find the optimal solution to linear programming problems. Linear Algebra is often called the arithmetic of higher mathematics, so you may expect to see this process frequently in your mathematical career.

LEARNING OBJECTIVES:

1. Understand the process of solving systems of equations using Gauss-Jordan elimination.

2. Learn to apply this methodology.

3. Become familiar with the difference between a process and a concept activity [This is a process activity]

VOCABULARY:

Row Echelon Form

The final form of a matrix during the Gauss-Jordan elimination process. It is as much like the Identity matrix as it is possible to transform the original matrix using elementary row operations.

The first non-zero entry in each row is a 1.. These "initial 1's" are later (further to the right) in lower rows. The entries above and below these "initial 1's" are 0's

Elementary Row Operations

1. Interchange rows

2. Multiply [divide] a row by a (non-zero) constant, changing that row

3. Use one row [the "pivot row"] to change another row [the "target row"] by adding a multiple of the pivot row to the target row [The pivot row is not changed]. [The selection of pivot and target row is usually based on a particular element of the pivot row,which is then called the "pivot element"] – This is sometimes called “a pivot operation”.

Consistent System

A system of equations is consistent if its set of solutions is not empty. It is inconsistent if the set of solutions is empty.

Solution Space

The vector space consisting of the set of solutions to a homogenous system of equations (all equations have 0 as the constant on the right-hand side). The solution space is a subspace of Rn [where n is the number of variables in the system of equations]

Column Space

The vector space spanned by the columns of the coefficient matrix of the system of equations [the set of all linear combinations of these column vectors]. It is a subspace of Rm where m is the number of equations.

Basis and dimentsion:

A basis for a vector space [or subspace] is a linearly independent set of vectors which spans the space.

The dimension of the space is the number of vectors in a basis.

CRITERIA:

1. Quality of answers to the Critical Thinking questions.

2. Success in applying the methodology to the exercises.

3. Success in keeping all members of the team together in understanding the material.

METHODOLOGY:

|1. Form Coefficient Matrix |Write the coefficients of the equation variables in matrix form. |

|2. Form Augmented Matrix |Adjoin the column of constants on the right sides of the equations to the right of the coefficient matrix. |

|3. Make a11 = 1 |Divide row 1 by a11 or use row operations to make upper left entry 1. |

|4. Convert column 1 |Use pivot operations to make other entries in column 1 into 0's ["pivot on a11"] |

|5. Convert other columns |Repeat steps 3 and 4 (with appropriate choice of i & j for aij) until the first nonzero entry in each row is 1 with |

| |0's above and below (in its column) |

|6. Check Consistency |The system of equations is inconsistent if the augmented matrix contains a row with all zeroes in the coefficient |

| |matrix and a non-zero entry in the augmented (farthest right) column. |

|7. Form Equations |If the system is consistent, write it in equation format. |

|8. Add Equations |For each independent variable [does not correspond to a column containing an initial 1] v write an auxiliary equation|

| |in form v = v. |

|9. Solve |Solve each equation for its first variable. Intersperse auxiliary equations (in order of original variable list) |

|10. Write vector form of solution |Rewrite the right side of the step 9 system of equations as a vector of constants plus each independent variable |

| |times its vector of coefficients. |

|11. Check answer |Assign values to the independent variables, determine dependent variable values, plug in and make sure these values |

| |satisfy the original system. |

RESOURCES:

1. Chapter 0: Strategic Mathematics

2. 20 minutes

PLAN:

1. Read through the methodology and discussion and check through the models given

2. Use the methodology to complete the exercise

3. Answer the Critical Thinking questions

MODEL 1:

We will solve the system x + 2y + 3z = 1; 2x + 5y + 8z = 3.

1. Form Coefficient Matrix Write the coefficients of the equation variables in matrix form.

A = [pic]

2. Form Augmented Matrix Adjoin the column of constants on the right sides of the equations to the right of the coefficient matrix

3. Make a11 = 1 Divide row 1 by a11 or use row operations (interchange and division) to make upper left entry 1.

a11 is already 1.

4. Convert column 1 Use pivot operations to make rest of first column of (A|b) = 0.

Multiply the pivot row (row 1) by -2 and add it to the target row 2 changing row 2 to obtain

[pic]

5. Convert other columns Repeat steps 3 (but in later rows and columns) and 4 until the first nonzero entry in each row is 1 with its column a unit vector.

The first nonzero entry in row 2 is already 1. Multiply the pivot row (row 2) by -2 and add it to the target row 1 changing row 1 as follows. Since there are no more rows we are finished.

[pic]

6. Check Consistency The system of equations is inconsistent if the augmented matrix contains a row with all zeroes in the coefficient matrix and a non-zero entry in the augmented (farthest right) column.

There are no zero rows in the row echelon form so the system is consistent.

7. Form Equations If the system is consistent, write the system in equation format.

x - z = -1

y + 2z = 1

8. Add Equations For each independent variable v [never appears as first variable in an equation] write an auxiliary equation in form v = v.

The only independent variable is z so we add the equation z = z.

9. Solve Equations Solve each equation for its first variable. Intersperse auxiliary equations.

x = z - 1

y = -2z + 1

z = z

10. Write vector Rewrite the right side of the step 9 system of equations as a vector of constants plus each independent

form of solution variable times its vector of coefficients.

[pic]

11. Check answer Assign values to the independent variables, determine dependent variable values, plug in and make sure these values satisfy the original system.

Let z = 1. Then x = 0, y = -1, z = 1. Substituting these values into the original equations we get

0 + 2(-1) + 3(1) = 1 Check

0 + 5(-1) + 8(1) = 3 Check

DISCUSSION:

The matrix representation of the system has a row for each equation. In a system of equations, we do not change the solution set (because we do not change the meaning - the system still imposes the same conditions on the set of values) if we interchange the order of equations, multiply (divide) an equation by a non-zero constant or add a multiple of one equation to another equation. The elementary row operations are the matrix representation of these actions - as long as we interpret each "row" to include the constant right-hand side of the equation.

In the ideal situation (unique solution) we can find an equivalent (= "same solution set") system of equations of the form

x = (some number)

y = (some number)

z = (some number) [Each coefficient is 0 or 1, there is only one "1" for each variable, only one "1" for each equation] - This makes the coefficient matrix an identity matrix. Usually we aren't this fortunate - either there are many solutions or there is no solution (system is inconsistent). The best we can always be sure of (closest to identity matrix we can guarantee) is the row-echelon form for the coefficient matrix, which allows us to see if there is a solution and to see (if there is) which variables may be freely chosen and which have their values fixed in relation to the free variables.

Step 1. Form Coefficient Matrix

The variables in a system of equations can be considered placeholders to identify where the coefficients go. They are not used during the solution of the system. By putting the coefficients in matrix form we can keep them correctly oriented and use linear algebra to simplify the problem.

Step 2. Form Augmented Matrix

We are allowed to interchange equations, add multiples of one equation to another, and multiply both sides of an equation by the same constant. These are called elementary row operations when done to the coefficient matrix. Whatever we do to the left side of an equation we have to do to the right side. Adjoining the right side vector to the coefficient matrix ensures that it is not forgotten during the row operations.

Step 3. Make a11 = 1

The goal matrix for row reduction is the Identity matrix whose columns are unit basis vectors. We start to transform the first column into the first unit basis vector by making the top left entry 1. Sometimes this can be done by interchanging rows so that a row whose first entry is already 1 is on top. Otherwise, the most straightforward way to make a11 = 1 is to divide the first row by its first element a11.

Step 4. Convert 1st Column

To make the other entries in the first column 0 using only row operations, we use the first row as the pivot row (the entry at the beginning of the row is the "pivot element"). If the entry we want to convert to 0 is in row i then we multiply the first row by -ai1 and add it to the ith row, changing the ith row. This step is repeated for i = 2, 3, ..., m.

Step 5. Convert Other Columns

This is where the work gets done and where mistakes are easiest to make. Remember, we are trying to convert the coefficient matrix as close as possible to an Identity matrix. Ignoring any rows that are finished (only the first row, at first), examine the columns of the matrix, starting from the left, looking for the first one which has a nonzero entry in some later row. Interchange rows if necessary until the nonzero entry (preferably 1) is in the top row of those we're working on. If this entry is not 1, divide the row by the entry. Then make the rest of the entries in that column (both above and below) zero by pivoting on this entry. We repeat this process for each row so that its first nonzero entry is 1. This entry is called a “pivot”. All the columns containing pivots should have zeros everywhere else (columns of an identity matrix). The columns that don't contain pivots correspond to independent variables and indicate the independent (free) variables. We can assign any value to an independent variable.

Step 6. Check Consistency

A system of equations is consistent if it has a solution. If the reduced augmented matrix has a row of zeroes except for a nonzero final entry, it yields the equation 0 = nonzero which is impossible. When we find that a system is inconsistent, we stop the solution process.

Step 7. Rewrite Equations

If we put the variables back into the equations with the revised coefficients and set each equation equal to the right hand column entries of the reduced auxiliary matrix, we derive a system of equations equivalent to the original system (the solutions to the two systems are the same) but solutions are easier to see.

Step 8. Add Equations

To write the solution in vector form we will need an equation for each variable. Since independent variables have no pivot in their columns, they will not appear first in any revised equation. Thus we use the trick of setting each independent variable equal to itself. These new equations are trivially valid.

Step 9. Solve Equations

It is easy to rewrite the equations from steps 7 and 8 as: "the pivot variable = a linear combination of the independent variables and the constant term". We can assign arbitrary values to the independent variables and evaluate the right side of each revised equation to get values for the pivot variables (for a particular solution).

Step 10. Write Solution in Vector Form

When we write the general solution to a system in vector form, we can identify basis vectors for the solution space (set of solutions to the corresponding homogeneous system of equations). Note that these are the coefficient vectors of the independent variables (the non-unit-vector columns) in the reduced matrix. Note that we can identify the basis for the column space by finding vectors in the original coefficient matrix that correspond to unit vector columns in the row echelon form . There will be as many column space basis vectors as there are non-zero rows in the reduced matrix; the number is the dimension of the column space.

Step 11. Check Answers

You should always check your answer. It is easy to do in this methodology since the equations are all set up for you.

MODEL 2:

We will solve the system: x + 2y - z + 3s - 4t = -4

2x + 4y - 2z + 5s - 5t = -2

3x + 6y + 2z + 4s - 2t = 23

Step 1. Form Coefficient Matrix

The matrix of coefficients of the variables is:

[pic]

Step 2. Form Augmented Matrix

Because the augmented column is all zeroes, it will never change when using row operations. Thus we could omit it in further computations (as you can see, below)

[pic]

Step 3. Make a11 = 1

a11 is already 1.

Step 4. Convert 1st Column

-2R1 + R2 -> R2 gives [pic] and then

-3R1 + R3 -> R3 gives[pic]

Step 5. Convert Other Columns

The first column with a nonzero entry below the first row is column 3. Since the nonzero entry is the 5 in the third row, we must interchange rows 2 and 3.

[pic]

Since the pivot entry in row 2 column 3 is not 1, we must divide row 2 by 5 and then use this pivot to make the entry in row 1 column 3 zero.

(1/5)R2 -> R2 [pic], R2 + R1 -> R1 [pic]

Finally, we need to multiply row 3 by -1 and pivot on the element in row 3 column 4 to make the rest of column 4 zero. Then the matrix will be in row echelon form since every row will have a pivot for its first nonzero entry and each column with a pivot will be a unit vector.

(-1)R3->R3, R3 + R2 -> R2, [pic], -2R3 + R1 -> R1 [pic]

Step 6. Check Consistency

Since there are no zero rows in the row echelon form, we know that the system is consistent. There will be a solution.

Step 7. Rewrite Equations

Substituting the revised coefficients from the row echelon form back into the equations we obtain the system:

x + 2y + 4t = 15

z - t = 1

s - 3t = –6

Step 8. Add Auxiliary Equations

Since columns 2 and 5 have no pivot, y and t will be independent variables. Thus we need to add two equations

y = y and t = t to the three equations in step 7.

Step 9. Solve Equations

We rewrite the equations with a single variable on the left and the rest on the right as follows:

x = 15 – 2y - 4t

y = y

z = 1 + t

s = –6 + 3t

t = t

Step 10. Write Solution in Vector Form

[pic]

Step 11. Check Answer

We need to assign values to the independent variables y and t, say y = 2, t = 4. Then evaluate the other variables from the equations in step 9 or the vectors in step 10. Thus x = -5, y = 2, z = 1, s = -6, t = 4. Substituting these values into the original equations we get:

–5 + 2(2) – 5 + 3(6) – 4(4) = –4 check

2(-5) + 4(2) – 2(5) + 5(6) – 5(4) = –2 check

3(-5) + 6(2) + 2(5) + 4(6) – 2(4) = 23 check

Everything checks out so we are fairly confident that our answer is correct. Checking a different mix of values for y and t would give us more confidence.

EXERCISE:

Use the methodlogy to determine whether this system is consistent - if so, give the solution (set) in vector form.

[pic]

CRITICAL THINKING QUESTIONS:

1. The goal in using the row operations is to obtain a matrix as close as possible to an identity matrix. Why?

2. What are some of the errors you might expect to make when performing step 5?

3. Why do the columns without pivots correspond to the independent variables in the problem? What does "independent" mean in this context?

4. Suppose that we wanted to find a basis and the dimension of the solution space (for a homogeneous system). Which step gives us the information to answer this question?

5. Suppose that we wanted to find a basis and the dimension of the column space of the coefficient matrix. Which step gives us the information to answer this question?

-----------------------

[pic]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download