查看“︁巴拿赫不动点定理”︁的源代码

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

== 定理 ==

设(''X'', ''d'')为非空的[[完备度量空间]]。设''T'' : ''X'' → ''X''为''X''上的一个[[压缩映射]]，也就是说，存在一个非负的[[实数]]''q''&nbsp;<&nbsp;1，使得对于所有''X''内的''x''和''y''，都有：
:<math>d(T(x),T(y)) \le q\cdot d(x,y)</math>
那么映射''T''在''X''内有且只有一个不动点''x''<sup>*</sup>（这就是说，''Tx''<sup>*</sup> = ''x''<sup>*</sup>）。更进一步，这个不动点可以用以下的方法来求出：从''X''内的任意一个元素''x''<sub>0</sub>开始，定义一个[[迭代法|迭代]]序列''x''<sub>''n''</sub> = ''Tx''<sub>''n''-1</sub>，其中''n'' = 1，2，3，……。那么，这个序列收敛，[[极限]]为''x''<sup>*</sup>。以下的不等式描述了收敛的速率：

:<math>d(x^*, x_n) \leq \frac{q^n}{1-q} d(x_1,x_0).</math>

等价地：

:<math>d(x^*, x_{n+1}) \leq \frac{q}{1-q} d(x_{n+1},x_n)</math> 
且
:<math>d(x^*, x_{n+1}) \leq q d(x_n,x^*).</math>

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

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

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

== 证明 ==

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

::<math>d(x_{n+1}, x_n) \leq q^n d(x_1, x_0)</math>。

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

::<math>d(x_{1+1}, x_1) = d(x_2, x_1) = d(Tx_1, Tx_0) \leq qd(x_1, x_0)</math>。

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

::{|
|-
|<math>d(x_{(k + 1) + 1}, x_{k + 1})\,\!</math>
|<math>= d(x_{k + 2}, x_{k + 1})\,\!</math>
|-
|
|<math>= d(Tx_{k + 1}, Tx_k)\,\!</math>
|-
|
|<math>\leq q d(x_{k + 1}, x_k)</math>
|-
|
|<math>\leq q \cdot q^kd(x_1, x_0)</math>
|-
|
|<math>= q^{k + 1}d(x_1, x_0)\,\!</math>。
|}

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

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

::<math>q^N < \frac{\epsilon(1-q)}{d(x_1, x_0)}</math>。

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

::{|
|-
|<math>d\left(x_m, x_n\right)</math>
|<math>\leq d(x_m, x_{m-1}) + d(x_{m-1}, x_{m-2}) + \cdots + d(x_{n+1}, x_n)</math>
|-
|
|<math>\leq q^{m-1}d(x_1, x_0) + q^{m-2}d(x_1, x_0) + \cdots + q^nd(x_1, x_0)</math>
|-
|
|<math>= d(x_1, x_0)q^n \cdot \sum_{k=0}^{m-n-1} q^k</math>
|-
|
|<math>< d(x_1, x_0)q^n \cdot \sum_{k=0}^\infty q^k</math>
|-
|
|<math>= d(x_1, x_0)q^n \frac{1}{1-q}</math>
|-
|
|<math>= q^n \frac{d(x_1, x_0)}{1-q}</math>
|-
|
|<math>< \frac{\epsilon(1-q)}{d(x_1, x_0)}\cdot\frac{d(x_1, x_0)}{1-q}</math>
|-
|
|<math>= \epsilon\,\!</math>。
|}

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

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

::<math>0 \leq d(x_{n+1}, Tx^*) = d(Tx_n, Tx^*) \leq q d(x_n, x^*)</math>。

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

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

::<math>0 \leq d(x^*, y) = d(Tx^*, Ty) \leq q d(x^*, y)</math>。

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

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

设<math>f:X\rightarrow X</math>为一个抽象[[集合 (数学)|集合]]的映射，使得每一个[[迭代函数|迭代]]''f''<sup>&nbsp;n</sup>都有一个唯一的不动点。设''q''为一个实数，0 &lt; q &lt; 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.
* {{cite book
 | author     = Kirk, William A.; Khamsi, Mohamed A.
 | title      = An Introduction to Metric Spaces and Fixed Point Theory
 | year       = 2001
 | publisher  = John Wiley, New York.
 | id         = 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. 
* [http://bourbawiki.no-ip.org Bourbawiki]{{dead link|date=2017年12月 |bot=InternetArchiveBot |fix-attempted=yes }}上[https://archive.today/20121221140350/http://nfist.ist.utl.pt/~edgarc/wiki/index.php/Banach_fixed_point_theorem 巴拿赫不动点定理的证明]

[[Category:拓扑学|B]]
[[Category:不动点|B]]
[[Category:度量几何|b]]
[[Category:数学定理|B]]