再谈迭代：今天不关心混沌与周期，我只想计算
再谈迭代：今天不关心混沌与周期，我只想计算函数迭代是数学中一个非常重要和有趣的主题，它在不同的领域有着不同的应用和着眼点。在动力系统中，函数迭代可以揭示复杂系统的演化规律和混沌现象；在计算数学中，函数迭代可以求解各种非线性方程和优化问题。关于动力系统和混沌领域里的迭代函数，《返朴》之前已刊发数篇相关文章，本文则是从计算数学的角度，重新向读者介绍函数迭代的基本内容。
撰文 | 丁玖（美国南密西西比大学数学系教授）
1
我在最近撰写的《这么说迭代，你一定能懂》以及几篇后续文章中，介绍了函数迭代的基本概念，展示了倍周期分叉的美妙图形，历经了周期三点引爆出的“天下大乱”，并运用高中代数、大学初等微积分加上几何图形的直观，帮助读者理解从有序到混沌沿途各种现象之“所以然”，从中领略数学推理在发现自然规律的过程中的奇妙作用。
然而，上述几篇数学科普文章的立足点位于“动力系统”的地盘，或更具体地说是在它的子领域“离散动力系统”。离散动力系统这门学科的主要任务就是研究“函数迭代”。自然，这里的“函数”是在最广泛的意义上理解的，即它的定义域可以是任何“空间”——带有某个数学结构的一类集合。当然，最简单的空间就是实数轴上的单位区间或坐标平面上的单位圆周，即便对于这样“简单”的空间所对应的“一维离散动力系统”，其主题却可以写成一本有五百页的大书，需要的数学语言来自分析、拓扑、几何、代数等几乎所有现代数学的分支。
在离散动力系统的范围谈论函数迭代，讨论的重点是不动点和周期点的稳定性问题，探索的目光聚焦在迭代点轨道的最终性态，而混沌学家则更感兴趣于最终走向不可预测的不规则行为，并由此进一步用概率统计的工具研究所有这些行踪诡异的轨道的整体性质。这些都是我在前几篇文章中试图向读者介绍的基本概念和知识。
然而，在出发点和目的性完全不一样的另一个极其有用的数学领域——计算数学里，“函数迭代”同样扮演着不可或缺的角色。“计算数学”，顾名思义，就是以计算为特征的数学，它设计可行、快速、有效、稳定的算法，通过电子计算机的程序实现，数值求解科学技术中建立起来的各类方程：常微分方程、偏微分方程、积分方程或一般的算子方程。离散化这些“连续性方程”就得到线性或非线性的代数方程组，求解这些方程组的一个主要方法就是“迭代法”。
与离散动力系统研究函数迭代的多重目的不太一样的是，计算数学研究迭代的目标很一致：寻求迭代轨道的收敛性及其速率。为此，计算数学领域里的学者谈到迭代时对周期点几乎是“冷若冰霜”的，因为它导致迭代法不收敛，这不是计算数学家和工程学家所乐见的。所以当我们从计算数学的观点看函数迭代时，我们的注意力只需放在迭代轨道收敛性这点上。
四十一年前，我在南京大学数学系修读计算数学最优化理论与方法硕士研究生的第一门专业基础课是“非线性方程组的迭代解”，选用的教材是马里兰大学数学系 James M. Ortega 和 Werner C. Rheinboldt 于 1970 年出版的 Iterative Solution of Nonlinear Equations in Several Variables（多变元非线性方程的迭代解），分两学期学完。第一学期由老师讲授课程，第二学期由学生分章报告，我们的收获很大，我甚至做了书中全部习题。五年后，在密歇根州立大学读博士学位的课程时，由于修了李天岩教授一门“ 上的遍历理论”学年课程，我对离散动力系统中的“函数迭代”产生了兴趣，第二年写的博士论文居然与计算遍历理论挂上了钩。可以说，在我求学成长的岁月中，我先后戴着计算数学和动力系统的面具，学过两次“函数的迭代”。
学过的知识有用，就没有白学。这两种“函数迭代”的理论都对我的研究论文有过贡献，所以算是做到了“学以致用”。但是现在的我多了一个想法：将自己年轻时代学来的有用知识服务于公众，传播更多的数学真理。在这篇文章里，我将向对科学计算感兴趣的人介绍迭代法背后的基本思想。与往常一样，我们主要考虑区间函数的简单情形，方便大家理解。
2
假设 G 是定义在一个区间I上的连续函数，并将I映到自身，这样在I中取定一个初始点x0，由此出发，就可以周而复始地迭代下去得到迭代点数列
x0, x1, x2, …, xn, …，
记为 {xn} ，其中第 n 个迭代点 xn 是G在第 n-1 个迭代点 xn-1 的值，即
xn = G(xn-1) , n = 1, 2, … ;给定 x0 。
如果将 n 个 G 复合起来的复合函数记为 Gn ，则 xn = Gn(x0) 。由于函数 G 连续并将 I 映入 I ，函数 Gn 也连续且将 I 映入 I 。
计算数学家对函数迭代的基本要求是：迭代点数列 {xn} 必须收敛。在讨论这个数列何时收敛的问题前，我们先问另一个问题：假设 {xn} 确实收敛到 I 中的一点，这个极限点会有什么性质？或言之，数列 {xn} 的极限 x* 与迭代的函数 G 有什么关系？
注意我们已经假设 G 在定义域区间 I 上连续，这个信息加上初等微分学中的连续概念就提供了回答上述问话的线索。连续函数有一个基于数列的等价说法，即函数 f 在点 a 连续当且仅当任给 f 定义域内的数列 {xn} ，只要它收敛于 a ，则对应的函数值数列 {f(xn)} 收敛到 f(a) 。由迭代程式 xn = G(xn-1) 可知，两个数列 {xn} 和 {G(xn-1)} 是恒等的数列，既然 {xn} 收敛到 x* ，那么 {G(xn-1)} 也收敛到同一个极限 x* 。另一方面，由于数列 {xn-1} 和 {xn} 一样收敛到 x* ，故 G 在 x* 的连续性就推出 {G(xn-1)} 收敛到 G(x*) 。这样 x* 和 G(x*) 都是 {xn} 的极限，由收敛数列极限的唯一性，必有 x* = G(x*) 。这说明，迭代点数列 {Gn(x0)} 如果收敛到连续函数 G 的定义域中的一点，则它一定是 G 的不动点。这个命题的逆否命题可以帮助我们确认何时一个迭代点数列不可能收敛，那就是只要迭代函数 G 没有不动点。例如，如果一个人迭代自然指数函数 G(x) = e^x ，则无论他从哪一个初始点出发，迭代点数列都不会收敛，因为不动点方程 x = e^x 在实数集合里无解。
上述简单结论的一个逻辑后果是，计算数学中迭代法的目的是数值求解不动点方程 x = G(x) 。如果这个方程根本无解，那就不必构造什么迭代法求解它了，所以在研究迭代法前，要先假设 G 至少有一个不动点。但是，如果闭着眼睛随便选取初始点 x0 开始迭代，能保证 {Gn(x0)} 收敛吗？
3
我们先看一个简单的例子。设 G(x) = -x ，则 G 有唯一的不动点 0 。然而如果我们取任一非零数 x0 作为初始点迭代G，则得到一个周期为二的轨道：x0, -x0, x0, -x0, …，不收敛到 0 。对函数 G 求导数，我们发现在不动点 0 处，G 的导数值的绝对值等于 1 。如果 G(x) = 2x ，则对任一初始点 x0 ，易见 Gn(x0) = 2^n x0，故当 xn > 0 时，{Gn(x0)} 发散到正无穷大，而当 xn < 0 时，{Gn(x0)} 发散到负无穷大，都不收敛到唯一不动点 0 。注意到对这个 G ，导数在不动点 0 的值的绝对值大于 1 。
我们再看一个例子：G(x) = x – x^2 。这时 G 依然只有唯一的不动点 0 。运用《这样讲迭代，你一定能懂》中的“图像迭代法”，或通过初等微分学中的“单调收敛定理”可以严格证明：当 0 < x0 ≤ 1 时，{Gn(x0)} 收敛到不动点0，而当 x0 < 0 或 x0 > 1 时，{Gn(x0)} 发散到负无穷大。虽然 G 在不动点 0 处导数的绝对值等于 1 ，但对不动点右侧临近的初始点，迭代点数列收敛到该不动点。读者可以用几何方法画出一个连续函数 y = G(x) 的图像曲线，它与 xy-直角坐标系的对角线 y = x 相切于一点 (x*, x*) ，在切点的左侧，曲线位于对角线上方，向上弯曲；在切点的右侧，曲线位于对角线下方，向下弯曲。然后你就会发现，尽管 G 在 x* 处的导数绝对值等于 1 ，但从 x* 左右两边附近的任一初始点 x0 出发的迭代点数列 {Gn(x0)} 收敛到 x* 。
这些例子说明，在迭代函数G可求导数的前提下，当 G 在其不动点 x* 的导数绝对值等于1时，在其附近出发的迭代点数列可能收敛到 x* ，也可能不收敛到 x* ；而当 G 在不动点 x* 的导数绝对值大于 1 时，则根本不能指望迭代点数列会收敛到 x* 。因此，要想迭代法 xn = G(xn-1) 生成的数列收敛到 G 的一个不动点，我们一般需要假设 G 在这个不动点的导数绝对值严格小于 1 。虽然这个假设不是迭代法收敛的必要条件，但确实是保证收敛的一个充分条件。它的证明不难，也容易理解，但需要对导数的极限定义有透彻的理解。
许多人号称学过微积分，但可能还需要温故一下微积分学中最基础性的概念——极限，所以我们先来回忆一下函数在一点的极限的精确定义：函数 f 当自变量 x 趋向于数 a 时有极限 L ，是指对于任意给定的正数 ε ，存在正数 δ ，使得只要位于 f 定义域内的 x 减去 a 的绝对值大于 0 但又小于 δ ，其对应的函数值 f(x) 减去 L 的绝对值就会小于 ε 。用数学的符号，就是要找到 δ ，使得若不等式 0 < |x – a| < δ 成立，则不等式 |f(x) – L| < ε 也成立。
由于函数的导数是通过函数的平均变化率的极限来定义的，函数 f 在其定义域内一点a的导数 f'(a) = lim (x → a) (f(x) – f(a))/(x-a) 按照上面的 “ε-δ”语言来说就是：任给正数 ε ，存在正数 δ ，使得对 f 定义域内的所有 x ，不等式 0 < |x – a| < δ 推出不等式
|(f(x)–f(a))/(x-a) – f'(a)| <ε。
好了，我们用上面的导数定义来证明关于迭代法收敛性的一个基本定理：设想迭代函数 G 在其定义域区间内部有一个不动点 x* 并且在该点有导数。如果 |G'(x*)| < 1 ，则存在以 x* 为中点的一个小区间 (x* - δ, x* + δ) ，使得任取此区间中的一点 x0 作为初始点，迭代点数列 {Gn(x0)} 中的所有点都在同一区间内并且 lim (n → ∞) Gn(x0) = x* 。
在读懂下面的解析证明之前，不知道这个命题的读者可用图像迭代法看到迭代点的收敛性。我们现在严格证明之。首先因为 x* 位于 G 的定义域区间的内部，存在一个正数 δ0 使得区间 (x*-δ0, x*+δ0) 包含在 G 的定义域中。由假设条件，可取 ε = (1 - |G'(x*)|)/2 > 0 。对于这个正数，上述的导数定义告诉我们，存在正数 δ ≤ δ0 ，使得满足不等式 0 < |x – x*| < δ 的所有点 x 也满足不等式
|(G(x)–G(x*))/(x-x*) – G'(x*)| <(1 - |G'(x*)|)/2 。
由于 G(x*) = x* ，上式可以改写成
|(G(x)–x*)/(x-x*) – G'(x*)| <(1 - |G'(x*)|)/2。
运用代数不等式 |a| - |b| ≤ |a – b| ，就可推出 |G(x*)-x*|/|x-x*| - |G'(x*)| < (1 - |G'(x*)|)/2 。故
|G(x)-x*|/|x-x*| < |G'(x*)| + (1 - |G'(x*)|)/2 = (1 + |G'(x*)|)/2。
记 r = (1 + |G’(x*)|)/2 ，则正数 r < 1 。上面的不等式即为
|G(x)-x*| < r |x-x*| ， 任给 (x*-δ, x*+δ) 中的点 x 。
因为 r 小于 1 ，此不等式说明，当初始点 x0 属于 (x*-δ, x*+δ) 时，第一个迭代点 x1 = G(x0) 也在 (x*-δ, x*+δ) 之中，故同一不等式保证第二个迭代点 x2 = G(x1) = G2(x0) 继续落在 (x*-δ, x*+δ) 当中，且有 |x2 – x*| < r |x1 – x*| < r^2 |x0 – x*| 。推而广之，我们知道所有迭代点 xn 都在区间 (x*-δ, x*+δ) 之内，并满足不等式
|xn – x*| < r^n |x0 – x*| ，n = 1, 2, 3, … 。
因为 lim (n → ∞) r^n = 0，结论就是：迭代点数列 {xn} 趋向于 x* 。
4
我们证明了 G 在不动点 x* 的导数绝对值小于 1 是迭代法 xn = G(xn-1) , n = 1, 2, … 具有“局部收敛性”的一个绝对重要的充分条件，这里的“局部”意指当初始点充分靠近 x* 时就能获得收敛性。更进一步，这个收敛的快慢程度也与 |G'(x*)| 有关：此值越接近于 0 ，则收敛得越快。自然，最理想的值应该就是 0 了，这时的收敛速度超过了像趋向于 0 的等比数列 {r^n} 那样的“线性收敛”，所以被称为“超线性收敛”。
那么，有名闻遐迩且至少具有超线性收敛的迭代法吗？当然有，而且只需要初等微分学中的泰勒公式就可以构造出许多更高收敛阶的迭代法。然而一般而言，如同俗语所述，“一分耕耘一分收获”，要获得高阶的迭代法，成本也是可观的，计算数学中的“成本”是用“计算工作量”来衡量的。不过，我们几乎都听过一个大名鼎鼎的迭代法，甚至和它常打交道，这就是名字挂的是“牛顿”但实际上应该是“辛普森”的“牛顿迭代法”。为何它应该易名为“辛普森迭代法”，可见我的师兄弟曾钟刚教授和我合写的科普文章《牛顿迭代法传奇（上）：张冠李戴的命名》。
牛顿迭代法用于数值求解非线性方程，它的基本思想用几何表达最直观易懂。解方程 f(x) = 0 的几何意义就是找到函数 y = f(x) 的图像与 x-轴的交点。在函数 f 可求导且导数值都不为零的条件下，设 x* 是方程的一个解，但我们却不知道它是几，于是我们先取一个初始点 x0 作为 x* 的一个猜测。自然 f(x0) 一般不恰好为零。在图像上的点 (x0, f(x0)) 处作曲线的切线，根据导数的几何解释，这根切线的斜率是 f'(x0) 。由直线的点斜式方程可知，切线的方程是 y – f(x0) = f'(x0)(x – x0) ，在此方程中令 y = 0 而解出未知数 x 的值 x1 = x0 - f(x0)/f'(x0) ，它就是切线与 x-轴的交点的 x-坐标，当 x0 距离精确解 x* 不远时应该比 x0 更靠近 x* 。对 x1 重复做上面的事，得到比 x1 离 x* 更近的点 x2 。由此类推，有了下列求解方程 f(x) = 0 的牛顿迭代法：
xn = xn-1 – f(xn-1)/f'(xn-1) ，n = 1, 2, 3, … 。
如果将原方程 f(x) = 0 改写成与之等价的不动点方程 x = x – f(x)/f'(x) ，那么上述的牛顿法就是用于后一个方程的直接迭代法 xn = G(xn-1) , n = 1, 2, … , 其中 G(x) = x – f(x)/f'(x) 。为了研究牛顿法的收敛速率，我们需要假定 f 的二阶导数在 x* 存在，这样就保证了迭代函数 G 在 x* 处一阶导数的存在性。求导数的商法则给出
G'(x*) = 1 – /f'(x*)2 = f(x*)f''(x*)/f'(x*)2 = 0，
理由是 f(x*) = 0 。根据上面证明出的迭代收敛基本定理，存在以 x* 为中心的某个开区间 (x*-δ, x*+δ) ，使得只要初始点 x0 取之于它，牛顿法产生的迭代点数列 {xn} 不仅收敛到解 x* ，而且收敛速率是超线性的。事实上，在关于二阶导数稍微更强一点的条件下，牛顿迭代是二阶收敛的。
5
到目前为止讲到的迭代收敛都是局部性的，那怎么扩大保证收敛的初始点范围呢？当然，有不少途径，其中一个十分简单，但对导数的要求却颇为苛刻。既然简单，便适合在这里提及。应用这个方法需满足的条件是：将定义域区间 映到自身的迭代函数 G 有一个不动点 x* ，且导数处处存在并满足不等式 |G'(x)| ≤ r ，其中 r 为小于 1 的一个正数。
若条件成立，则对 中的任一初始点 x0 ，由微分学里的拉格朗日中值定理，
G(x0) – x* = G(x0) – G(x*) = G'(c)(x0 – x*)，
其中 c 是位于 x0 和 x* 之间的一个数。这样，
|G(x0) – x*| = | G'(c)(x0 – x*)| = |G'(c)| |x0 – x*| ≤ r |x0 – x*| ，
即 G(x0) 不仅位于 ，而且比 x0 更靠近 x* 。用归纳法，得到
|Gn(x0) – x*| ≤ r^n |x0 – x*| → 0 。
因此，迭代点数列 {Gn(x0)} 收敛到 x* 。
如果我们再看一次证明就会发现，施加于导数的要求事实上是为了实现不等式
|G(x) – G(x*)| ≤ r |x – x*| ，任给定义域 中的点 x 。
只要这个不等式满足，该迭代法对任意初始点都会收敛。然而该不等式并不要求 G 必须可导，甚至也不需要 G 在 x ≠ x* 处连续。当然，用于迭代的函数一般都是至少连续的，所以可以将上述不等式中的特殊点 x* 改为与 x 有同等地位的 y ，即
|G(x) – G(y)| ≤ r |x – y| ，任给闭区间 中的点 x 和 y ，
其中 G 将 映到自身，且 0 < r < 1 。满足这些条件的 G 称为在区间 上是压缩的。区间上的压缩函数是处处连续的，但不一定处处可导。压缩函数一定存在不动点，因为这是“压缩”性质的一个直接推论，证明的基本思想来自公比绝对值小于 1 的等比级数的收敛性和实数的完备性这两个事实，细说如下：
在区间 中任取一点 x0 迭代 G ，得迭代点数列 {xn} ，其中 xn = G(xn-1) = Gn(x0) 。则对任意正整数 n有
|xn+1 – xn| = |G(xn) – G(xn-1)| ≤ r |xn – xn-1| 。
累次使用上述过程，就有 |xn+1 – xn| ≤ r^n |x1 – x0| 。从而对任意自然数 p ，由代数中的三角不等式及已得的不等式，
|xn+p – xn|≤|xn+1 – xn| + |xn+2 – xn+1| + … + |xn+p – xn+p-1|
≤ (1 + r + … + r^p) |xn+1 – xn| ≤ r^n |x1 – x0|/(1-r)。
既然 lim (n → ∞) r^n = 0 ，上式右端数列的极限为 0 ，说明 {xn} 是一个柯西数列，即双下标数列 {|xm – xn|} 当 m 和 n 都趋于无穷大时的极限为 0 。因为在实数集内，任何柯西数列都是收敛的，故极限 lim (n → ∞) xn = x* 存在。由于对所有 n 都有 a ≤ xn ≤ b ，极限 x* 属于 ；由于 G 处处连续，x* 是 G 的不动点。如果在几行之上的不等式中取 p → ∞ 时的极限，我们还可以得出迭代到第 n 步后的“误差估计”：
|x* – xn|≤r^n |x1 – x0|/(1-r)，
这是计算数学家和工程师最爱看到的结果。
更进一步，压缩函数不仅有不动点，而且仅有一个不动点，因为如果有相异不动点 x* 和 y* 的话，则 |x*- y*| = |G(x*) – G(y*)| ≤ r |x* - y*| ，因为 x* - y* ≠ 0 及 r < 1 ，这个不等式是不可能的。这个唯一性是许多其他著名的不动点定理如“布劳威尔不动点定理”所缺乏的，一维的布劳威尔不动点定理本质上就是微分学里的介值定理，它只要求函数连续，所以少了一点限制条件，不动点的个数就有可能大于一。这和家长对孩子读书的框框条条效果类似，限制越多，自由越少，子女今后的成就也就可能越少。
6
在数学上，“唯一性”是很重要的一条性质，因此压缩函数的概念被抽象成泛函分析中所谓“距离空间”内的“压缩映射”。这门学科的集大成者、波兰利沃夫数学学派的领袖巴拿赫 (Stefan Banach，1892-1945)，在他进入而立之年时，提出了一个“压缩映射定理”，现在该定理又以它的创立者命名为：巴拿赫不动点定理。其专业性陈述是这样的：
令 (X, d) 为一个完备的距离空间。若 G: X → X 为一压缩映射，即存在小于 1 的一个数 r ，使得
d(G(x), G(y)) ≤ r d(x, y)
对 X 中所有的元素 x 和 y 都成立，则 G 有并只有一个不动点 x* ，且从 X 中任一初始点 x0 出发的迭代点列 {Gn(x0)} 收敛到 x* ，其第 n 个迭代点的逼近上界为
d(x*, xn) ≤ r^n d(x1, x0)/(1-r)。
这几个抽象术语自然需要解释，但只要发现上面定理的内容，包括条件结论中的两个不等式，与之前实变量的压缩函数几乎是一个模式，就会知道巴拿赫不动点定理理解起来一点也不难。这也充分说明任何抽象理论都源自简单的具体模型。
首先，什么是距离空间？“距离”是我们日常生活中司空见惯的几何概念，这个量不能为负，与度量距离的两点次序无关，而且两点之间的距离为零当且仅当这两点重合。距离还有一个关键的性质：北京和南京之间的距离肯定不大于北京和扬州的距离加上扬州和南京的距离。据说这个被称为“三角不等式”的性质连聪明的狗都可透彻理解，否则它们一见主人就不会沿着人狗连线的方向直奔而来。显而易见，实数轴上两点 x 和 y 之间的距离等于非负数 |x – y| ，用符号 d(x, y) 表示，其中“d”是距离的英文单词 distance 的首字母。这样我们可以将任意一个实数的集合 A ，比如一个区间，连同这个距离 d 组成的“二元组” (A, d) 称为距离空间。同样，任意抽象集合 X 连同一个定义在其上的距离函数 d ，合起来的 (X, d) 就称为一个距离空间，其中距离函数 d 满足通常名词距离对于我们已经习以为常的如下性质：对 X 中任意的元素 x, y, z，
(1) d(x, y) ≥ 0 且 d(x, y) = 0 当且仅当 x = y ；
(2) d(x, y) = d(y, x) ；
(3) d(x, y) ≤ d(x, z) + d(z, y) 。
其次，什么叫“完备”的距离空间？在微积分中用两数 x 和 y 之间的通常距离 |x – y| 可以定义数列的收敛性：数列 {xn} 收敛到数 x ，假如距离数列 {|xn – x|} 当 n 趋于无穷大时趋向于 0 。用完全同样的方式可以定义距离空间 (X, d) 中元素序列的收敛性：我们说 X 中的序列 {xn} 收敛到 X 的一个元素 x ，如果距离数列 {d(xn, x)} 当 n 趋于无穷大时趋向于 0 。类似地，实数集合中的柯西数列也可直接推广到距离空间中的序列：X 中的序列 {xn} 被称为是柯西序列，若双指标数列 {d(xm, xn)} 当 m 和 n 都趋于无穷大时趋向于 0 。我们知道在实数中任何柯西数列都有极限，但并非每一个距离空间都有这一性质，就像有理数组成的柯西数列不一定收敛到有理数那样。如果一个距离空间 (X, d) 中的每一个柯西序列都有极限，那么 (X, d) 称为是完备的。
既然闭区间是我们大学时代就熟悉的一个代表性完备距离空间，上面关于压缩函数的不动点定理的全部证明，只要将绝对值符号改为距离符号，完全就可以移植为巴拿赫不动点定理的证明，读者可以自行写出这一证明。巴拿赫不动点定理的一个标准应用是常微分方程初值问题解的存在唯一性定理证明，这时初值问题的解被表达成将连续函数映成连续函数的某个积分算子的不动点，这里定义在某个闭区间 上的所有连续函数全体构成一个距离空间，它的距离函数定义为 d(f, g) = max{|f(x) – g(x)|: a ≤ x ≤ b}。
7
再回到牛顿迭代法，我们已知它总是局部收敛的，但如果初始点取得距离方程 f(x) = 0 的解 x* 太远了，那会有什么结果？牛顿法非局部的收敛性问题是一门大学问，苏联数学家康特诺维奇 (Leonid Kantorovich，1912-1988) 于上世纪中叶发展了半局部收敛理论，在 James M. Ortega和Werner C. Rheinboldt 的那本名著中有详细的讨论。该理论的特点是，即便初始点没能选在保证局部收敛的局部收敛域内，只要某些关键不等式被满足，就能保证迭代点的序列收敛到方程的解。自然，许多初始点却满足不了这些条件，容易构造一个例子，在许多点出发的牛顿迭代数列发散，如下图所示。
事实上，让牛顿法不收敛的那些初始点可以形成复杂无比的点集。上世纪 80 年代的某个学期，康奈尔大学数学教授哈伯德 (John Hubbard，1945-) 在法国一所大学度学术假，同时给一年级新生讲授一门微积分课程。有次他灵光一闪，将自己从事的一部分事业——复离散动力系统——和计算数学中古老的牛顿法联系在一起。复离散动力系统，顾名思义，就是迭代复变函数看看最终走向如何。
中学生就已经知道像 2 + 3 i 这样的复数是什么，这是几百年前为了迎合求解二次方程 x^2 + 1 = 0 的需要不得不创造出来的“虚无缥缈”之数。这“由实数到虚数”的一个大跳，解决了许多数学大问题，例如代数基本定理——在复数范围内，每个代数方程都有根。复动力系统和分形几何这两门当代学科紧密相连。
教授了太多次微积分课本里介绍的牛顿法，有点厌倦标准教法的哈伯德想换一换花样。他把目光转向在复数平面上用牛顿法解最简单的三次方程 z^3 – 1 = 0 ，即算出 1 的三个立方根，分别是实数 1 和两个互相共轭的复数 (-1 + i√3)/2 和 (-1 - i √3)/2 。这三个根在复平面上形成一个等边三角形。任取一个复数作为初始点，他让学生们看看牛顿法将引向三个根中的哪一个。这个创造性的习题给学生铺下了一条发现之路！
自然，根据牛顿法的局部收敛性，当初始点取得靠近三根之一时，迭代点复数列将收敛到那个根。但是，哈伯德让学生用计算机编程找出复平面上哪些初始点将走到第一个根，哪些点趋向于第二个根，哪些点会导致第三个根。这三类初始点分别用三种不同的颜色区别开来。在粗糙的选点下，牛顿法迭代的最终性态果然如他所猜把平面分成三个扇形，但随着选点越来越精细，他和学生们发现这三个区域的分界线越来越不清楚：三种颜色互相缠绕，只要两种颜色靠近一些，第三种颜色便乘虚而入，挤进来夹在它们中间，就好像红黄蓝三股绳绞在一起彼此纠缠不清。这又引起一连串新的自相似的涌入，似乎没有哪个点可以分开任意两种颜色。就这样，美国数学教授哈伯德和修其课程的法国大学生们意外地发现了已经广泛使用了几百年的牛顿法所制造的分形图。
当然，这个漂亮的牛顿分形图令研究动力系统的学者兴高采烈，却令冀望算法收敛的计算数学家愁眉苦脸，因为他们看到即便像牛顿法这样优秀的迭代法，不产生收敛迭代序列的那些初始点，看上去是如此的复杂！从而，在计算数学领域，迭代法的收敛性一直是引人注目的课题。
写于 2023 年 6 月 29 日星期四
美国哈蒂斯堡夏日山庄
原创 丁玖 返朴 2023-08-08 08:02 发表于广东
页:
[1]