4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Carl Christian Jan 22 at 22:54
  • $\begingroup$ 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. $\endgroup$ – LutzL Jan 22 at 23:05
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ how about if $|g'(r)| > 1$ can we find counterexample ? $\endgroup$ – James Jan 21 at 6:59
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.