CHAPTER 03.03: BISECTION METHOD: Algorithm  of Bisection Method 

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.