In this segment we'll talk about the Bisection Method; we'll talk about
the algorithm of how to find the root of a nonlinear equation by this particular method.
So, in the previous lesson we talked about that how if there is a real and a continuous function
in the equation f(x) equal to zero, so if we plot this particular function f of x
as a function of x and we are able to find two points so that the function is changing sign,
then we can guarantee that there is at least one root between x_l and x_u.
Of course, the function has to be real, and it has to be continuous between those two points.
So, what we have basically done is that we have bracketed the root between x_l and x_u. So how
does it help us so far as the Bisection Method is concerned is that what we're going to do is we're
going to say, hey, let me choose the midpoint between x_l and x_u, so let's suppose it's right
here. So that is the midpoint so let's suppose I call that to be x_m one, let's suppose, because
it's the first iterative value so I get this as my root. Now what I got to figure out is that, hey,
I can start with two brackets now; I can start with this bracket and this bracket,
and I’ll have to now see that, hey, which bracket does the root fall in? And if I apply the same
principle of that, hey, is the function changing sign, I’ll find out hey, yeah, the function
change sign between the first bracket and not in the second bracket for this particular case.
So, what I basically done is that I have created a new lower limit and a new upper limit for my
interval in which the root is occurring. And I can continue this process again I can say
okay the midpoint is right here, and then I have to decide whether it is in this bracket
or whether it's in this bracket, and you'll find out hey it will be in this bracket right here
that the root will be existing. And you continue this process
of finding the midpoints in these brackets, and that's how you'll be able to find out what the
root of the equation is, and of course what you're going to do is you are going to compare:
so let's suppose you have a new midpoint which you have found out by doing this and you have an old
midpoint, and you're going to compare it with the old the previous one which you have found
out and you multiply by 100 and that gives you the absolute relative approximate error.
So based on this what you can do is you can compare it with the pre-specified tolerance
which might be given in terms of a percentage or in terms of number of significant digits I want
to be correct in my answer. And that's how you will develop this algorithm or
of course you will also have an upper limit on the number of iterations you're going to go through,
because it's quite possible that you might take it might converge slowly. In fact, Bisection Method
does converge generally slowly. But one of the good things about Bisection Method is that that it
converges this convergence is guaranteed. Because you already bracketed the root the only thing
which you have to wait for is that how fast it is going to zero in on the root of the equation.
So, let's go and what we'll do is we'll write the algorithm for the Bisection Method.
Okay so the algorithm for the Bisection Method will be first as follows: what we got to do
is choose two points, x_l and x_u, such that the value of the function at the lower limit
times the value of the function at the upper limit is less than zero. So, we're starting with
trying to find the root of the equation of that equation at f(x) = 0. [JP1] That’s
our goal. We’re trying to find the root of that equation. So, we're going to choose x_l and x_u
such that the function is changing sign, and of course we are given that it is real and
continuous, of course, between those two points. Keep in mind that if somebody gives you these two
limits of the or bracket of the root here keep in mind that you should always check whether it's a
valid bracket or not. Many times, students will not check whether it's a valid bracket or not.
Then what you're going to do is you are going to estimate you're going to estimate the root,
and the estimate of the root would be that hey x_m is equal to x_l plus x_u divided by 2, and then
how you're estimating the root is the midpoint, and that's how you would find the midpoint in the
of those two points. Now what you what you have to do is you in order to figure out
hey if this is x_l and this is x_u and this is my x_m, what I have to decide is this my
is this my new bracket or is this my new bracket? I have to choose between one and two
bracket so I have a bracket which is x_u minus x_l length now, and I’m basically making the
bracket to be half of, so far as the width is concerned, half of what it was before. So how
do I make that determination is by checking I will check if the value of the function x_l
times the x_m is less than zero. If that is so, then then root is between
x_l and x_m . Because the function is changing sign between these two points. So,
what that would mean is that I will make my lower limit to be the same x_l and I’ll change
my upper limit to the midpoint. Now we also will check if the value of the function at x_l
times x_m is greater than zero. Then we know that the root is between
x_m and x_u. Because surely, it's not between x_l and x_m because the function isn't changing sign,
so it has to be between x_m and x_u and if that is the case then my lower limit will become my
midpoint, and my upper limit is going to stay the same. It is also possible by chance that
the value of the function at the lower limit times the value of the function the upper limit will
turn out to be exactly equal to zero. There's a very small chance, then we already know that we
have already got the root, and the root will be equal to x_m. And we will of course in this case
what we'll do is we will stop the process. Or stop the algorithm.
So, let's go and see what we're going to do next.
So, what I’m going to do next is now that since I’ve updated my
lower and upper limit, I will find a new midpoint which will be given by this. And what I have to
do is I have to check whether it is within a pre-specified tolerance. So, I will calculate
the absolute relative approximate error, which is the new midpoint minus the old midpoint divided by
the new midpoint, and I’ll multiply by 100. So, this is from the previous iteration, this is from
the current iteration. So, you can call old to be previous and new to be current. That's the
same thing. And then what you're going to do is you're going to check if epsilon a is less than
epsilon s, where epsilon s is nothing but whatever we have pre-specified as our tolerance.
So, if this is true, then we stop. Else we go back to
step three where we are going to again check hey is the function changing sign between x_l and x_m,
or between x_m and x_u. Or we also going to also stop if maximum iterations have been used.
Because Bisection Method is known to be a slowly converging method, so we got to be careful about
maybe not allowing to have as many iterations as it needs. So, you may have to stop if maximum
iterations has, have been used. In that case of course if the maximum number of iterations have
been used then you have to tell the user that you have used the maximum number of iterations
and not given them false hope that you have achieved the pre-specified tolerance.
And that is the end of this segment here.