1
$\begingroup$

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 :)

$\endgroup$
1
$\begingroup$

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|$.

$\endgroup$
  • $\begingroup$ Thanks for your start, but how did you get $x_n=e_n+1/2$? $\endgroup$ – Bernard.Mathews Jul 22 '14 at 1:21
  • 1
    $\begingroup$ From the definition given in your post. We have $e_k=x_k-1/2$, so $x_k=e_k+1/2$. $\endgroup$ – André Nicolas Jul 22 '14 at 1:22
  • $\begingroup$ 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 $\endgroup$ – Bernard.Mathews Jul 22 '14 at 1:24
  • $\begingroup$ 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 $\endgroup$ – Bernard.Mathews Jul 22 '14 at 1:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Jul 22 '14 at 1:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.