Bisection Method: Example


Uploaded by numericalmethodsguy on 18.02.2009

Transcript:
.
.
In this segment, we're going to take an example of the
bisection method.|So we have bisection method, and
we're going to see an example of how we can find the root of an equation.
So, again, bisection method is all about finding the root of an equation which
is of the form function, f of x, equal to 0.
So the example we're going to take is that somebody tells us that, hey, go ahead and find out the root of this
equation, x cubed equal to 20, that's the equation.|They're telling you that
your initial guess can be 1, and your
other initial guess can be 4, and
maybe asking you to conduct three iterations . . . conduct three
iterations.
So the initial guess is given to us as 1 and 4, those are the initial guesses
for doing the bisection method, the equation given to us is x cubed is equal to 20.
Now the first thing which you . . . which I have said is that the bisection
method works for the equation f of x equal to 0, so if your equation is
not in that form, you have to rewrite the equation in that particular form, so what that means is that I've
got to rewrite this equation as this, x cubed minus 20 equal to 0,
and that becomes my function f of x, then.|It's very important
to be sure that you are writing down the equation in the form f of x equal to 0,
so in this case all I have to do is to just take 20 to the left-hand side, and I get my . . . get my
equation in the proper form.|Now the first step which we said, again, is that we have to
check, although somebody's giving us what the lower and upper limits are,
we still have to check whether the function is changing sign, so what I have to do is I have to find out what
the value of the function at 1 is, which is at xl, so function . . . the value of the function at
xl is equal to the function at 1, which is 1 cubed minus 20, which
is -19.|The value of the function at the upper limit is
the value of the function at 4, which is 4 cubed minus 20, which is 44.
So what you are finding out is that the function value
at 1 times the value of the function at 4 is equal to -19
times 44, and it is in fact less than 0.
So what we have claimed . . . what we are claiming here is that since the function is changing
sign between 1 and 4, and we know that the function x cubed minus 20 is continuous
between 1 and 4, then there should be at least one root between 1 and 4.
It does not tell you whether there are more than one root, but at least it's telling you that there is at least one root between
1 and 4.|So we have established the fact that the lower limit and the upper limit
guess which are given to us, or the lower and upper guesses which are given to us for the root
of the equation, that they are valid, that's the first important thing which you have to do whenever you are going to apply
bisection method.|So let's go ahead and do iteration one, so iteration one
basically tells me that, hey, what I have to do is I have to find the lower and the upper
limit, so lower and upper limit is given to me, so I'll find the midpoint between the
lower and upper guesses which are given to me, which is 1 plus 4,
divided by 2, which is 2.5.
And now, based on the algorithm which we discussed, I've got to find out what the . . .
what the value of the function at the lower limit is.|The function at the lower limit
is the value of the function at 1, which is 1 cubed minus
20, which is -19, and the value of the function at the midpoint
is the value of the function at 2.5, which turns out to be
equal to minus, sorry, 2.5 cubed minus 20,
which is -4.375.|So that's what
I get as the value of the function at 2.5, so you can very well see now, the value of the function
at the lower . . . lower value, the value of the function at the midpoint
is -19, star,
-4.375, which is greater than 0.|The function is not changing sign
between xl, which is 1, and between xm, which is 2.5.
So the root cannot be between 1 and 2.5.
The root cannot be between 1 and 2.5, so it has to be between 2.5 and 4, because
that's the upper limit, the upper limit is 4, the lower limit is 1, and your 2.5
is the midpoint between those two guesses, so since it is not between 1 and 2.5,
the new . . . the new bracket
is 2.5, comma, 4.
So you can already see that the initial bracket, which was between 1 and 4, which
was 3 . . . which was 3 units in length, now
has been reduced to a length from 2.5 to 4, which is only now 1.5 in length, and that's
the reduction of the interval of the bracket, length of the interval of the bracket
which is . . . which is happening in the bisection method.|So that's the end of the first iteration, we cannot
calculate any kind of relative approximate errors or anything like that, because we don't have a
previous . . . previous estimate.|So let's go for iteration two now.
.
The iteration two is that the midpoint will be now, so we have the . . .
the new bracket is 2.5, comma, 4, that's the new bracket, 2.5, comma, 4,
so that means that the midpoint will be 2.5 plus 4, divided by 2,
which turns out to be 3.25, so that's
our new estimate of the root, 3.25.
So, again, I'm going to calculate my value of the function at xl, which is the value of the function at 2.5,
which I already calculated, but I'm going to write it down here, which is
-4.375.|I'm going to calculate the value of the function at the new midpoint
which I just obtained, which is the value I have to calculate at 3.25,
and that number here turns out to be equal to
14.328.|Now, keep in mind that these function values are basically
being calculated from x cubed minus 20, so you put 2.5 in x
cubed minus 20, you put the value of x to be 3.25 in x cubed minus 20, and that's
the values which you are getting.|Now, what you are finding out here is that the values of the function
between the lower limit and the midpoint, which is the value of the function at 2.5,
the value of the function at 3.25.|The value
of the function at 2.5, we just calculated -4.375,
the value of the function at 3.25, we just calculated 14.328, and in fact it is
less than 0.|So what you have established by this is that since the root is
between 2.5 and 3.25, that's why it is
changing sign between the values of x equal to 2.5 and x equal to 3.25,
and the function values are changing sign, so the root has to be between 2.5 and
3.25.|So, that is the new bracket, so the new bracket now,
the new bracket of the root is now 2.5 and
3.25, and you can very well see that the width of this
bracket here is 0.75, the width of the bracket we started with is 1.5,
so it has already become half of what it was before.|Now, also here,
we can calculate the absolute relative approximate error,
because we have a previous approximation and a current approximation, the present approximation is
3.25, the previous approximation was 2.5,
divided by 3.25, times 100,
and that turns out to be about 23 percent.
So we're getting a large relative approximate error between the old value . . .
new value, old value, and the new value here, which is about 23 percent.
So, I'm going to ask you to do the other iterations yourself.
I'm going to write down the values which I get for various iterations,
so iteration number three, I get the value to be
2.875.
For iteration four,
I get 2.6875.
For iteration five, which is conducting one more iteration,
I get
2.78125.
So those are the iterations which you can do as your homework,
and convince yourself that how you can find out the new bracket of the root
as you go along from one iteration to another.|And that's the end of
this segment.
.
.