Welcome to our community

Be a part of something great, join today!

Bisection method-numerical analysis

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Hi!!!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
[tex] \left |x_{k}-x_{k-1} \right | [/tex] < ε , [tex] \left | f(x_{k})\right |[/tex] <ε

termination criteria of this method?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
Hi!!!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
[tex] \left |x_{k}-x_{k-1} \right | [/tex] < ε , [tex] \left | f(x_{k})\right |[/tex] <ε

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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Do you mean that [tex] x_{k-1} [/tex] is the real root?? If yes,why???
And..could you explain me both of the conditions further??I haven't understood them yet :confused:
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,197
Do you mean that [tex] x_{k-1} [/tex] 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 :confused:
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!
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
Do you mean that [tex] x_{k-1} [/tex] 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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
I think that I got it..!!
For the first criteria, using the following loop :
Code:
if fa*fmid <=0
           b = (a+b)/2;
 else
           a = (a+b)/2;
(where fmid=(a+b)/2)

the [tex] x_{k} [/tex] and [tex] x_{k-1} [/tex] are [tex] a [/tex] and [tex] b [/tex] respectively? Or am I wrong??
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
I think that I got it..!!
For the first criteria, using the following loop :
Code:
if fa*fmid <=0
           b = (a+b)/2;
 else
           a = (a+b)/2;
(where fmid=(a+b)/2)

the [tex] x_{k} [/tex] and [tex] x_{k-1} [/tex] are [tex] a [/tex] and [tex] b [/tex] respectively? Or am I wrong??
Yes. That is correct.
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Nice..Thank you both very much..!!! :p
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
I looked the exercise again...Is there an other way to express |[tex] x_{k}-x_{k-1} [/tex]|<ε ,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 |[tex] x_{k}-x_{k-1} [/tex]| ???
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
I looked the exercise again...Is there an other way to express |[tex] x_{k}-x_{k-1} [/tex]|<ε ,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 |[tex] x_{k}-x_{k-1} [/tex]| ???
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
I understand :) And...for this: [tex] \left | f(x_{k})\right |[/tex] <ε ,which
[tex] x_{k} [/tex] do I have to use?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
I understand :) And...for this: [tex] \left | f(x_{k})\right |[/tex] <ε ,which
[tex] x_{k} [/tex] 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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
So,do I have to use fmid ??
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
Nice.. :eek: And..something else..I found implementations of the bisection method and there the termination criteria is
Code:
 while(fabs((b-a)/2)>TOL)
.

Why is it like that?? :confused:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
Nice.. :eek: And..something else..I found implementations of the bisection method and there the termination criteria is
Code:
 while(fabs((b-a)/2)>TOL)
.

Why is it like that?? :confused:
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
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 [tex] x_{k} [/tex] must be printed if [tex]\left | x_{k}-x_{k-1} \right | < ε [/tex] and [tex] \left | f(x_{k}) \right | < ε [/tex] ??
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
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 [tex] x_{k} [/tex] must be printed if [tex]\left | x_{k}-x_{k-1} \right | < TOL [/tex] and [tex] \left | f(x_{k}) \right | < TOL [/tex] ??
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
At each step of the bisection method my code should print the current approximation [tex] x_{k} [/tex] and f([tex] x_{k} [/tex]).....The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
[tex]\left | x_{k}-x_{k-1} \right | [/tex] < ε and [tex] \left | f(x_{k}) \right | [/tex] < ε
are valid.

So,what do you think now? :eek:
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
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???
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
At each step of the bisection method my code should print the current approximation [tex] x_{k} [/tex] and f([tex] x_{k} [/tex]).....The program should end if the number of iterations surpass the maximum number of iterations,or if one or both of these conditions :
[tex]\left | x_{k}-x_{k-1} \right | [/tex] < ε and [tex] \left | f(x_{k}) \right | [/tex] < ε
are valid.

So,what do you think now? :eek:
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

Well-known member
Feb 3, 2013
134
Hi!!!I wanted to ask you something about the Bisection method,because I got stuck.
Why are these conditions:
[tex] \left |x_{k}-x_{k-1} \right | [/tex] < ε , [tex] \left | f(x_{k})\right |[/tex] <ε

termination criteria of this method?? :confused:
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

Well-known member
MHB Site Helper
Apr 13, 2013
3,723

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,723
I am facing also difficulties at an other subquestion. :eek:
I have to find the error [tex] \left | x_{k}-B \right | [/tex] (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?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,851
I am facing also difficulties at an other subquestion. :eek:
I have to find the error [tex] \left | x_{k}-B \right | [/tex] (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.