Does an attractive fixed point always have a derivative between 1 and -1?

Question

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

Answer 1

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

---

Appendix: On the use of the Leibniz test and its bounds

If $a_0(x)>a_1(x)>a_2(x)>...>0$ converges to $0$ for $|x|<r$, then the alternating series $$s(x)=a_0(x)-a_1(x)+a_2(x)\mp...$$ converges and is bounded by the partial sums, above by even index and below by odd index, so that $$s_1(x)<s(x)\le s_2(x).$$ As $$1-\cos x=\frac{x^2}2-\frac{x^4}{24}+\frac{x^6}{720}\mp...$$ one gets for $|x|<\sqrt{12}$ the bounds $$\frac{x^2}2-\frac{x^4}{24}\le 1-\cos x\le \frac{x^2}2-\frac{x^4}{24}+\frac{x^6}{720},$$ which is used in the bound of $(1-\cos2x)/2\le x^2-x^4/3+2x^6/45$.

---

Supplement: Higher order terms

Having found the first order approximation, one could wonder if there is some function $f(y)=b\ln(y)+a_1y+a_2y^2+...$ that transforms the iteration to the form $$ y_{n+1}^{-1}+f(y_{n+1})=c+y_n^{-1}+f(y_n), $$ so that then an exact solution formula can be obtained from $$ y_n^{-1}+f(y_n)=cn+d,~~ d=y_0^{-1}+f(y_0),~~ y_n\approx \frac1{cn+d} $$ Using $y_{n+1}=y_ng(y_n)$, where $x^2g(x^2)=\frac12(1-\cos(2x))$, $g(0)=1$, results in the functional equation \begin{align} r(y)=y^{-1}(g(y)^{-1}-1)&=c+f(y)-f(yg(y)) \\ &=c-b\ln(g(y))+a_1y(1-g(y))+a_2y^2(1-g(y)^2)+... \\ &=c-b(g_1y+g_2y^2)+\frac b2(g_1y)^2-a_1g_1y^2+O(y^3) \end{align} One finds that $$ g(y)=1 - \frac13y + \frac2{45}y^2 \mp... \\ r(y)=\frac13 + \frac1{15}y + \frac2{189}y^2 + ... $$ so that in the comparing the leading coefficients \begin{align} c&=\frac13\\ b&=\frac15\\ a_1&=3\left(\frac2{189}+\frac2{5\cdot45}-\frac1{10\cdot9}\right) =\frac{79}{3150} \end{align}

A<a>:=FunctionField(Rationals());
PS<y>:=PowerSeriesRing(A);
Pol<z>:=PolynomialRing(Rationals());

N:=10; 
g := (1-Cos(2*(y+O(y^(2*N+5)))))/2;
gc := Coefficients(g); g:=PS!gc[1..#gc by 2];
r := PS!((g^(-1)-1)/y); 

f := PS!0;
for k in [1..N] do
    fa := f+(a+O(y^2))*y^k;
    res := 1/3+fa-Evaluate(fa, y*g)-r-Log(g)/5;res;
    eqn := Coefficient(res , k+1 );
    c := Roots(Pol!eqn)[1,1]; k,c;
    f +:= c*y^k;
end for;

giving the start of the series expansion of $f$ as $$ f(y)=\frac15\ln(y)+\frac{79}{3150}y + \frac{29}{7875}y^2 + \frac{91543}{109147500}y^3 + \frac{18222899}{85135050000}y^4 + \frac{88627739}{1719073125000}y^5+... $$

Answer 2

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

Answer 3

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.