Bisection Method for root finding

Question

My university teacher gave us a project. He wants us to create a program which will execute a modified bisection method for a function but not by diving everytime the range by $2$, but by dividing it with a random number. The process stops when $6$ digits precision occurs. My problem is with finding the correct condition for stopping finding roots.

*In classic Bisection when it gives us accuracy (for example, $6$) there's a formula for iterations that says:

Given a function $f$ defined on $(a,b)$,

$N> \frac{ \ln(b-a)-\ln k }{\ln2}$ with

$N$: number of iterations

$k: \frac12 \times 10^{-n}$ with $n$ being the wanted accuracy ($6$ in this example).

score 1 · Answer 1 · answered Dec 21 '16 at 21:07

1

Write a while loop, at each step, check the size of interval that you are working on $(a_k,b_k)$, you may stop when $b_k-a_k < 10^{-6}$.

If you know more information about how you are going to draw your random number, such that we know $\frac{b_k-a_k}{b_{k-1}-a_{k-1}} \leq r$ for some constant $r$, you should be able to come out with a closed form.

answered Dec 21 '16 at 21:07

Siong Thye Goh

149,520
20
88
149

I have already tried that. Everytime i'm dividing i store the number in an array so i call a function that when (array[n]-array[n-1] < 10^(-6)) returns true and my loop stops. But it won't work! – Georgio3 Dec 21 '16 at 21:11
hmm... something is weird. perhaps you want to print out elements of array and see what is going on. – Siong Thye Goh Dec 21 '16 at 21:36
Im already printing them everytime while runs. Here is my function for checking and the main program: http://i.imgur.com/6yoLpdO.png – Georgio3 Dec 21 '16 at 21:40
and this one i forgot http://i.imgur.com/3dNT1tW.png – Georgio3 Dec 21 '16 at 21:40
what about checking $|b_k-a_k| < 10^{-6}$? note the absolute value since it seems that you are storing one value at a time, which can be either smaller or bigger than the previous value. – Siong Thye Goh Dec 21 '16 at 21:46
Tried that with fabs() function!!! Still nothing. I don't know why it's not happening – Georgio3 Dec 21 '16 at 21:51
it seems to me that your $a$ and $b$ stays the same throughout the algorithm, isn't that a bug? – Siong Thye Goh Dec 21 '16 at 21:56
Considering how Bisection method works I think that it's OK. Everytime we are deviding and getting a new range one of the two values stays always the initial a or b – Georgio3 Dec 21 '16 at 22:01
Let us continue this discussion in chat. – Siong Thye Goh Dec 21 '16 at 22:03

Bisection Method for root finding

1 Answers1