函数迭代是数学中一个非常重要和有趣的主题，它在不同的领域有着不同的应用和着眼点。在动力系统中，函数迭代可以揭示复杂系统的演化规律和混沌现象；在计算数学中，函数迭代可以求解各种非线性方程和优化问题。关于动力系统和混沌领域里的迭代函数，《返朴》之前已刊发数篇相关文章，本文则是从计算数学的角度，重新向读者介绍函数迭代的基本内容。
撰文 | 丁玖（美国南密西西比大学数学系教授）
1
我在最近撰写的《这么说迭代，你一定能懂》以及几篇后续文章中，介绍了函数迭代的基本概念，展示了倍周期分叉的美妙图形，历经了周期三点引爆出的“天下大乱”，并运用高中代数、大学初等微积分加上几何图形的直观，帮助读者理解从有序到混沌沿途各种现象之“所以然”，从中领略数学推理在发现自然规律的过程中的奇妙作用。
然而，上述几篇数学科普文章的立足点位于“动力系统”的地盘，或更具体地说是在它的子领域“离散动力系统”。离散动力系统这门学科的主要任务就是研究“函数迭代”。自然，这里的“函数”是在最广泛的意义上理解的，即它的定义域可以是任何“空间”——带有某个数学结构的一类集合。当然，最简单的空间就是实数轴上的单位区间或坐标平面上的单位圆周，即便对于这样“简单”的空间所对应的“一维离散动力系统”，其主题却可以写成一本有五百页的大书，需要的数学语言来自分析、拓扑、几何、代数等几乎所有现代数学的分支。
在离散动力系统的范围谈论函数迭代，讨论的重点是不动点和周期点的稳定性问题，探索的目光聚焦在迭代点轨道的最终性态，而混沌学家则更感兴趣于最终走向不可预测的不规则行为，并由此进一步用概率统计的工具研究所有这些行踪诡异的轨道的整体性质。这些都是我在前几篇文章中试图向读者介绍的基本概念和知识。
然而，在出发点和目的性完全不一样的另一个极其有用的数学领域——计算数学里，“函数迭代”同样扮演着不可或缺的角色。“计算数学”，顾名思义，就是以计算为特征的数学，它设计可行、快速、有效、稳定的算法，通过电子计算机的程序实现，数值求解科学技术中建立起来的各类方程：常微分方程、偏微分方程、积分方程或一般的算子方程。离散化这些“连续性方程”就得到线性或非线性的代数方程组，求解这些方程组的一个主要方法就是“迭代法”。
与离散动力系统研究函数迭代的多重目的不太一样的是，计算数学研究迭代的目标很一致：寻求迭代轨道的收敛性及其速率。为此，计算数学领域里的学者谈到迭代时对周期点几乎是“冷若冰霜”的，因为它导致迭代法不收敛，这不是计算数学家和工程学家所乐见的。所以当我们从计算数学的观点看函数迭代时，我们的注意力只需放在迭代轨道收敛性这点上。
四十一年前，我在南京大学数学系修读计算数学最优化理论与方法硕士研究生的第一门专业基础课是“非线性方程组的迭代解”，选用的教材是马里兰大学数学系James M. Ortega和Werner C. Rheinboldt 于1970年出版的Iterative Solution of Nonlinear Equations in Several Variables（多变元非线性方程的迭代解），分两学期学完。第一学期由老师讲授课程，第二学期由学生分章报告，我们的收获很大，我甚至做了书中全部习题。五年后，在密歇根州立大学读博士学位的课程时，由于修了李天岩教授一门“[0, 1]上的遍历理论”学年课程，我对离散动力系统中的“函数迭代”产生了兴趣，第二年写的博士论文居然与计算遍历理论挂上了钩。可以说，在我求学成长的岁月中，我先后戴着计算数学和动力系统的面具，学过两次“函数的迭代”。
学过的知识有用，就没有白学。这两种“函数迭代”的理论都对我的研究论文有过贡献，所以算是做到了“学以致用”。但是现在的我多了一个想法：将自己年轻时代学来的有用知识服务于公众，传播更多的数学真理。在这篇文章里，我将向对科学计算感兴趣的人介绍迭代法背后的基本思想。与往常一样，我们主要考虑区间函数的简单情形，方便大家理解。
2
3
4
那么，有名闻遐迩且至少具有超线性收敛的迭代法吗？当然有，而且只需要初等微分学中的泰勒公式就可以构造出许多更高收敛阶的迭代法。然而一般而言，如同俗语所述，“一分耕耘一分收获”，要获得高阶的迭代法，成本也是可观的，计算数学中的“成本”是用“计算工作量”来衡量的。不过，我们几乎都听过一个大名鼎鼎的迭代法，甚至和它常打交道，这就是名字挂的是“牛顿”但实际上应该是“辛普森”的“牛顿迭代法”。为何它应该易名为“辛普森迭代法”，可见我的师兄弟曾钟刚教授和我合写的科普文章《牛顿迭代法传奇（上）：张冠李戴的命名》。
5
到目前为止讲到的迭代收敛都是局部性的，那怎么扩大保证收敛的初始点范围呢？当然，有不少途径，其中一个十分简单，但对导数的要求却颇为苛刻。既然简单，便适合在这里提及。应用这个方法需满足的条件是：将定义域区间[a, b]映到自身的迭代函数G有一个不动点x*，且导数处处存在并满足不等式|G’(x)| ≤ r，其中r为小于1的一个正数。
如果我们再看一次证明就会发现，施加于导数的要求事实上是为了实现不等式
|G(x) – G(x*)| ≤ r |x – x*|，任给定义域[a, b]中的点x。
只要这个不等式满足，该迭代法对任意初始点都会收敛。然而该不等式并不要求G必须可导，甚至也不需要G在x ≠ x*处连续。当然，用于迭代的函数一般都是至少连续的，所以可以将上述不等式中的特殊点x*改为与x有同等地位的y，即
|G(x) – G(y)| ≤ r |x – y|，任给闭区间[a, b]中的点x和y，
其中G将[a, b]映到自身，且0 < r < 1。满足这些条件的G称为在区间[a, b]上是压缩的。区间上的压缩函数是处处连续的，但不一定处处可导。压缩函数一定存在不动点，因为这是“压缩”性质的一个直接推论，证明的基本思想来自公比绝对值小于1的等比级数的收敛性和实数的完备性这两个事实，细说如下：
这是计算数学家和工程师最爱看到的结果。
更进一步，压缩函数不仅有不动点，而且仅有一个不动点，因为如果有相异不动点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和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)。
既然闭区间是我们大学时代就熟悉的一个代表性完备距离空间，上面关于压缩函数的不动点定理的全部证明，只要将绝对值符号改为距离符号，完全就可以移植为巴拿赫不动点定理的证明，读者可以自行写出这一证明。巴拿赫不动点定理的一个标准应用是常微分方程初值问题解的存在唯一性定理证明，这时初值问题的解被表达成将连续函数映成连续函数的某个积分算子的不动点，这里定义在某个闭区间[a, b]上的所有连续函数全体构成一个距离空间，它的距离函数定义为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日星期四美国哈蒂斯堡夏日山庄
本文受科普中国·星空计划项目扶持
出品：中国科协科普部
监制：中国科学技术出版社有限公司、北京中科星河文化传媒有限公司
特 别 提 示
1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。
2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
版权说明：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。
扫码下载APP
科普中国APP
科普中国
科普中国
京公网安备11010202008423号