LU factorization

hey thanks for watching and welcome to the Lu factorization and I know what you're thinking oh my god Shen Lu no it's another new it's literally new factorization how cool is that and it's actually a very nice way of decomposing a matrix and I'll show you a very neat application to solving systems of equations so in fact let's do that let's find the Lu find Lu factorization of the matrix 3 9 4 5 so this is the matrix a and what do we want to do we would like to write it as a product of two very special matrices one which is L as a lower triangular so it looks like this where the terms above the diagonal are 0 and upper triangular we're not the entries above the diagonal so we're the entries below the diagonal are 0 and of course you can generalize this very easily to 3 by 3 4 by 4 etcetera etcetera matrices so that's not a problem ok how do you do this it's very similar to the technique of writing a matrix as a product of elementary matrices namely you have to row reduce this matrix and keep track of the row reduction steps so whoops sorry different video what let's see so just run reduce so let's do that we have the matrix 3 9 4 5 then notice first of all we can divide this by 3 so the first step would be division by 3 to get 1 3 4 5 and then so very important by the way when you wanna add a certain road to the other one you have to go down like it would not be possible so it wouldn't give you Lu decomposition if you for example add negative 1/4 times this row to this row so very important if you do a elementary row operation it would have to go down so in particular would would like to do now who would like to ah negative 4 times this row to this row then we get how nice actually upper triangular matrix 1 3 0 minus 7 and this will be argue because it's upper triangular and of course for 3x3 matrices you just repeat the steps until you basically get the row echelon form which is sort of an upper triangular matrix so here we know we're done because it does look upper triangular and then the question is how would we get L and we just get L by writing those two operations as matrices so what did we have we started with 3 9 4 5 and then the first thing was we divided the first row by 3 and the elementary matrix that says divide the first row by three it's the identity matrix except you know the first row becomes the first entry becomes 1/3 and you can indeed check that if you do this multiplication you get this matrix then what was the second thing we added negative four times the first row to this row and we get simply one it's the identity matrix except because you took minus four fourth times the first row which becomes the first column to the second row we have a minus 4 here it's so minus 4 1 and we get our upper triangular matrix and just notice one thing with all those operations and that's what was so careful of doing stuff going down in all those operations the matrices they will always be lower triangular so in particular this matrix the product will be lower triangular and the inverse will be as well that's why we would get a lower triangular matrix at the end so what do we get that we get you know 3 9 4 5 equals 2 so we have this matrix times this matrix if we want to put this junk on the left hand side would have to use the inverse so this becomes whatever this matrix is 1 0 negative 4 1 1/3 0 1 sorry 0 0 1 inverse of 1 3 0 minus 7 and remember to find the inverse of a product you reverse the order so it would be 1/3 0 0 1 inverse 1 0 negative 4 1 inverse and 1 3 0 negative 7 and you're so cool thing the inverse of an elementary matrix is still an elementary matrix so the inverse of dividing the first row by 3 is multiply the first row by 3 so we get 3 0 0 1 and the inverse of subtract 4 times the first row to the second row becomes add to 4 4 times the first row to the second row so 1 0 4 1 so you change this minus 4 into a plus 4 and then we get a 1 3 0 minus 7 and lastly all you need to do is just multiply those two matrices together and basically because each matrix is lower triangular the product will still be lower triangular so we get 3 0 4 1 now you see this becomes ul this becomes u u and that a will be Lu so in other words what do we get in the end we just have a which was three nine four five so that's a equals to adore triangular matrix so this is L times an upper triangular matrix which is U so a equals to Lu Oh actually 25.5 in persian are lu a means Alec peach so yeah peachy matrix I think also in Hindi is are like potato or something I'd like a loon on so that's good why is this useful in fact it's useful because I think that's how computer soft systems of equations they usually use the Lu decomposition because so let me give you an application so why useful it's soup it it basically helps you solve systems of equations very easily suppose we want to solve ax equals three minus three well a is just lu lu x Fiats is three minus now let yd u x then all we really need to solve first is ly is three minus three but L was really easy so it turns out this system becomes very easy to be solved so maybe let me write that here so really what we have to solve is 3 0 4 1 y1 y2 equals 3 and minus 3 so this is why and let us write this in terms of systems of equations and you'll see why this is useful we just get 3y 1 equals 3 and 4 y 1 plus y 2 equals minus 3 okay and okay good then notice this becomes much easier because first we solve y 1 to get 1 and then we solve y 2 y 2 is simply minus 3 minus 4 y 1 and it's minus 3 minus 4 and that's minus 7 and so you see that's why the fact that this was lower triangular is useful because the first equation becomes easy to solve then the second one is easy to solve then the third one etc etc so you're taking a complicated system and essentially turn it into two systems that are easier to solve so in other words what do we get y is now 1 minus 7 the question is now what is X but remember what X was Y was just UX to just solve X using this equation so in other words UX equals y and now remember that use upper triangular so it's also easy to solve 1 3 is 0 minus 7 say X is X 1 X 2 equals 1 minus 7 and then you just write it in terms of systems so x1 plus 3x2 equals 1 and minus 7 x2 is minus 7 again you see we get an easier system so from this we get X 2 equals 1 and from this we get X 1 is 1 minus 3 X 2 and it's 1 minus 3 and that's minus 2 and so our solution in the end is minus 2 1 and indeed you can check that if X is this and a is this that ax is precisely 3 minus 3 of course for 2x2 systems it seems kind of crazy but the advantage is really for 3x3 systems and higher assistance because you're essentially taking a super complicated system and you turn it into two systems that are much easier to solve that's why this Lu decomposition is very nice alright I hope you like this Lu extravaganza if you wanna see more math please make sure to subscribe to my channel thank you very much

Channel: Dr Peyam

Views: 17,795

Keywords: linear algebra, matrix, inverse, row-reduction, row reduction, echelon form, pivot, gaussian elimination, system of equations, math, peyam, dr peyam, algebra, LU, lu, lu decomposition, decomposition, factorization, LU factorization, lower, upper, lower-triangular, upper-triangular, triangular, algorithm, solving system fast, computer solving system, computer, computer algebra, decompose matrix, elementary matrix, elementary

Id: HwUjN5JKzQU

Length: 13min 5sec (785 seconds)

Published: Sat Feb 23 2019