.
I'm going to show you how to do Gauss elimination with partial pivoting, we're going to talk about the theory
behind Gauss elimination with partial pivoting, and one of the which I would suggest to you
strongly is that if you have not looked at the Naive Gaussian method theory and
example, that you do that before you start understanding what Gauss elimination with
partial pivoting is.|The reason why that is so is because there's a small difference between
Gauss elimination with partial pivoting and Naive Gaussian method, and in order to be able to understand what
that difference is, and also because we'll be skipping steps in the Gauss elimination with partial pivoting, because
it's very similar to Naive Gaussian method except for one step, you do need to
understand that first.|Now, the reason why
we talk Gauss elimination with partial pivoting is because there are certain pitfalls of the Gauss elimination.
One is that there's a possibility of division by 0, and the other one is that you
get large round off errors.|So that's the . . . those are the two pitfalls of the Naive Gaussian
method when . . . when we start using that to solve
simultaneous linear equations.|Now, in order to avoid the pitfalls, what
we can do is we can increase the number of significant digits, and what that will do is it
will . . . we can go from single precision to double precision, or to quad precision,
or extended double precision as some people might call it, or extended precision some people may call it, and what
that will do is that will surely decrease the round off error, but it is not going to avoid division
by 0, because no matter how many significant digits you're going to choose, if there is going to be division by 0,
that is going to occur anyway.|So the way to do it
this way, what we do is we avoid these pitfalls by using Gauss elimination with
partial pivoting, where we avoid the division by 0, and
also reduce the round off error.|So the Gauss elimination with partial pivoting helps us in both instances
of avoiding the pitfalls of the Naive Gaussian method, because it avoids division
by 0.|Now somebody might say, hey, is this possible that we'll get division
by 0 even in Gauss elimination with partial pivoting?|Yes, it is possible that you will get
division by 0 in Gauss elimination with partial pivoting, but that will imply that
the coefficient matrix which you have is not invertible, that it is . . .
that you don't have a unique solution to the set of equations, that's what's going to happen if you are not able to
avoid division by 0 with Gauss elimination with partial pivoting.|So I'm going to
assign that as homework to see that whether you can come up with a . . . with a set of equations where
you are not able to avoid division by 0 whether you are doing Gauss elimination with
partial pivoting or Naive Gaussian method.
So what is different about partial pivoting?|This is the only thing which is different between
Gauss elimination with partial pivoting and Naive Gaussian method, this is very important for you to
realize what the difference between the two is.|So since . . .
at the kth step of forward elimination, what you do is you find the maximum of
these values.|Now, before I talk about what do we mean by find the maximum of these values,
you've got to understand there are n-minus-1 steps in forward elimination,
because there are a hundred equations, let's suppose, you'll have ninety-nine steps
of forward elimination, and you'll have to go through this whole process before
each step of forward elimination, not at just the first step or the second step or the third step, but at . . .
before the beginning of each step of forward elimination you have to do that.|So let's suppose we are at
the kth step of forward elimination.|So what we do is we look at the kth row, kth column, which is the diagonal element
in the kth row, and then we look at the element which is right below
the diagonal element in the same column, and all the way to last element in the nth row.
We take the absolute value of those, so that's why you find out you have these
marks there, so you're finding the absolute value of all those elements, and once you find the absolute value of those
elements, you figure out, hey, in which row do you have this maximum element.|So,
let's suppose the maximum of all these elements which you are finding out here, the absolute value of,
let's suppose the maximum element is in the pth row.|So if the maximum element is in the pth
row, what you're going to do is you're going to switch rows p and k.
Keep in mind that you're only switching rows p and k, you're going to make row p
to be the row k, and row k to be the row p.|You're not moving
other rows at all, the only thing which you are doing, you're just doing a switch, a clean switch between rows
p and k.|And this you do at the beginning of each step of forward elimination,
and then you follow the same steps, exactly the same steps of forward elimination of the
Naive Gaussian method.|So as an
example with symbols here, let's suppose we are at the beginning of the second step
of forward elimination.|So if you're at the beginning step of the forward elimination, that means that you're going to take second row,
second column as your pivot element, you're going to take the absolute value of this, you're going to take the absolute value of this,
you may . . . you will again have another element, let's suppose a42, and so on and so forth,
all the way up to an2.|You're going to take the absolute value of all of these elements
which are in the second row and below in the second
column, and then you're going to find the maximum of these . . . you're going to find the
maximum of these, and let's suppose the maximum turns out to be in fourth row,
this element turns out to be the maximum of all the absolute elements which we are trying to find.
If that is the case, we're going to switch row four with row two, that's all we're going to do,
every other row will stay in place.|So what that means is this whole row which you have right here
will be switched with this second row right here, and then you
will conduct the steps of forward elimination like we have done before, nothing changes about that.
So let's look at an example here.|So here we are
at the beginning of the second step of forward elimination.|That means that I'm going to take the
second row, second column here, take the absolute value of that, absolute value of this, absolute value of this,
so basically what I'm doing is I'm taking the absolute value of all the second column elements
below . . . in the second row and below.|So the absolute value of
this is 7, the absolute value of this is 4, the absolute value of this is 9, the absolute value of this is
17.|So which one is the maximum?|I know that, hey, this one is the maximum, 17 is the
maximum.|So if 17 is the maximum, that means that I'll have to take this row
four, so this is row five . . . row five, and this is
row two, so I'm going to do a switch.|So I'll have to switch
row five with row two, and take this down to
fifth row.|So that's what I have to do at the beginning of the step of forward elimination
in this example right here.|Now keep in mind that when you are switching the rows
that you need to switch not only the coefficient matrix part of the row, but also
the right-hand side.|Same thing right here, you will have to switch this one as well as this one
right here, and because the equations should not change when you go from . . . when you switch
the rows.|So this shows
you how the rows have been switched, so you see that row five which I had previously
has become row two, and row two has become row five, and once
that switch has taken place, now you conduct the same steps of Naive Gaussian method
of forward elimination as before, so that has not changed at all.|So that's why I'm
emphasizing that before you go through this presentation that you
do have looked at Naive Gaussian method to be able to figure out what we are
trying to do here.|So the Gauss elimination with partial
pivoting is, again, a method to solve simultaneous linear equations, n equations, n
unknowns, and it has two steps, just like Naive Gaussian method, of forward elimination and back substitution.
The forward elimination . . . the forward elimination
part is same as the Naive Gaussian method, except for the fact that we switch rows before each
of the . . . at the beginning of each of the n-minus-1 steps of forward elimination,
and I told you that before.|And
as an example, this is the matrix at the beginning of the second step of forward elimination,
and we're going to, again, look at the maximum element
of the second column and below,
and then, depending on where the maximum is, we'll switch that row with row number two.
And this is what we get at the end of the
forward elimination steps following doing that for each one of them.
So what we are doing is we are making the second row, second column . . .
second column to be 0 below the second row, same thing we are making
fourth row . . . fourth row below the third column to be 0,
and eventually what we are doing is we are ending up with all 0s below the diagonal, which
basically makes this particular coefficient matrix into an upper triangular matrix which we can solve by using
back substitution just like in the Naive Gaussian method.|So the
back substitution steps are exactly the same as Naive Gaussian method.|The only
difference between Gauss elimination with partial pivoting and Naive Gaussian method is in the forward elimination steps,
and that, too, is in the beginning of each step of forward elimination, but the back substitution steps in
Gauss elimination with partial pivoting and Naive Gaussian method, they're exactly
the same, so there's no need to talk too much about it, but that's what we get, we
solve the last . . . last equation for the unknown, and then we are going backwards, we are going
to the second . . . last but one equation, and
keep on going backwards to find out what our unknowns are.|And the reason why we see that
the coefficient matrix being an upper triangular matrix translates the back substitution steps into solving only
one equation, one unknown at a time.|And that's the end of this
segment.
.