迭代是什么意思呢（这么说迭代，你一定能懂）

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

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

0.5, 0.25, 0.0625, 0.00390625, 0.0000152587890625, …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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