巴拿赫不動點定理

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

定理

設(X, d)為非空的完備度量空間。設T : X → X為X上的一個壓縮映射，也就是說，存在一個非負的實數q < 1，使得對於所有X內的x和y，都有：

${\displaystyle d(T(x),T(y))\leq q\cdot d(x,y)}$

那麼映射T在X內有且只有一個不動點x^*（這就是說，Tx^* = x^*）。更進一步，這個不動點可以用以下的方法來求出：從X內的任意一個元素x₀開始，定義一個迭代序列x_n = Tx_n-1，其中n = 1，2，3，……。那麼，這個序列收斂，極限為x^*。以下的不等式描述了收斂的速率：

${\displaystyle d(x^{*},x_{n})\leq {\frac {q^{n}}{1-q}}d(x_{1},x_{0}).}$

等價地：

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

且

${\displaystyle 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的一個元素。

證明

選擇任何${\displaystyle x_{0}\in (X,d)}$。如果${\displaystyle Tx_{0}=x_{0}}$，則不必證明；以下設${\displaystyle x_{1}=Tx_{0}\neq x_{0}}$。對於每一個${\displaystyle n\in \{2,\ldots \}}$，定義${\displaystyle x_{n}=Tx_{n-1}\,\!}$。我們聲稱對於所有的${\displaystyle n\in \{1,2,\dots \}}$，以下等式都成立：

${\displaystyle d(x_{n+1},x_{n})\leq q^{n}d(x_{1},x_{0})}$。

我們用數學歸納法來證明。對於${\displaystyle n=1\,\!}$的情況，命題是成立的，這是因為：

${\displaystyle d(x_{1+1},x_{1})=d(x_{2},x_{1})=d(Tx_{1},Tx_{0})\leq qd(x_{1},x_{0})}$。

假設命題對於某個${\displaystyle k\in \{1,2,\ldots \}}$是成立的。那麼，我們有：

${\displaystyle d(x_{(k+1)+1},x_{k+1})\,\!}$	${\displaystyle =d(x_{k+2},x_{k+1})\,\!}$
	${\displaystyle =d(Tx_{k+1},Tx_{k})\,\!}$
	${\displaystyle \leq qd(x_{k+1},x_{k})}$
	${\displaystyle \leq q\cdot q^{k}d(x_{1},x_{0})}$
	${\displaystyle =q^{k+1}d(x_{1},x_{0})\,\!}$。

從第三行到第四行，我們用到了歸納假設。根據數學歸納法原理，對於所有的${\displaystyle n\in \{1,2,\ldots \}}$，以上的命題都成立。

設${\displaystyle \epsilon >0\,\!}$。由於${\displaystyle 0\leq q<1}$，我們便可以找出一個較大的${\displaystyle N\in \{1,2,\ldots \}}$，使得：

${\displaystyle q^{N}<{\frac {\epsilon (1-q)}{d(x_{1},x_{0})}}}$。

利用以上的命題，我們便有對於任何${\displaystyle m\,\!}$，${\displaystyle n\in \{0,1,\ldots \}}$以及${\displaystyle m>n\geq N}$，都有：

${\displaystyle d\left(x_{m},x_{n}\right)}$	${\displaystyle \leq d(x_{m},x_{m-1})+d(x_{m-1},x_{m-2})+\cdots +d(x_{n+1},x_{n})}$
	${\displaystyle \leq q^{m-1}d(x_{1},x_{0})+q^{m-2}d(x_{1},x_{0})+\cdots +q^{n}d(x_{1},x_{0})}$
	${\displaystyle =d(x_{1},x_{0})q^{n}\cdot \sum _{k=0}^{m-n-1}q^{k}}$
	${\displaystyle <d(x_{1},x_{0})q^{n}\cdot \sum _{k=0}^{\infty }q^{k}}$
	${\displaystyle =d(x_{1},x_{0})q^{n}{\frac {1}{1-q}}}$
	${\displaystyle =q^{n}{\frac {d(x_{1},x_{0})}{1-q}}}$
	${\displaystyle <{\frac {\epsilon (1-q)}{d(x_{1},x_{0})}}\cdot {\frac {d(x_{1},x_{0})}{1-q}}}$
	${\displaystyle =\epsilon \,\!}$。

第一行的不等式可以從三角不等式推出；第四行的級數是一個幾何級數，其中${\displaystyle 0\leq q<1}$，因此它收斂。以上表明${\displaystyle \{x_{n}\}_{n\geq 0}}$是${\displaystyle (X,d)\,\!}$內的一個柯西序列，所以根據完備性，它是收斂的。因此設${\displaystyle x^{*}=\lim _{n\to \infty }x_{n}}$。我們作出兩個聲明：第一，${\displaystyle x^{*}\,\!}$是${\displaystyle T\,\!}$的一個不動點，也就是說，${\displaystyle Tx^{*}=x^{*}\,\!}$；第二，${\displaystyle x^{*}\,\!}$是${\displaystyle T\,\!}$在${\displaystyle (X,d)\,\!}$中的唯一的不動點。

為了證明第一個命題，我們注意到對於任何的${\displaystyle n\in \{0,1,\ldots \}}$，都有：

${\displaystyle 0\leq d(x_{n+1},Tx^{*})=d(Tx_{n},Tx^{*})\leq qd(x_{n},x^{*})}$。

由於當${\displaystyle n\to \infty }$時，${\displaystyle qd(x_{n},x^{*})\to 0}$，因此根據夾擠定理，可知${\displaystyle \lim _{n\to \infty }d(x_{n+1},Tx^{*})=0}$。這表明當${\displaystyle n\to \infty }$時，${\displaystyle x_{n}\to Tx^{*}}$。但當${\displaystyle n\to \infty }$時，${\displaystyle x_{n}\to x^{*}}$，且極限是唯一的；因此，一定是${\displaystyle x^{*}=Tx^{*}\,\!}$的情況。

為了證明第二個命題，我們假設${\displaystyle y\,\!}$也滿足${\displaystyle Ty=y\,\!}$。那麼：

${\displaystyle 0\leq d(x^{*},y)=d(Tx^{*},Ty)\leq qd(x^{*},y)}$。

由於${\displaystyle 0\leq q<1}$，因此上式意味著${\displaystyle 0\leq (1-q)d(x^{*},y)\leq 0}$，這表明${\displaystyle d(x^{*},y)=0\,\!}$，於是根據正定性，${\displaystyle x^{*}=y\,\!}$，定理得證。

逆定理

巴拿赫不動點定理有許多逆定理，以下的一個是Czesław Bessaga在1959年發現的：

設${\displaystyle f:X\rightarrow X}$為一個抽象集合的映射，使得每一個迭代f ⁿ都有一個唯一的不動點。設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^{[永久失效連結]}上巴拿赫不動點定理的證明