Let the bisection method be applied to a continuous function, resulting in intervals $[a_0, b_0], [a_1, b_1],$ and so on. Let

Question

Let the bisection method be applied to a continuous function, resulting in intervals $[a_0, b_0], [a_1, b_1],$ and so on. Let $r=\lim_{n\to \infty}a_n$. Which of these statements can be false?

(a) $a_0\leq a_1\leq a_2\leq ...$

(b) $|r-2^{-1}(a_n+b_n)|\leq 2^{-n}(b_0-a_0), (n\geq 0)$

(c) $|r-2^{-1}(a_{n+1}+b_{n+1})|\leq |r-2^{-1}(a_n+b_n)|, (n\geq 0)$

(d) $[a_{n+1},b_{n+1}]\subset [a_n,b_n], (n\geq 0)$

(e) $|r-a_n|=O(2^{-n}) \text{ as } n\to \infty$

(f) $|r-c_n|<|r-c_{n-1}|, (n\geq 0)$

By definition I know that $a_0\leq a_1\leq ...$, besides $|r-c_n|=|r-2^{-1}(a_n+b_n)|\leq 2^{-(n+1)}(b_0-a_0)\leq2^{-n}(b_0-a_0)$, then (a) and $b$ are true, I have the suspicion that (c), (e) and (f) are false but I can not find a counterexample, could someone help me please? Thank you very much.

Answer 1

Part $[c]:$

From part $B$ we can say:

$|r-2^{-1}(a_n+b_n)|\leq 2^{-n}(b_0-a_0), (n\geq 0) \tag 1$

$|r-2^{-1}(a_{n+1}+b_{n+1})|\leq 2^{-(n+1)}(b_0-a_0), (n\geq 0) \tag 2$

Since: $ 2^{-(n+1)}(b_0-a_0) - 2^{-n}(b_0-a_0)<0$ by substracting $2$ from $1$ we have:

$|r-2^{-1}(a_{n+1}+b_{n+1})|-|r-2^{-1}(a_n+b_n)|<0$

$\to |r-2^{-1}(a_{n+1}+b_{n+1})|<|r-2^{-1}(a_n+b_n)|$

In other words: $|r-2^{-1}(a_{n+1}+b_{n+1})|$ is the distance between the ${n+1}_{st}$ iteration value and the final converged value. As we increase $n$ then this distance decreases since it is converging. In ${n+1}_{st}$ iteration we are closer the final value than $n_{th}$ interation. So part $c$ is true.

Part $[f]:$

$|r-c_n|<|r-c_{n-1}|, (n\geq 0)$

This is also true and exactly like part $[c]$ as $c_n=2^{-1}(a_{n+1}+b_{n+1})$. Just substitute it with $c_n$ and everything is the same.

Part $[e]:$

Each step you are dividing your interval by $2$. This makes the accuracy of your answer $2$ times better than the previous iteration, meaning:

$|r-a_n|=O(2^{-n})$

As $n\to \infty$ then $2^{-n} \to 0$ and this means convergence.

Answer 2

Part (e) is true because $\left\{r,a_n\right\}\subset\left[a_n,b_n\right]$ and $b_n-a_n=2^{-n}\left(b_0-a_0\right)$ so $\left|r-a_n\right|\le\left(b_n-a_n\right)=2^{-n}\left(b_0-a_0\right)$.

Part (c) is the same as part (f) and so is false. Let $f(x)=x-\frac25$, $a_0=0$, and $b_0=1$. Then $r=\frac25$ and $c_0=\frac12$ and $\left|\frac25-\frac12\right|=\frac1{10}$. Since $f(a_0)f(c_0)=\left(-\frac25\right)\left(\frac1{10}\right)<0$, $a_1=a_0=0$ and $b_1=c_0=\frac12$. Then $c_1=\frac14$ and $\left|r-c_1\right|=\left|\frac25-\frac14\right|=\frac3{20}$.