.
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.
.