# Metric Spaces: Contraction Mappings

**Definition**
Let \(A\) be a mapping of a metric space \(R\) onto itself. Then \(x\) is a *fixed
point* of \(A\) if \(Ax = x\). Suppose there exists \(\alpha < 1\) such that
\(\rho(Ax, Ay)\) for all \(x, y \in R\), then \(A\) is a *contraction mapping*. Every
contraction mapping is automatically continuous, since \(Ax_n \rightarrow Ax\)
whenever \(x_n \rightarrow x\).

**Theorem 1** (Fixed point theorem)

Every contraction mapping \(A\) defined on a complete metric space \(R\) has a unique fixed point.

*Proof*

Keep contracting, i.e. applying \(A\).

**Theorem 1’**

Given a continuous mapping of a complete metric space \(R\) onto itself, suppose \(A^n\) is a contraction mapping (\(n\) an integer \(>1\)). Then \(A\) has a unique fixed point.

*Proof*

Let \(x = \lim_{x \rightarrow \infty} A^{kn} x_0\) and \(Ax = \lim_{k \rightarrow \infty} A A^{kn} x_0\). Since \(A^n\) is a contraction mapping, then \[\rho(Ax, x) = \lim_{k \rightarrow \infty} \rho(AA^{kn}x_0, A^{kn} x_0) = 0\] i.e. \(Ax = x\) so \(x\) is a fixed point of \(A\). Has to be unique, otherwise \(A^n\) also has multiple fixed points, which is impossible by Theorem 1 since \(A^n\) is a contraction mapping.

**Note** The most interesting applications of Theorems 1 and 1’ arise when the
space \(R\) is a function space. Below we find out the conditions for when a
solution for initial value problems exist (and is unique).

**Theorem 2** (Picard, also known as Picard–Lindelöf)

Given a function \(f(x,y)\) defined and continuous on a plane domain \(G\) containing the point \((x_0, y_0)\), suppose \(f\) satisfies a Lipschitz condition of the form \[|f(x,y) - f(x,\tilde{y})| \leq M |y - \tilde{y}|\] in the variable \(y\). Then there is an interval \(|x - x_0| \leq \delta\) in which the differential equation \[\frac{dy}{dx} = f (x, y)\] has a unique solution \[y = \phi(x)\] satisfying the initial conditions \[\phi(x_0) = y_{0}\]

**Theorem 2’**

Given \(n\) functions \(f_i (x, y_1, \ldots, y_n)\) defined and continuous on an \((n+1)\)-dimensional domain \(G\) containing the point \[(x_n, y_{01}, \ldots, y_{0n})\] suppose each \(f_i\) satisfies a Lipschitz condition of the form \[|f_i(x, y_1, \ldots, y_n) - f_i(x, \tilde{y}_1, \ldots, \tilde{y}_n)| \leq M \max_{1 \leq i \leq n} |y_i - \tilde{y}_i|\] in the variables \(y_1, \ldots, y_n\). Then there is an interval \(|x - x_i| \leq \delta\) in which the system of differential equations \[\frac{dy_i}{dx} = f_i (x, y_1, \ldots, y_n) \quad (i = 1, \ldots, n)\] has a unique solution \[y_1 = \phi_1(x), \ldots, y_n = \phi_n(x)\] satisfying the initial conditions \[\phi_1(x_0) = y_{01}, \ldots, \phi_n(x_0) = y_{0n}\]

**For additional information**
Check out libretext or these notes by Denise Gutermuth from the University of
Berkeley.

**Note**
Now show the method of successive approximations can be used to prove the
existence and uniqueness of solutions of two kinds of integral equations:
Fredholm and Volterra.

**Example 1**
A *Fredholm equation (of the second kind)* is an integral equation of the form
\[f(x) = \lambda \int_b^a K(x, y) f(y) dy + \phi(x)\]
involving two given functions \(K\) and \(\phi\), an unknown function \(f\) and an
arbitrary parameter \(\lambda\).

**Example 2**
A *Volterra equation*
\[f(x) = \lambda \int_b^x K(x, y) f(y) dy + \phi(x)\]
differs from the Fredholm equation by having the variable \(x\) rather than the
fixed number \(b\) as the upper limit of integration.

## Problems

Let \(A\) be a mapping of a metric space \(R\) into itself. Prove the condition \[\rho(Ax, Ay) < \rho(x, y) \quad (x \neq y)\] is insufficient for the existence of a fixed point of f\(A\).

Let \(R\) be \((0, 1)\) and \(A = \frac{1}{2}\), then fixed point would be \(0\), but \(0 \notin R\). Need \(R\) to be complete.

Let \(F(x)\) be a continuously differentiable function on the interval \([a, b]\) such that \(F(a) < 0\), \(F(b)> 0\) and \[0 < K_1 \leq F^\prime(x) \leq K_2 (a \leq x \leq b)\] Use Theorem 1 to find the unique root of the equation \(F(x) = 0\)

*Hint.*Introduce the auxiliary function \(f(x) = x - \lambda F(x)\), and choose \(\lambda\) such that the theorem works for the equivalent equation \(f(x) = x\).\[f(x) = x - \lambda F(x) \quad f^\prime(x) = 1 - \lambda F^\prime(x)\] Select λ so that \(|f^\prime(x)| = |1 - \lambda F^\prime(x)| < 1\), whenever \(\lambda F^\prime(x) < 1\) since \(F^\prime(x)\) is strictly positive. Can do this by setting \(\lambda = \frac{1}{K_1 + K_2}\) since \[\lambda F^\prime(x) \leq \lambda K_2 = \frac{K_2}{K_1 + K_2} < 1\] By Theorem 1, \(f\) has a fixed point \(x_0 \in [a, b]\) such that \(f(x_0) = x_0\), which means \(\lambda F(x_0) = 0\), and \(x_0\) is the unique root of \(F(x) = 0\).

Devise a proof of the implicit function theorem based on the use of the fixed point theorem.

Don’t know what the implicit function theorem is.

**TODO.**Prove that the method of successive approximations can be used to solve the system \[x_i = \sum_{j=1}^n a_{ij}x_j + b_i\] if \(|a_{ij}| < \frac{1}{n}\) (for all \(i\) and \(j\)), but not if \(|a_{ij}| = \frac{1}{n}\).

Easy.

Prove that the condition \(\sum_{j=1}^n|a_{ij}| \leq \alpha < 1\) is sufficient for the mapping \(y_i = \sum_{j=1}^n a_{ij}x_j + b_i\) to be a contraction mapping in the space \(R_0^n\).

Easy.

Prove that any of the \(n\)-dimensional contraction mapping conditions imply \[\det\left(\begin{matrix} a_{11}-1 & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22}-1 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn}-1 \\ \end{matrix}\right) \not= 0\]

If one of the conditions is satisfied, then \[Ax = x \implies Ax - x = 0 \implies (A - I)x = 0\] meaning that \(A - I\) has rank \(n\) and is thus invertible and therefore has a nonzero determinant.

Consider the nonlinear integral equation \[f(x) = \lambda\int_a^b K(x, y; f(y)) dy + \psi(x)\] with continuous \(K\) and \(\psi\), where \(K\) satisfies a Lipschitz condition of the form \[|K(x, y; z_1) - K(x, y; z_2)| \leq M|z_1 - z_2|\] in its ‘functional’ argument. Prove that the equation has a unique solution for all \[|\lambda| < \dfrac{1}{M(b-a)}\] Write the successive approximations to this solution.

Tweak the method used for Fredholm’s equation.