Skip to main content

Banach Fixed point Theorem

· 5 min read
PuQing
PuQing
AI, CVer, Pythoner, Half-stack Developer

两个例子​

落在地图上的地图

有命题：将一座公园的地图铺开在公园的地面上，则地面上恰好有唯一一点与地图上对应的点重合

设公园可以用有界的面闭区域 Ωˉ\bar{\Omega} 表示。设地图的比例是 λ\lambda (它当然介于 0 和 1 之间)。现在固定一个平面坐标系，把地图铺在区域 Ωˉ\bar{\Omega} 内（公园内），则从 Ωˉ\bar{\Omega} 内的点（物理公园中的地点）到地图上对应点的变换由下面的公式给出：

x→λRx+bx \to \lambda Rx+b

这里 RR 是一个旋转变换，bb 是一个平移向量。于是，我们要找的重合点必然满足方程：

x=λRx+b→(1−λR)x=bx = \lambda Rx+b \to (1-\lambda R)x=b

由于 ∥λR∥=λ<1\left \| \lambda R \right \|=\lambda<1，这个方程就有唯一的解

x=(1−λR)−1b=∑n=0∞λnRnb.x = (1-\lambda R)^{-1}b = \sum^{\infty}_{n=0}\lambda^nR^nb.

这就是要求的重合点

函数的迭代

在计算器中任意输入一个数，然后不断地计算它的余弦值，会得到什么结果？ image.png 上面是其中的模拟；迭代的结果越来越逼近对角线 y=xy=x 与余弦 y=cos⁡xy=\cos x 的唯一交点。验算若干数值，不难作出如下猜想：不论实数的迭代序列

xn+1=cos⁡xnx_{n+1} = \cos x_{n}

开始于哪个数，它最后都会收敛到方程 x=cos⁡xx=\cos x 的唯一实数解 x=0.739…x=0.739\dots

下面我们证明该迭代过程会收敛到唯一不动点。

定义

设 II 是一个区间，f(x)f(x) 是定义在 II 上的函数，如有 α\alpha，0<α<10<\alpha <1，使对任意 x∈I,y∈Ix \in I,y \in I 恒有

∣f(x)−f(y)∣≤α∣x−y∣\mid f(x)-f(y) \mid \le \alpha\mid x-y\mid

则称 f(x)f(x) 是 II 上的压缩函数。

^977396

定理

设 f(x)f(x) 是区间 II 到 II 中的一个压缩函数，则 f(x)f(x) 在 II 上有唯一不动点。

^1b7fa3

Proof

∀x0∈I,x1=f(x0),x2=f(x1),x3=f(x2),…,xn=f(xn−1),…\forall x_{0} \in I, x_{1}=f\left(x_{0}\right), x_{2}=f\left(x_{1}\right), x_{3}=f\left(x_{2}\right), \ldots, x_{n}=f\left(x_{n-1}\right), \ldots

则

∣x1−x2∣=∣f(x0)−f(x1)∣≤α∣x0−x1∣=α∣x0−f(x0)∣∣x2−x3∣=∣f(x1)−f(x2)∣≤α∣x1−x2∣=α2∣x0−f(x0)∣…∣xn−xn+1∣=∣f(xn−1)−f(xn)∣≤α∣xn−1−xn∣=αn−1∣x0−f(x0)∣\begin{array}{l} \left|x_{1}-x_{2}\right|=\left|f\left(x_{0}\right)-f\left(x_{1}\right)\right| \leq \alpha\left|x_{0}-x_{1}\right|=\alpha\left|x_{0}-f\left(x_{0}\right)\right| \\ \left|x_{2}-x_{3}\right|=\left|f\left(x_{1}\right)-f\left(x_{2}\right)\right| \leq \alpha\left|x_{1}-x_{2}\right|=\alpha^{2}\left|x_{0}-f\left(x_{0}\right)\right| \\ \dots \\ \left|x_{n}-x_{n+1}\right|=\left|f\left(x_{n-1}\right)-f\left(x_{n}\right)\right| \leq \alpha\left|x_{n-1}-x_{n}\right|=\alpha^{n-1}\left|x_{0}-f\left(x_{0}\right)\right| \end{array}

从而

∣xn−xn+p∣≤∣xn−xn+1∣+∣xn+1−xn+2∣+…∣xn+p−1−xn+p∣≤(αn+αn+1+…+αn+p−1)∣x0−f(x0)∣≤αn1−α∣x0−f(x0)∣\begin{array}{l} \left|x_{n}-x_{n+p}\right| \leq\left|x_{n}-x_{n+1}\right|+\left|x_{n+1}-x_{n+2}\right|+\ldots\left|x_{n+p-1}-x_{n+p}\right| \\ \leq\left(\alpha^{n}+\alpha^{n+1}+\ldots+\alpha^{n+p-1}\right)\left|x_{0}-f\left(x_{0}\right)\right| \leq \frac{\alpha^{n}}{1-\alpha}\left|x_{0}-f\left(x_{0}\right)\right| \end{array}

而由于 0<α<10<\alpha<1，因此 {xn}\{x_{n}\} 是 Cauchy 序列，设 lim⁡n→∞xn=x∗\lim_{n \to \infty}x_{n}=x^*，x∗x^* 为 f(x)f(x) 在 II 上的不动点

证明唯一性：

假设存在另一个不动点 y∗=f(y∗)y^*=f(y^*)，则

∣x∗−y∗∣=∣f(x∗)−f(y∗)∣≤α∣x∗−y∗∣\left|x^{*}-y^{*}\right|=\left|f\left(x^{*}\right)-f\left(y^{*}\right)\right| \leq \alpha\left|x^{*}-y^{*}\right|

由于 0<α<10<\alpha<1，因此 ∣x∗−y∗∣=0,x∗=y∗\mid x^*-y^*\mid=0,x^*=y^*.

□\Box

巴拿赫不动点定理​

定理

设 (X,d)(X,d) 是完备度量空间，T:X→XT:X \to X 是其上的 压缩映射，那么映射 TT 有唯一的不动点，即满足 x=Txx=Tx 的点。而且，对于任意 x0∈Xx_{0} \in X，点列 {Tnx0}n∈R\{T^nx_{0}\}_{n \in \mathbb{R}} 都收敛到这个不动点。

Proof

根据度量空间中的三角不等式，我们可以直接略过上面的递推方程，显然有：

d(Tnx0,Tn+kx0)≤∑j=1kd(Tn+j−1x0,Tn+jx0)≤∑j=1kqn+j−1d(x0,Tx0)≤qn1−qd(x0,Tx0).\begin{aligned} d\left(T^{n} x_{0}, T^{n+k} x_{0}\right) & \leq \sum_{j=1}^{k} d\left(T^{n+j-1} x_{0}, T^{n+j} x_{0}\right) \\ & \leq \sum_{j=1}^{k} q^{n+j-1} d\left(x_{0}, T x_{0}\right) \\ & \leq \frac{q^{n}}{1-q} d\left(x_{0}, T x_{0}\right) . \end{aligned}

于是点列 {Tnx0}n∈R\{T^nx_{0}\}_{n \in \mathbb{R}} 是柯西序列，在完备度量空间 XX 之中自然的收敛到某一个 x∗x^*。而这个点 x∗x^* 就是不动点，不动点的唯一性则可以由 d(Tx,Ty)≤qd(x,y)d(Tx,Ty)\le qd(x,y) 得到 (0<q<10<q<1) □\Box。

后话​

不动域

在 定理 中提到该压缩映射必须是满足这样的映射 T:X→XT:X\to X 。当实际应用这个定理时，最艰难的部分通常是如何恰当的定义 XX，使得从集合 XX 映射到 XX，即 TxTx 总是集合 XX 的元素。

“ 缓坡 ”

在 压缩映射 中我们要求任意 x,yx,y 满足：

∣f(x)−f(y)∣≤α∣x−y∣\mid f(x)-f(y) \mid \le \alpha\mid x-y\mid

其中 0<α<10<\alpha<1.

∣f(x)−f(y)∣∣x−y∣\displaystyle\frac{\mid f(x)-f(y)\mid}{\mid x-y\mid} 可以视为斜率，所以该限定条件可以视为该函数在该不动域的导数小于 1，而我们管最小的 α\alpha 称为函数 ff 的利普希茨常数。而压缩映射有时称为利普希茨映射。

参考资料​