Iterated Sequences and Geometric Convergence

The sequence of iterates

Given $f$ and a starting point $u_0$, the sequence of iterates is defined recursively:

$$u_{n+1} = f(u_n)$$

If this sequence converges to a real number $c$ and $f$ is continuous, then taking the limit in the recurrence relation gives $f(c) = c$: the limit is necessarily a fixed point. The whole question is therefore how to guarantee convergence.

Geometric decay of the error

Suppose $f$ is $k$-contracting and has a fixed point $c$. Applying the definition to the pair $\left(u_n, c\right)$, and since $f(c) = c$:

$$\lvert u_{n+1} - c \rvert = \lvert f(u_n) - f(c) \rvert \leq k\,\lvert u_n - c \rvert$$

A straightforward induction then gives the fundamental bound:

$$\lvert u_n - c \rvert \leq k^n\,\lvert u_0 - c \rvert$$

Since $0 \leq k < 1$, we have $k^n \to 0$, so $u_n \to c$: the convergence is geometric, and it occurs whatever the starting point.

A step-by-step example

Let us iterate $f(x) = \cos x$ starting from $u_0 = 0$. The fixed point, called the Dottie number, is $c \approx 0.739085$.

$n$	$u_n$	$\lvert u_n - c \rvert$
$0$	$0$	$0.7391$
$2$	$0.540302$	$0.1988$
$4$	$0.654290$	$0.0848$
$6$	$0.701369$	$0.0377$
$8$	$0.722102$	$0.0170$
$10$	$0.731404$	$0.0077$

The error is divided by a little more than $2$ every two steps, which corresponds to $\lvert f'(c) \rvert^2 = \sin^2 c \approx 0.45$, well below the bound $k^2 \approx 0.71$:

Usable error estimates

In practice we do not know $c$, so the bound in terms of $\lvert u_0 - c \rvert$ is useless as it stands. Two variants, however, can be computed from the observed values alone:

$$\lvert u_n - c \rvert \leq \frac{k^n}{1 - k}\,\lvert u_1 - u_0 \rvert \qquad \text{and} \qquad \lvert u_n - c \rvert \leq \frac{k}{1 - k}\,\lvert u_n - u_{n-1} \rvert$$

The first, called the a priori estimate, lets you fix in advance the number of iterations needed; the second, called the a posteriori estimate, turns the gap between two consecutive terms into a bound on the actual error. It is the stopping criterion used in algorithms.

Classic pitfall

Believing that a sequence defined by $u_{n+1} = f(u_n)$ converges as soon as $f$ has a fixed point. For $f(x) = -2x$, the fixed point is $0$, and yet the sequence starting from $u_0 = 1$ is $1, -2, 4, -8, \ldots$: it diverges, because $\lvert f' \rvert = 2 > 1$. The fixed point is then called repelling. Only contraction guarantees that it is attracting.