ECE 174 Lecture Supplement SPRING 2009 Review of Gaussian Elimination and LU Factorization Ken Kreutz Delgado Electrical and Computer Engineering Jacobs School of Engineering University of California San Diego VERSION ECE174LSGE S09v1 Copyright c 2006 2009 All Rights Reserved April 7 2009 The Elementary Row Matrices ERM s Ep q and Pp q Elementary row matrices are defined by the elementary row operations which they perform Ep q Add rowp to rowq I e rowq rowq rowp Pp q Interchange Permute rows p and q 1 E E is lower triangular for p q Ep q p q p q 1 0 0 1 0 0 E2 3 4 E2 3 4 I3 E2 3 4 0 1 0 0 1 0 0 0 1 0 4 1 1 P P 2 I Pp q Pp q q p p q P1 3 1 0 0 0 0 1 P1 3 I3 P1 3 0 1 0 0 1 0 0 0 1 1 0 0 It is important to note that ERM s premultiply the matrix that they are operating one Also note T which is true only for an elementary permutation matrix It is not true for a that Pp q Pp q 1 2 K Kreutz Delgado Copyright c 2006 All Rights Reserved Version ECE174LSGE S06v1 general permutation matrix P A general permutation matrix P is defined to be a product of elementary permutation matrices P Pp q Pk l and has the property that P 1 P T P P T I As mentioned in general P 6 P T P 1 Example 1 Gaussian Elimination GE 1 3 3 2 6 9 5 R3 4 A 2 1 3 3 0 1 3 3 2 U E2 3 2 E1 3 1 E1 2 2 A 0 0 3 1 z 0 0 0 0 L Recall that The matrix U L A is said to be in Upper Echelon Form Because L is a product of lower triangular matrices it is itself lower triangular Pivots are 1 and 3 Pivots cannot have the value 0 Rank of A r A Number of Pivots r A Number of linearly independent columns dim R A The pivot columns of A are linearly independent and form a basis for R A r A Number of linearly independent rows dim R AT dim R A dim R AT A E1 2 2 E1 3 1 E2 3 2 U L U 1 L E1 2 2 E1 3 1 E2 3 2 2 1 where 0 0 1 0 2 1 Note that L L 1 The inverse of a lower respectively upper triangular invertible matrix is always a lower upper triangular matrix Note the pattern which holds between the elements of L and its factors Ep q This pattern does not hold for the elements of L K Kreutz Delgado Copyright c 2006 All Rights Reserved Version ECE174LSGE S06v1 3 Example 2 GE with Row Exchange 1 1 1 A 1 1 3 2 5 8 r A 3 1 1 1 P2 3 E1 3 2 E1 2 1 A U 0 3 6 0 0 2 E1 2 2 E1 3 1 P2 3 A U 1 0 0 P2 3 A E1 3 1 E1 2 2 U LU 2 1 0 z 1 0 1 0 A LU Factorization We have shown that there is an equivalence between Gaussian elimination which you first encounter in middle school and LU factorization Without loss of generality one often discusses the simpler problem A LU This is because one can always fix a matrix A for which this is not true via the transformation A A0 P A where P is a product of elementary permutation matrices which rearranges the rows of A We often want an even simpler structure Namely we would like the pivots of A to be on the main diagonal of U Thus U of example 2 is OK in this regard while U of example 1 can be placed into the simpler diagonal form by permuting columns 2 and 3 This natural leads us to a discussion of elementary column matrices Elementary Column Matrices Postmultiplication of a matrix A by an elementary matrix results in an elementary column operation In particular postmultiplication a matrix A by the elementary permutation matrix Pp q results in 1 P T a swapping of column p with column q As before Pp q p q Pp q Example 1 continued 1 3 3 2 L A 0 0 3 1 0 0 0 0 K Kreutz Delgado Copyright c 2006 All Rights Reserved Version ECE174LSGE S06v1 L A P2 3 4 1 3 3 2 0 3 0 1 U 0 0 0 0 A P2 3 L U z A0 A0 Thus the transformed matrix has an L U factorization where L is lower triangular and U is upper echelon with pivots on the diagonal Most generally if we premultiply a matrix A from the left by a permutation matrix PL to rearrange the rows and postmultiply from the right by a permutation matrix PR to rearrange the columns we can always place A into a form A0 which has an L U factorization with the pivots on the diagonal of U A0 PL A PR L U For ease of exposition and without loss of generality in most discussions of LU factorization it is common to assume the simpler case that A L U where L is lower triangular and U is upper echelon with pivots on the diagonal This is because one can always fix A to ensure that this is true via the transformation A A0 PL A PR Solving the Linear Inverse Problem Ax b The same row operations L acting on both sides of the equation Ax b preserves equality Ax b L Ax L b The simultaneous operation of L on A and b can be written in the equivalent form A b L A b L A L b z c Example 1 continued With L E2 3 2 E1 3 1 E1 2 2 then b1 b1 b b2 c L b b2 2b1 b3 2b2 5b1 b3 Alternatively one can find the value of c by solving the system L c b using forward substitution Once the value of c has been determined we can then focus on the system L A x c Thus T L A P2 3 P2 3 x c z z U x K Kreutz Delgado Copyright c 2006 All Rights Reserved Version ECE174LSGE S06v1 x1 x1 x 1 x x 2 T 3 x 2 P2 3 x P2 3 x3 x2 x 3 x x4 x4 x 4 x 1 3 3 2 1 0 3 0 1 x 2 c x 3 0 0 0 0 z x 4 z U 5 1 x U1 U2 x b c 0 0 x f z z x U with 1 3 U1 0 3 3 2 U2 0 1 x 1 x x b 1 x 2 x3 x 3 x and x f 2 x 4 x4 …