On convergence of a fixed point iteration

Question

I'm stating the problem that I'm stuck with, along with the progress that I've made.

Problem : The iteration defined by $x_{k+1}=\frac{1}{2}\left(x_k^2+c\right)$, where $0<c<1$, has two fixed points $\xi_1$ and $\xi_2$, where $0 < \xi_1 < 1 < \xi_2$ . Show that $$x_{k+1}-\xi_1=\frac{1}{2}\left(x_k+\xi_1\right)\left(x_k-\xi_1\right), \,\,k=0,1,2,\dots$$ and deduce that $\lim_{k \to \infty}x_k=\xi_1$ if $0 \leq x_0<\xi_2$. How does the iteration behave for other values of $x_0$?

---

I have progressed in the following way :

The fixed point iteration is given by \begin{equation}\tag1 x_{k+1}=\frac{1}{2}(x_k^2+c) \end{equation}

If $\xi_1$ is a fixed point, then \begin{equation}\tag2 \xi_1=\frac{1}{2}(\xi_1^2+c) \end{equation}

$(1)-(2)$ gives, for $k=0,1,2,\dots$, \begin{align*} x_{k+1}-\xi_1&=\frac{1}{2}(x_k^2+c)-\frac{1}{2}(\xi_1^2+c)\\ &=\frac{1}{2}\left(x_k^2-\xi_1^2\right)\\ &=\frac{1}{2}\left(x_k+\xi_1\right)\left(x_k-\xi_1\right) \end{align*}

Now, \begin{align*} x_{k+1}-\xi_1&=\frac{1}{2}\left(x_k+\xi_1\right)\left(x_k-\xi_1\right)\\ &=\frac{1}{2}\left(x_k+\xi_1\right)\frac{1}{2}\left(x_{k-1}+\xi_1\right)\left(x_{k-1}-\xi_1\right)\\ &=\left(\frac{1}{2}\right)^2 \left(x_k+\xi_1\right)\left(x_{k-1}+\xi_1\right)\left(x_{k-1}-\xi_1\right)\\ &=\left(\frac{1}{2}\right)^3 \left(x_k+\xi_1\right)\left(x_{k-1}+\xi_1\right)\left(x_{k-2}+\xi_1\right)\left(x_{k-2}-\xi_1\right)\\ &\dots \dots \dots \dots \dots \dots\\ &=\left(\frac{1}{2}\right)^{k+1} \left(x_0-\xi_1\right) \prod\limits_{i=0}^k \left(x_i+\xi_1\right) \end{align*}

How can I ensure that this quantity goes to $0$ as $k \to \infty$? Can I show that $x_i+\xi_1$ will eventually be $<2$? Also, what happens to the situation when $x_0 \notin [0,\xi_2)$? Any help would be much appreciated. Thank you.

Answer 1

Hints. You have to find those fixed points, given $x_{k+1}=f(x_k)=\frac{1}{2}\left(x^2_{k}+c\right)$, where $f(x)=\frac{1}{2}\left(x^2+c\right)$ of course, fixed points $f(\xi)=\xi$ are those satisfying $\xi^2-2\xi+c=0$ or $\xi_1=1-\sqrt{1-c}$ and $\xi_2=1+\sqrt{1-c}$.

---

One thing to observe is that $f'(x)=x \geq0, \forall x\geq0$ so the function is ascending. As a result $$0\leq x_0<\xi_2 \Rightarrow 0\leq x_1=f(x_0) \leq f(\xi_2)=\xi_2$$ and by induction $$0\leq x_k \leq \xi_2, \forall k$$ which makes $(x_k)$ a bounded sequence when $x_0 \in \left[0,\xi_2\right)$.

---

Another thing to observer is that

• $f(x)\geq x \iff x \in \left[0, 1-\sqrt{1-c}\right] \cup \left[1+\sqrt{1-c},\infty\right)$
• $f(x)< x \iff x \in \left(1-\sqrt{1-c},1+\sqrt{1-c}\right)$

As a result:

• $x_0 \in \left[0, 1-\sqrt{1-c}\right] \Rightarrow x_1=f(x_0)\geq x_0$ and by induction $x_{k+1}\geq x_k$, making $(x_k)$ increasing and bounded, thus it has a limit.
• $x_0 \in \left[1+\sqrt{1-c},\infty\right) \Rightarrow x_1=f(x_0)\geq x_0$ and by induction $x_{k+1}\geq x_k$, making $(x_k)$ increasing, but it's not bounded anymore.
• $x_0 \in \left(1-\sqrt{1-c},1+\sqrt{1-c}\right) \Rightarrow x_1=f(x_0)\leq x_0$ and by induction $x_{k+1}\leq x_k$, making $(x_k)$ decreasing and bounded, thus it has a limit.

Answer 2

Hint. Note that $0<\xi_1 = 1 - \sqrt{1-c}<1<\xi_2 = 1 + \sqrt{1-c}$. Show by induction that

i) if $x_0\in [0,\xi_1)$ then $x_k<x_{k+1}<\xi_1$.

ii) if $x_0\in (\xi_1,\xi_2)$ then $\xi_1<x_{k+1}<x_k$.

iii) if $x_0\in (\xi_2,+\infty)$ then $\xi_2<x_k<x_{k+1}$.

Then recall that a monotone bounded sequence has a finite limit and any finite limit $L$ of the recurrence $x_{k+1}=\frac{1}{2}\left(x_k^2+c\right)$ satisfies the equation $L=\frac{1}{2}\left(L^2+c\right)$ that is $L\in\{\xi_1,\xi_2\}$.