CHAPTER 04.07: LU DECOMPOSITION: Example

In this segment, what we're going to do is we're going to take an example of using the LU decomposition method to solve a set of equations. So let's suppose somebody's giving you three equations, three unknowns, like this, 25, 5, 1, 64, 8, 1, 144, 12, and 1, and here is x1, x2, x3, is equal to 106.8, 177.2, and 279.2.  So you are given this three sets . . . set of equations, three equations, three unknowns, and what you want to do is you want to find out what x1, x2, and x3 are.  So the first step which you have to do in LU decomposition method is to decompose this particular matrix into L times U. So I'm going to write down what the L times U of this is, 64, 8, 1, 144, 12, and 1, the L times U is given as follows, and this is shown in a separate segment, how do you decompose a coefficient matrix, or this n-by-n matrix, into an L times U.  And it looks like this, 1, 0, 0, 2.56, 1, 0, 5.76, 3.5, and 1, and the upper triangular part is 25, 5, 1, 0, -4.8, -1.56, 0, 0, 0.7. So this is the LU decomposition of the coefficient matrix, and this is shown in a separate segment.  And what we want to do is we're going to now say, hey, L times Z is equal to C, so that's your right-hand side, and L is the lower triangular matrix, which is right here, and we'll find Z from there, so this is our first set of equations.  Once we have found Z from there, then we'll say U times X is equal to Z, and this will be our second set of equations. So once we have solved this set of equations, which will be this lower triangular matrix times Z equal to C, which is your right-hand side vector right here, 106.8, 177.2, and 279.2.  So once we have solved that, we'll find out what Z is.  So once Z is found, we will plug it back in here, we know our upper triangular matrix is this matrix right here, and we'll be able to find out what X is.  So that's what the . . . how the LU decomposition method is going to work.  So let's go ahead and take these steps and see what we get, so I'm going to write my lower triangular matrix, which is 1, 0, 0, 2.56, 1, 0, 5.76, 3.5, and 1, and Z is z1, z2, z3, and the right-hand side is already given to us is 106.8, 177.2, and 279.2. So that's what we get for the first part, which is L times Z is equal to C, lower triangular matrix times unknown vector, Z, is equal to the right-hand side here. 

So now you can see that you're going to use the forward substitution.  You're going to use the forward substitution to find out what the values of z1, z2, and z3 are. And the reason why it's called forward is because you're going to start from the first equation, then the second equation, and then the third equation.  So if look at the first equation, that's just nothing but z1 equal to 106.8, because it's 1 times z1 equal to 106.8.  The second equation is 2.56 times z1, plus z2 is equal to 177.2. And you can very well see right here that you got z1 from this part here, so you already . . . you can substitute that value of z1 right here, and you find z2, so every time you are doing forward substitution or back substitution in the next step, it's all about solving one equation, one unknown at a time.  So z2 will be 177.2, minus 2.56 times z1, and this becomes 177.2 minus 2.56, z1 is 106.8, so I get z2 equal to -96.208.  Same thing if I look at the last equation now.  It will be 5.76 z1, plus 3.5 z2, plus z3 is equal to 279.2.  That's the last equation, and again, you have three unknowns in here, but you just found out what z1 is, which is 106.8, you just found out what z2 is, which is -96.208, so there's only one unknown in this particular equation, which is z3. So z3 becomes 279.2, minus 5.76 times z1, minus 3.5 times z2. So that's 279.2, minus 5.76, z1 I just found out to be 106.8, z2 I just found out to be -96.208, and this number here, z3, turns out to be 0.76.  So these steps of forward . . . forward substitution are giving us the values of the intermediate Z vector, z1 being 106.8, z2 being -96.208, and z3 being 0.76, and these are the ones which are going to be now used to be able to find out what x1, x2, and x3 are.

So let's go ahead and do that.  So now what we have is U times X is equal to Z, and x1, x2, x3 is the X vector, which is the one which we are actually trying to find, will be equal to z1, z2 and z3, which we just established as the following numbers, z1 being 106.8, z2 being -69.208, and z3 is 0.76. And what is U?  U we have already seen what the decomposition is, 25, 5, 1, 0, -4.8, -1.56, and 0, 0, 0.7. Now, you can very well see that in this case what I'm going to do is I'm going to start from the last equation, because the last equation will have only one unknown, x3, and then the second-last equation will have only one unknown, which will be x2, and the third-last equation, which in this case is the first equation, we'll have only one unknown, which will be x1.  So let's go ahead and take the steps of back substitution.  Keep in mind that these are the same steps which we had for Naive Gaussian method, so you are following the same steps of back substitution of the Naive Gaussian method to find out what x1, x2, and x3 are.  So I'll take the last equation, which is right here, so I get 0.7 x3 is equal to 0.76. That gives me x3 equal to 1.08571, so I have found out x3.  Now I'm going to go to the second equation, which is this equation right here, and you can see that there are two unknowns, x2 and x3, but the only unknown is x2, because I just found out what x3 is.  So I get -4.8 x2, minus 1.56 x3 is equal to -96.208, and that gives me x2 is equal to -96.208, plus 1.56 x3, divided by -4.8.  I substitute the value of x3 in there, I get -96.208, plus 1.56 times 1.08571, divided by -4.8, and the value here will be . . . turns out to be 19.6905. So that's by simply substituting the value of x3 in there.  Now let's go ahead and look at the first equation, which is 25 x1, plus 5 x2, plus x3 equal to 106.8, and in this case your x2 and x3 are just . . . have just been found out, x2 and x3 have just been found out, so I can find out x1 from there.  So x1 will be 106.8, minus 5 x2, minus x3, divided by 25, and that gives you 106.8, minus 5 times x2, which I found out to be 19.6905, minus x3, which I just found out to be 1.08571, and I'm going to divide it by 25, because that's my 25 in the denominator there, and this number here turns out to be 0.290472. So that's how you are able to find out what the unknowns now are in the set of equations which were given to you by the LU decomposition method.  Your x3 is 1.08571 . . . you had x3 as 1.08571, you had x2 as 19.6905, and your x1 is 0.290472.  And that's the end of this segment.