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.

.

.

.

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.

.

.