# Bisection method-numerical analysis

#### evinda

##### Well-known member
MHB Site Helper
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?? #### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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

##### Indicium Physicus
Staff member
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!

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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 $$x_{k}$$ and $$x_{k-1}$$ are $$a$$ and $$b$$ respectively? Or am I wrong??

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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 $$x_{k}$$ and $$x_{k-1}$$ are $$a$$ and $$b$$ respectively? Or am I wrong??
Yes. That is correct.

#### evinda

##### Well-known member
MHB Site Helper
Nice..Thank you both very much..!!! #### evinda

##### Well-known member
MHB Site Helper
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}$$| ???

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
I understand And...for this: $$\left | f(x_{k})\right |$$ <ε ,which
$$x_{k}$$ do I have to use?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
So,do I have to use fmid ??

Staff member

#### evinda

##### Well-known member
MHB Site Helper
Nice.. 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?? #### Klaas van Aarsen

##### MHB Seeker
Staff member
Nice.. 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?? 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
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 | < ε$$ ??

Last edited:

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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

##### Well-known member
MHB Site Helper
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
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 = -1.278320313 and f(x) = 0.000184396.

#### zzephod

##### Well-known member
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

##### Well-known member
MHB Site Helper
With a = -2, b = -1, and TOL = 0.001, I get:

x = -1.278320313 and f(x) = 0.000184396.
Great!!!!I get the same output #### evinda

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.