Convergence of the Iterative Sequence

From Iteration to Convergence

In “Constructing the Iterative Sequence,” the recursion $x_{n+1}=f(x_n)$ was defined for a self-map $f:X\to X$. Construction alone says that every term exists; it does not say that the terms approach a limit. For a contraction on a complete metric space, the Contraction Mapping Theorem guarantees a unique fixed point. Here we focus on the behavior of the orbit: why its terms approach that point, how quickly they do so, and what convergence can tell us about subsequences.

Let $f:X\to X$ be a contraction with constant $q$, where $0\leq q<1$, and let $p$ be its fixed point, so $f(p)=p$. For any starting point $x_0\in X$, define $x_{n+1}=f(x_n)$. The Contraction Estimate for Iterates, established in “Contractions,” compares the images of two points after the same number of iterations. Apply it to $x_0$ and $p$: the orbit stays close to the fixed point, with its distance reduced by a factor of at least $q$ at each step.

Theorem (Convergence of the Iterative Sequence): Let $f:X\to X$ be a contraction with constant $q$, where $0\leq q<1$, and let $p\in X$ be a fixed point of $f$. For every $x_0\in X$, the iterative sequence $x_{n+1}=f(x_n)$ converges to $p$.

Proof. Since $p$ is a fixed point, $f^n(p)=p$ for every nonnegative integer $n$. The Orbit and Tail Identity gives $x_n=f^n(x_0)$. By the Contraction Estimate for Iterates,

d(x_n,p) =d\bigl(f^n(x_0),f^n(p)\bigr) \leq q^n d(x_0,p).

Because $0\leq q<1$, $q^n\to0$ as $n\to\infty$. The distance $d(x_0,p)$ is fixed, so the right-hand side tends to zero. Thus $d(x_n,p)\to0$, which is exactly the statement that $x_n\to p$. If $q=0$, the same conclusion holds: for every $n\geq1$, the displayed bound is zero, so $x_n=p$. $\square$

This proof identifies the role of completeness precisely. Completeness is needed in the Contraction Mapping Theorem to guarantee that a fixed point exists in $X$. Once a fixed point $p\in X$ is known, the convergence estimate above needs only the contraction inequality and the fixed-point identity. The estimate also applies to every starting point, not just to one particular choice of $x_0$.

A Quantitative Error Bound

The preceding estimate involves the distance from the initial point to the fixed point, which may be unknown in an application. A different estimate uses only the first step of the iteration, $d(x_1,x_0)$. It bounds the remaining error by summing the distances between consecutive terms. The Cauchy Estimate for Successive Iterates from “Contractions” controls each of those distances geometrically.

Theorem (A Priori Error Bound from the First Step): Under the hypotheses above, for every $n\geq0$, $$ d(x_n,p)\leq \frac{q^n}{1-q}\,d(x_1,x_0). $$ Here $q^0=1$, including when $q=0$.

Proof. The Cauchy Estimate for Successive Iterates gives, for every $j\geq0$,

d(x_{j+1},x_j)\leq q^j d(x_1,x_0).

Fix $n$, and take any integer $N>n$. Repeated use of the triangle inequality gives

d(x_n,p) \leq \sum_{j=n}^{N-1}d(x_{j+1},x_j)+d(x_N,p) \leq d(x_1,x_0)\sum_{j=n}^{N-1}q^j+d(x_N,p).

By the Convergence of the Iterative Sequence theorem, $d(x_N,p)\to0$ as $N\to\infty$. The finite geometric sums tend to $q^n/(1-q)$, since $0\leq q<1$. Taking the limit in the inequality therefore gives

d(x_n,p)\leq d(x_1,x_0)\sum_{j=n}^{\infty}q^j =\frac{q^n}{1-q}\,d(x_1,x_0).

This also covers $q=0$. For $n=0$, the infinite sum is $1$; for $n\geq1$, it is $0$. In that case the orbit reaches its fixed point at $x_1$. $\square$

The bound is useful before the fixed point has been computed: it supplies a guaranteed maximum error after $n$ steps using the contraction constant and the first observed displacement. It is an upper bound, not necessarily the exact error. In particular, a small bound certifies that the iterate is close to $p$, while a large bound does not show that the actual error is large.

Worked Examples: Reading the Convergence Estimates

Worked Example: An Affine Contraction on the Real Line

Let $X=\mathbb{R}$, define $f(x)=(x+4)/3$, and start at $x_0=0$. For all $x,y\in\mathbb{R}$,

|f(x)-f(y)| =\left|\frac{x+4}{3}-\frac{y+4}{3}\right| =\frac13|x-y|.

Thus $f$ is a contraction with $q=1/3$. Solving $f(p)=p$ gives $(p+4)/3=p$, so $p=2$. The first two iterates are $x_1=4/3$ and $x_2=16/9$; the first-step displacement is $d(x_1,x_0)=4/3$. The theorem gives

|x_n-2| \leq \frac{(1/3)^n}{1-1/3}\cdot\frac43 =2\left(\frac13\right)^n.

In fact, the recurrence gives the exact error. Since $x_{n+1}-2=(x_n-2)/3$ and $x_0-2=-2$, induction yields $x_n-2=-2(1/3)^n$. For example, $x_1-2=-2/3$ and $x_2-2=-2/9$, matching the formula. Here the bound is exact, and it shows explicitly how the orbit approaches $2$.

Worked Example: A Nonlinear Contraction on an Interval

Let $X=[0,1]$, $f(x)=1/(3+x)$, and $x_0=0$. The map takes values between $1/4$ and $1/3$, so it maps $X$ into itself. For $x,y\in[0,1]$,

|f(x)-f(y)| =\frac{|x-y|}{(3+x)(3+y)} \leq\frac19|x-y|,

because each denominator factor is at least $3$. Thus $q=1/9$ is a contraction constant. The fixed point satisfies $p=1/(3+p)$, or $p^2+3p-1=0$. The root in $[0,1]$ is $p=(-3+\sqrt{13})/2$; it is positive because $\sqrt{13}>3$, and less than $1$ because $\sqrt{13}<5$. Also $x_1=1/3$, so $d(x_1,x_0)=1/3$. The a priori estimate becomes

|x_n-p| \leq \frac{(1/9)^n}{1-1/9}\cdot\frac13 =\frac38\left(\frac19\right)^n.

The estimate guarantees convergence even though the successive terms do not have a simple pattern of rational values. It also gives a numerical stopping principle: as $n$ increases, the stated upper bound decreases by a factor of $1/9$ at each step.

Worked Example: A Contraction Without a Limit in Its Domain

Consider $X=(0,1)$ with the usual metric and $f(x)=x/2$. This is a self-map, since $0<x<1$ implies $0<x/2<1$, and it is a contraction with $q=1/2$. Starting at $x_0=1/2$, direct iteration gives

x_1=\frac14,\qquad x_2=\frac18,\qquad x_n=\frac{1}{2^{n+1}}.

In the ambient space $\mathbb{R}$, these terms converge to $0$. But $0\notin X$, and $f$ has no fixed point in $X$: the equation $x/2=x$ forces $x=0$. Thus the orbit does not converge to a point of $X$. This metric space is not complete, and this example shows why completeness matters when a theorem promises a fixed point inside the space. It does not contradict the convergence estimate for a known fixed point, because there is no such point in $X$.

Convergent Subsequences and Fixed Points

For a general sequence, the term immediately following a selected subsequence need not approach the same limit. A contraction orbit has additional control: consecutive terms become close, and this allows a limit of any convergent subsequence to be identified. The argument uses the successive-iterate estimate, not an assumption that the shifted indices belong to the selected subsequence.

Theorem (Limits of Convergent Subsequences of a Contraction Orbit): Let $f:X\to X$ be a contraction, and let $(x_n)$ be an iterative sequence. If a subsequence $(x_{n_k})$, with strictly increasing indices $n_k$, converges to $z\in X$, then $z$ is the unique fixed point of $f$.

Proof. The Contraction Estimate for Iterates applied to $x_1$ and $x_0$ gives

d(x_{n+1},x_n) =d\bigl(f^n(x_1),f^n(x_0)\bigr) \leq q^n d(x_1,x_0).

Since $n_k\to\infty$ and $q^n\to0$, it follows that $d(x_{n_k+1},x_{n_k})\to0$. Using $x_{n_k}\to z$, the triangle inequality yields

d(x_{n_k+1},z) \leq d(x_{n_k+1},x_{n_k})+d(x_{n_k},z)\longrightarrow0.

Therefore $x_{n_k+1}\to z$ as well. On the other hand, contractions are continuous, as established in “Contractions.” Hence $f(x_{n_k})\to f(z)$. The recursion says $f(x_{n_k})=x_{n_k+1}$, and this sequence has just been shown to converge to $z$. Limits in a metric space are unique, so $f(z)=z$. The Uniqueness of a Fixed Point theorem then implies that $z$ is the unique fixed point. $\square$

The key step is the estimate $d(x_{n_k+1},x_{n_k})\to0$. Strict increase of the indices makes $(x_{n_k+1})$ a subsequence of the full orbit, but does not generally make it a subsequence of $(x_{n_k})$. The small-distance estimate, together with $x_{n_k}\to z$, is what establishes the needed convergence of the shifted terms.

Interpreting the Results

The two error estimates answer different questions. The bound $d(x_n,p)\leq q^n d(x_0,p)$ is direct when the initial error is known. The bound based on $d(x_1,x_0)$ is useful when the fixed point is unknown, because the first step is available from the iteration itself. Both express geometric control, but neither should be confused with an exact description of the error unless equality has been verified for the particular map.

For practical use, keep the domain in view. A contraction on a complete metric space has a fixed point there by the Contraction Mapping Theorem, and every orbit converges to it. On an incomplete space, the orbit may still be Cauchy in the metric but have its limit outside the domain, as in the interval $(0,1)$ example. Also, a few computed terms alone cannot certify convergence; the contraction estimates provide the uniform control that makes the conclusion rigorous.

Check Your Understanding

Use the convergence arguments and estimates above to answer the following questions.

Which previously established estimate, applied to $x_0$ and a fixed point $p$, proves convergence of the orbit?
For a contraction with $q=1/2$ and $d(x_1,x_0)=3$, what upper bound does the a priori error estimate give for $d(x_2,p)$?
Why does completeness matter for obtaining a fixed point in $X$, but not for convergence once a fixed point $p\in X$ is already known?
In the subsequence theorem, what establishes that $x_{n_k+1}\to z$ when $x_{n_k}\to z$?
For $f(x)=x/2$ on $(0,1)$, where does the orbit starting at $1/2$ converge in $\mathbb{R}$, and why is that not convergence to a point of $X$?