5

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

wlad
  • 8,185
James
  • 3,997

3 Answers3

4

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^(2N+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, yg)-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+... $$

Community
  • 1
Lutz Lehmann
  • 126,666
  • 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 '19 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. – Lutz Lehmann Jan 22 '19 at 23:05
  • Cool answer. What does this have to do with the Leibniz test? – wlad Aug 02 '19 at 09:41
  • @manandlaptop : I added a section on this topic, in short, the cosine is an alternating series and the Leibniz test in its full version has quantitative claims on the convergence. – Lutz Lehmann Aug 02 '19 at 09:59
  • 1
    @CarlChristian Something similar is possible with $\arctan$. See here: https://i.stack.imgur.com/twZHU.png – wlad Aug 04 '19 at 08:25
3

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

Fred
  • 77,394
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.

Mark Bennet
  • 100,194