压缩定理和其应用
什么是压缩
压缩(contraction)的准确描述是这样的：
取完备度量空间$X$, 度量$d$, 函数$\varphi$是$X$到本身的映射, 且满足
其中$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$:
从而会有
对于$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)=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$,
且有递推关系求证此数列收敛, 并求出极限.
在这里设$\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$时, 有
考虑到$y=bx-x^2$在$[\frac{a}{b},\frac{b}{2}]$单调递减, 而$\frac{b}{2}\geq1$, 故有 而$y(\frac{a}{b})\geq y(0)=0$,
故$x_{n+1}\geq\frac{a}{b}$.
因此不等式对所有$n>0$成立.
利用这个不等式, 得到
$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}}$.