Numerical analysis objective question on bisection method.

Question

Let $M$ be the length of the initial interval $[a_0,b_0]$ containing a solution of $f(x)=0$ . Let $\{x_0,x_1,\cdots \}$ represents the successive points generated by the bisection method. Then the minimum number of iterations required to guarantee an approximation to the solution with an accuracy of $\epsilon $ is given by

$1.$ $-2-\frac{log(\frac{\epsilon}{M})}{log(2)}$.

$2.$ $-2+\frac{log(\frac{\epsilon}{M})}{log(2)}$.

$3.$ $-2-\frac{log(\frac{\epsilon}{M})}{log^2(2)}$.

$4.$ $-2-\frac{log(M\epsilon)}{log(2)}$.

Using $$ n\ge \frac{\log{(b_0-a_0)}-\log{\epsilon}}{\log2} $$ I only got that $$n\ge \frac{\log{M}-\log{\epsilon}}{\log2} $$ So $$ n\ge \frac{\log(\frac{M}{\epsilon})}{\log2} =-\frac{\log(\frac{\epsilon}{M})}{\log2}$$

Now I don’t know from where $-2$ comes. Please help to find the correct option . Thank you .

Answer 1

Ok so in my opinion it doesn't really matter, because you already have the answer to your question, which is more about the number of iterations when the ratio $\frac{\varepsilon}{M}$ is small and the $-2$ is not important, probably put in by the lecturer/course director/whoever.

Wikipedia states,

In mathematics, the bisection method is a root-finding method that applies to any continuous functions for which one knows two values with opposite signs.

So for your question, I think we do know (i.e. we are told) the sign of $f(a_0)$ and $f(b_0)$ because otherwise, $f(a_0), f(b_0), f\left(\frac{a_0+b_0}{2}\right)$, and almost every subsequent midpoint obtained by the bisection method could have the same sign, making it impossible to know which interval a root is in.

If $x_0 \in (a_0,b_0)$ or $x_1 \in (a_0,b_0)$, then assuming your bisection method will happen inside $[x_0,x_1],$ the roots could lie outside of $[x_0,x_1]$ but inside $(a_0,b_0),$ so the bisection method might not find the roots, in $(a_0,b_0)$, because it only searches in $[x_0,x_1].$

So I think the following is implicitly assumed by the question:

1. You know the sign of $f(a_0)$ and you know that the sign of $f(b_0)$ is different to the sign of $f(a_0)$: for example you know that $f(a_0)$ is negative and $f(b_0)$ is positive.
2. One of {$x_0, x_1$} equals $a_0$ and the other one of {$x_0, x_1$} equals $b_0.$

This way, the change of sign in the interval $[a_0,b_0] = [x_0,x_1]$ means that the first two points $x_0$ and $x_1$ told us that the root is in the interval $[a_0,b_0]$. So you only start obtaining "new information" that you didn't already know from the 3rd iteration, namely $x_2$, and onwards.