Contraction Mapping Mastery

Reading Contraction Estimates Precisely

A contraction estimate is more than a statement that images tend to be closer together: it requires one uniform factor strictly below $1$ to work for every pair of points. This uniformity is what allows the Contraction Mapping Theorem to control an entire sequence of iterates. In this tutorial, we examine how such factors behave under common constructions and how an estimate at a single point can locate a region where the theorem applies.

Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces, and let $T:X\to Y$. A Lipschitz bound is required to be nonnegative. The distinction matters even in degenerate cases, such as when the domain has only one point.

Definition: A finite nonnegative number $L$ is a Lipschitz bound for $T$ if $$ d_Y(Tx,Ty)\leq Ld_X(x,y) $$ for all $x,y\in X$. If $T:X\to X$ has a Lipschitz bound $q$ with $0\leq q<1$, then $T$ is a contraction, and $q$ is a contraction constant.

A map may have several Lipschitz bounds. Any one below $1$ certifies that it is a contraction; the smallest possible bound need not be attained. One way to describe the limiting size of all its pairwise ratios is the supremum of those ratios over distinct $x,y$. If there are no distinct points in $X$, take this supremum to be $0$. A map is a contraction exactly when this supremum is strictly less than $1$.

The last condition is stronger than saying that each individual ratio is less than $1$. Individual ratios can approach $1$ as the points vary, leaving no uniform contraction constant. The distinction is worth checking before applying the Contraction Mapping Theorem.

Worked Example: Ratios Below One Without a Contraction Constant

On the complete metric space $X=[0,\infty)$, define $T(x)=x/(1+x)$. The map takes values in $X$. For $x,y\geq0$,

|T(x)-T(y)| =\left|\frac{x}{1+x}-\frac{y}{1+y}\right| =\frac{|x-y|}{(1+x)(1+y)}.

For distinct $x,y$, the denominator is greater than $1$, so the ratio $|T(x)-T(y)|/|x-y|$ is less than $1$. However, choosing $y=0$ and letting $x>0$ approach $0$ gives

\frac{|T(x)-T(0)|}{|x-0|} =\frac{1}{1+x}\longrightarrow 1.

Thus no single $q<1$ bounds all the ratios, and $T$ is not a contraction. The example has a fixed point, since $T(0)=0$, but the Contraction Mapping Theorem cannot be invoked on the basis of these estimates. Pairwise strict decrease alone is not the required uniform condition.

Contraction Constants Under Composition

A common way to build a map is to apply one transformation and then another. The contraction constants multiply, as the following result shows. It allows estimates to be assembled one stage at a time rather than derived again for the full composition.

Theorem (Composition of Contractions): Let $(X,d_X)$, $(Y,d_Y)$, and $(Z,d_Z)$ be metric spaces. Suppose $f:X\to Y$ has a Lipschitz bound $a\geq0$, and $g:Y\to Z$ has a Lipschitz bound $b\geq0$. Then $g\circ f:X\to Z$ has Lipschitz bound $ab$. In particular, if both maps are contractions, their composition is a contraction.

Proof. For arbitrary $x_1,x_2\in X$, apply the Lipschitz bound for $g$ to $f(x_1),f(x_2)$, and then the bound for $f$:

d_Z(g(f(x_1)),g(f(x_2))) \leq b\,d_Y(f(x_1),f(x_2)) \leq ba\,d_X(x_1,x_2).

Since $a,b\geq0$, the product $ab$ is a finite nonnegative Lipschitz bound for $g\circ f$. If $a<1$ and $b<1$, then $0\leq ab<1$, so this composition is a contraction. $\square$

Worked Example: Composing Two Affine Contractions

Let $f:\mathbb{R}\to\mathbb{R}$ and $g:\mathbb{R}\to\mathbb{R}$ be given by

f(x)=\frac{x}{3}+1, \qquad g(y)=\frac{y}{2}-2.

For any $x_1,x_2\in\mathbb{R}$, direct subtraction gives

|f(x_1)-f(x_2)|=\frac13|x_1-x_2|, \qquad |g(y_1)-g(y_2)|=\frac12|y_1-y_2|.

Thus $f$ and $g$ are contractions with constants $1/3$ and $1/2$, respectively. Their composition is

(g\circ f)(x) =\frac12\left(\frac{x}{3}+1\right)-2 =\frac{x}{6}-\frac32.

Its contraction constant is $1/6$, in agreement with the product $(1/3)(1/2)$. Since $\mathbb{R}$ is complete and $g\circ f$ maps $\mathbb{R}$ into itself, the Contraction Mapping Theorem gives a unique fixed point. Solving its equation confirms the value:

x=\frac{x}{6}-\frac32 \quad\Longleftrightarrow\quad \frac56x=-\frac32 \quad\Longleftrightarrow\quad x=-\frac95.

Substitution checks the result: $(-9/5)/6-3/2=-3/10-15/10=-18/10=-9/5$.

Relaxing an Iteration

In a normed vector space, one can combine a map $T$ with the identity map. This changes the step taken at each iteration: instead of moving all the way to $T(x)$, the new map moves a proportion $\lambda$ of the way there. For $0<\lambda\leq1$, the resulting map remains a contraction whenever $T$ is one, and it has exactly the same fixed points.

Theorem (Relaxation of a Contraction): Let $V$ be a complete normed vector space, let $C\subseteq V$ be nonempty, closed, and convex, and suppose $T:C\to C$ is a contraction with constant $q$, where $0\leq q<1$. For $0<\lambda\leq1$, define $$ R_\lambda(x)=(1-\lambda)x+\lambda T(x). $$ Then $R_\lambda:C\to C$ is a contraction with constant $1-\lambda+\lambda q<1$, and $R_\lambda$ and $T$ have the same fixed points.

Proof. First, $x,T(x)\in C$, and $C$ is convex. Since $0<\lambda\leq1$, the coefficients $1-\lambda$ and $\lambda$ are nonnegative and sum to $1$; hence $R_\lambda(x)\in C$. So $R_\lambda$ is a self-map of $C$.

For $x,y\in C$, the triangle inequality and homogeneity of the norm give

\begin{aligned} \|R_\lambda(x)-R_\lambda(y)\| &=\|(1-\lambda)(x-y)+\lambda(T(x)-T(y))\|\\ &\leq (1-\lambda)\|x-y\|+\lambda\|T(x)-T(y)\|\\ &\leq (1-\lambda+\lambda q)\|x-y\|. \end{aligned}

Because $\lambda>0$ and $q<1$, we have $1-\lambda+\lambda q=1-\lambda(1-q)<1$; it is also nonnegative. Thus $R_\lambda$ is a contraction. Finally, if $R_\lambda(x)=x$, then

(1-\lambda)x+\lambda T(x)=x \quad\Longrightarrow\quad \lambda(T(x)-x)=0.

Since $\lambda>0$, this is equivalent to $T(x)=x$. Conversely, $T(x)=x$ immediately gives $R_\lambda(x)=x$. The fixed-point sets are therefore equal. $\square$

Worked Example: A Half-Step Iteration

Take $C=[0,2]$ and $T(x)=(x+1)/3$. For $x\in[0,2]$, $1/3\leq T(x)\leq1$, so $T$ maps $C$ into itself. Also, $|T(x)-T(y)|=|x-y|/3$, so it is a contraction with constant $q=1/3$. With $\lambda=1/2$, its relaxed map is

R_{1/2}(x) =\frac12x+\frac12\left(\frac{x+1}{3}\right) =\frac{4x+1}{6}.

The theorem predicts contraction constant $1-\lambda+\lambda q=1/2+1/6=2/3$. Directly, $|R_{1/2}(x)-R_{1/2}(y)|=(2/3)|x-y|$, confirming the bound. The fixed point is unchanged: solving either equation gives

x=\frac{x+1}{3} \quad\Longleftrightarrow\quad x=\frac12, \qquad x=\frac{4x+1}{6} \quad\Longleftrightarrow\quad x=\frac12.

Thus the half-step map still converges to the same fixed point by the Contraction Mapping Theorem, although its guaranteed contraction factor is larger than that of $T$.

Locating a Fixed Point with a Closed Ball

A global self-map on a complete space is not always necessary. Sometimes the useful estimate shows that a closed ball is invariant, even if the map is originally defined on a larger space. The following criterion uses the displacement of the ball’s center to verify invariance.

Theorem (Fixed Point in an Invariant Ball): Let $(X,d)$ be a complete metric space, let $x_0\in X$, and let $R>0$. Suppose $T$ is defined on the closed ball $$ \overline{B}(x_0,R)=\{x\in X:d(x,x_0)\leq R\} $$ and satisfies a contraction estimate there with constant $0\leq q<1$. If $$ d(Tx_0,x_0)\leq(1-q)R, $$ then $T$ maps this ball into itself and has a unique fixed point in it.

Proof. The closed ball is closed in $X$, hence complete with the restricted metric. For any $x\in\overline{B}(x_0,R)$, the triangle inequality, the contraction estimate, and the assumed center-displacement bound give

\begin{aligned} d(Tx,x_0) &\leq d(Tx,Tx_0)+d(Tx_0,x_0)\\ &\leq q\,d(x,x_0)+(1-q)R\\ &\leq qR+(1-q)R=R. \end{aligned}

Therefore $Tx\in\overline{B}(x_0,R)$, so the restriction of $T$ is a contraction from this complete, nonempty ball into itself. The Contraction Mapping Theorem gives a unique fixed point in the ball. $\square$

Worked Example: Applying the Ball Criterion

On $\mathbb{R}$, let $T(x)=x/3+1$, and consider the closed ball with center $x_0=2$ and radius $R=1$, namely $[1,3]$. The map has contraction constant $q=1/3$, and

|T(2)-2| =\left|\frac23+1-2\right| =\frac13 \leq \left(1-\frac13\right)1 =\frac23.

The criterion applies. Its invariance estimate can also be checked directly: for $x\in[1,3]$, $4/3\leq T(x)\leq2$, so $T(x)\in[1,3]$. The unique fixed point in the ball is obtained from

x=\frac{x}{3}+1 \quad\Longleftrightarrow\quad \frac23x=1 \quad\Longleftrightarrow\quad x=\frac32,

and $3/2\in[1,3]$. The criterion is useful because its hypotheses can be checked from one center displacement and a contraction estimate, rather than by inspecting every image in the ball separately.

Putting the Estimates to Work

These techniques address different parts of a fixed-point argument. Composition is useful when a transformation is naturally built in stages: estimate each stage, then multiply the bounds. Relaxation is useful when an iteration should take partial steps while preserving the target fixed point. The ball criterion is useful when a global self-map is unavailable but a suitable complete region can be shown invariant.

In every case, keep track of the exact hypotheses. A Lipschitz bound must be nonnegative; a contraction constant must be strictly below $1$; and the space on which the Contraction Mapping Theorem is applied must be complete and mapped into itself. A calculation that gives only pointwise ratios below $1$, without a uniform bound, does not establish contraction. Likewise, the relaxation result requires $\lambda>0$ to preserve the fixed points, and the ball criterion requires the stated bound on the center displacement.

Check Your Understanding

Use the definitions and results in this tutorial to answer each question.

Why does the map $x\mapsto x/(1+x)$ on $[0,\infty)$ fail to be a contraction even though each ratio for distinct points is less than $1$?
If $f$ and $g$ have nonnegative Lipschitz bounds $a$ and $b$, what bound does the composition $g\circ f$ have, and why?
For $0<\lambda\leq1$, why do $T$ and $R_\lambda=(1-\lambda)I+\lambda T$ have the same fixed points?
In the invariant-ball theorem, which estimate proves that the image of every point in the ball remains in the ball?
For $T(x)=x/3+1$ on the ball $[1,3]$, verify the center-displacement condition and identify the fixed point.

What You'll Learn