Banach fixed-point theorem (contraction mapping principle)

An accurate map of California is spread out flat on a table in Evans Hall, in Berkeley. Prove that there is exactly one point on the map lying directly over the point it represents.

Define a sequence of positive numbers as follows. Let $x_0 > 0$ be any positive number, and let $x_{n+1} = (1+x_n)^{-1}$. Prove that this sequence converges, and find its limit.

Let $K$ be a continuous function on the unit square $0 \leq x, y \leq 1$ satisfying $\left|K(x,y)\right| < 1$ for all $x$ and $y$. Show that there is a continuous function $f(x)$ on $[0,1]$ such that we have

Can there be more than one such function $f$?

Let $g$ be a continuous real valued function on $[0,1]$. Prove that there exists a continuous real valued function $f$ on $[0,1]$ satisfying the equation

Show there is a unique continuous real valued function $f : [0,1] \to \mathbb {R}$ such that

Let $(M,d)$ be a nonempty complete metric space. Let $S$ map $M$ into $M$, and write $S^2$ for $S \circ S$; that is, $S^2(x) = S(S(x))$. Suppose that $S^2$ is a strict contraction; that is, there is a constant $\lambda < 1$ such that for all points $x, y \in M$, $d(S^2(x), S^2(y)) \leq \lambda d(x,y)$. Show that $S$ has a unique fixed point in $M$.

Let the function $f: \mathbb {R} \rightarrow \mathbb {R}$ be differentiable on $\mathbb {R}$ and satisfy $\sup_{t \in \mathbb {R}}\left|f^{\prime }(t)\right| \leqslant q < 1$. Prove that the equation $f(t) = t$ has a unique solution on $\mathbb {R}$.

Using the contraction mapping theorem, compute the limit of the sequence of continued fractions: $2 ; 2+\frac{1}{2}$; $2+\frac{1}{2+\frac{1}{2}} ; \ldots$

Let the function $f: \mathbb {R} \rightarrow \mathbb {R}$ be differentiable on $\mathbb {R}$ and satisfy $\inf_{t \in \mathbb {R}}\left|f^{\prime }(t)\right| \geqslant q > 1$. Prove that the equation $f(t) = t$ has a unique solution on $\mathbb {R}$.

Prove that the equation $x(t) = t+\varepsilon x\left(t^{\alpha }\right)$, where $\left|\varepsilon \right| < 1, \alpha > 0$, has a unique solution in the space $C[0,1]$.

Prove that the mapping $A: C[0,1] \rightarrow C[0,1], A x(t) = \lambda \int_{0}^{t} x(s) d s+1$, is a contraction for $\left|\lambda \right| < 1$, and find its fixed point.

Let, in a complete metric space $X$, the mapping $f$ be continuous and let some power $f^{p} = \underbrace{f \circ f \circ \ldots \circ f}_{p}$ of the mapping $f$ be a contraction: $\rho \left(f^{p}(x), f^{p}(y)\right) \leqslant q \rho (x, y)$, where $q < 1, x, y \in X$. Prove that the mapping $f$ has a unique fixed point in $X$: $f(x) = x$.

Does there exist an incomplete metric space in which the contraction mapping principle holds?

Construct an example of a complete metric space $X$ and a mapping $f: X \rightarrow X$ such that $\rho (f(x), f(y)) < \rho (x, y)$, but $f$ has no fixed point.

Let $(M,d)$ be a nonempty complete metric space. Let $S$ map $M$ into $M$, and write $S^{2}$ for $S \circ S$, that is, $S^{2}(x) = S(S(x))$. Suppose that $S^{2}$ is a strict contraction, that is, there is a constant $\lambda < 1$ such that for all points $x, y \in M$, $d(S^{2}(x), S^{2}(y)) \leq \lambda d(x,y)$. Show that $S$ has a unique fixed point in $M$.

Let $K$ be a continuous function on the unit square $0 \leq x, y \leq 1$ satisfying $\left|K(x,y)\right| \leq 1$ for all $x$ and $y$. Show that there is a continuous function $f(x)$ on $[0,1]$ such that we have

Can there be more than one such function $f$?

Let $A$ be the quincunx matrix given in equation (12.7) and let $d = (1,0)$. Then $f(K) = A^{-1}(K) \cup A^{-1}(K+d)$ maps $\mathcal{H}\left(\mathbb {R}^{2}\right)$ into itself, and it can be shown that $f$ is contractive with respect to the metric given in Exercise 12.5. This implies that $f$ has a unique fixed point $Q$, and given any set $K_{0} \in \mathcal{H}\left(\mathbb {R}^{2}\right)$ the iteration $K_{n+1} = f\left(K_{n}\right)$ converges to $Q$. Use this to plot the twin dragon $Q$ (take $K_{0} = \left\{ 0\right\}$).

The function $f$, defined on $\mathbb {R}$, satisfies the Lipschitz condition: there exists $k > 0$ such that for any $x_{1}, x_{2} \in \mathbb {R}$ the inequality holds

Prove that if $k < 1$, then there exists a solution of the equation $f(x) = x$, and it is the only one.

Prove the stated assertion. A contraction mapping $f: X \rightarrow X$ is uniformly continuous on $X$.

Prove the stated assertion. A contraction mapping $f$ of a complete metric space into itself has a unique fixed point, i.e., a point such that $f(x) = x$.

Prove the stated assertion. If some power of a mapping of a complete metric space into itself is a contraction mapping, then the mapping itself has a unique fixed point.

Prove the stated assertion. If the function $f(t)$ is continuous on the segment $[a ; b]$, the function $K(t ; s)$ is continuous on the square $Q = [a ; b] \times [a ; b], c = \max_{Q}\left|K(t ; s)\right|, \lambda$ is some number, and then:

Prove the stated assertion. The mapping $A(x)$ of the preceding problem, of the space $C[a ; b]$ into itself, has a unique fixed point, i.e., the equation

has, for any $\lambda$, a unique continuous solution.

Give an example of a mapping $f$ of a complete metric space $X$ into itself for which, for any two points $x \in X$, $y \in X$, the condition $\rho (f(x) ; f(y)) \leqslant \rho (x ; y)$ holds, but which has no fixed point.

In solving the equation $x=\frac{1}{x}+a$ ($a$ a positive parameter) by the iteration method, a recurrent sequence $x_{n}=\frac{1}{x_{n-1}}+a, x_{0}>0$ arises. Prove that the limit $l=\lim x_{n}$ exists, and find the asymptotics of the differences $x_{n}-l$.

Prove Banach Fixed-point Theorem (Theorem 2.3.21).

Theorem 2.3.21 (Banach Fixed-point Theorem): A contraction on a metric space has exactly one fixed point, i.e., the point $x$ such that $f(x)=x$.

Does a mapping of a metric space $X$ into itself that is Lipschitz with Lipschitz constant less than 1 necessarily have a fixed-point?

Does a mapping of a complete metric space into itself that is Lipschitz with Lipschitz constant 1 necessarily have a fixed-point?

In Euclidean space $\mathbb {R}^{n}$ consider the closed unit ball $B = \left\{ x \in \mathbb {R}^{n} \mid \left\| x\right\| \leq 1\right\}$. Let $f$ map $B$ into $B$ and be Lipschitz with Lipschitz constant 1. Without using the Brouwer Fixed-Point Theorem, show that $f$ has a fixed-point.

Let $X$ be a complete metric space containing the point $x_{0}$ and let $r$ be a positive real number. Define $K = \left\{ x \text{ in } X \mid \rho \left(x, x_{0}\right) \leq r\right\}$. Suppose that the mapping $T: K \rightarrow X$ is Lipschitz with Lipschitz constant $c$. Suppose also that $c r+\rho \left(T\left(x_{0}\right), x_{0}\right) \leq r$. Prove that $T(K) \subseteq K$ and that $T: K \rightarrow X$ has a fixed-point.

Use the Banach Contraction Principle to prove Lemma 1.

Lemma 1: Let $E$ be a Banach space and the operator $C \in \mathcal{L}(E)$ have $\left\| C\right\| < 1$. Then $\operatorname {Id} - C$ is invertible and $\left\| (\operatorname {Id} - C)^{-1}\right\| \leq (1 - \left\| C\right\| )^{-1}$.

Suppose $f$ is a real function on $(-\infty , \infty )$. Call $x$ a fixed point of $f$ if $f(x) = x$.

Let $X = (X, d)$ be a complete metric space and $T: X \rightarrow X$ a contraction, i.e., there exists $M \in [0,1)$ such that $d(Tx, Ty) \leq M d(x, y)$ for all $x, y \in X$. Theorem 6.11 (the Banach contraction mapping principle) states that there exists a unique point $x \in X$ with $Tx = x$; its proof chooses any $x_{0} \in X$ and puts $x_{1} = T x_{0}$, $x_{2} = T x_{1} = T^{2} x_{0}$, and so on, $x_{n} = T^{n} x_{0}$.

Give an inductive proof of the inequality $d\left(x_{n+1}, x_{n}\right) \leq M^{n} d\left(x_{1}, x_{0}\right)$, $n=1,2, \ldots$, and thereby complete the proof of the contraction mapping theorem.

Consider the function $f: \mathbb {R} \rightarrow \mathbb {R}$ given by

Show that $\left|f(x)-f(y)\right|<\left|x-y\right|$ for all $x$ and $y$, yet $f$ has no fixed point. Does this contradict the contraction mapping principle? Explain.

Let $(X, d)$ be a compact metric space, and $f : X \to X$ continuous. $x \in X$ is called a fixed point of $f$ if $f(x) = x$. $f$ is called a contraction if there is a number $a < 1$ such that $d(f(x), f(y)) \leq a \, d(x, y)$ for all $x, y \in X$. Show that a contraction has a unique fixed point. This result is known as the contraction mapping principle and plays a key role in analysis.