LU decompositionEl ementary ma tricesExample 1.•1 00 1a bc d=•0 11 0a bc d=•1 0 00 2 00 0 1a b cd e fg h i=•1 0 00 1 03 0 1a b cd e fg h i=Definition 2. An elementary matrix is one that is obtained by performing a singleelementary row operation on an identity matri x.The result of an elementary row operation on A is EAwhere E is an elementary matrix (namely, the one obtained by performing the same row operationon the appropriate identity matrix).Example 3. Elementary matrice s are invertible because row operations are reversible.•1 0 00 1 0−3 0 11 0 00 1 03 0 1=We write1 0 00 1 03 0 1−1=1 0 00 1 0−3 0 1, but more on inverses soon.•1 0 02 1 00 0 1−1=•1 0 00 2 00 0 1−1=•1 0 00 0 10 1 0−1=Armin [email protected] elimination revisit edExample 4. Keeping track of the elementary matrices during Gaussian elimination on A:A =2 14 −6EA =1 0−2 12 14 −6=2 10 −8Note that:A = E−12 10 −8=1 02 12 10 −8We factored A as the product o f a lower and upper tria ngular matrix!We say that A has triangular fact orization.A = LU is kn own as the LU decomposition of A.Definition 5.lower triang ular∗ 0 0 0 0 0 0 0∗∗ 0 0∗ ∗∗ 0∗ ∗ ∗∗upper triangular∗ ∗ ∗∗∗ ∗∗∗∗ ∗missing entries are 0Example 6. Factor A =2 1 14 −6 0−2 7 2as A = LU .Solution. We begin w ith R2 → R2 − 2R1 followed by R3 → R3 + R1:E1A =1 0 0−2 1 00 0 12 1 14 −6 0−2 7 2E2(E1A) =1 0 00 1 01 0 1Armin [email protected] =1 0 00 1 00 1 1=2 1 10 −8 −20 0 1= UThe factor L is given by:L = E1−1E2−1E3==In conclusion, we found the followi ng LU decomposition of A:A =2 1 14 −6 0−2 7 2= LU =2 1 10 −8 −20 0 1Once we have A = LU, it is simple to solve Ax = b.Ax = bL(Ux) = bLc = b and Ux = cBoth of t h e final systems are triangular and hence easily solved:• Lc = b by forward substituti o n to find c, and th e n• Ux = c by backward substitution to find x.Important practical point : can be quickly repeated for many differentb.Example 7. Solve2 1 14 −6 0−2 7 2x =410−3.Solution.Armin [email protected] ar factors for an y matrixCan we factor any matrixA as A = LU ?Yes, almost! Thi nk about the process of Gaussian elimina t ion.• In each step, we use a pi vot to produce zeros below it.The corresponding elementary matrices are lower diagonal!• The only other thing we might have to do, is a row exchange.Namely, if we run into a zero in the position of the pivot.• Al l of these row exchanges can be done at the beginning!Definition 8. A permutati on matrix is on e that is obtained by performing rowexchanges on an identity matrix.Theorem 9. For any matrix A there is a permutation matrix P such that PA = LU .Example 10. Consider A =0 23 4.Armin
View Full Document
Unlocking...