# Iteration for fixed point

Suppose $$x_{k+1}= g(x_k)$$ is fixed point iteration for some continuously diffrentiable $$g(x)$$. The theorem im learning says that if $$g(r) = r$$ and $$|g'(r)| < 1$$ then the fixed point iteration converges to $$r$$ for initial guess $$x_0$$ sufficiently close to $$r$$.

MY question is: Is the converse is also true? That is, if the fixed point iteration converges to $$r$$, then we must have $$|g'(r)|<1$$?

OR is it possible to have situations where $$g'(r) \geq 1$$ with $$(x_k)$$ convergent to $$r$$.

## 3 Answers

The iteration $$x_{n+1}=\sin(x_n)$$ converges towards $$r=0$$ despite the derivative there being $$\cos(0)=1$$.

### Details on the convergence

For $$y_k=x_k^2$$ one has the estimate by the Leibniz rule on alternating series $$y_{k+1}=\frac12(1-\cos(2x_k)) \le y_k-\frac13y_k^2+\frac2{45}y_k^3 %=y_k\frac{1-\frac{1}{15}y_k^2-\frac2{135}y_k^3}{1+\frac13y_k} \le\frac{y_k}{1+\frac13y_k}\\~\\ \implies y_{k+1}^{-1}\ge\frac13+y_k^{-1}\implies y_k\le\frac{y_0}{1+\frac{k}3y_0}$$ so that one finds the convergence by the non-geometric majorant $$|x_k|\le\frac{|x_0|}{\sqrt{1+\frac{k}3x_0^2}}.$$

• A good example with a nice bound. I also like $x_{k+1} = tan^{-1}{x_k}$ for which I imagine we can also apply alternating series. Please reconsider the use of the small font. I have to magnify it to read it. – Carl Christian Jan 22 at 22:54
• From $x_{k+1}=x_k-\frac13x_k^3+...$ you get by similar Bernoulli-like considerations $x_{k+1}^{-2}\approx x_k^{-2}+\frac23$. Exact inequalities are a little bit more complicated, as there is no nice identity for the square of the arcus tangent. – LutzL Jan 22 at 23:05

Let $$g(x)=x$$. Then the sequence $$(x_k)$$ is constant hence convergent. We have $$g'(x)=1$$ for all $$x$$.

• how about if $|g'(r)| > 1$ can we find counterexample ? – Jimmy Sabater Jan 21 at 6:59

Suppose you have the function $$f(x)=kx(x-a)+a$$ so that $$f(a)=a$$

Then $$f'(x)=2kx-k = k(2x-1)$$ and if $$a\neq \frac 12$$ it is possible to choose a value of $$k$$ to make $$f'(a)$$ any value you choose.

The difference is that if $$|f'(a)| \gt 1$$ there is no open interval containing $$a$$ in which the iteration converges - this only happens at the point.

The behaviour in general where $$|f'(a)| = 1$$ depends on the function.