非精确压缩映射——容错执行器下的收敛

上级：analysis

精确的 Banach 迭代假设每一步都被完美地执行；如果每一步都由一个容错求解器执行、误差不超过 $\varepsilon$，会发生什么？答案是：你依然会收敛——但收敛到的是半径为 $\varepsilon/(1-k)$ 的一个球，而不是那个点本身。

压缩映射

设 $(X, d)$ 是一个度量空间，$T : X \to X$ 是一个映射。若存在 $0 \le k < 1$，使得

$$d(Tx, Ty) \le k \, d(x, y) \quad \text{for all } x, y \in X.$$

则称 T 是一个因子为 k 的压缩映射。 Banach 不动点定理： T 存在唯一的不动点 $x^* = Tx^*$，且精确迭代 $x_{n+1} = T(x_n)$ 都以几何速度收敛到 $x^*$（从任意起点 $x_0$ 出发）：

$$d(x_n, x^*) \le k^n d(x_0, x^*).$$

非精确迭代

非精确迭代是指一个序列 $(x_n)$，满足

$$d(x_{n+1}, T(x_n)) \le \varepsilon$$

对所有 n 成立——即每一步落点与 T 本该给出的落点之间的偏差不超过 $\varepsilon$。真正的压缩映射 T 并未被调用；取而代之的是一个容错的执行者（例如一个 LLM、一个近似求解器），它只需满足这一距离约束，就能产生 $x_{n+1}$。

非精确压缩

设 $(x_n)$ 是压缩映射 T（因子 k < 1，不动点为 $x^*$）下的一个非精确迭代。则：

$$d(x_n, x^*) \;\le\; k^n d(x_0, x^*) + \varepsilon \, \frac{1-k^n}{1-k}.$$

当 $n \to \infty$ 时，迭代序列收敛到 $x^*$ 周围半径为 $\frac{\varepsilon}{1-k}$ 的球：

$$\limsup_{n \to \infty} d(x_n, x^*) \;\le\; \frac{\varepsilon}{1-k}.$$

Proof

单步： 对 $x_{n+1}$ 应用三角不等式和压缩性质：

$$d(x_{n+1}, x^*) \le d(x_{n+1}, T x_n) + d(T x_n, T x^*) \le \varepsilon + k \, d(x_n, x^*).$$

展开递推： 从 $d(x_0, x^*)$ 出发，将单步不等式反复应用 $n$ 次：

$$d(x_n, x^*) \le k \, d(x_{n-1}, x^*) + \varepsilon \le k(k \, d(x_{n-2}, x^*) + \varepsilon) + \varepsilon = k^2 d(x_{n-2}, x^*) + k\varepsilon + \varepsilon \le \cdots$$

一路展开下去：

$$d(x_n, x^*) \le k^n d(x_0, x^*) + \varepsilon(1 + k + k^2 + \cdots + k^{n-1}) = k^n d(x_0, x^*) + \varepsilon \, \frac{1-k^n}{1-k}.$$

第一项以几何速度衰减到 0。第二项则趋向 $\frac{\varepsilon}{1-k}$，且随着 $n \to \infty$ 不断增大。因为 $0 < k < 1$，所以 $1 - k^n \to 1$，于是 $\limsup_{n \to \infty} d(x_n, x^*) \le \frac{\varepsilon}{1-k}$。∎

算例：常数误差下的减半

设 $X = \mathbb{R}$，$T(x) = x/2$，于是 k = 1/2，不动点为 $x^* = 0$。假设每一步的最坏误差为 $\varepsilon = 0.1$——也就是说 $x_{n+1} = x_n/2 + 0.1$，从 $x_0 = 1$ 出发。根据定理，极限球的半径为 $\frac{0.1}{1 - 0.5} = \frac{0.1}{0.5} = 0.2$。

n	$d(x_n, 0)$	$(x_n/2) + 0.1$
0	1.0	—
1	0.6	0.6
2	0.4	0.4
3	0.3	0.3
4	0.25	0.25
5	0.225	0.225
6	0.2125	0.2125
∞	0.2	0.2

迭代序列从 1.0 逐步下降，趋向极限球 0.2 = $\frac{\varepsilon}{1-k}$，恰好落定在定理所保证的那个上界上。

读法——映射到 harness

在一个寻找不动点的收敛循环中：

• T = 循环体中一个被验证过的步骤（一个可证明地更靠近目标的函数）；
• k = 验证质量——即 recursion-convergence-contraction 中的压缩因子，衡量每个被验证的步骤能保证多少进展；
• $\varepsilon$ = 一个容错执行者的单步误差，例如被用作理论求解器的 LLM；
• $\frac{\varepsilon}{1-k}$ = 永久存在的松弛下限——目标的最终 ε 邻域，容许公差的那个球，是设计容差的一个实例。

放大因子 $\frac{1}{1-k}$ 是关键：当 k 趋近于 1（验证很弱，几乎没有压缩性）时，同样大小的单步松弛 $\varepsilon$ 在极限处会被灾难性地放大。例如在 k = 0.9 时，每一单位的 $\varepsilon$ 会变成 10 单位的最终误差；在 k = 0.99 时则会变成 100 单位。

非压缩的毒性

没有压缩性——也就是说，若 k ≥ 1——同样的单步递推式只能给出

$$d(x_n, x^*) \le d(x_0, x^*) + n\varepsilon,$$

误差线性累积，永远不会稳定下来。更糟的是，若 k > 1，误差会呈指数增长。所以，放宽每一步（允许最多 $\varepsilon$ 的误差）只有在配合强压缩性时才是安全的。没有压缩性的容差就是漂移：你买到的不过是系统性失败的许可。序理论中与 Banach 压缩映射对应的精确表亲，见 kleene-fixed-point。