这么说迭代，你一定能懂
加星标，才能不错过每日推送！方法见文末动图
编者按
科学传播当中有个有意思的现象，就是越为基础和艰深的学问，其相关的科普著作就越为丰富和繁多，很明显的例证就是数学、物理方面的科普读本远超其他学科，有关数学中著名的猜想和悖论、物理学中相对论和量子力学等的通俗解读可以用汗牛充栋来形容。这起码说明一点，艰涩的学问，也可以有浅显易懂的切入点。高明的科普作者可以经由作者在阐述上下的功夫降低读者理解的难度。本文就想从初等数学出发，来深入地谈谈“迭代”这一数理学问中极重要的概念。
迭代一词对一些人或许生疏，但在数学上它历史悠久。大约三千五百年前，古巴比伦人就想出了一个聪明的办法来逐次近似给定正数A的平方根，以今日的标准说法，它就是用众所周知的牛顿迭代法解方程x2 – A = 0。当今，在数学天地的几乎所有园区，迭代都留下活跃的身影，而求解方程各式各样的迭代法，则是计算数学家和工程学家们从不离手的利器。
为了形象地说明什么是迭代，让我们拿出一只假设误差为零的理想计算器，输进一个数，比方说0.5，然后按一下标有“x2”的那个平方键，小屏幕上就能看到结果：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：取定义域中的一个初始点x0，将它代入到f的具体代数表达式中，计算出其对应的函数值，这样就得到第一个迭代点x1；因为x1也属于函数的定义域，再将x1代入到f的表达式中赋值，就得出第二个迭代点x2……如此进行下去，对于所有的自然数n = 1, 2, 3, …，在得到第n-1个迭代点xn-1后，由于xn-1属于函数的定义域，将它代入到f的表达式中计算，就得出第n个迭代点xn。这样，我们获得了函数f的一个迭代点数列：
x0, x1, x2, …, xn, …。
这个数列也称为从初始点x0出发的f的迭代点轨道，或简称轨道。“轨道”是一种很形象的说法，因为起步于初始点的迭代点数列看上去就像是向远处伸展而去的一条铁路轨线。
在数学上，一个迭代过程可以写成
xn = f(xn-1)，n = 1, 2, 3, …。
本文开头时提到的数值求解方程g(x) = 0的牛顿迭代法就是一例，它具有形式
xn = xn-1 - g(xn-1)/g’(xn-1)，n = 1, 2, 3, …，
其中记号g’表示可微函数g的导函数。
迭代是一个从初始点出发，一步步从当前迭代点计算出后继迭代点的递归过程。所以在一般情况下，如果想知道第100个迭代点是什么，只好耐住性子算一百步后才能知道答案。然而，如果我们运气好到能“一步到位”地从0跳到n，写出n个f的复合函数fn的简洁表达式，那么就可以一步算出第n个迭代点xn = fn(x0)。可惜，令人沮丧的是，除了极少数简单情形外，比如从线性函数f(x) = ax立刻可以导出的简单式子fn(x0) = anx0，我们无力能将复杂的fn化简到一个封闭的代数表达式。幸运的是，数学理解我们的苦衷而为我们提供了微积分的十八般武艺，这些武艺打造出一门专攻迭代的现代学科——离散动力系统。
考察迭代，就会不可避免地碰到“不动点”和“周期点”这两个重要术语。如果在函数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*这两个等式 。
对于一个初始点x0，如果函数f被迭代到第n步后，又首次返回到初始点x0，即从初始点x0开始迭代后的第一个迭代点直到第n-1个迭代点x1 = f(x0), x2 = f(x1) = f2(x0), …, xn-1= f(xn-2) = fn-1(x0) 都不等于x0，但第n个迭代点xn= f(xn-1) = fn(x0)等于x0，则称x0为f的一个周期为n的周期点，其对应的有限数列x0, x1, x2, …, xn-1或集合{x0, x1, x2, …, xn-1}称为f的一个周期为n的周期轨道或周期-n轨道。
注意：上面的记号fk并非表示f的k次方，而是表示k个f复合而成的复合映射，即f0(x) = x, f1(x) = f(x), f2(x) = f(f(x)) = f(f1(x)), f3(x) = f(f(f(x))) = f(f2(x))，依次类推。
显而易见，如果n = 1，则周期为1的周期点就是不动点。找到函数f的所有不动点等价于求出方程f(x) = x的所有解，它们的几何意义就是f的图象与坐标系对角线的所有交点。当n大于1时，f的所有周期为n的周期点都是方程fn(x) = x的解，但反之，方程fn(x) = x的解却不一定是f的周期为n的周期点，而可能是f的周期为k的周期点，其中k是n的一个真因子。举个简单的例子，设f(x) = -x，则f2(x) = -(-x) = x。显然x = 0是f2(x) = x的一个解，但它却不是f周期为2的周期点，而是f的不动点。此外，方程f2(x) = x的每个非零解都是f的周期为2的周期点。
另一方面，一个周期-n轨道中的每一个点都是周期为n的周期点。比如说，如果{x0, x1, x2}是一个周期-3轨道，则由f(x0) = x1, f(x1) = x2及 f(x2) = x0可知，{x1, x2, x0}和{x2, x0, x1}都是周期-3轨道，因而组成同一个周期-3轨道的三个点x0, x1, x2都是周期为3的周期点。从一个周期点开始的迭代点无穷数列是其周期轨道“周而复始”的无穷次复制，因此该数列的最终走向是事先知道的，或言之，是可以预测的。我们对自然界中的周期现象太熟悉不过了，所以应该对数学中的周期点感到亲切。
由上可知，当初始点是周期点时，给定的函数迭代到某一步就会首次返回到初始点，然后再重复地无限循环下去，就像一个体格健壮的学生每天早晨绕着学校的椭圆形跑道一圈又一圈地跑个不停。当初始点不是周期点时，由此点出发后的所有迭代点自然永远不会回到初始点。既然永远不会回到初始点，这些迭代点的最终性态一定会是不可预知的吗？
答案是不确定。它既可能可以预知，也可能不可预知。先看一种只需要上述简单概念而无需高深一点的初等微分学知识就能理解的情形。如果初始点x0不是周期点，即对任意的自然数j都有不等式fj(x0) ≠ x0，但它的某次迭代点xm = fm(x0)却首次成为周期点，周期为n，即x0, x1, …, xm互不相同，但 fn(xm) = xm并且对所有的k = 1, 2, …, n-1，都有fk(xm) ≠ xm，那么这条迭代点轨道的最终走向还是可以预知的，亦即轨道的尾巴都是有限片段xm, xm+1, …, xm+n-1无限次的复制。这个初始点x0称为最终周期点；如果n = 1，最终周期点也称为最终不动点。这样从初始点x0启程的迭代点数列，前m+1个点互不相同，但从xm开始就一个周期-n轨道一个周期-n轨道地重复行进下去，如此一来，这个迭代点数列的最终性态当然还是可以预测的。例如对于简单的二次函数f(x) = x(1-x)，x = 1是一个最终不动点，因为它的第一次迭代点f(1) = 0是f的不动点。因而从最终不动点1开始的轨道是1, 0, 0, …。
还有一种情形，初始点既不是周期点，也不是最终周期点，即它对应的所有迭代点都互不相同，但我们依然可以预测迭代点数列的最终走向，比如说这个数列最终收敛到一个固定的数，或与一个固定的周期轨道越来越靠近，或发散到正无穷大，或发散到负无穷大，或其绝对值的数列发散到正无穷大。对这些不同状况下可预测性的分析求解，初等代数的数学工具则显得不够用了，需要一点初等微分学的知识。这就是为什么高等数学是一门很有用途的学问。具体来说，微分学中的“中值定理”或“单调收敛定理”常常是这个解析过程的数学后盾。既然本文是“浅说迭代”，我在后面将依然用浅显的语言解释其中一个定理的应用，但如果辅之以图象的视觉效应，则会帮助理解。为此，我们先介绍关于函数迭代眼睛看得更清楚的“图象表示法”，相对于前述依赖于函数赋值的“代数表示法”。
在检查迭代点数列的最终走向时，如果觉得一次又一次地用手或计算器算出函数值来得到一个又一个的迭代点太费时间，我们也可以借函数的图象来做与代数方法等价的事，只要图象曲线能够足够精确地画出。该几何方法让我们从初始点出发沿着一条上下和左右方向交替转弯的快捷路径急速地向前移动，这样就能直观地观察到迭代点列的“运动轨迹”，进而很方便地看出轨道的最终目标。
首先在平面上的xy-直角坐标系中作出函数y = f(x)的图象，然后在x-轴上取一个初始点x0，再从这个点出发，沿着y-轴的平行线朝着图象方向走，一直走到与它相交为止，在交点处向左或向右沿着x-轴的平行线走，一直走到和坐标系的对角线相交为止，这个交点的坐标为(x1, x1)，代表着第一个迭代点x1。然后从这点起沿着铅锤线走，直到和图象相交，在交点处沿着水平线走，直到和对角线相交，这个交点则代表着第二个迭代点x2。如此这般地走下去，我们就依次得到对角线上代表着各个迭代点x1, x2, x3, x4, x5, … 的一个几何点列。
读者如果将上一段的走路加转弯法则分别用到函数f(x) = x/2和g(x) = 2x，就很容易地几何论证出下列结论：对于函数f，从任一初始点出发的迭代点轨道最终将趋向于f 的唯一不动点0，而对于函数g，从任一正的初始点出发的迭代点轨道最终将发散到正无穷大，而从任一负的初始点出发的迭代点轨道最终将发散到负无穷大。这自然和从代数表达式fn(x0) = x0/2n及gn(x0) = 2nx0得到的结论一致。第一个函数的迭代令人想起两千三百年前战国时期的学者庄子 (约公元前369-约公元前286) 已包含朴素极限思想的那句名言“一尺之捶，日取其半，万世不竭”。
更一般地，用上述的“图象迭代法”就能快速地证明：对于线性函数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上，看一看它们各自的迭代轨道最终将走向何方。
看来既有不动点又有周期点的例子只能在非线性函数堆里去找了，好在这样的例子无穷多，随便抓来一个：f(x) = -x3。易见，0还是f唯一的不动点，但由于f(1) = -1并且f(-1) = 1，这个三次多项式函数有了一个周期为2的周期轨道{1, -1}。
本文的读者一定能够作出y = -x3的图象，然后用图象迭代法就会发现：对位于开区间(-1, 1)内的任意一个初始点x0，迭代点数列{fn(x0)}将趋向于极限0，故不动点0是吸引的；而当初始点x0的绝对值大于1时，迭代点的绝对值数列{|fn(x0)|}将趋向于正无穷大。也就是说，f的周期-2轨道{1, -1}排斥了它附近不等于1和-1的各个点。
上面函数f的反函数f-1(x) = - x1/3则给出了周期轨道的另一个性质。对f-1的图象进行几何迭代就会知道，不动点0具有排斥性，而周期-2轨道{1, -1}则成为吸引的了，理由是当非零初始点x0的绝对值小于1或大于1时，迭代点数列{(f-1)n(x0)}都将会无限接近于这个周期-2轨道{1, -1}。
再一次地，上面这两个非线性函数都展示出其迭代点轨道的正规性态：对所有的初始点，迭代点数列的最终走向都是可以预测的，并且，除了唯一的不动点和两个周期为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迭代下去。
这条抛物线与坐标系的对角线有两个交点(0, 0)和(1/2, 1/2)，换言之，f有两个不动点0和1/2。我们给自己提出的问题是：从[0, 1]中任一初始点x0启程的迭代点轨迹，最后将通向何方？自然，当x0分别取为0、1/2或1时，读者马上就知道它们对应的轨道，因为前两者是不动点，第三者是最终不动点。所以我们只需着眼于初始点x0为正但小于1，而且不为1/2。
当然，满心希望快速求得答案的那些人马上会想起“图象迭代法”，用铅笔尖在抛物线和对角线之间竖直线段、水平线段地画上几笔，就能获得结论：对所有的大于0并且小于1的初始点，由此出发的迭代点数列总是趋向于第二个不动点1/2。然而，一位分析学家不会仅仅满足于几何直觉带来的结果，他追求的是怎样严格地证明它。
下面就是证明，除了最后一步外，前几步都属于中学代数。首先我们提请注意，如果初始点x0选在(1/2, 1)内，那么第一个迭代点x1就落到(0, 1/2)内了，之后的迭代点最终走向就与初始点选在(0, 1/2)之内没有什么两样了。基于这个观察，不失一般性，我们可以假设初始点x0满足0 < x0 < 1/2。那么2(1-x0) > 1，故2x0(1-x0) > x0。注意2x0(1-x0)即为第一个迭代点x1，从而x1 > x0。这就严格论证了为什么在开区间(0, 1/2)上，抛物线严格位于对角线的上方。显然x1 < 1/2。
第二步，我们证明f在[0, 1/2]上是严格递增的。一个函数在其定义域的某个子区间上被称为是严格递增的，如果在此区间上，自变量的值变大导致因变量的值也变大。设0 ≤ s < t ≤ 1/2，则t – s > 0及0 < t + s < 1，故t2 – s2 = (t + s)(t - s) < t - s，即s – s2 < t – t2，因而f(s) = 2s(1-s) < 2t(1-t) = f(t)。这就证明了f在[0, 1/2]上的严格递增性。
第三步，我们用数学归纳法证明迭代点数列{xn}是严格单调递增的，并且总是小于1/2。既然f在[0, 1/2]上是严格递增的正函数，不等式0 < x0 < x1 < 1/2推出不等式0 < x1 = f(x0) < f(x1) = x2 < f(1/2) = 1/2。假设对自然数n > 1有0 < xn-1 < xn < 1/2，则0 < xn = f(xn-1) < f(xn) = xn+1 < f(1/2) = 1/2。这就证明了数列{xn}的严格单调递增性并以1/2为一严格上界。用数学符号表示，就是：
0 < x0 < x1 < x2 < x3 < ··· < xn-1 < xn < xn+1 < ··· < 1/2。
这时，我们不得不从初等数学一跃跳上高等数学，需要的就是上文提及过的“单调收敛定理”：单调有界数列一定有极限。它的证明需要关于实数全体的“完备性公理”，此公理在美国是《高等微积分》教材的起点，在中国属于数学系的《数学分析》课程。但是我们可以用如下形象化的例子来帮助理解上述定理：设想一列有上万名士兵组成的队伍步行前进，这相当于一个单调递增的数列，如果前方永远没有障碍，这队士兵将一直走向远方，然而如果前面有一座爬不过去的城墙挡住他们，则这群保持向前走的士兵最终只能聚集在城墙脚下，这就相当于有上界的递增数列一定收敛到一点。
这样，从位于(0, 1/2)的初始点x0出发的迭代点数列{xn}将趋向于一个极限x*。但是，x*为什么一定就是1/2呢？要回答这个问题，我们又得求助于在高等数学里学过的“连续性”概念了。我们说一个函数h在其定义域区间中的一点x = a连续，是指这个函数h当自变量x趋向于a时不仅极限存在，而且极限等于它在a点的函数值，这个定义可用一个数学表达式完全概括：limx→a h(x) = h(a)。连续性定义还有一个等价性的数列说法，即函数h在a点连续当且仅当对于定义域中任一个收敛于a的数列{xn}，对应的函数值数列{h(xn)}也都收敛于同一个数h(a)。哪些函数是连续函数呢？所有的“初等函数”，即有单个代数表达式的函数，包括那些代数课本里人人熟知的多项式函数，在它们的“自然定义域”内是处处连续的，这里的二次函数f(x) = 2x(1-x)为其一例，它在每一个实数点连续。
好了，我们可以快乐地用到如上的基本事实了。对所有自然数n都成立的恒等式xn ≡ f(xn-1)，其左右两端是一模一样的数列，故它们的极限也必定是一模一样的数。左端数列{xn}的极限从上一段已知是x*，而数列{xn-1}只是数列{xn}的“右移一位”的平移，因而它也收敛到极限x*，故根据上一段中关于连续性的数列说法，右端数列{f(xn-1)}收敛到极限f(x*)。由于收敛数列的极限是唯一的，我们便得到等式x* = f(x*)。换句话说，x*是f的某个不动点。
然而二次多项式方程x = f(x)有两个解，一个是0，另一个是1/2。试问，x*会是不动点0吗？不可能！原因是x*是从一个大于0的数x0出发的递增的无穷数列的极限，这个向前推进的数列怎么可能后退收敛到比初始点还要后的0呢？因此，唯一的可能是x* = 1/2。这样，我们严格地证明了如下结论：对于定义在[0, 1]上的函数f(x) = 2x(1-x), 从(0, 1)中任意一点出发的迭代点轨道都收敛到1/2。
事实上，我们在上面顺便证明了一个一般性的断言。我们将它作为本文的最后礼品：
命题. 若函数f的一个迭代点数列收敛到x*，且f在x*连续，则x*是f的不动点。
“函数迭代”是一个内容丰富、用途宽广的数学话题，鉴于篇幅，我在本文中仅仅普及了“可以预见未来”的某些有序迭代过程。然而，从有序到无序——即混沌，更为神奇的情景还在前头，用浅显的初等语言解释背后的数学操作，将是继续讲述迭代的指导思想。写于2023年3月27日星期一美国哈蒂斯堡夏日山庄
相关阅读
5 马尔可夫——传薪火于数学内外，留得身后百年声名丨纪念马尔可夫逝世一百周年
近期推荐
1 深度剖析：ChatGPT 及其继任者会成为通用人工智能吗？| AI那厮
特 别 提 示
1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。
2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
版权说明：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。
长按下方图片关注「返朴」，查看更多历史文章