Tutorials › Real Analysis › Applications to Equations

Home  /  Tutorials  /  Contraction Mappings

Contraction Mappings · Tutorial 759 of 1000

Applications to Equations

Reformulate equations as fixed-point problems and use contractions to prove that a solution exists, is unique, and can be approximated by iteration.

Advanced 10 min read

What You'll Learn

  • Reformulate an equation as a fixed-point equation without changing its solutions
  • Apply the Contraction Mapping Theorem to prove existence and uniqueness of a solution
  • Use a derivative bound to verify that an iteration is a contraction
  • Choose an invariant interval on which the contraction argument applies
  • Check an iteration and its numerical terms exactly

Turning an Equation into a Fixed-Point Problem

A contraction is not only a map whose iterates converge: it can also be a practical way to solve an equation. The main idea is to rewrite the equation so that its solutions are exactly the fixed points of a map. If that map sends a complete space into itself and is a contraction, the Contraction Mapping Theorem gives a unique solution and guarantees convergence of the iteration.

The choice of rewriting matters. An equation can have several algebraically equivalent forms, but the associated maps need not all be contractions. A useful formulation must both preserve the solutions of the original equation and make the contraction hypotheses verifiable on an appropriate domain.

Definition: Suppose an equation in a set \(X\) is written as \(F(x)=0\). A fixed-point formulation of the equation is a map \(T:X\to X\) for which \(F(x)=0\) holds exactly when \(T(x)=x\). Such a map is called an iteration map for the equation.

The equivalence in this definition is essential. It is not enough that every solution of \(F(x)=0\) be a fixed point if the map also has fixed points that do not solve the original equation. In an application, we check both directions of the equivalence.

Theorem (Contraction Criterion for an Equation): Let \((X,d)\) be a nonempty complete metric space, and let \(F:X\to\mathbb{R}\). Suppose there is a map \(T:X\to X\) such that $$ F(x)=0 \quad\Longleftrightarrow\quad T(x)=x $$ for every \(x\in X\), and suppose \(T\) is a contraction. Then the equation \(F(x)=0\) has exactly one solution in \(X\). For any starting point \(x_0\in X\), the iteration \(x_{n+1}=T(x_n)\) converges to that solution.

Proof. By the Contraction Mapping Theorem, \(T\) has a fixed point \(p\in X\), and the iteration starting from any \(x_0\in X\) converges to \(p\). The assumed equivalence gives \(F(p)=0\), so \(p\) is a solution of the equation.

If \(r\in X\) is any other solution, then \(F(r)=0\), so the equivalence implies \(T(r)=r\). Thus \(r\) is also a fixed point of \(T\). The Uniqueness of a Fixed Point theorem for contractions gives \(r=p\). Therefore the equation has exactly one solution in \(X\), and the asserted convergence is the convergence of the fixed-point iteration. \(\square\)

This criterion separates an equation-solving argument into three checks: select a domain, verify that the iteration map preserves that domain, and prove that it is a contraction there. The equivalence between solutions and fixed points completes the argument. Completeness is needed for the existence conclusion; a contraction on an incomplete space need not have a fixed point.

A Derivative Test for the Iteration Map

For maps on real intervals, a derivative bound is a convenient way to verify the contraction inequality. The next result converts a uniform bound on the derivative into a Lipschitz estimate. The interval and the uniformity of the bound matter: checking the derivative at a single point does not establish contraction on the entire domain.

Theorem (Derivative Criterion for a Contraction): Let \(I=[a,b]\) be a closed interval with \(a<b\). Suppose \(T\) is differentiable on an open interval containing \(I\), \(T[I]\subseteq I\), and there is a constant \(q\) with \(0\leq q<1\) such that $$ |T'(x)|\leq q $$ for every \(x\in I\). Then \(T:I\to I\) is a contraction with contraction constant \(q\).

Proof. Take any \(x,y\in I\). If \(x=y\), then \(|T(x)-T(y)|=0=q|x-y|\). If \(x\ne y\), the Mean Value Theorem applies to \(T\) between \(x\) and \(y\). It gives a point \(c\) between them such that

$$ |T(x)-T(y)|=|T'(c)|\,|x-y|. $$

Since \(c\in I\), the derivative bound implies

$$ |T(x)-T(y)|\leq q|x-y|. $$

This holds for every pair \(x,y\in I\), so \(T\) is a contraction on \(I\). The assumption \(T[I]\subseteq I\) ensures it is a self-map, as required. \(\square\)

A closed interval in \(\mathbb{R}\) is complete, so the Contraction Criterion for an Equation applies once the derivative criterion and the fixed-point equivalence have been checked. If the interval consists of a single point, the derivative test is unnecessary: any self-map of that interval fixes its sole point.

Worked Examples: Choosing and Checking an Iteration

Worked Example: Solving \(x^2+x=1\) on a Positive Interval

Consider \(x^2+x=1\) on \(I=[1/2,1]\). Since \(1+x\) is positive on this interval, the equation is equivalent to

$$ x^2+x=1 \quad\Longleftrightarrow\quad x(1+x)=1 \quad\Longleftrightarrow\quad x=\frac{1}{1+x}. $$

Thus choose \(T(x)=1/(1+x)\). For \(x\in[1/2,1]\), the denominator lies between \(3/2\) and \(2\), so

$$ \frac12\leq T(x)\leq\frac23. $$

In particular, \(T[I]\subseteq I\). The derivative is \(T'(x)=-1/(1+x)^2\), and hence

$$ |T'(x)|=\frac{1}{(1+x)^2}\leq\frac{1}{(3/2)^2}=\frac49. $$

The derivative criterion shows that \(T\) is a contraction on \(I\), and the equation has exactly one solution in \(I\). For example, starting from \(x_0=1/2\), the first terms are

$$ x_1=T\left(\frac12\right)=\frac23,\qquad x_2=T\left(\frac23\right)=\frac35,\qquad x_3=T\left(\frac35\right)=\frac58. $$

Each equality follows by substituting into \(T(x)=1/(1+x)\); for instance, \(T(3/5)=1/(8/5)=5/8\). The contraction theorem guarantees that the full sequence converges to the unique solution, even though the solution need not be known in advance.

Worked Example: Solving \(x^3+x=1\)

On \(I=[1/2,1]\), the equation \(x^3+x=1\) is equivalent to

$$ x(1+x^2)=1 \quad\Longleftrightarrow\quad x=\frac{1}{1+x^2}. $$

Take \(T(x)=1/(1+x^2)\). If \(1/2\leq x\leq1\), then \(1/4\leq x^2\leq1\), and therefore \(1/2\leq T(x)\leq4/5\). Thus \(T\) maps \(I\) into itself. Its derivative satisfies

$$ |T'(x)|=\frac{2x}{(1+x^2)^2}. $$

Because \((1-x)^2\geq0\), we have \(2x\leq1+x^2\). Also \(1+x^2\geq5/4\) on \(I\). Consequently,

$$ |T'(x)| \leq\frac{1}{1+x^2} \leq\frac45. $$

So \(T\) is a contraction, and the equation has exactly one solution in this interval. Iterating from \(x_0=1/2\) gives

$$ x_1=\frac{1}{1+(1/2)^2}=\frac45,\qquad x_2=\frac{1}{1+(4/5)^2}=\frac{25}{41}. $$

For the second calculation, \(1+(4/5)^2=1+16/25=41/25\), whose reciprocal is \(25/41\). The example illustrates how an algebraic rearrangement can produce a self-map and how a uniform derivative bound then controls the iteration.

Worked Example: A Correctly Checked Iteration for \(x^2=2\)

On \(I=[1,2]\), the equation \(x^2=2\) is equivalent to \(x=x/2+1/x\): multiplying the latter equation by \(2x\), which is positive on \(I\), gives \(2x^2=x^2+2\), and hence \(x^2=2\). Define

$$ T(x)=\frac{x}{2}+\frac1x. $$

For \(x\in[1,2]\), both terms are positive, \(x/2\geq1/2\), and \(1/x\geq1/2\), so \(T(x)\geq1\). Also \(x/2\leq1\) and \(1/x\leq1\), so \(T(x)\leq2\). Thus \(T\) maps \(I\) into itself. Its derivative is \(T'(x)=1/2-1/x^2\). Since \(1/4\leq1/x^2\leq1\), it follows that

$$ -\frac12\leq T'(x)\leq\frac14, \qquad |T'(x)|\leq\frac12. $$

The derivative criterion proves that \(T\) is a contraction. Therefore \(x^2=2\) has exactly one solution in \([1,2]\), and iteration converges to it. Starting from \(x_0=2\), the first two steps are

$$ x_1=T(2)=\frac22+\frac12=\frac32, \qquad x_2=T\left(\frac32\right) =\frac{3/2}{2}+\frac{1}{3/2} =\frac34+\frac23 =\frac{9}{12}+\frac{8}{12} =\frac{17}{12}. $$

In particular, \(17/12\) is the second iterate, not the first. The exact substitutions matter: the first iterate is \(3/2\), and applying \(T\) to \(3/2\) gives \(17/12\).

Why the Choice of Reformulation Matters

A given equation may admit more than one fixed-point formulation. For instance, rearranging an equation can make a derivative large, or can produce a map that leaves the chosen interval. In either case the contraction argument fails, even if the equation itself has a solution. Failure to verify a particular iteration map is not proof that the original equation has no solution; it means only that this method has not established one.

A common general way to construct an iteration is to start with \(F(x)=0\) and choose a nonzero constant \(\lambda\), then set \(T(x)=x-\lambda F(x)\). Since \(\lambda\ne0\),

$$ T(x)=x \quad\Longleftrightarrow\quad x-\lambda F(x)=x \quad\Longleftrightarrow\quad F(x)=0. $$

When \(F\) is differentiable, the derivative is \(T'(x)=1-\lambda F'(x)\). This formula can help select \(\lambda\), but a useful choice must still give a uniform bound \(|T'(x)|\leq q<1\) on the domain and must make \(T\) map that domain into itself. A pointwise derivative value, or a bound that holds only near a suspected solution, is not enough for the theorem on the whole interval.

Once the hypotheses hold, the error results established earlier in this course can also quantify the approximation. In particular, the A Posteriori Error Bound applies to the iterates, and the Fixed-Point Residual Error Bound can certify the distance to the solution from the residual \(d(x,T(x))\). These estimates do not replace the initial existence and contraction checks; they build on them.

Check Your Understanding

Use the equation criterion and derivative test to answer the following questions.

  1. Why must a fixed-point formulation preserve solutions in both directions?
  2. What three checks allow the Contraction Mapping Theorem to be applied to an equation on a complete metric space?
  3. In the derivative criterion, why must the bound on \(|T'(x)|\) hold throughout the interval?
  4. For \(T(x)=x-\lambda F(x)\), why does \(\lambda\ne0\) ensure that fixed points correspond exactly to solutions of \(F(x)=0\)?
  5. In the \(x^2=2\) example, which iterate equals \(17/12\), and what is the preceding iterate?

Previous

Next

Back to Tutorials