压缩定理和其应用

什么是压缩

压缩(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}}\).

Author

Desvl

Posted on

2019-08-04

Updated on

2022-06-26

Licensed under