11. LU Decomposition

1 11. LU DecompositionCertain matrices are easier to work with than others. In this section, wewill see how to write any square matrixMas the product of two matricesthat are easier to work with. We ll writeM=LU, where: Lislower triangular. This means that all entries above the maindiagonal are zero. In notation,L= (lij) withlij= 0 for allj > Uisupper triangular. This means that all entries below the maindiagonal are zero. In notation,U= (uij) withuij= 0 for allj < M=LUis called is a useful trick for many computational reasons. It is much easierto compute the inverse of an upper or lower triangular matrix. Since inversesare useful for solving linear systems, this makes solving any linear systemassociated to the matrix much faster as well.

2 We haven t talked aboutdeterminants yet, but suffice it to say that they are important and very easyto compute for triangular systems associated to triangular matrices are very easy tosolve by back substitution.(a b10ce) y= (1 bec) 1 0 0da1 0eb c1f x=d. y=e ad, z=f bd c(e ad)For lower triangular matrices,backsubstitution gives a quick solution;for upper triangular matrices,forwardsubstitution gives the to Solve Linear SystemsSuppose we haveM=LUand want to solve the systemMX=LUX=V. Step 1: SetW= uvw =UX. Step 2: Solve the systemLW=V. This should be simple by forwardsubstitution sinceLis lower triangular. Suppose the solution toLW=VisW0. Step 3: Now solve the systemUX=W0. This should be easy bybackward substitution, sinceUis upper triangular.

3 The solution tothis system is the solution to the original can think of this as using the matrixLto perform row operationson the matrixUin order to solve the system; this idea will come up againwhen we study the linear system:6x+18y+3z= 32x+12y+ = 194x+15y+3z= 0 AnLUdecomposition for the associated matrixMis: 6 18 32 12 14 15 3 = 3 0 01 6 02 3 1 2 6 10 1 00 0 1 . Step 1: SetW= uvw =UX. Step 2: Solve the systemLW=V: 2 0 01 6 02 3 1 uvw = 3190 2By substitution, we getu= 1,v= 3, andw= 11. ThenW0= 13 11 Step 3: Solve the systemUX=W0. 2 6 10 1 00 0 1 xyz = 13 11 Back substitution givesz= 11,y= 3, andx= 63 11 , and we re an LU any given matrix, there are actually many , there is a uniqueLUdecomposition in which theLmatrix hasones on the diagonal; thenLis called alower unit triangular find theLUdecomposition, we ll create two sequences of matricesL0,L1.

4 AndU0,U1,..such that at each step,LiUi=M. Each of theLiwill be lower triangular, but only the lastUiwill be upper by settingL0=IandU0=M, becauseL0U0= , use the first row ofU0to zero out the first entry of every rowbelow it. For our running example,U0=M= 6 18 32 12 14 15 3 , so the secondrow minus13of the first row will zero out the first entry in the second , the third row minus23of the first row will zero out the first entryin the third be the lower triangular matrix whose first column is filledwith the constants used to zero out the first column ofM. ThenL1= 1 0 0131 0230 1 . SetU1to be the matrix obtained by zeroing out the firstcolumn ofM. ThenU1= 6 18 3060031 .3 Now repeat the process by zeroing the second column ofU1below thediagonal using the second row ofU1, and putting the corresponding entriesintoL1.

5 The resulting matrices areL2andU2. For our example,L2= 1 0 0131 023121 , andU2= 6 18 3060001 . SinceU2is upper-triangular, we redone. Inserting the new number intoL1to getL2really is safe: the numbersin the first column don t affect the second column ofU1, since the firstcolumn ofU1is already zeroed the matrix you re working with has more than three rows, just continuethis process by zeroing out the next column below the diagonal, and repeatuntil there s nothing left to fractions in theLmatrix are admittedly ugly. For two matricesLU, we can multiply one entire column ofLby a constant and divide thecorresponding row ofUby the same constant without changing the productof the two matrices. Then:LU= 1 0 0131 023121 I 6 18 3060001 = 1 0 0131 023121 3 0 00 6 00 0 1 130 001600 0 1 6 18 3060001 = 3 0 01 6 02 3 1 2 6 10 1 00 0 1.

6 The resulting matrix looks nicer, but isn t in standard matrices that are not square,LUdecomposition still makes anm nmatrixM, for example we could writeM=LUwithLa square lower unit triangular matrix, andUa rectangular matrix. ThenLwill be anm mmatrix, andUwill be anm nmatrix (of the sameshape asM). From here, the process is exactly the same as for a squarematrix. We create a sequence of matricesLiandUithat is eventually theLUdecomposition. Again, we start withL0=IandU0= s find theLUdecomposition ofM=U0=( 2 1 3 4 4 1).4 SinceMis a 2 3 matrix, our Decomposition will consist of a 2 2 matrixand a 2 3 matrix. Then we start withL0=I2=(1 00 1).The next step is to zero-out the first column ofMbelow the is only one row to cancel, then, and it can be removed by subtracting2 times the first row ofMto the second row ofM.

7 Then:L1=(1 02 1), U1=( 2 1306 5)SinceU1is upper triangular, we re done. With a larger matrix, we wouldjust continue the a square block matrix with square blocksX,Y,Z,Wsuch thatX 1exists. ThenMcan be decomposed with anLDUdecomposition,whereDis block diagonal, as follows:M=(X YZ W)Then:M=(I0ZX 1I)(X00W ZX 1Y)(I X 1Y0I).This can be checked simply by multiplying the product on the a 2 2 matrix, we can regard each entry as a block.(1 23 4)=(1 03 1)(100 2)(1 20 1)By multiplying the diagonal matrix by the upper triangular matrix, weget the standardLUdecomposition of the : LUDecomposition BlockLUDecomposition5 Review Questions1. Consider the linear system:x1=v1l21x1+l22x2= + +xn= to find a formula LetM=(X YZ W)be a squaren nblock matrix invertible, what size areX,Y, andZ?

8 AUDLdecomposition forM. In other words, fill in thestars in the following equation:(X YZ W)=(I 0I)( 00 )(I0 I)6