Fixed-point iteration

Remarks

If $X$ is a metric space, $f$ is continuous, and the iteration converges to $x^*$, then $x^*$ is a fixed point, since $f(x^*) = \lim f(x_n) = \lim x_{n+1} = x^*$. Example: for $f(x) = x/2 + 1/x$ on $(0, \infty)$ and $x_0 = 1$, the iterates are $1, 1.5, 1.41\overline{6}, \ldots$, and they converge to $\sqrt{2}$, the fixed point, since $x = x/2 + 1/x$ means $x^2 = 2$. Non-example of convergence: for $f(x) = 2x$ on $\R$ and $x_0 = 1$, the iterates $2^n$ diverge, although $0$ is a fixed point. The Banach fixed point theorem says the iteration converges to the unique fixed point when $f$ is a contraction of a nonempty complete metric space. If $q < 1$ is the contraction constant, the error after $n$ steps is at most $q^n d(x_1, x_0) / (1 - q)$. The sequence is also written $x_n = f^n(x_0)$, the $n$-th iterate of $f$ applied to $x_0$.