12 Gaussan Elimination12高斯消去法
1.2 Gaussian EliminationRow-Echelon FormIn 1.1, we worked on manipulating an augmented matrix using elementary row operations so that our resulting equations could easily be solved for the values of the variables.Our Goal was to get the augmented matrix into Row-Echelon Form: All zero rows are at the bottom The first non-zero entry in any row is a 1 (leading 1) The leading 1 in a row is in a column to the right of all leading ones above (show on the board)Reduced Row-Echelon FormIf a matrix in row-echelon form meets the following condition, it is said to be in reduced row-echelon form: Each leading 1 is the only non-zero entry in its column. (show on the board)Solving a systemSolve the following augmented matrices. Are they in row-echelon form? Are they in reduced row echelon form?10040103001510052010220014600001 The technique of solving an augmented matrix which is in row-echelon form is called back-substitution.One more exampleThe variables which are represented by a column with a leading one are called leading variables.When we solve the system, any non-leading (free) variables will be parameters. They are free to take on any value, and those values will determine the values of our leading variables.120025001022000134Solving a SystemSolve the following system using reduced row-echelon form.x 2y z 22x 5y 2z 17x 17y 5z 1 Note that the third row became a row of zeros. Why did this happen? The third row is simply a linear combination of the first two rows: R3 = 3R2 + R1 (We can see this by working through the row operations we have performed.)Solving a SystemSolve the following system using reduced row-echelon form.2x y z 24x y 4y 2z 5 Third row became a row of zeros and makes the system impossible. Why? The last row is R3 + (2R1 - R2), so lets compare R3 w/ 2R1-R2 R3 : y - 2z = -5 2R1 - R2 : 2(2x-y+z) - (4x-y) = -4 +4 -y +2z = 0 or y - 2z = 0 (both cannot be true)Gaussian AlgorithmStep 1: Rearrange rows so that each row has its leading entry at least as far to the left as the rows belowStep 2: Multiply row 1 by the value that will create a leading 1.Step 3: Add a multiple of row 1 to the each of the rows below to eliminate the other non-zero terms in the same column as the leading 1. Step 4: Repeat steps 2-3 with row 2 (then 3,4,etc)03649121312303114597Consistent SystemsA system is said to be consistent if there is at least one solution, otherwise, the system is inconsistent.EXAMPLE: p. 23, 9a. (just do consistent or inconsistent)Theorems to be proven laterGiven a matrix, its equivalent representation in reduced row echelon form is unique (i.e. no matter the order of the elementary row operations, we will always arrive at the same matrix in reduced row echelon form.)Row echelon form, on the other hand, is not unique. If we perform the elementary row operations in a different order, we are likely to arrive at different matrices which are in row-echelon form.However, each of the possible representations in row-echelon form will have the same number of leading 1s (and the same number of leading vs. free variables).The number of leading 1s in the matrix when in row-echelon form is the Rank.Rank ExampleWhat is the rank of the following matrix (it is one of the matrices we have already worked with in this section)?03649121312303114597Implications of the RankSo, if you know the rank (r) of a matrix: then you know the number of leading 1s in the matrix and therefore the number of leading variables (r) If there are n variables altogether, then you have n - r free variables which will all be parameters in the solution (assuming a solution exists).Number of Solutions (Summary)We can determine the number of solutions that a system will have based on the row-echelon or reduced row-echelon form. If one of the equations has all zero coefficients, but the constant is not zero, the system must be inconsistent (no solution). If every variable is a leading variable (the rank is equal to the number of variables), then there is a unique solution. If there is at least one free variable, there will be a parameter in the solution and therefore infinite solutions (rank number of variables) Example: p. 23 #9a (finish)