1

I have an exam in a previous exam paper which i have no solutions too. I am stuck on the last 2 parts of the question and have been for several days now! Any help much appreciated. Here is the question:

Let $D:=[1/4,3/4]$

and consider the iteration $x_k = 2x_{k-1} (1-x_{k-1})$ with any fixed $x_0 \in D$

Define the residual $r_k:=x_k - x_{k-1}$

and define the error $e_k:=x_k - 1/2$

c.)Argue from first principles that there exists constants $C$,$\kappa >0$ with $\kappa <1$

such that $|e_k|$$\leq C\kappa^k $

d.)then deduce by showing all steps that $\lim_{k \to \infty} x_k = 1/2 $

Obviously for part C i have to use some kind of theorem or formula but i am unsure whether t means something like banach caccioppoli or a basic analysis theorem. I also know that the error term is generally defined as $e_k:=\hat{x}-x_k$ but i am unsure how i can apply this to prove/show the statement. Please help! Many thanks :)

Bernard.Mathews
  • 834

1 Answers1

1

A start: We have $x_n=e_n+1/2$. Substituting in the recurrence we obtain $$e_k+1/2=2(e_{k-1}+1/2)(1/2-e_{k-1}),$$ which simplifies to $$e_k =-2e_{k-1}^2.$$ Initially, $|e_0|\le \frac{1}{4}$. Thus $|e_1|\le \frac{1}{2}|e_0|$, and in particular $x_1$ remains in the interval $D$. But then $|e_2|\le \frac{1}{2}|e_1|$, and so $x_2$ remains in $D$. In general $|e_k|\le \frac{1}{2^k}|e_0|$.

André Nicolas
  • 507,029
  • Thanks for your start, but how did you get $x_n=e_n+1/2$? – Bernard.Mathews Jul 22 '14 at 01:21
  • 1
    From the definition given in your post. We have $e_k=x_k-1/2$, so $x_k=e_k+1/2$. – André Nicolas Jul 22 '14 at 01:22
  • Oh sorry i ment the "n"'s instead of "k"'s but just reading the rest of your answer i realised it is an error! Thanks i will check i understand this and maybe get back to you in a min if i dont. Thanks very much for your help – Bernard.Mathews Jul 22 '14 at 01:24
  • thanks for your answer that is great! all understood feel stupid for asking now. Is there a method or special way of showing that the limit is $1/2$? Sorry for the stupid questions, i havent done any maths for a while as i was ill, revising for the retake now hence i have the exam paper and no sols, my lecturer is away. Thanks very much – Bernard.Mathews Jul 22 '14 at 01:28
  • 1
    It is equivalent to showing that $\lim_{k\to\infty}e_k=0$. How you show that depends on the tools you are allowed to use. Since $e_0$ has absolute value $\lt 1$, we have $|e_k|\lt \frac{1}{2^k}$, and presumably you are allowed to use the fact that $1/2^k$ has limit $0$. If not, one can use the binomial expansion of $(1+1)^k$ to show that $2^k\gt 1+k\gt k$ if $k\ge 1$, so $1/2^k\lt 1/k$. – André Nicolas Jul 22 '14 at 01:39