Does the following limit exist as a result of the bisection method?

Question

$$\lim_{n\rightarrow\infty}\dfrac{|r-c_{n+1}|}{|r-c_{n}|}$$

where $r$ is the root as a result of the method, and $c_n=\dfrac{a_n+b_n}{2}$

My professor has told me that the limit does NOT always exist, but I'm stuck on how to show it (and he's not giving me any more hints on this lol). I've dabbled with the theorem regarding its bounds a little with no success; that doesn't mean that won't lead me to the answer - I just don't see it yet.

Any ideas?

Lutz Lehmann · Answer 1 · 2018-02-15T20:19:08.837

Try $f(x)=5x-1$ on the interval $[0,1]$.

Essentially, you are computing the quotients of the remainder of the binary expansion after a certain digit. To get convergence this sequence must have at most period 2, but most rational numbers have a binary expansion with a higher period. And irrational numbers are even more irregular.

Using the MAGMA CAS online calculator for their built-in rational numbers with the script

f:=func<x|5*x-1>;
a:=0; b:=1; 
for k in [0..20] do
  c := (a+b)/2;
  if f(c) lt 0 then a:=c; else b:=c; end if;
  printf "%15o  %15o\n", c, (c-1/5)*2^k;
end for;

returns the table

   k:              c[k]        (c[k]-1/5)*2^k

   1:              1/2             3/10
   2:              1/4             1/10
   3:              1/8            -3/10
   4:             3/16            -1/10
   5:             7/32             3/10
   6:            13/64             1/10
   7:           25/128            -3/10
   8:           51/256            -1/10
   9:          103/512             3/10
  10:         205/1024             1/10
  11:         409/2048            -3/10
  12:         819/4096            -1/10
  13:        1639/8192             3/10
  14:       3277/16384             1/10
  15:       6553/32768            -3/10
  16:      13107/65536            -1/10
  17:     26215/131072             3/10
  18:     52429/262144             1/10
  19:    104857/524288            -3/10
  20:   209715/1048576            -1/10
  21:   419431/2097152             3/10

which shows the period 4 pattern in the remainders leading to an oscillation between -3 and 1/3 in the quotients.

Could you better explain your counterexample? I know that in this case $r=1/5$, but what would $c_n$?, how can I determine $\lim_{n\to \infty}|r-c_{n+1}|/|r-c_n|$ this case to conclude that $\lim_{n\to \infty}|r-c_{n+1}|/|r-c_n|$ not exist? — user424241, Feb 15 '18 at 17:36

Does the following limit exist as a result of the bisection method?

1 Answers1