什么是压缩

压缩(contraction)的准确描述是这样的：

取完备度量空间$X$, 度量$d$, 函数$\varphi$是$X$到本身的映射, 且满足
\[
d(\varphi(x),\varphi(y)) \leq cd(x,y).
\]
其中$x,y\in{X}$, $c<1$. 那么$\varphi$就是一个从$X$到本身的压缩.

一个最简单的例子是, $y=\frac{x}{2}$. 这是一个“平缓”的函数. 平缓的程度是怎样呢? 斜率小于1.

而压缩定理指出, 对于这个函数, 有且仅有一个$x$使得$\varphi(x)=x$. 例如上面的例子, 只有$0=0$这一个点. 接下来要给出证明.

压缩的证明

任取$x_0\in{X}$, 按照如下方法定义数列$x_n$:

\[
x_{n+1}=\varphi(x_n)
\]

从而会有

\[d(x_2,x_1)=d(\varphi(x_1),\varphi(x_0))\leq cd(x_1,x_0)\] (如果你不理解这里的$d(x,y)$,
可以简单地看成$|x-y|$) 推广下去, 就有

\[d(x_{n+1},x_n)\leq c^nd(x_1,x_0)\]

对于$n<m$, 就有 \begin{equation} \begin{aligned} d(x_n,x_m)\leq\sum_{i=n+1}^m
d(x_i,x_{i+1})\leq(c^n+c^{n+1}+\cdots+c^{m-1})d(x_1,x_0)\leq\frac{c^n}{1-c}d(x_1,x_0)
\end{aligned} \end{equation} 这说明, $x_n$是一个Cauchy数列, 又考虑到$X$是完备空间, 因此$x_n$收敛.
设$x_n$的极限为$x$. 由压缩的定义可知, $\varphi$为一致连续的函数, 从而有
\[
\varphi(x)=\lim\limits_{n\to\infty}\varphi(x_n)=\lim\limits_{n\to\infty}x_{n+1}=x
\]
至于唯一性的证明, 可设$\varphi(x)=x$, $\varphi(y)=y$.
从而有$d(\varphi(x),\varphi(y))=d(x,y)\leq cd(x,y)$ 这只有在$d(x,y)=0$时成立. 唯一性得到证明.

简单应用

下面是一道数学专业研究生入学考试题. 在这个题中可以发现, 在指定的条件下, 利用“压缩”这个工具, 问题的解决变得非常简单.

已知$0\leq a\leq 1, b \geq2$, 有数列${x_n}$ 满足$x_0=0$,
且有递推关系\[x_{n+1}=x_n-\frac{1}{b}(x_n^2-a),\]求证此数列收敛, 并求出极限.

在这里设$\phi(x)=x-\frac{1}{b}(x^2-a)$, 那么有$x_{n+1}=\varphi(x_n)$.
如果能证出$\varphi$为一个压缩, 极限的问题就迎刃而解了.

证明

设$\varphi(x)=x-\frac{1}{b}(x^2-a)$. 则$x_{n+1}=\varphi(x_n)$.
在这里$x_1=\varphi(x_0)=\frac{a}{b}$. 现证明对所有$n>0$ 有$\frac{a}{b}\leq x_n\leq 1$,
对$n$进行归纳.

$n=1$时, 不等式已成立.

假设$n=k$时成立, 则$n=k+1$时, 有 \[ x_{k+1}=\frac{a}{b}-\frac{bx_k-x_k^2}{b} \]
考虑到$y=bx-x^2$在$[\frac{a}{b},\frac{b}{2}]$单调递减, 而$\frac{b}{2}\geq1$, 故有 \[
x_{n+1}\leq\frac{a}{b} +\frac{b-1}{b}\leq 1 \] 而$y(\frac{a}{b})\geq y(0)=0$,
故$x_{n+1}\geq\frac{a}{b}$.

因此不等式对所有$n>0$成立.

利用这个不等式, 得到 \[ |f(x)-f(y)|=|x-y||1-\frac{x+y}{b}|\leq|x-y||1-\frac{2a}{b^2}|,
\quad \frac{a}{b}\leq x,y \leq 1 \]

$a=0$时, 得到$x_1=x_2=\cdots=0$, 故极限存在且为$0$.

$a\neq 0$时, 令$c=|1-\frac{2a}{b^2}|$, 则始终有$c<1$. 此时就是上文中所提到的压缩. 收敛的证明略去.

设$\lim\limits_{n\to\infty}x_n=x$, 则$x=\varphi(x)$. 解得$x=\sqrt{a}$.
这在$a=0$时也成立.

综上, $\lim\limits_{n\to\infty}x_n$存在, 且值为$\sqrt{a}$.

总结

压缩映射在处理迭代生成的数列时很有效, 而且可以推广到多维甚至无穷维中. 但是要注意, 这个映射实质上是在处理局部性质, 大范围的非线性的问题则不能处理.
处理迭代数列是它在离散形式下的基本应用, 但压缩在连续形式下也有很多重要的应用, 例如在$\mathbb{R}^n$中证明隐函数定理

关于度量

度量函数$d(x,y)$即表示两点之间的距离, 满足以下三个条件：

$d(x,y)\geq 0$, 等号成立当且仅当$x=y$.
$d(x,y)=d(y,x)$.
$d(x,y) + d(y,z) \leq d(x,z)$ (三角形不等式)

而度量空间即一个有度量函数的集合. 度量空间的完备性指, 这个空间的任意Cauchy列都收敛. 一个简单的例子是, 全体实数$\mathbb{R}$, 度量函数$d(x,y)=|x-y|$.

而$\mathbb{Q}$在这个相同的度量下是发散的. 例如Cauchy数列${\left(1+\frac{1}{n}\right)^n}$这个数列收敛到$e$, 而$e\notin{\mathbb{Q}}$.