度量空间

它说明距离函数本身对每个变量都是利普希茨连续的(常数为1),这正是能安全地对距离取极限的原因。

第一步 — 两次应用三角不等式。由(M3),$d(x,z) \le d(x,y) + d(y,z)$,整理得 $d(x,z) - d(y,z) \le d(x,y)$。在同一公理中交换 $x$ 与 $y$ 的角色,得 $d(y,z) \le d(y,x) + d(x,z) = d(x,y) + d(x,z)$(利用对称性 $d(y,x)=d(x,y)$),整理得 $d(y,z) - d(x,z) \le d(x,y)$,即 $-(d(x,z)-d(y,z)) \le d(x,y)$。

第二步 — 合并两个界。这两个不等式同时说明 $d(x,z)-d(y,z) \le d(x,y)$ 与 $-(d(x,z)-d(y,z)) \le d(x,y)$,根据绝对值的定义,这恰好就是命题 $|d(x,z)-d(y,z)| \le d(x,y)$:实数 $u$ 满足 $|u| \le c$ 当且仅当 $u \le c$ 与 $-u \le c$ 同时成立。

它把存在性与唯一性问题(这个方程恰好有一个解吗?)转化为一个保证收敛的机械计算过程,并给出达到任意目标精度所需迭代次数的可预先计算的界。

第一步 — 迭代序列是柯西列。固定 $x_0 \in X$,令 $x_n = T^n(x_0)$。反复应用压缩性质,$d(x_{n+1},x_n) = d(T(x_n),T(x_{n-1})) \le q\,d(x_n,x_{n-1}) \le \dots \le q^n\,d(x_1,x_0)$。对 $m > n$,沿路径 $x_n, x_{n+1}, \dots, x_m$ 应用三角不等式相连:$d(x_m,x_n) \le \sum_{k=n}^{m-1} d(x_{k+1},x_k) \le \sum_{k=n}^{m-1} q^k\,d(x_1,x_0) \le d(x_1,x_0)\sum_{k=n}^{\infty} q^k = d(x_1,x_0)\,\dfrac{q^n}{1-q}$,其中利用了 $0 \le q < 1$ 时的几何级数公式。当 $n \to \infty$ 时 $q^n \to 0$,故此尾项界趋于0:$(x_n)$ 是柯西列。

第二步 — 完备性给出极限,连续性使其成为不动点。由于 $X$ 完备,柯西列 $(x_n)$ 收敛于某个 $x^* \in X$。压缩不等式 $d(T(x),T(y)) \le q\,d(x,y)$ 说明 $T$ 是(利普希茨)连续的,因此 $T(x^*) = T(\lim_n x_n) = \lim_n T(x_n) = \lim_n x_{n+1} = x^*$。故 $x^*$ 是不动点。

第三步 — 唯一性。设 $x^*$ 与 $y^*$ 都是不动点。则 $d(x^*,y^*) = d(T(x^*),T(y^*)) \le q\,d(x^*,y^*)$,故 $(1-q)\,d(x^*,y^*) \le 0$。因 $1-q>0$,这迫使 $d(x^*,y^*)=0$,即 $x^*=y^*$。

第四步 — 误差界。在第一步的估计 $d(x_m,x_n) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$ 中令 $m \to \infty$,并利用 $d$ 的连续性,恰好得到 $d(x_n,x^*) \le \dfrac{q^n}{1-q}\,d(x_1,x_0)$:第 $n$ 步后到真实不动点的距离按几何速度缩小,且该界可以在运行任何一次迭代之前就计算出来。