CHAPTER 03.03: BISECTION METHOD: Background of Bisection Method

In this segment, we're going to talk about the bisection method. I'm going to give you some background on the bisection method in this segment. Now, bisection method is basically based on trying to find out the root of the equation which is of this form.  So you've got, from a graphical point of view, you've got a function which is given to you, f of x as a function of x, and what you want to do is you want to find out where does it cross the x-axis, and that's what sets up this equation.  So you are trying to find out the root of the equation, the function f of x equal to 0, or in other words, you might say, hey, let me try to find the zero of this function, which is the same thing.  So what bisection method is based on is that if you look at this particular example here, that what I'm going to do is I'm going to choose one point here and another point here, and I'm going to look at the value of the function here, and I'm going to look at the value of the function there.  And what you are seeing here is that the value of the function here is negative, and the value of the function here is positive.  So since the value of the function here is positive and the value of the function is negative, this function, if it is continuous, it has to cross the x-axis, because you cannot have a function which is continuous and turn from negative to positive from one point to another without crossing the x-axis, so if it is crossing the x-axis, that means that it's crossing the root, which in this case is this one.  So the whole point about the bisection method, or the whole basis of bisection method, which is also sometimes, bisection method is also, let me write this down, bisection method is also, in many books, called the binary search method. So they're both the same thing. 

So let's go ahead and see . . . let's go ahead and write down what the theorem tells us, that when a function is continuous, and you are able to find out two points, so let me call this point to be xl, and this to be xu, when you're able to find two points where . . . between which the function is changing sign, then what can we say about the roots which lie between xl and xu? So if you are choosing two points, xl and xu, where the function is changing sign, what can you say about the roots of that particular equation, f of x equal to 0? So here is the theorem, the theorem says if f of x is real and continuous then if the value of the function at some point xl and some point xu, the multiplication of that is less than 0, which basically means the same thing as the function changing sign, because if the function changes sign, one of them has to be positive, one of them has to be negative, so the multiplication of the two function values is going to be less than 0, then if . . . then what can you say? Then you can say that there is at least . . . there is at least one root between xl and xu. So it's very important to understand that in order to be able to use this particular theorem as the basis of the bisection method, that the function has to be continuous, the function has to be real, the function has to change sign, or the multiplication of the two function values has to be less than 0, or negative, and that there is at least one root between xl and xu. 

So, let's look at some more examples to see that, hey, what does this mean when we are applying this theorem?  So let's suppose somebody says . . . gives me, again, and equation, and he tells me, go ahead and plot the left-hand side of that equation. You have f of x equal to 0, go ahead and plot out the left-hand side of the equation, and gives me something like this, and says, okay, hey, there is xl, and there's your xu, and says, okay, you have two points now, xl and xu right here, and what is happening is that the function is not changing sign, because here the value of the function is positive, and the value of the function here is positive, but you're getting two roots . . . you're getting two roots between xl and xu in spite of the function not changing sign.  That is not a violation of the theorem which we just discussed.  The reason why this is not a violation of the theorem which we just discussed is because the theorem only tells you if the function is changing sign. It's not . . . it does not tell you anything about if the function is not changing sign, whether there are going to be any roots between the two limits or not.  So that's one thing which you've got to understand is that the theorem's only telling you if the function is changing sign, that you are going to get at least one root. 

If the function is not changing sign, as is the case here, then there may or may not be roots between those two points.

Let's look at another case here. You may have something like this, you may have a function going like this, and you may have xl right here, so, again, this is the function, f of x, which I am plotting, which is the left-hand side of the equation, f of x equal to 0, and I can have this as my xu.  So here, now, I have two points, xl and xu, and I'm finding out that the value here is positive, the value here is negative. So the function is changing sign between the two points, however there are one, two, and three roots between xl and between xu.  Is this a violation of the theorem? No, again, it's not a violation of the theorem, because the only thing which the theorem's telling you is that if the function is changing sign between xl and xu that there is at least one root. It does not tell you how many roots there are.  It does not tell you if there's one, two, three, or four roots of that equation between those two points.  It only tells you there's at least one root, and in this case, that is correct, because you have one, two, and three, so when it says at least one root, that seems to be a correct theorem there, or what you are stipulating in the theorem.

Let's look at another example here, that you may . . . you may have a function f of x equal to 0, you may have the equation, sorry, equation f of x equal to 0, and you are plotting f of x as a function of x. And what you can have is you can have a function which looks like this. And now you may choose your xl to be that number, and you may choose xu to be that number. So what you have is two points which you are choosing on the x domain.  You have xl, where the value of the function is positive, you have xu, where the value of the function is negative, and since you have positive and negative there, what is happening is the function is changing sign, but there's no root between xl and xu, because it's never crossing the x-axis, and the reason why that is so is because your function f of x is not continuous from xl to xu. And if you go back to the theorem, the theorem tells you that the function f of x, this function f of x, if it's going to have a root between xl and xu, it has to be a continuous function between those two points, only then can I say that, hey, there's at least one root.  So these are some of the common things which you've got to understand when we are talking about the background theorem for the bisection method so that you apply it correctly when you are going to do the algorithm of the bisection method. And that's the end of this segment.