Convergence rate of a nonlinear fixed point iteration Let $f(x)=x-\frac{1}{8}x^3$. Given the initial point $x_0=2$, consider the fixed point iteration $x_{k+1}=f(x_k)$. I could prove that the sequence $x_k$ is monotonically  decreasing and $x_k\to 0$. However, how to find out the exact convergence rate of $x_k$? Numerically, the sequence $x_k$ should have an asymptotic convergence rate $\Theta(1/\sqrt{k})$, but I don't know how to argue it rigorously. Can anyone help?
 A: Assuming $x_k\rightarrow 0$, and for $\alpha\in\mathbb R$
$$\begin{split}
x_{k+1}^\alpha &= \left ( x_k - \frac 1 8 x_k^3\right)^\alpha\\
&=x_k^\alpha \left(1-\frac 1 8 x_k^2 \right)^\alpha\\
&= x_k^\alpha \left(1-\frac \alpha 8 x_k^2 +o(x_k^2)\right)\\\\
&= x_k^\alpha - \frac \alpha 8 x_k^{\alpha+2}+o(x_k^{\alpha+2})
\end{split}$$
Thus by choosing $\alpha=-2$
$$\frac 1 {x_{k+1}^2}=\frac 1 {x_{k}^2}+\frac 1 4+o(1)$$
Summing this yields $$\frac 1 {x_k^2}\sim \frac k 4$$
or
$$x_k\sim \frac 2 {\sqrt k}$$
A: This just formalises Stefan's answer.
Note that $f([0,2]) \subset [0,2]$ so $x_k \in [0,2]$ for all $k$. Since $1-{x^2 \over 8} \in [0,1]$ for $x \in [0,2]$ we see that $0 \le x_{n+1} \le x_n$ for all $n$. In particular, $x_n \to x^*$ for some $x^*$, and since $x^*=f(x^*)$ we must have $x^* = 0$, hence $x_k \downarrow 0$.
We have
${1 \over x_{n+1}^2 } = {1 \over x_{n}^2 } ({1 \over 1-{x_n^2 \over 8}})^2 \ge {1 \over x_{n}^2 } (1 +{x_n^2 \over 8})^2 \ge {1 \over x_{n}^2 } + {1 \over 4}$, hence
${1 \over x_n^2} \ge {1 \over x_{0}^2 } + {n \over 4}$ and
so $|x_n-0| \le {2 \over \sqrt{n}}$.
