Python | 3个递推公式,100万次迭代,都收敛到同一个数——压缩映射的秘密

1. 引言

2022年5月21日，QIAN数据发了《压缩数列与Stolz定理》——一篇纯数学推导的文章。那时风格偏学术：给定义、列定理、写代码算结果。

当时是这样的：三个递推公式，100万次迭代，n×x_n都收敛到2。结果很漂亮，但文章的叙述方式偏向数学论文。

四年后回头看，这篇文章可以拆得更深。核心问题只有一个：

为什么不同的公式，n×x_n 会收敛到同一个数？

这篇文章用更直观的方式重新讲这个发现。

2. 三个递推公式

考虑三个递推公式，x₁=1：

这三个公式看起来完全不同：一个是对数、一个是根号、一个是二次函数。但它们有一个共同点。

图中画了这四个函数和 y=x 的对比。注意到什么？

所有函数在区间 [0,2] 上都满足 f(x) ≤ x，而且斜率都小于1。这意味着：

• 如果 x₁=1，下一次 x₂ = f(1) < 1
• 再下一次 x₃ = f(x₂) < x₂
• 不断迭代下去，序列一直在往下走，最终趋近于0

• 看迭代路径：

三条曲线，从x₁=1出发，50步后全部趋近于0。这就是压缩映射的核心：每次迭代都在"压缩"数值，最终收敛到不动点——对于这些函数，不动点都是 f(0)=0。

3. 真正的反直觉：n×x_n 的极限

如果序列本身收敛到0，那没什么特别的。真正有意思的是——

当这个序列以非常慢的速度趋近于0时，n×x_n 会收敛到一个常数。

来看三条曲线：

三条曲线从不同的路径逼近2.0。不是"差不多"，是完全精确地收敛到2。

100万次迭代后的精确值：

三个不同的公式，100万次迭代后，n×x_n 都收敛到2.000000。相对误差都在10⁻⁴级别，而且随着n增大还会继续缩小。

这不是巧合——是数学定理保证的。

4. 为什么一定是2？Stolz定理的解释

要理解为什么极限是2而不是其他数，需要用到 Stolz-Cesàro定理。

Stolz定理解决的是这类问题：当分子分母都趋于无穷大时，如何求比值极限。

它的核心思想是：两个数列的比值极限等于它们差分的比值极限。用公式说就是：

这不就是"离散版的洛必达法则"吗？是的——洛必达法则是求连续函数比值的极限，Stolz定理是求离散数列比值的极限。

回到我们的问题。令 a_n = 1/x_n，b_n = n。那么 n×x_n = n / (1/x_n) = b_n / a_n。

根据Stolz定理：

对 x_{n+1} = f(x_n) 做泰勒展开。以 f(x)=ln(1+x) 为例：

所以：

代入：

这就是为什么n×x_n的极限永远是2。不是某些公式的巧合，是所有满足 f(x) = x - x²/2 + O(x³) 的函数共同的极限。

5. 一个更广泛的结论

更一般地，如果函数 f 满足：

• f(0) = 0（不动点）
• f'(0) = 1（收敛速度慢——这是关键）
• f''(0) ≠ 0（展开后有一阶项）

• 那么由 x_{n+1} = f(x_n) 生成的序列一定满足：

对于我们的三个函数：

• ln(1+x)：f''(0) = -1 → 极限 = -2/(-1) = 2
• 2√(1+x)-2：f''(0) = -1 → 极限 = -2/(-1) = 2
• ½-½(x-1)²：f''(0) = -1 → 极限 = -2/(-1) = 2

所以极限一定是2。如果换一个函数使得 f''(0) = -2，极限就是1。换一个使得 f''(0) = -0.5，极限就是4。这个公式预测了一切。

6. 数学文化：从Stolz到Banach

这篇文章涉及两个重要的数学思想。

Stolz定理（1885年）是奥地利数学家Otto Stolz提出的。它在数学分析中被称为"离散版本的洛必达法则"，但它的知名度远不如洛必达法则——很多数学系学生学过微积分但没听过Stolz定理。有趣的是，Stolz本人一生都在意大利的因斯布鲁克大学教书，他的工作在德语世界广为人知，但在英语和中文世界却相对冷门。

压缩映射原理（1922年）是波兰数学家Banach在他的博士论文中提出的。它说的是：如果一个函数是"压缩"的（任意两点的距离经过函数作用后缩短了），那么从任意起点出发迭代，都会收敛到唯一的不动点。

Banach不动点定理是整个数值分析的基石之一：

• 解方程：牛顿法求根就是不动点迭代
• 解微分方程：Picard迭代
• 机器学习：梯度下降本质上也是在寻找一个不动点
• 经济学：博弈论的纳什均衡存在性证明也用到了它

• 这个定理的价值在于：它给了你一个极其强大的保证——只要f是压缩的，迭代就一定会收敛，而且无论从哪里开始都会收敛到同一个点。 这正是我们的三个函数能收敛到同一个极限的本质原因。

7. 关键要点

• 压缩映射
  ：如果 f(x) ≤ x 且斜率<1，从x₁=1开始的迭代序列递减并收敛到0
• n×x_n 收敛到常数
  ：当函数满足 f(0)=0、f'(0)=1 时，n×x_n 收敛到 -2/f''(0)
• Stolz定理
  ：离散版的洛必达法则，用来计算比值极限，数学之美在于简洁
• 通用性
  ：不是巧合，是数学定理的必然结果。三个函数的二阶导数都是-1，所以极限都是2

推荐阅读