CHAPTER 04.07: LU DECOMPOSITION: Decomposing a Square Matrix: Part 1 of 2
In this segment, we're going to take an example of how you do LU decomposition of a square matrix. So this is not an . . . this is not an example of the LU decomposition method itself, but how do you decompose A is equal to L times U, because that's what you need in order to be able to do the LU decomposition method, you first need to decompose your A into L times U. I mentioned in a separate segment, the way . . . one of the ways to find out A is equal to L times U is by following the same steps of forward elimination as given in the Naive Gaussian method. So if you follow the steps of the Naive Gaussian method, the forward elimination steps, you'll be able to determine what L and U should be. So let's go ahead and see that how do we go about doing that through an example. So let's suppose somebody says that, hey, I'm going to give you this 3-by-3, three equations, three unknowns, 25, 5, 1, 64, 8, and 1, and 144, 12, and 1. Now, what I want you to do is, I want you to write it as a lower triangular matrix multiplied by an upper triangular matrix. So what we're going to do is, on this we're going to do the forward elimination steps of Naive Gaussian method, that's what we're going to do. So we're going to follow the Naive Gaussian method forward elimination steps to be able to find out what the L times U of this quantity here is.
So if you recall how forward elimination is done in Naive Gaussian method is that you want to, in the first step . . . so in the first step, what you want to do is you want to take this particular row, and make this particular column here to be 0 below the first row. So you're taking the first row, and you want to make this to be 0 and you want to make this to be 0, and in the second step you will try to make this to be 0, so as to convert this into an upper triangular matrix, so that's what we're going to do. So if you look at the first step, the first step . . . so what you have to keep track of is that what the multipliers are which are going to make this to be 0, this to be 0, and this to be 0, and that's how we'll be able to figure out what the L times U is. So what I'm going to do is, in order to be able to make this to be 0, I'll have to multiply this row by 64 and divide it by 25. So first I will divide it by 25, multiply by 64, and subtract it from there. So if I have the first row, which is 25, 5, and 1, I need to multiply it by 64 and divided it by 25, which is same as 2.56. So remember this, that what I'm doing is in order to be able to make this to be 0, I'll have to take the first row and multiply it by 2.56. The reason why I'm asking you to remember this is because this is going to show up in your lower triangular matrix at the place which is trying to make this to be 0, because what's going to happen is that 64, this is what we are trying to make 0 by using this multiplier, so this multiplier is going to show up at second row, first column in the lower triangular matrix, exactly at the same place where you are trying to make this to be 0. So because you are using this first step to make this to be 0, that's where the multiplier's going to show up in your lower triangular matrix. So once I multiply this, I get 64, 12.8, and 2.56. I subtract it from the . . . subtract this from the second row, which is 64, 8, and 1, and I subtract 64, 12.8, and 2.56. And if I subtract that, I'll get 0, -4.8, and -1.56, that's what I will get if I subtract this . . . this row from that row. So this becomes my second row of the . . . of the coefficient matrix now, with this being . . . being a 0. So same thing I'm going to do here, in order to make this to be 0, I'll have to . . . in order to make this to be 0, I'll have to divide this first row by 25 and multiply by 144, and, again, remember the multiplier which I'm going to get in order to make this to be 0. So I have the first row, which is 25, 5, 1, and I'm going to multiply it by 144 divided by 25, which is 5.76. So when I multiply by 5.76, this number turns out to be 144, because it should, because I want to make that to be 0, and this is what I will get for the . . . after I multiply the first row by 5.76. Now I've got to take my third row, which is 144, 12, and 1, that's my third row, and I'm going to subtract 144, 28.8, and 5.76, and what am I going to get from there? It will be 0, because this will cancel with this, -16.8, and -4.76, that's what I'm going to get by doing the . . . by doing the subtraction. Now, remember this, this 5.76, the multiplier was used to make this to be 0, which is the third row, first column become 0, so this will correspond to third row, first column in the lower triangular matrix, the value of 5.76. So if you look at the end of first step . . . at the end of first step of forward elimination, what I have is that I'll have a matrix which looks like this, I will have 25, 5, 1, then I'll have a 0 here, -4.8 here, and -1.56 here, and then I'll have a 0 here, -16.8 here, and -4.76 here. So this has become 0, this has become 0 by doing the proper multiplication and subtractions based on what we have in the first row. And also what I've established is that the second row, first column of the lower triangular matrix is 2.56, and the third row, first column is 5.76. So those are the things which I have obtained by doing this LU decomposition method here, or to find the LU decomposition. But I'm not done here, because I need to reduce this to the . . . to an upper triangular matrix, do all the steps of forward elimination. |