巴拿赫不動點定理

巴拿赫不動點定理，又稱為壓縮映射定理或壓縮映射原理，是度量空間理論的一個重要工具。它保證了度量空間的一定自映射的不動點的存在性和唯一性，並提供了求出這些不動點的構造性方法。這個定理是以斯特凡·巴拿赫命名的，他在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上 巴拿赫不動點定理的證明