Necessary conditions for convergence in the fixed-point iteration algorithm?

Question

What are the necessary conditions for convergence of the fixed point iteration algorithm?

One condition I have come across is that if $|g'(x)|<1$ for all $x$ in some interval $[a,b]$ where g is continuously differentiable in [a.b] then the iteration $x_{n+1}=g(x_n)$ converges for any initial guess $x_0 \in [a.b]$. Is this just a sufficient condition, or is it necessary and sufficient?

You need more, like that $g$ has a fixed-point in $[a,b]$ or that it's a contraction, see Banach's fixed-point theorem for example. — emacs drives me nuts, Jul 19 '22 at 13:46
There are at least half a dozen fixed point theorems. You must be more precise. — Jean Marie, Jul 19 '22 at 15:21
It's difficult to give a necessary condition, since even in very bad function you can have a good luck and for example $g(g(g(x)))$ is a fixed point. — Mateo, Jul 21 '22 at 16:56

score 1 · Answer 1 · answered Jul 21 '22 at 16:36

A common version is that if $g:[a,b]\to [a,b]$ is contractive, i.e. there exists a constant $0\leq L <1$ such that $|g(x)-g(y)| \leq L|x-y|, \forall x,y \in [a,b]$, then $g$ has one and only fixed point $z \in [a,b]$ and the sequence $x_{n+1}=g(x_n)$ converges to $z$, for any initial approximation $x_0\in[a,b]$.

If $g$ is differentiable, the contractivity can be established if $|g'|<1$.

Necessary conditions for convergence in the fixed-point iteration algorithm?

1 Answers1