这么说迭代，你一定能懂

撰文 | 丁玖（美国南密西西比大学数学系教授）

迭代一词对一些人或许生疏，但在数学上它历史悠久。大约三千五百年前，古巴比伦人就想出了一个聪明的办法来逐次近似给定正数  的平方根，以今日的标准说法，它就是用众所周知的牛顿迭代法解方程 。当今，在数学天地的几乎所有园区，迭代都留下活跃的身影，而求解方程各式各样的迭代法，则是计算数学家和工程学家们从不离手的利器。

为了形象地说明什么是迭代，让我们拿出一只假设误差为零的理想计算器，输进一个数，比方说 ，然后按一下标有“”的那个平方键，小屏幕上就能看到结果：，如果再按一次平方键，看到的结果是 ，再按一次，就有 ，如此一次次地按下去，依次出现的是以“初始数” 开头的一系列数：

尽管算了这几步后我们或许会失去耐心，不想再按下去，但我们至少可以从上面几个数的变化趋势知道，这些越来越小的数最终会趋向于 。

这样的计算确实足够简单，似乎连幼儿园的孩子也能操作。即便丢掉计算器，小学生也可以用纸和笔一个接着一个地算出这样的“平方”。如果用初中学过的数学概念表达，那么计算器上的平方键就代表了“ 平方”这个函数。

上述数列中的第一个数  是我们所选定的一个初始值，第二个数  是  平方函数在  时的函数值，第三个数  是  平方函数在  时的函数值，而第四个数  是  平方函数在  时的函数值，第五个数  则是  平方函数在  时的函数值，等等。

如果把  平方函数看成是一只“黑箱”，那么输入  的值，这只黑箱就会输出  这个函数值。上面的计算器操作实际上就是选取一个初始值输进黑箱，然后再一次次地将黑箱吐出的函数值输入同一个黑箱，周而复始，直至无穷。这种“黑箱操作”的整个过程在数学上叫作函数迭代，简称迭代。

一般地，假定我们有定义在某个实数区间上的一个函数 ，它把定义域区间映到自身内——也就是说，这个函数的自变量  以及因变量  都取值于该定义域中。

这样我们就可以随心所欲、不停顿地迭代这个函数 ：取定义域中的一个初始点 ，将它代入到  的具体代数表达式中，计算出其对应的函数值，这样就得到第一个迭代点 ；因为  也属于函数的定义域，再将  代入到  的表达式中赋值，就得出第二个迭代点 ……如此进行下去，对于所有的自然数 ，在得到第  个迭代点  后，由于  属于函数的定义域，将它代入到  的表达式中计算，就得出第  个迭代点 。这样，我们获得了函数  的一个迭代点数列：

。

这个数列也称为从初始点  出发的  的迭代点轨道，或简称轨道。“轨道”是一种很形象的说法，因为起步于初始点的迭代点数列看上去就像是向远处伸展而去的一条铁路轨线。

在数学上，一个迭代过程可以写成

，。

本文开头时提到的数值求解方程  的牛顿迭代法就是一例，它具有形式

，，

其中记号  表示可微函数  的导函数。

迭代是一个从初始点出发，一步步从当前迭代点计算出后继迭代点的递归过程。所以在一般情况下，如果想知道第  个迭代点是什么，只好耐住性子算一百步后才能知道答案。然而，如果我们运气好到能“一步到位”地从  跳到 ，写出  个  的复合函数  的简洁表达式，那么就可以一步算出第  个迭代点 。可惜，令人沮丧的是，除了极少数简单情形外，比如从线性函数  立刻可以导出的简单式子 ，我们无力能将复杂的  化简到一个封闭的代数表达式。幸运的是，数学理解我们的苦衷而为我们提供了微积分的十八般武艺，这些武艺打造出一门专攻迭代的现代学科——离散动力系统。

考察迭代，就会不可避免地碰到“不动点”和“周期点”这两个重要术语。如果在函数  的定义域中有个点 ，它满足等式 ，即  在  下的迭代结果还是它本身，这个点就被称为是函数  的一个不动点。

不动点在代数上的意义就是方程  的一个解 ，而在几何上的意义是函数  在平面上 -直角坐标系中的图象与坐标系的对角线  之交点的坐标，因为这个交点既在函数  的图象上，又在坐标系的对角线上，它的两个直角坐标  同时满足  和  这两个等式。

对于一个初始点 ，如果函数  被迭代到第  步后，又首次返回到初始点 ，即从初始点  开始迭代后的第一个迭代点直到第  个迭代点 , , …,  都不等于 ，但第  个迭代点  等于 ，则称  为  的一个周期为  的周期点，其对应的有限数列  或集合  称为  的一个周期为  的周期轨道或周期- 轨道。

注意：上面的记号  并非表示  的  次方，而是表示  个  复合而成的复合映射，即 , , , ，依次类推。

显而易见，如果 ，则周期为  的周期点就是不动点。找到函数  的所有不动点等价于求出方程  的所有解，它们的几何意义就是  的图象与坐标系对角线的所有交点。当  大于  时， 的所有周期为  的周期点都是方程  的解，但反之，方程  的解却不一定是  的周期为  的周期点，而可能是  的周期为  的周期点，其中  是  的一个真因子。举个简单的例子，设 ，则 。显然  是  的一个解，但它却不是  周期为  的周期点，而是  的不动点。此外，方程  的每个非零解都是  的周期为  的周期点。

另一方面，一个周期- 轨道中的每一个点都是周期为  的周期点。比如说，如果  是一个周期- 轨道，则由 ,  及  可知， 和  都是周期- 轨道，因而组成同一个周期- 轨道的三个点  都是周期为  的周期点。从一个周期点开始的迭代点无穷数列是其周期轨道“周而复始”的无穷次复制，因此该数列的最终走向是事先知道的，或言之，是可以预测的。我们对自然界中的周期现象太熟悉不过了，所以应该对数学中的周期点感到亲切。

由上可知，当初始点是周期点时，给定的函数迭代到某一步就会首次返回到初始点，然后再重复地无限循环下去，就像一个体格健壮的学生每天早晨绕着学校的椭圆形跑道一圈又一圈地跑个不停。当初始点不是周期点时，由此点出发后的所有迭代点自然永远不会回到初始点。既然永远不会回到初始点，这些迭代点的最终性态一定会是不可预知的吗？

答案是不确定。它既可能可以预知，也可能不可预知。先看一种只需要上述简单概念而无需高深一点的初等微分学知识就能理解的情形。如果初始点不是周期点，即对任意的自然数都有不等式，但它的某次迭代点却首次成为周期点，周期为，即互不相同，但 并且对所有的，都有，那么这条迭代点轨道的最终走向还是可以预知的，亦即轨道的尾巴都是有限片段无限次的复制。这个初始点称为最终周期点；如果，最终周期点也称为最终不动点。这样从初始点启程的迭代点数列，前个点互不相同，但从开始就一个周期-轨道一个周期-轨道地重复行进下去，如此一来，这个迭代点数列的最终性态当然还是可以预测的。例如对于简单的二次函数，是一个最终不动点，因为它的第一次迭代点是的不动点。因而从最终不动点开始的轨道是。

还有一种情形，初始点既不是周期点，也不是最终周期点，即它对应的所有迭代点都互不相同，但我们依然可以预测迭代点数列的最终走向，比如说这个数列最终收敛到一个固定的数，或与一个固定的周期轨道越来越靠近，或发散到正无穷大，或发散到负无穷大，或其绝对值的数列发散到正无穷大。对这些不同状况下可预测性的分析求解，初等代数的数学工具则显得不够用了，需要一点初等微分学的知识。这就是为什么高等数学是一门很有用途的学问。具体来说，微分学中的“中值定理”或“单调收敛定理”常常是这个解析过程的数学后盾。既然本文是“浅说迭代”，我在后面将依然用浅显的语言解释其中一个定理的应用，但如果辅之以图象的视觉效应，则会帮助理解。为此，我们先介绍关于函数迭代眼睛看得更清楚的“图象表示法”，相对于前述依赖于函数赋值的“代数表示法”。

在检查迭代点数列的最终走向时，如果觉得一次又一次地用手或计算器算出函数值来得到一个又一个的迭代点太费时间，我们也可以借函数的图象来做与代数方法等价的事，只要图象曲线能够足够精确地画出。该几何方法让我们从初始点出发沿着一条上下和左右方向交替转弯的快捷路径急速地向前移动，这样就能直观地观察到迭代点列的“运动轨迹”，进而很方便地看出轨道的最终目标。

首先在平面上的xy-直角坐标系中作出函数的图象，然后在x-轴上取一个初始点，再从这个点出发，沿着y-轴的平行线朝着图象方向走，一直走到与它相交为止，在交点处向左或向右沿着x-轴的平行线走，一直走到和坐标系的对角线相交为止，这个交点的坐标为，代表着第一个迭代点。然后从这点起沿着铅锤线走，直到和图象相交，在交点处沿着水平线走，直到和对角线相交，这个交点则代表着第二个迭代点。如此这般地走下去，我们就依次得到对角线上代表着各个迭代点 的一个几何点列。

读者如果将上一段的走路加转弯法则分别用到函数和，就很容易地几何论证出下列结论：对于函数，从任一初始点出发的迭代点轨道最终将趋向于 的唯一不动点，而对于函数，从任一正的初始点出发的迭代点轨道最终将发散到正无穷大，而从任一负的初始点出发的迭代点轨道最终将发散到负无穷大。这自然和从代数表达式及得到的结论一致。第一个函数的迭代令人想起两千三百年前战国时期的学者庄子 (约公元前369-约公元前286) 已包含朴素极限思想的那句名言“一尺之捶，日取其半，万世不竭”。

更一般地，用上述的“图象迭代法”就能快速地证明：对于线性函数，只要项的系数的绝对值严格小于1，即，则以任意实数作为初始点的迭代点数列最终都将趋向于 唯一的不动点，而若，则从任意不等于的实数出发的迭代点数列最终都将发散到无穷远处。相比之下，这两个事实的分析证明则要多花一点时间了。

对于上述其直线图象相当平坦以至于斜率绝对值小于1的线性函数，因为不动点像美丽的姑娘吸引周围的男孩一样将其周围的各点吸引到自己，令从这些附近点出发的所有迭代点轨道统统最终将趋向于它，所以这个不动点被形象化地称为是吸引的。其实，不动点不光吸引了它附近的所有点，而且也吸引了实数轴上所有的点，因而它是一个全局吸引的不动点。

另一方面，当线性函数的直线图象看上去相当陡峭，以至于其斜率绝对值大于1时，由于不动点像战争狂人远离周围的和平主义者那样“排斥”了其周围与之相异的各点，令从这些点出发的迭代点数列统统最终将对它“敬而远之”而不愿与之靠近，这个不动点被称之为是排斥的，更进一步它还是全局排斥的。

由上可知，对于满足条件的任意线性函数，其唯一的不动点不是全局吸引的就是全局排斥的。一个直接的推论是该函数没有其他周期点。理由很简单，因为如果有一个周期大于1的周期点，比方说其周期为三，那么从这个周期点出发的所有迭代点总是在同一个周期-3轨道的三个点中间“轮流坐庄”，它们怎么可能会趋向于不动点或发散到无穷大？

读到这里，我相信读者们不仅读懂了其中的数学，而且还会将获得的知识用到不符合上述条件的两个剩余的线性函数和上，看一看它们各自的迭代轨道最终将走向何方。

看来既有不动点又有周期点的例子只能在非线性函数堆里去找了，好在这样的例子无穷多，随便抓来一个：。易见，还是唯一的不动点，但由于并且，这个三次多项式函数有了一个周期为2的周期轨道。

本文的读者一定能够作出的图象，然后用图象迭代法就会发现：对位于开区间内的任意一个初始点，迭代点数列将趋向于极限，故不动点是吸引的；而当初始点的绝对值大于1时，迭代点的绝对值数列将趋向于正无穷大。也就是说，的周期-2轨道排斥了它附近不等于1和-1的各个点。

上面函数的反函数则给出了周期轨道的另一个性质。对的图象进行几何迭代就会知道，不动点具有排斥性，而周期-2轨道则成为吸引的了，理由是当非零初始点的绝对值小于1或大于1时，迭代点数列都将会无限接近于这个周期-2轨道。

再一次地，上面这两个非线性函数都展示出其迭代点轨道的正规性态：对所有的初始点，迭代点数列的最终走向都是可以预测的，并且，除了唯一的不动点和两个周期为2的周期点外，它们都没有其他的周期点。我将在下一篇的科普文章中讨论既有不动点又有周期为2的更高次方的周期点的那些简单函数，并追溯它们与自然科学的一些历史因缘。

到目前为止，我还没有正式地运用过高等数学，全是用初等数学谈论迭代问题，引进基本概念，可能一部分拥有博士、硕士甚至学士学位的理工科读者感到“内容太浅”，然而正如数学写作与演讲大师、匈牙利裔的美国数学家哈尔莫斯(Paul Halmos，1916-2006)在生前一直强调的那样，越是初等的公众报告越能俘获人心。现在，我试图用一个二次多项式来示范一下初等微分学在函数迭代中的一个妙用，即便读者没有接触过微积分，那也无妨，因为我知道她或他至少懂得中学代数并具有一定的几何直觉力，而且我在之前已经保证过用浅显的语言解释数学，否则我就愧对标题中保证的“你一定能懂”五字。

我所给出的函数是，但将它的定义域限制在闭区间上。显然的图象是经过两点和、开口朝下、对称轴为、最高点为的一段抛物线，它位于坐标平面上的单位正方形内，故的值域是，因而将映到自身内。所以，从定义域区间中的任意一点出发，我们可以无限地将迭代下去。

这条抛物线与坐标系的对角线有两个交点和，换言之，有两个不动点和。我们给自己提出的问题是：从中任一初始点启程的迭代点轨迹，最后将通向何方？自然，当分别取为、或时，读者马上就知道它们对应的轨道，因为前两者是不动点，第三者是最终不动点。所以我们只需着眼于初始点为正但小于，而且不为。

当然，满心希望快速求得答案的那些人马上会想起“图象迭代法”，用铅笔尖在抛物线和对角线之间竖直线段、水平线段地画上几笔，就能获得结论：对所有的大于并且小于的初始点，由此出发的迭代点数列总是趋向于第二个不动点。然而，一位分析学家不会仅仅满足于几何直觉带来的结果，他追求的是怎样严格地证明它。

下面就是证明，除了最后一步外，前几步都属于中学代数。首先我们提请注意，如果初始点选在内，那么第一个迭代点就落到内了，之后的迭代点最终走向就与初始点选在之内没有什么两样了。基于这个观察，不失一般性，我们可以假设初始点满足。那么，故。注意即为第一个迭代点，从而。这就严格论证了为什么在开区间上，抛物线严格位于对角线的上方。显然。

第二步，我们证明在上是严格递增的。一个函数在其定义域的某个子区间上被称为是严格递增的，如果在此区间上，自变量的值变大导致因变量的值也变大。设，则及，故，即，因而。这就证明了在上的严格递增性。

第三步，我们用数学归纳法证明迭代点数列是严格单调递增的，并且总是小于。既然在上是严格递增的正函数，不等式推出不等式。假设对自然数有，则。这就证明了数列的严格单调递增性并以为一严格上界。用数学符号表示，就是：

这时，我们不得不从初等数学一跃跳上高等数学，需要的就是上文提及过的“单调收敛定理”：单调有界数列一定有极限。它的证明需要关于实数全体的“完备性公理”，此公理在美国是《高等微积分》教材的起点，在中国属于数学系的《数学分析》课程。但是我们可以用如下形象化的例子来帮助理解上述定理：设想一列有上万名士兵组成的队伍步行前进，这相当于一个单调递增的数列，如果前方永远没有障碍，这队士兵将一直走向远方，然而如果前面有一座爬不过去的城墙挡住他们，则这群保持向前走的士兵最终只能聚集在城墙脚下，这就相当于有上界的递增数列一定收敛到一点。

这样，从位于的初始点出发的迭代点数列将趋向于一个极限。但是，为什么一定就是呢？要回答这个问题，我们又得求助于在高等数学里学过的“连续性”概念了。我们说一个函数在其定义域区间中的一点连续，是指这个函数当自变量趋向于时不仅极限存在，而且极限等于它在点的函数值，这个定义可用一个数学表达式完全概括：。连续性定义还有一个等价性的数列说法，即函数在点连续当且仅当对于定义域中任一个收敛于的数列，对应的函数值数列也都收敛于同一个数。哪些函数是连续函数呢？所有的“初等函数”，即有单个代数表达式的函数，包括那些代数课本里人人熟知的多项式函数，在它们的“自然定义域”内是处处连续的，这里的二次函数为其一例，它在每一个实数点连续。

好了，我们可以快乐地用到如上的基本事实了。对所有自然数都成立的恒等式，其左右两端是一模一样的数列，故它们的极限也必定是一模一样的数。左端数列的极限从上一段已知是，而数列只是数列的“右移一位”的平移，因而它也收敛到极限，故根据上一段中关于连续性的数列说法，右端数列收敛到极限。由于收敛数列的极限是唯一的，我们便得到等式。换句话说，是的某个不动点。

然而二次多项式方程有两个解，一个是，另一个是。试问，会是不动点吗？不可能！原因是是从一个大于的数出发的递增的无穷数列的极限，这个向前推进的数列怎么可能后退收敛到比初始点还要后的呢？因此，唯一的可能是。这样，我们严格地证明了如下结论：对于定义在上的函数, 从中任意一点出发的迭代点轨道都收敛到。

事实上，我们在上面顺便证明了一个一般性的断言。我们将它作为本文的最后礼品：

命题: 若函数的一个迭代点数列收敛到，且在连续，则是的不动点。

“函数迭代”是一个内容丰富、用途宽广的数学话题，鉴于篇幅，我在本文中仅仅普及了“可以预见未来”的某些有序迭代过程。然而，从有序到无序——即混沌，更为神奇的情景还在前头，用浅显的初等语言解释背后的数学操作，将是继续讲述迭代的指导思想。