Class Note for MATH 410 with Professor Dostert at UA
Class Note for MATH 410 with Professor Dostert at UA
Popular in Course
Popular in Department
This 11 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Arizona taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Class Note for MATH 410 with Professor Dostert at UA
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
THE UNIVERSITY Q or ARIZONA Math 410 Matrix Analysis Section 13 Gaussian Elimination Regular Case Section 14 Pivoting and Permutations Paul Dostert January 13 2009 111 A Augmented Matrix We define the augmented matrix to be a matrix formed by the coefficient matrix and right hand side 6011 G12 39 39 39 aln 51 G21 G22 39 39 39 G271 52 M Ab aml am2 39 39 39 amn bm Note that this is an m gtlt n 1 matrix For now we ll consider only m n Ex Write the following system in augmented matrix form xy7rz 5 4xy 2z 1 0 xy z A Gaussian Elimination We have an operation on the augmented matrix corresponding to the Linear System Operation 1 Elementary Row Operation 1 Add a scalar multiple of one row of the augmented matrix to another row Using this operation we attempt to reduce the augmented matrix to triangular form We call each diagonal entry starting at all a pivot entry The an entry would be the first pivot the second pivot is a22 and so on We require a pivot be nonzero This process of reducing to triangular form is called Gaussian Elimination The process of Gaussian Elimination is complete when we have reduced Alb gt Ulc7 where U is upper triangular uij 0 when 239 gt j After the system is reduced we can solve for the unknowns via back substitution We refer to this as regular Gaussian Elimination because we require each diagonal entry in the elimination procedure to be nonzero A Gaussian Elimination Examples Ex Attempt to solve each of the systems using Gaussian Elimination a 22yz 1 x yz x2y z 1 1 b 3y zw 1 x y z w 1 y2z3w 0 2z2w 8 At Elementary Matrices The elementary matrix E associated with an elementary row operation for m rowed matrices is the matrix obtained by applying the row operation to Im Ex Write the elementary matrix corresponding to the following operations on say a 3 gtlt 3 matrix a T2 T2 37quot1 b 7quot3 7quot3 T2 Since each elementary row operation can be written as an elementary matrix we can write the upper triangular matrix found using GE as a product of elementary matrices EjEj1 E1A U The inverse elementary matrix is the matrix that undoes the elementary matrix operation Ex For each of the matrices from the previous example find their inverses A LU Factorization For a regular 3 gtlt 3 matrix A we can apply GE so that E3E2E1A U Then L1L2L3E3E2E1A A L1L2L3U If A is regular then each L is lower triangular and U is upper triangular Thus we can write ALU where L is lower triangular and U is upper triangular This is referred to as LUFactorization Thm A matrix A is regular iff it can be factored as A LU with L lower triangular and Li 1 and U is upper triangular with UN 7 0 In practice the LU decomposition is computed by finding U by GE then filling in the entries of L that correspond to A LU Ex Compute the LU factorization of Alt Milki k NOON wHH V Ah Solving using LU Factorization Suppose we have written A LU and we wish to solve Ax b How can we do this Wewrite AmbLUmb gtLcb where c Use 80 we solve Lc b for c using forward substitution then we solve Um c using backward substitution Ex Using the LU decomposition of the system on the previous slide solve Ax b for A Pivoting Suppose in the GE algorithm we end up with a zero on the diagonal entry What can we do Since the order in which the linear equations are written is arbitrary we can swap rows Elementary Row Linear System Operation 2 We can interchange two rows of the matrix two equations of the linear system Ex Write the following system as an augmented matrix and reduce to upper triangular form using GE with pivoting 2yz 1 x yz 3 x2y z 1 A square matrix is called nonsingular if it can be reduced to upper triangular form with non zeros on the diagonal using elementary row operations 1 and 2 Thm A linear system Ax b has a unique solution for every 9 iff A is square and nonsingular A Permutation Matrices and LU Factorization A permutation matrix is a matrix obtained from the identity matrix by any combination of row interchanges Ex What are the different permutation matrices for 2 gtlt 2 matrices What about 3 gtlt 3 Recall that we were not able to perform LU factorization on a non regular matrix However if we can perform all necessary permutations first then LU factorization may work just fine Thm Let A be an n gtlt n matrix The following conditions are equivalent a A is nonsingular b A has n nonzero pivots c A admits a permuted LU factorization PA LU In practice we simply keep track of any permutations made during LU factorization and incorporate these into the P matrix Ex Compute the permuted LU factorization of A GE in Matlab Suppose we have 4 6 2 0 3 8 11 4 1 4 2 11 In Matlab we need to write the augmented matrix as the coefficient matrix and a column vector containing the constants the RHS vector To write a matrix or vector we use brackets A comma separates entries in a row and a semicolon indicates a move to a new row Generally we refer to the matrix as A and the RHS vector as b The command c Ab means solve Ax b for m using Gaussian Elimination We write A 46 2 381 1 14 2 b 041 1 X A b This will only work correctly for uniquely solvable systems Otherwise it will give you a possible solution if there are infinitely many solutions or a close solution if there are no solutions A Permuted LU in Matlab Suppose we have lt3me summon l wuo 1 Matlab has a nice construct to compute and LU factorization As you might guess the function is lu and the function returns matrices L and U Let us try this out A1 23001 24 1 341 307 1 L U uA What happened What do L and U look like Since L is not lower triangular this indicates that we should have used a permuted LU This is actually the SAME EXACT function but we just need to tell it that it can return a P matrix as well Try L U P uA Note that we have a lower triangular L upper triangular U and a non identity permutation matrix P
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'