Convergence rate of a nonlinear fixed point iteration

Question

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?

Answer 1

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

Answer 2

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