CHAPTER 04.07: LU DECOMPOSITION: Basis

In this segment, we're going to talk about LU decomposition method of solving simultaneous linear equations, and try to figure out what the basis of LU decomposition method is to solve . . . to solve simultaneous linear equations.  So let's look at just the basis of it. So when you are given a set of equations, you might be given, let's suppose, n equations, n unknowns, so you'll have the coefficient matrix, A, which will be an n-by-n matrix, and then you have your solution vector, or your unknown vector as they may call it, equal to C, which is the right-hand side vector.  So what we want to do is, we are given the coefficient matrix, A, we are given the right-hand side vector, C, and we want to find out what the solution vector, X, is. 

So let's see what the LU decomposition method is based on.  It's based on that if you can write A is equal to L times U.  So if you are able to take the coefficient matrix and write it as a lower triangular matrix multiplied by an upper triangular matrix, so this is a lower triangular matrix, and this is an upper triangular matrix. So if you are able to write down A is equal to L times U, then how can we use this . . . this equation, or this breaking down of A into L times U into solving a set of equations, and how does it help us? So if I have A is equal to L times U, I can substitute my . . . instead of A, I'll put L times U into my . . . into my set of equations and see what I get.  So what that means is that instead of A I'm putting L times U times X is equal to C.  So A has been decomposed into a lower triangular matrix multiplied by an upper triangular matrix, X is still the unknown vector, the solution vector, and C is the right-hand side.  Now I can take L inverse of both sides, if L inverse exists.  So I can multiply it by L inverse on both sides, if L inverse exists, and that's what I'm going to get.  Now, I know that L inverse times L is nothing but the identity matrix.  So I'll get identity matrix times the upper triangular matrix times the solution vector is equal to the inverse of the lower triangular matrix times the right-hand side vector, C. Now, identity matrix multiplied to any other matrix, if, again, the multiplication is possible, will be the matrix itself, so it's U times X is equal to L inverse times C.  So is what I have been able to get it broken down into, and I'm going to say, hey, let this be equal to Z.  Let this be equal to Z, and you can very well see that what Z will be, since U is n-by-n, X is n-by-1, L inverse will be n-by-n, C is n-by-1, Z will be also an n-by-1 matrix, it'll be n rows and one column, that's what Z will be.  Again, keep in mind that Z is not known to us, so I'm going to put in parentheses here, say, say that U times X is equal to L inverse times C, which we got from here, but equal to the single column vector here, which is just simply Z.  So let's say that it is equal to Z.  How does that help me? Because now I can say, hey, L inverse times C is equal to Z, and I can multiply now both sides by L . . . L matrix, and I'll get L times Z, and since L times L inverse is the identity matrix, that's the definition of an inverse of a matrix, and then since identity matrix times C will be the C itself will be equal to L times Z.  So that's what I'm going to get from here, the C will be equal to L times Z, and then I also have that U times X is equal to Z from here, right?  So basically what I have is two sets of equations.  U times X is equal to Z, and then I have L times Z is equal to C.  So you can see that you can solve this L times Z first equal to C, because you know the L, because you know what the decomposition is taking place for A.  So you know L, you know C, which is your right-hand side, you can find Z.  So once you have found Z, you can plug it back in here, and since you know your upper triangular matrix, you can find out what the value of X is.  So that's what the LU decomposition method is based on.  So let me write this down here.  So basically what you will be doing is that you'll solving L times Z equal to C first, which is the first set of equations which you're going to solve, and then once you have found Z, you'll have U times X is equal to Z.  So L is known, C is known, you'll be able to find Z, so once Z is known, Z is known, U is known, you'll be able to find out what X is, so that'll be the second set of equations which you'll be solving. Now what is the advantage of doing it this way?  It is because of the fact that when you have an L, let's suppose you have a 3-by-3 matrix, let's suppose L is a 3-by-3 matrix, so our L is going to look like this . . . your L is going to look like this, it'll have nonzero numbers here, and then there will be 0 numbers right here.  So that's your Z is going to be here and your right-hand side, C, is going to be here. 

So you can very well see that in order to find z1, z2, z3, you can solve the first equation right here, because there's only one unknown in the equation, because these two are 0s, and then you can find out the next entry of z, so let me just change the Z to, just for clarification purposes, z1, z2, z3, and then c1, c2, and c3. So you can see that what is happening is that if you look at the first equation, the only unknown is z1, because 0 will get multiplied by z2 and 0 will get multiplied by z3, so you will get z1 from the first equation.  So from the first equation, you can definitely get z1, because it is just one equation, one unknown.  Now if you look at the second equation, it is this term multiplied by z1, this term multiplied by z2, plus 0 times z3, so you have two unknowns, you have z1 and z2 unknowns, but z1 you just found out, so you can find out z2 from there.  Same thing here, here you have this multiplied by z1, this multiplied by z2, this multiplied by z3 equal to c3, so you might think there are three unknowns, but there is only one unknown, because you just found z1 and z2 from the previous relationships, so you will get z3 from there. So you can very well see that the reason why we do LU decomposition method is because we can solve this equation . . . this set of equations by solving one equation, one unknown at a time, by something which is called forward substitution, because you are doing the substitution forwards.  And same thing, once your z1, z2, and z3 are found, you can look at this, if this is the U matrix, which is x1, x2, x3, let's suppose, for a 3-by-3 example, and I'll put my z1, z2, and z3 values, which I just obtained from solving the first set of equations there, and then I'll have for the upper triangular matrix is going to look like this so far as its population is concerned, and there will be 0s right here, and now here I can do back substitution, because I can solve this equation, and I'll be able to find out what x3 is.  Now, when I take this equation here, I know that there are two unknowns in there, x2 and x2, but I just found out x3, so it is basically trying to solve only one equation at a time.  Same thing here, with the forward substitution here, I'll have x1, x2, x3 in the equation, but since x2 and x3 were just found out by the back substitution, I will have the value of x1 from the first equation.  So, again, this part also is about solving one equation, one unknown at a time, and that's called back substitution. So this forward substitution and back substitution is what's going to help us to be able to do the . . . do the LU decomposition method, solve L times Z equal to C first, and then solve U times X equal to Z, and that's the basis of the LU decomposition method. And that's the end of this segment.