压缩映射原理

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

## 定理

設 (_X_, _d_) 為非空的完備度量空間。設 _T_ : _X_ → _X_ 為 _X_ 上的一個壓縮映射，也就是說，存在一個非負的實數 _q_< 1，使得對於所有 _X_ 內的 _x_ 和 _y_，都有：

　
: $d(T(x),T(y))\leq q\cdot d(x,y)$

那麼映射 _T_ 在 _X_ 內有且只有一個不動點 _x_\*（這就是說，_Tx_\* = _x_\*）。更進一步，這個不動點可以用以下的方法來求出：從 _X_ 內的任意一個元素 _x_0 開始，定義一個迭代序列 _x_n = _Tx_n-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 qd(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}\neq 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 \}$ 是成立的。那麼，我們有：

　
: :

從第三行到第四行，我們用到了歸納假設。根據數學歸納法原理，對於所有的 $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$ ，都有：

　
: :

第一行的不等式可以從三角不等式推出；第四行的級數是一個幾何級數，其中 $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 qd(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 qd(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 < q < 1。那麼存在 _X_ 上的一個完備度量，使得 _f_ 是壓縮映射，且 _q_ 是壓縮常數。

## 推廣

一個有趣的事實是，若把某國的地圖縮小後印在該國領土內部，那麼在地圖上有且僅有這樣一個點，它在地圖中的位置也恰巧表示它所落在的土地位置。證明如下：

* 為了方便起見，這裡把地球近似看作是正球體。
* 首先，按照經緯度可以給地球表面上每一個點標出坐標 (x, y)，其中前元是經度、後元是緯度。又定義地面上任意兩點間的距離 d (A, B) 是 A 到 B 間大圓弧的弧長。
* 其次，把這國家的地圖上的點按照其所代表點的實際經緯度標出坐標 (u, v)。
* 那麼對於地圖上任意一點 P 而言，它既在地圖上表示地點 (up, vp)，又實際在地面上占有點 (xp, yp)。顯然，這構成了從集合 S={P|P 是地面上的點且 P 屬於該國領土} 到其本身的映射，現記作 M (P)=M ((xp, yp))=(up, vp)。
* 又因為地圖是縮小的，即對於任意兩個地點 A∈S、B∈S 而言，d (A, B)>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.
* Kirk, William A.; Khamsi, Mohamed A. An Introduction to Metric Spaces and Fixed Point Theory. John Wiley, New York. 2001. ISBN 978-0-471-41825-2.
* William A. Kirk and Brailey Sims, _Handbook of Metric Fixed Point Theory_ (2001), Kluwer Academic, London ISBN 0-7923-7073-2.
* Bourbawiki 上巴拿赫不動點定理的證明