CHAPTER 04.06: GAUSSIAN ELIMINATION: Naive Gauss Elimination Method: Example: Part 1 of 2 (Forward Elimination)
In this segment, we're going to take an example for Naive Gauss elimination. Naive Gauss elimination is a technique to solve simultaneous linear equations, and we'll look at an example to do so. In this segment, also, we'll only talk about the forward elimination part of it, and in the next segment we'll talk about the second part of Gauss elimination, which is called back substitution.
So we'll look at the following given sets of equations. So let's suppose somebody gives you a set of equations which looks like this, 25, 5, 1, 64, 8, 1, 144, 12, 1, and says that a1, a2, a3 are the three unknowns, and the right-hand side vector of these three equations, three unknowns is given as follows. Now we're going to show the forward elimination steps, which we need to understand that in the forward elimination steps what we are doing is that we are converting the coefficient matrix into an upper triangular matrix, and see what the changes will take place also in the right-hand side vector based on that conversion we are trying to do. So what that means is that we've got to make this element to be 0, this element to be 0, and this element to be 0, so as to be able to make this coefficient matrix to be an upper triangular matrix. So how we're going to go about doing that is by understanding that forward elimination has n-minus-1 steps itself, so forward elimination has n-minus-1 steps, so since we have three equations, we'll have 3 minus 1 equal to two steps. So what's going to happen in the first step, these two numbers are going to be converted to 0, or made to be 0 by doing some matrix operations, and in the second step, we'll be looking now at the . . . what's below the second row, second column and make this to be 0. So in the first step you're making everything below the first row in the first column to be 0, in the second step you're going to make everything below the second row in the second column to be 0, so as to convert it into an upper triangular matrix. So let's go ahead and see what we'll have to do in the first step, so if we have the first step of forward elimination, how we're going to go about doing this. So what that means is that we've got to make this to be 0 and make this to be 0, so the way to do it is to divide this first equation by 25 and multiply it by 64, and then subtract it from there, because that will make it to be 0, same thing here, we'll divide this by 25, multiply by 144 and subtract it here, and that will make it to be 0. So we are looking for multipliers of this equation so as to make this to be 0 and this to be 0, and let's go ahead and see what that means. So since we have . . . we're going to divide . . . so let's suppose we're looking at row number two, we're going to divide 25, multiply by 64, so that gives me a multiplier of 2.56. So what that means is the first row which I have, which is 25, 5, 1, 106.8, that's the first row which I have, I'm going to multiply this by 2.56, and reason why I'm going to multiple by 2.56 is because this is going to become 64 then, so I'll get 64, 12.8, 2.56, and 273.408. So by making this to be 64, now I can subtract this particular multiple of the first equation from the second equation. So the second equation is like this, 64, 8, 1, 177.2, so I'm writing it in an augmented fashion, this particular row, 64, 8, and 1 are the parts of the coefficient matrix, 177.2 is the right-hand side vector, so I'm going to take this particular multiple of the first row and put it there, and I'm going to subtract it. So you do need to follow the algorithm exactly as it's shown in the example, otherwise you're not following the Naive Gauss elimination forward elimination steps, so I get 0, I get -4.8, -1.56, and then I get -96.208, so this becomes your second equation now, 0 times a1, minus 4.8 a2, minus 1.56 a3 is -96.208. So that takes care of the second row, now I've got to take care of the third row. In the third row, what I said was I'll have to divide by 25 and multiply by 144, and that's what's going to make the third row, first column to be 0, so this number here turns out to be 5.76. So I'm going to take the first row which I have, which is 25, 5, 1, 106.8, and I'm going to multiply it by 5.76, and what I'm going to get is 144, 28.8, 5.76, and 615.168. And since this has become 144, now I can subtract this part from equation three, so I'm going to write my equation three here, which is 144 . . . the elements are 144, 12, 1 of the coefficient matrix, and 279.2 is the right-hand side element of the third . . . third equation, and now I'm going to take this and write it down underneath it so that I can subtract it. So I subtract it, and what I get, I get 0, -16.8, -4.76, and I get -335.968, so that's what I get as the third . . . third equation. So if I rewrite my equations now, this is . . . this is considered to be the end of the first step of forward elimination, and as I said that if you have n equations, you have to conduct n-minus-1 steps of forward elimination. So this is the end of the first step of forward elimination, I'm going to get the equations look like this in the matrix form. So the first equation does not change, because that's what we used to make the first column under the first row to be 0, then this became 0, -4.8, -1.56, and -96.208, this number here stays to be 106.8, and this one here is this equation which we just found out, 0, -16.8, -4.76, and -335.968. So that's what you get at the end of the first step of forward elimination.
So let's go ahead and see that what do we get at the end of now . . . now what do we get at the second step of forward elimination? So if we're going to look at the second step of forward elimination, let me go back here to this . . . to this matrix form here. Now what we want to do to this particular set of equations here is that we want to make this to be 0, so we're going to use the second row, second column to make everything below the second column, second row to be 0. So we're going to use the second row, second column to make everything below the second row in the second column to be 0, since there's only one element, that's the only one which we need to make to 0. So what that means is that I have to divide this first . . . second equation by -4.8 and then multiply by -16.8 to get the multiplier so that I can do the subtraction and get this to be 0. So, if I take 0, -4.8, -1.56 . . . no, let me write down the multiplier first, the multiplier will be -16.8 divided by -4.8, because we've got to divide by -4.8 and multiply by -16.8, and that turns out to be 3.5. So I'm going to write down the second equation, which is like this, and this whole thing needs to be multiplied by 3.5, because that's the multiplier which we obtained, and we get 0, -16.8, -5.46, and -336.728. Now this needs to be subtracted from the third equation, which is 0, -16.8, -4.76, and -335.968, and I'm going to take this multiple of the second equation now, which is 0, -16.8, -5.46, -336.728, then I'm going to subtract it, I get this, and I get 0 here, 0 here, 0.7 here, and 0.76 here, so that becomes my now third . . . third equation. So, at the end of the second step of forward elimination, which is also the end of the forward elimination steps, because I have three equations, three unknowns, so I only need to conduct three steps of forward elimination. I get 25 here, 5 here, 1, 106.8, then the second equation stays the same, and this becomes -96.28, and the last equation is 0, 0, 0.7, and 0.76. And that's the end of the forward elimination steps, and in the next segment, I'm going to show you to do back substitution be able to get our solution to the set of equations. And that's the end of this segment. |