Let $c_n=\frac{1}{2}(a_n+b_n), r=\lim_{n\to \infty}c_n,$ and $e_n=r-c_n$. Here $[a_n,b_n]$, with $n\geq 0$, denotes the succesive intervals the arise in the bisection method when it is applied to a continuous function $f$.

  • (a) Show that $|e_n|\leq 2^{-n}(b_1-a_1)$

  • (b) Show that $e_n=O(2^{-n})$ as $n\to \infty$

  • (c) Is it true that $|e_0|\geq |e_1|\geq ...$? Explain.

  • (d) Show that $|c_n-c_{n+1}|=2^{-n-2}(b_0-a_0)$

For (a) $|e_n|=|r-c_n|\leq \frac{1}{2}|b_n-a_n|=\frac{1}{2}2^{-(n-1)}(b_1-a_1)=2^{-n}(b_1-a_1)$ because $b_{n+1}-a_{n+1}=\frac{1}{2}(b_n-a_n)$

For (b) We know that $|e_n|\leq 2^{-n}(b_1-a_1)$ for $n\geq 0$ and so, taking $C:=(b_1-a_1)>0$ we get that $|e_n|\leq C2^{-n}$ for all $n\geq 0$, which means that $e_n=O(2^{-n})$ as $n\to \infty$.

For (c) yes it is true because $(b_1-a_1)\geq (b_1-a_1)/2\geq (b_1-a_1)/4\geq...$.

For (d) Show that $|c_n-c_{n+1}|=2^{-n-2}(b_0-a_0)$.

Is this reasoning correct? Thank you very much.

  • 1
    $\begingroup$ I'm suspicious of (c), since you're drawing on the fact that the sequence converges exponentially, without addressing whether one estimate is necessarily closer to another. For example, the sequence $\sin(n) \cdot e^{-n}$ is exponentially convergent, but not monotonically convergent. $\endgroup$ – Theo Bendit Feb 13 '18 at 4:11
  • $\begingroup$ @TheoBendit How could I solve this problem? Is there a different way of doing this? $\endgroup$ – user402543 Feb 13 '18 at 18:12
  • 1
    $\begingroup$ Well, I question whether it's true at all (as does the question!). I would try formulating a counter-example. Try starting with a very wide interval whose midpoint is very close to (but not on) a root of the function. $\endgroup$ – Theo Bendit Feb 14 '18 at 0:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.