CHAPTER 04.06: GAUSSIAN ELIMINATION: Naive Gaussian Elimination: Theory: Part 2 of 2
So once we have that, what we have to do is we have to do the step of back substitution. Again, I'm going to go through an example to illustrate that, which I was just showing it to you, is that now if you have three equations, three unknowns, and you are at the end of the forward elimination steps, you're going to basically get . . . still get three equations, three unknowns, but you can solve one equation at a time.
Here, you are just solving for x3. Now when you look at this particular equation you have two unknowns, x2 and x3, but x3 has just been found out, so there's only one equation, one unknown at this time. Here, in the first equation, you've got three equations, three unknowns, x1, x2, x3, but x2 and x3 were just found out, so I have only one unknown. So that's the beauty of converting the coefficient matrix into an upper triangular matrix, that the back substitution steps basically require you to start from the last equation, but you are only solving one equation, one unknown at a time. So algorithmically, how does it . . . how does it look like? It's that this is the . . . these are the starting equations for the back substitution, as we showed earlier. Now what you're going to do is you're going to solve the last unknown by solving one equation, one unknown, by doing that, and then the other ones which you're going to do is let's suppose you are looking at xi, looking at n-minus-1 let’s suppose, then you have b-sub-n-minus-1, and then corresponding values of x which you have already found out will be involved in the negative elements which you are seeing here, divided by the diagonal element corresponding to that unknown. Now I can compact all these negative elements into this form right here, and you can very well see that only the values of xj, which are showing up in this summation, are the ones which you have already found out, because those are the ones which are before this, so let's suppose you had i equal to, let's suppose 5, this starts from 6 to n, so those are the elements which you have already found out. So it just becomes solving one equation, one unknown at a time. And that's the end of this segment. |