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

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 ? – James 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.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 31, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/3081576/iteration-for-fixed-point", "fetch_time": 1555837124000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-18/segments/1555578530505.30/warc/CC-MAIN-20190421080255-20190421102255-00521.warc.gz", "warc_record_offset": 483829051, "warc_record_length": 32987, "token_count": 777, "char_count": 2272, "score": 3.75, "int_score": 4, "crawl": "CC-MAIN-2019-18", "snapshot_type": "latest", "language": "en", "language_score": 0.7780877351760864, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00028-of-00064.parquet"}