- Thread starter
- #1

- Apr 13, 2013

- 3,723

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??

- Thread starter evinda
- Start date

- Thread starter
- #1

- Apr 13, 2013

- 3,723

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??

- Admin
- #2

- Mar 5, 2012

- 8,851

Hi evinda!!

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??

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.

- Thread starter
- #3

- Apr 13, 2013

- 3,723

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

- Admin
- #4

- Jan 26, 2012

- 4,197

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.Do you mean that [tex] x_{k-1} [/tex] is the real root??

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!And..could you explain me both of the conditions further??I haven't understood them yet

- Admin
- #5

- Mar 5, 2012

- 8,851

No, the real root is between $x_{k-1}$ and $x_{k}$.Do you mean that [tex] x_{k-1} [/tex] is the real root?? If yes,why???

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 ε.

- Thread starter
- #6

- Apr 13, 2013

- 3,723

For the first criteria, using the following loop :

Code:

```
if fa*fmid <=0
b = (a+b)/2;
else
a = (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??

- Admin
- #7

- Mar 5, 2012

- 8,851

Yes. That is correct.

For the first criteria, using the following loop :

(where fmid=(a+b)/2)Code:`if fa*fmid <=0 b = (a+b)/2; else a = (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??

- Thread starter
- #8

- Apr 13, 2013

- 3,723

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

- Thread starter
- #9

- Apr 13, 2013

- 3,723

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]| ???

- Admin
- #10

- Mar 5, 2012

- 8,851

The difference between (a+b)/2 and (a+3b)/4 is the same as the difference between (a+3b)/4 and b.

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]| ???

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.

- Thread starter
- #11

- Apr 13, 2013

- 3,723

[tex] x_{k} [/tex] do I have to use?

- Admin
- #12

- Mar 5, 2012

- 8,851

The last calculated value seems nice.

[tex] x_{k} [/tex] do I have to use?

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

- Thread starter
- #13

- Apr 13, 2013

- 3,723

So,do I have to use fmid ??

- Admin
- #14

- Mar 5, 2012

- 8,851

Yes.So,do I have to use fmid ??

- Thread starter
- #15

- Apr 13, 2013

- 3,723

Code:

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

Why is it like that??

- Admin
- #16

- Mar 5, 2012

- 8,851

It's an optimization..Code:`while(fabs((b-a)/2)>TOL)`

Why is it like that??

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$

- Thread starter
- #17

- 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] ??

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:

- Admin
- #18

- Mar 5, 2012

- 8,851

I can not really tell you what you have to print. That depends on the question asked.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] ??

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

- Thread starter
- #19

- Apr 13, 2013

- 3,723

[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?

- Thread starter
- #20

- Apr 13, 2013

- 3,723

For example if we have the function exp(x)+x+1 what should be the output???

- Admin
- #21

- Mar 5, 2012

- 8,851

I see that your version of the algorithm is slightly different than I thought.

[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?

It stops if one of the conditions is satisfied and not necessarily both.

So my earlier comments on that topic are not applicable.

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

For example if we have the function exp(x)+x+1 what should be the output???

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

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

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??

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

.

- Thread starter
- #23

- Apr 13, 2013

- 3,723

Great!!!!I get the same outputWith a = -2, b = -1, and TOL = 0.001, I get:

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

- Thread starter
- #24

- Apr 13, 2013

- 3,723

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?

- Admin
- #25

- Mar 5, 2012

- 8,851

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).

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?

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.