巴拿赫不动点定理

巴拿赫不动点定理，又称为压缩映射定理或压缩映射原理，是度量空间理论的一个重要工具。它保证了度量空间的一定自映射的不动点的存在性和唯一性，并提供了求出这些不动点的构造性方法。这个定理是以斯特凡·巴拿赫命名的，他在1922年提出了这个定理。

## 定理

设(X, d)为非空的完备度量空间。设T : X → X为X上的一个压缩映射，也就是说，存在一个非负的实数q < 1，使得对于所有X内的x和y，都有：

$$d(T(x),T(y)) \le q\cdot d(x,y)$$

那么映射T在X内有且只有一个不动点x*（这就是说，Tx* = x*）。更进一步，这个不动点可以用以下的方法来求出：从X内的任意一个元素x0开始，定义一个迭代序列xn = Txn-1，其中n = 1，2，3，……。那么，这个序列收敛，极限为x*。以下的不等式描述了收敛的速率：

$$d(x^*, x_n) \leq \frac{q^n}{1-q} d(x_1,x_0).$$

等价地：

$$d(x^*, x_{n+1}) \leq \frac{q}{1-q} d(x_{n+1},x_n)$$

且

$$d(x^*, x_{n+1}) \leq q d(x_n,x^*).$$

满足以上不等式的最小的q有时称为利普希茨常数。

注意对于所有不同的x和y都有d(Tx, Ty) < d(x, y)的要求，一般来说是不足以保证不动点的存在的，例如映射T : `[1,∞) → [1,∞)`，T(x) = x + 1/x，就没有不动点。但是，如果空间X是紧的，则这个较弱的假设也能保证不动点的存在。

当实际应用这个定理时，最艰难的部分通常是如何恰当地定义X，使T把元素从X映射到X，即Tx总是X的一个元素。

## 证明

选择任何$x_0 \in (X, d)$。如果$Tx_0=x_0$，则不必证明；以下设$x_1=Tx_0\ne x_0$。对于每一个$n \in \{2, \ldots\}$，定义$x_n = Tx_{n-1}\,\!$。我们声称对于所有的$n \in \{1, 2, \dots\}$，以下等式都成立：

$d(x_{n+1}, x_n) \leq q^n d(x_1, x_0)$。

我们用数学归纳法来证明。对于$n = 1\,\!$的情况，命题是成立的，这是因为：

$d(x_{1+1}, x_1) = d(x_2, x_1) = d(Tx_1, Tx_0) \leq qd(x_1, x_0)$。

假设命题对于某个$k \in \{1, 2, \ldots\}$是成立的。那么，我们有：

$d(x_{(k + 1) + 1}, x_{k + 1})\,\!$｜$= d(x_{k + 2}, x_{k + 1})\,\!$

$$= d(Tx_{k + 1}, Tx_k)\,\!$$ $$\leq q d(x_{k + 1}, x_k)$$ $$\leq q \cdot q^kd(x_1, x_0)$$ $= q^{k + 1}d(x_1, x_0)\,\!$。

从第三行到第四行，我们用到了归纳假设。根据数学归纳法原理，对于所有的$n \in \{1, 2, \ldots\}$，以上的命题都成立。

设$\epsilon > 0\,\!$。由于$0 \leq q < 1$，我们便可以找出一个较大的$N \in \{1, 2, \ldots\}$，使得：

$q^N < \frac{\epsilon(1-q)}{d(x_1, x_0)}$。

利用以上的命题，我们便有对于任何$m\,\!$，$n \in \{0, 1, \ldots\}$以及$m > n \geq N$，都有：

$d\left(x_m, x_n\right)$｜$\leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n)$

$$\leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0)$$ $$= d(x_1, x_0)q^n \cdot \sum_{k=0}^{m-n-1} q^k$$ $$< d(x_1, x_0)q^n \cdot \sum_{k=0}^\infty q^k$$ $$= d(x_1, x_0)q^n \frac{1}{1-q}$$ $$= q^n \frac{d(x_1, x_0)}{1-q}$$ $$< \frac{\epsilon(1-q)}{d(x_1, x_0)}\cdot\frac{d(x_1, x_0)}{1-q}$$ $= \epsilon\,\!$。

第一行的不等式可以从三角不等式推出；第四行的级数是一个几何级数，其中$0 \leq q < 1$，因此它收敛。以上表明$\{x_n\}_{n\geq 0}$是$(X, d)\,\!$内的一个柯西序列，所以根据完备性，它是收敛的。因此设$x^* = \lim_{n\to\infty} x_n$。我们作出两个声明：第一，$x^*\,\!$是$T\,\!$的一个不动点，也就是说，$Tx^* = x^*\,\!$；第二，$x^*\,\!$是$T\,\!$在$(X, d)\,\!$中的唯一的不动点。

为了证明第一个命题，我们注意到对于任何的$n \in \{0, 1, \ldots\}$，都有：

$0 \leq d(x_{n+1}, Tx^*) = d(Tx_n, Tx^*) \leq q d(x_n, x^*)$。

由于当$n \to \infty$时，$qd(x_n, x^*) \to 0$，因此根据夹挤定理，可知$\lim_{n\to\infty} d(x_{n+1}, Tx^*) = 0$。这表明当$n \to \infty$时，$x_n \to Tx^*$。但当$n \to \infty$时，$x_n \to x^*$，且极限是唯一的；因此，一定是$x^* = Tx^*\,\!$的情况。

为了证明第二个命题，我们假设$y\,\!$也满足$Ty = y\,\!$。那么：

$0 \leq d(x^*, y) = d(Tx^*, Ty) \leq q d(x^*, y)$。

由于$0 \leq q < 1$，因此上式意味着$0 \leq (1-q) d(x^*, y) \leq 0$，这表明$d(x^*, y) = 0\,\!$，于是根据正定性，$x^* = y\,\!$，定理得证。

## 逆定理

巴拿赫不动点定理有许多逆定理，以下的一个是Czesław Bessaga在1959年发现的：

设$f:X\rightarrow X$为一个抽象集合的映射，使得每一个迭代f n都有一个唯一的不动点。设q为一个实数，0 d(M(A), M(B))，也即 M(P) 是一个压缩映射。

- 事实上，取实数 k>1 作为地图比例尺的分母、即 1:k，那么由比例尺的定义知 d(A, B)=kd(M(A), M(B))，两边同除以 k 得 d(A, B)*(1/k)=d(M(A), M(B))。换言之，存在实数 q=1/k<1 满足对于 S 内所有的 A 和 B，d(M(A), M(B))≤qd(A, B)，这里等号总是成立。
- 现在将 S 视为以 d 为度量的空间，那么它显然是一个完备度量空间。
- 根据巴拿赫不动点定理，M 在 S 内有且仅有一个不动点，即该点恰好被印在它所表示的土地位置上。Q.E.D.

关于巴拿赫不动点定理的推广，请参见无穷维空间中的不动点定理。

## 参考文献

- Vasile I. Istratescu, Fixed Point Theory, An Introduction, D.Reidel, the Netherlands (1981). ISBN 90-277-1224-7 See chapter 7.
- Andrzej Granas and James Dugundji, Fixed Point Theory (2003) Springer-Verlag, New York, ISBN 0-387-00173-5.
- William A. Kirk and Brailey Sims, Handbook of Metric Fixed Point Theory (2001), Kluwer Academic, London ISBN 0-7923-7073-2.
- Bourbawiki上 巴拿赫不动点定理的证明