On convergence of a fixed point iteration

convergence-divergencefixed points-fixed-point-theoremsnumerical methods

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.

Best Answer

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.
Related Question