.
In this segment, we're going to talk about the bisection
method,
and we're going to talk about the algorithm
of the bisection method.|So let's go ahead and see that
how we have to run the bisection method, how . . . what are the steps in the bisection method.
Again, what we are doing is that we are trying to find the root of the equation f of x
equal to 0, or in other words you might say that you're trying to find the zero of the function f of x,
either way is a correct way of saying it.|And what we already
said that, hey, it is based on the theorem that if I have the point xl
here, and point xu, that if the function f of x
is a continuous function between xl and xu, and the function is
changing sign, like here it is negative, here it is positive, then there is at least one root between
xl and xu.|So the first step which you will have in the bisection method
algorithm will be that to choose xl
and xu as the initial guesses.
But you've got to understand that
you cannot choose any two points as the initial guesses, this has to be true,
such that the value of the function at
xl and the value of the function at xu is opposite of each other,
which means that it's changing sign, is less than 0.|You
have to bracket the root, so this is what's called bracketing the root, you have to bracket
the root, because if you don't bracket the root, then you are not following the
bisection method.|So it's very important to understand that the first step, even if somebody tells you,
hey, go ahead and choose these as the initial guesses, you've got to check whether the
function is changing sign between those two initial guesses, because if it is not, then it is not following
the path which the bisection method requires you to do.|Now, what you're going to do is, what
bisection method is based on is that once you have these two points,
you're going to choose the midpoint between the two.|You're going to choose the midpoint between
the two, which I may call xm here, and that can be simply calculated
by taking the average of the lower value and the upper value of the guess.
So, what you're going to do is you're going to take the
average of the two, so it will be xl plus xu, divided by 2,
and what you are doing now by doing this is that you are trying to reduce the
interval in which your guesses are existing.|See, before here, when you look
back at this figure here, you had your guess going from xl to xu, so this
was the width of the interval.|Now the width of the interval is going to be only half of this, because what you're going to
do is, you're going to again check whether the value of the function at xm,
is it negative or positive?|Or, and later on we see that,
between what interval is it changing sign?|Is it changing sign right here?
No.|Is it changing sign right here?|It is, so what's going to happen is that
your interval is now going to become this, because it is that interval
where the function is changing sign, so the other half which is, you can forget about that.
So what you are seeing here is that you can see clearly how bisection method is going to work, you start with an interval
which is this long, going from here to here, your start interval which is
going from here to here, and then you are halving that interval by,
again, applying the same principle, that, hey, is it changing the function between the lower limit and the
midpoint, or between the midpoint and the upper limit, and depending on in which
interval it is changing sign, you're going to choose the new interval.|So
you're going to find the midpoint here, and then what that means is that you're going to find . . . you're going to
find f of xl times f of xm.
So that's the lower limit, the value of the function, the value of
the function at the midpoint, and you're going to see whether it is less than 0,
greater than 0, or equal to 0, because those are the three possibilities which you're going to
have, because when you're going to calculate the value of the function at the lower limit and the midpoint
now, there are three possibilities which you're going to have.|Either the function is changing sign between
these two points, then you're going to get less than 0, or if the function is not changing
sign between these two points, then you're going to get greater than 0, or you're going to get that the function
is . . . that the multiplication of the two function values is 0, in that case then this is the root itself.
So those are three possibilities which you're going to get.|So let's go ahead and write those down again, that
what does that mean?|So, you have your xl here, so I'm going to just show you the x-axis,
you have your xu here, and you have your xm here, and what you are
trying to decide now, should this become the lower limit or should this become the upper limit?
Because if this becomes the lower limit, then your interval . . . new interval
is this, if this becomes the upper limit, then your new interval is this, so it is
a question of choosing the right interval, so this is what I'm going to do, I'm going to say if,
let me not put 1 there, let me just put a,
if the value of the function at xl times the value of the function
at xu . . . xm is less than 0,
if the value of the function at xl times the value of the function at xm is less than 0,
then the lower limit stays as the lower limit
and the upper limit becomes the midpoint,
because if we're changing sign between these two points, then this should become the upper limit.
Now, the other possibility is that the value of the function at the lower limit and
the function at the midpoint will be greater than 0, then you know that
it's not changing sign between this point and this point, because it is greater than 0,
so both the function values are negative or positive, so it's not changing sign, so it
has to change the sign between these two, so then your lower limit will become your midpoint,
and your upper limit will stay as the upper limit.
Now the third possibility, which is going to be purely a coincidence, it may happen in
some cases, but very rarely, that you're going to get the value of the function at xl
times the value of the function at the midpoint to be exactly equal to 0.
So in that case then we know that the root which you have found is an
exact root, and the root will be xm.|And you will basically then
stop the whole process, because you don't have to go any further, because you have already
calculated what the . . . what the root is.|Now, once you have done that,
you again go through the same process, because you have now found out the new upper limit
or lower limit, you are going to go through the same process, you're going to find
your midpoint, which will be xl plus xu,
divided by 2.|The only difference, so rather than saying go back
to step two, I'm going to say that, hey, go ahead and find out the midpoint again, and the reason why I'm saying that
is because you have to now find also the relative
approximate error, because now you have an initial guess . . . you have an initial value
and a previous value, so the previous . . . so whatever you have to do is xm-new,
whatever the new value of the midpoint is, minus the old
value of the midpoint is, or the estimate of the root is, divided by xm-new,
and what you're going to do is you're going to multiply this by 100 to get a percentage, and
this is the value which you're going to check, check
if this absolute relative approximate which you just got is less than your pre-specified
tolerance, because when you're going to do any kind of iterative procedure, where you are trying
to find a better and better estimate of something, you've got to have some
pre-specified . . . pre-specified tolerance
so as to be able to figure out when the whole algorithm should stop.|So once you have done that,
you're going to go back to . . . go back to step three.
And step three is basically, again,
finding out the values of the function at the lower limit and midpoint, and trying to see that whether
in which interval is it changing . . . changing the function.|Now, if you go back to step three,
you might think that, hey, it's going into an infinite loop.|No, it's not going to go in infinite loop, because you're always going to
check whether your absolute relative approximate error is less than the prespecified . . . less than or equal to the
prespecified tolerance, that's how you're going to stop the program, but if it never meets that prespecified tolerance,
because either it is too small or it's taking a long time, you might be able to restrict
the number of iterations you're going to conduct to be able to keep track of that.
And that's the algorithm of the bisection method, and we'll take an example of . . .
we'll take an example to show you how this algorithm works.
.