Section 2.5 Matrix FactorizationDefinitionA matrix factorization is a representation of a matrix as a productof two or more other matrices.Example3 −19 −5=1 03 13 −10 −2MotivationTo solve a matrix equation A~x =~b, we typically perform rowreduction.Gaussian elimination implicitly factors A into a product of matricesthat enable us to solve the given equation.ExampleLetA =2 1 34 −1 3−2 5 5, U =2 1 30 −3 −30 0 2,and takeE1=1 0 0−2 1 00 0 1, E2=1 0 00 1 01 0 1, E3=1 0 00 1 00 2 1.Note thatE3E2E1A = U.Example continuedIt follows thatA = E−11E−12E−13U=1 0 02 1 00 0 11 0 00 1 0−1 0 11 0 00 1 00 −2 1U=1 0 02 1 0−1 −2 1U= LU.Hence A can be factored as a product of a unit lower triangularmatrix L and an upper triangular matrix U.Definition of LU FactorizationDefinitionLet A be a square matrix. A factorization of A as A = LU, where Lis unit lower triangular and U is upper triangular, is called an LUfactorization of A.Criterion for existence of LU factorizationTheoremIf A is a square matrix that can be reduced to row echelon formwithout using any row interchanges, then A has an LUfactorization.Solving matrix equations using LU factorizationConsider the matrix equationA~x =~b,and suppose that A = LU is an LU factorization of A.We can write the matrix equation asL(U~x) =~b.Defining~y = U~x, we can then solve in two stages.1 Solve L~y =~b for~y by forward substitution.2 Sove U~x =~y for~x back substitution.ExampleUse an LU factorization of A =2 1 34 −1 3−2 5 5to solve A~x =~b,where~b =1−49.You may recall that we earlier foundL =1 0 02 1 0−1 −2 1, U =2 1 30 −3 −30 0 2.Uniqueness of LU factorizationTheoremIf A is an invertible matrix that has an LU factorization, then Land U are unique.Existence of LU factorization not guaranteedExampleShow thatA =0 12 3does not have an LU factorization.Note however, that for P =0 11 0, we may reduce PA =2 30 1to row echelon form without using any row interchanges.In fact,PA =1 00 12 30 1= LU.Numerical NotesBoth LU factorization and computation of A−1require O(n3)operations.If A is sparse (with mostly zero entries), then L and U may besparse, too, whereas A−1is likely to be dense. In this case,solution of A~x =~b by LU factorization is much faster thanusing A−1.When A is invertible, the LU factorization of A can be used tofind A−1, and storage of the LU factorization may requiremuch less
View Full Document
Unlocking...