Bisection method-numerical analysis

[evinda]

Hi!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
$$\left |x_{k}-x_{k-1} \right |$$ < ε , $$\left | f(x_{k})\right |$$ <ε

termination criteria of this method??

 

[I like Serena]

Hi!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
$$\left |x_{k}-x_{k-1} \right |$$ < ε , $$\left | f(x_{k})\right |$$ <ε

termination criteria of this method??

Hi evinda! :)

The first condition makes sure that the difference of $x_k$ with the real root is less than ε.
If it's not, more bisections will bring us further.
The second conditions makes sure that the difference of $f(x_{k})$ with zero is less than ε, to verify we really have a root and not a singularity.

 

[evinda]

Do you mean that $$x_{k-1}$$ is the real root?? If yes,why?
And..could you explain me both of the conditions further??I haven't understood them yet

 

[Ackbach]

Do you mean that $$x_{k-1}$$ is the real root??

The Bisection Method is an approximation method. So $x_{k}$ is not, in general, the real root. However, you always want to know how good your approximation is. So, one criteria for knowing that is how close one approximation is to the next one.

And..could you explain me both of the conditions further??I haven't understood them yet

The first condition is sort of your tolerance. How exact an approximation do you need for your application? The second condition assures you that you really have found something vaguely looking like a root. The function should be zero, or very close to it, at your approximation!

 

[I like Serena]

Do you mean that $$x_{k-1}$$ is the real root?? If yes,why?

No, the real root is between $x_{k-1}$ and $x_{k}$.
That is what the bisection method guarantees.
So if their difference is less than ε, the difference of $x_{k}$ with the real root must also be less than ε.

 

[evinda]

I think that I got it..!
For the first criteria, using the following loop :

if fa*fmid <=0
           b = (a+b)/2;
 else
           a = (a+b)/2;

(where fmid=(a+b)/2)

the $$x_{k}$$ and $$x_{k-1}$$ are $$a$$ and $$b$$ respectively? Or am I wrong??

 

[I like Serena]

I think that I got it..!
For the first criteria, using the following loop :

if fa*fmid <=0
           b = (a+b)/2;
 else
           a = (a+b)/2;

(where fmid=(a+b)/2)

the $$x_{k}$$ and $$x_{k-1}$$ are $$a$$ and $$b$$ respectively? Or am I wrong??

Yes. That is correct.

 

[evinda]

Nice..Thank you both very much..! :p

 

[evinda]

I looked the exercise again...Is there an other way to express |$$x_{k}-x_{k-1}$$|<ε ,except from |b-a|<ε??

Because,for example if we have the interval [a,b] and f(a)*f((a+b)/2)>0 then our new interval is [(a+b)/2,b].If now f(a)*f((a+3b)/4)>0,then our new interval is [(a+3b)/4,b].

In this case is what is equal to |$$x_{k}-x_{k-1}$$| ?

 

[I like Serena]

I looked the exercise again...Is there an other way to express |$$x_{k}-x_{k-1}$$|<ε ,except from |b-a|<ε??

Because,for example if we have the interval [a,b] and f(a)*f((a+b)/2)>0 then our new interval is [(a+b)/2,b].If now f(a)*f((a+3b)/4)>0,then our new interval is [(a+3b)/4,b].

In this case is what is equal to |$$x_{k}-x_{k-1}$$| ?

The difference between (a+b)/2 and (a+3b)/4 is the same as the difference between (a+3b)/4 and b.
In other words, it does not matter.

Actually, it is somewhat arbitrary if you consider $x_{k-1}$ to be $(a+b)/2$ or $b$.
If you consider $x_{k}$ and $x_{k-1}$ to be the last 2, most accurate, approximations, then they are (a+3b)/4 respectively b.
If you consider $x_{k}$ and $x_{k-1}$ the be the last 2 values you calculated, then they are (a+3b)/4 respectively (a+b)/2.
Either way, their absolute difference is the same and $x_{k}$ is guaranteed to be within ε of the real root.

 

[evinda]

I understand :) And...for this: $$\left | f(x_{k})\right |$$ <ε ,which
$$x_{k}$$ do I have to use?

 

[I like Serena]

I understand :) And...for this: $$\left | f(x_{k})\right |$$ <ε ,which
$$x_{k}$$ do I have to use?

The last calculated value seems nice. :)

Note that it is only meant to verify we actually have a root.

 

[evinda]

So,do I have to use fmid ??

 

[I like Serena]

So,do I have to use fmid ??

Yes.

 

[evinda]

Nice.. And..something else..I found implementations of the bisection method and there the termination criteria is

 while(fabs((b-a)/2)>TOL)

.

Why is it like that??

 

[I like Serena]

Nice.. And..something else..I found implementations of the bisection method and there the termination criteria is

 while(fabs((b-a)/2)>TOL)

.

Why is it like that??

It's an optimization.
I take it the final value that is returned is (a+b)/2?

The algorithm terminates when $|(b-a)/2| \le TOL$ or $|(b-a)| \le 2 \cdot TOL$.
That means that the difference of (a+b)/2 with the real root is $\le TOL$ without doing a last function evaluation at this point.

 

[evinda]

Now,I have written the code and want to check my output.

Consider,for example, f(x) = x^3 + 3x – 5, where [a = 1, b = 2] and ε= 0.001
At the iteration 9, where a becomes 1.15234375, x 1.154296875 and b=1.15625, f(x) equals to 0.000877253711223602 that is smaller than 0.001 so the program stops at this point. My question is, do I have to print this last x or not?

Do $$x_{k}$$ must be printed if $$\left | x_{k}-x_{k-1} \right | < ε$$ and $$\left | f(x_{k}) \right | < ε$$ ??

 

[I like Serena]

Now,I have written the code and want to check my output.

Consider,for example, f(x) = x^3 + 3x – 5, where [a = 1, b = 2] and ε= 0.001
At the iteration 9, where a becomes 1.15234375, x 1.154296875 and b=1.15625, f(x) equals to 0.000877253711223602 that is smaller than 0.001 so the program stops at this point. My question is, do I have to print this last x or not?

Do $$x_{k}$$ must be printed if $$\left | x_{k}-x_{k-1} \right | < TOL$$ and $$\left | f(x_{k}) \right | < TOL$$ ??

I can not really tell you what you have to print. That depends on the question asked.
Presumably you're supposed to given an answer that is within ε of the root.

Since your algorithm has apparently terminated when $|a-x| \le 2\cdot ε$, the result x is not necessarily within ε of the root yet.
However, you can already see that the true root must be smaller than x (do you see why?).
So you might print the average of $a$ and $x$, which would be within ε of the root.

 

[evinda]

At each step of the bisection method my code should print the current approximation $$x_{k}$$ and f($$x_{k}$$)...The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
$$\left | x_{k}-x_{k-1} \right |$$ < ε and $$\left | f(x_{k}) \right |$$ < ε
are valid.

So,what do you think now?

 

[evinda]

Could you give me an example of the results of the bisection method,so that I can check my output??
For example if we have the function exp(x)+x+1 what should be the output?

 

[I like Serena]

At each step of the bisection method my code should print the current approximation $$x_{k}$$ and f($$x_{k}$$)...The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
$$\left | x_{k}-x_{k-1} \right |$$ < ε and $$\left | f(x_{k}) \right |$$ < ε
are valid.

So,what do you think now?

I see that your version of the algorithm is slightly different than I thought.
It stops if one of the conditions is satisfied and not necessarily both.
So my earlier comments on that topic are not applicable.

Could you give me an example of the results of the bisection method,so that I can check my output??
For example if we have the function exp(x)+x+1 what should be the output?

With a = -2, b = -1, and TOL = 0.001, I get:

x[10] = -1.278320313 and f(x[10]) = 0.000184396.

 

[zzephod]

Hi!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
$$\left |x_{k}-x_{k-1} \right |$$ < ε , $$\left | f(x_{k})\right |$$ <ε

termination criteria of this method??

The bisection method does not find roots, but points at which the function changes sign.

The first condition is a condition on the localisation of a point where the function changes sign.

The second condition is a test that the method has found an approximate root

.

 

[evinda]

With a = -2, b = -1, and TOL = 0.001, I get:

x[10] = -1.278320313 and f(x[10]) = 0.000184396.

Great!I get the same output ;)

 

[evinda]

I am facing also difficulties at an other subquestion.
I have to find the error $$\left | x_{k}-B \right |$$ (where B is the real solution of the function) of the last iteration of the method.Could you give me a hint what I have to do?? And..do I have to find firstly the solution B?If yes,how can I do this?

 

[I like Serena]

I am facing also difficulties at an other subquestion.
I have to find the error $$\left | x_{k}-B \right |$$ (where B is the real solution of the function) of the last iteration of the method.Could you give me a hint what I have to do?? And..do I have to find firstly the solution B?If yes,how can I do this?

You will not be able to find the solution B for $e^x+x+1=0$ without the use of numerical methods (it is not solvable with a finite number of standard functions).

However, you already have your error: it is $(b_k-a_k)/2$.
That is the case since the root is guaranteed to be either between $a_k$ and $x_k$, or between $x_k$ and $b_k$.
The bisection method is (almost) unique in the fact that it provides a reliable error.
With other methods, the difference with the last approximation is often used to specify an estimation of the error unless a more reliable estimation is available.

 

[evinda]

You will not be able to find the solution B for $e^x+x+1=0$ without the use of numerical methods (it is not solvable with a finite number of standard functions).

However, you already have your error: it is $(b_k-a_k)/2$.
That is the case since the root is guaranteed to be either between $a_k$ and $x_k$, or between $x_k$ and $b_k$.

So,in our case is the error at the last iteration: (bk-ak)/2:0.000977 Or,do you find something else??

The bisection method is (almost) unique in the fact that it provides a reliable error.
With other methods, the difference with the last approximation is often used to specify an estimation of the error unless a more reliable estimation is available.

What's,for example,about the Newton method?

 

[I like Serena]

So,in our case is the error at the last iteration: (bk-ak)/2:0.000977 Or,do you find something else??

Nope. That's what I have as well.

What's,for example,about the Newton method?

Yep! ;)

 

[evinda]

Nope. That's what I have as well.

Nice! :)

 

[evinda]

The difference between (a+b)/2 and (a+3b)/4 is the same as the difference between (a+3b)/4 and b.
In other words, it does not matter.

Actually, it is somewhat arbitrary if you consider $x_{k-1}$ to be $(a+b)/2$ or $b$.
If you consider $x_{k}$ and $x_{k-1}$ to be the last 2, most accurate, approximations, then they are (a+3b)/4 respectively b.
If you consider $x_{k}$ and $x_{k-1}$ the be the last 2 values you calculated, then they are (a+3b)/4 respectively (a+b)/2.
Either way, their absolute difference is the same and $x_{k}$ is guaranteed to be within ε of the real root.

I read your post again and I am confused right now..If we have the interval [a,b] then $x_{k-1}$=(a+b)/2 and if the new interval is [a,(a+b)/2] $x_{k}$=((3a+b)/4),so
|$x_{k}$-$x_{k-1}$| is equal to |(a-b)/4|,but |b-a|=|(b-a)/2|.So |$x_{k}$-$x_{k-1}$| and |b-a| are not equal.Or am I wrong?

 

[I like Serena]

I read your post again and I am confused right now..If we have the interval [a,b] then $x_{k-1}$=(a+b)/2 and if the new interval is [a,(a+b)/2] $x_{k}$=((3a+b)/4),so
|$x_{k}$-$x_{k-1}$| is equal to |(a-b)/4|,but |b-a|=|(b-a)/2|.So |$x_{k}$-$x_{k-1}$| and |b-a| are not equal.Or am I wrong?

What you write looks correct.
I guess the following would be more accurate.Suppose in iteration (k-1) you have the numbers $a_{k-1}$ and $b_{k-1}$.
Then:
$$x_{k-1} = \frac{a_{k-1} + b_{k-1}}{2}$$

Suppose the new interval is:
$$[a_k, b_k] = \left[a_{k-1}, \frac{a_{k-1} + b_{k-1}}{2}\right]$$
Then:
$$x_k = \frac{3a_{k-1} + b_{k-1}}{2}$$
And:
$$| x_k - x_{k-1} | = \frac{b_{k-1} - a_{k-1}}{4} = \frac{b_{k} - a_{k}}{2} = b_{k+1} - a_{k+1}$$

If however the new interval is:
$$[a_k, b_k] = \left[\frac{a_{k-1} + b_{k-1}}{2}, b_{k-1}\right]$$
you'll still get the same result for $| x_k - x_{k-1} |$.

 

[evinda]

Could you explain it further to me?
Because I found this:
When the interval is [$$a_{k-1}$$,$$b_{k-1}$$]

$$x_{k-1}$$=$$\frac{a_{k-1}+b_{k-1}}{2}$$

when the interval is [$$a_{k}$$,$$b_{k}$$]

$$x_{k}=\frac{a_{k-1}+\frac{a_{k-1}+b_{k-1}}{2}}{2}=\frac{3a_{k-1}+b_{k-1}}{4}$$

So,|$$x_{k}-x_{k-1}$$|=|$$\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})$$|=|$$\frac{a_{k-1}-b_{k-1}}{4}$$|

But |$$a_{k}-b_{k}$$|=|$$\frac{a_{k-1}-b_{k-1}}{2}$$|

so they are not equal..what have I done wrong?

 

[I like Serena]

Could you explain it further to me?
Because I found this:
When the interval is [$$a_{k-1}$$,$$b_{k-1}$$]

$$x_{k-1}$$=$$\frac{a_{k-1}+b_{k-1}}{2}$$

when the interval is [$$a_{k}$$,$$b_{k}$$]

$$x_{k}=\frac{a_{k-1}+\frac{a_{k-1}+b_{k-1}}{2}}{2}=\frac{3a_{k-1}+b_{k-1}}{4}$$

So,|$$x_{k}-x_{k-1}$$|=|$$\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})$$|=|$$\frac{a_{k-1}-b_{k-1}}{4}$$|

But |$$a_{k}-b_{k}$$|=|$$\frac{a_{k-1}-b_{k-1}}{2}$$|

so they are not equal..what have I done wrong?

I see nothing wrong.
That looks entirely correct! ;)

What you have matches with what I wrote:

$$| x_k - x_{k-1} | = \frac{b_{k-1} - a_{k-1}}{4} = \frac{b_{k} - a_{k}}{2} = b_{k+1} - a_{k+1}$$

 

[evinda]

I see nothing wrong.
That looks entirely correct! ;)

What you have matches with what I wrote:

|$$x_{k}-x_{k-1}$$|=|$$\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})$$|=|$$\frac{a_{k-1}-b_{k-1}}{4}$$|

|$$a_{k}-b_{k}$$|=|$$\frac{a_{k-1}-b_{k-1}}{2}$$|

How can they be equal?I don't understand :(

 

[I like Serena]

|$$x_{k}-x_{k-1}$$|=|$$\frac{3a_{k-1}+b_{k-1}}{4}-(\frac{a_{k-1}+b_{k-1}}{2})$$|=|$$\frac{a_{k-1}-b_{k-1}}{4}$$|

|$$a_{k}-b_{k}$$|=|$$\frac{a_{k-1}-b_{k-1}}{2}$$|

How can they be equal?I don't understand :(

They are not equal.
|$$x_{k}-x_{k-1}$$| is half of |$$a_{k}-b_{k}$$|.

If you want equality, pick |$$a_{k+1}-b_{k+1}$$|.

 

[evinda]

So,if they are not equal,why do we use the termination criteria |a-b|<TOL?I don't get it... :(