1.4　Python初步应用示例——迭代法

迭代法（Iteration）是现代计算机求解问题的一种基本形式。迭代法不仅是一种算法，更是一种思想。它不像传统数学解析方法那样一步到位，得到精确解，而是步步为营，逐次推进，逐步接近。迭代法又称辗转法或逐次逼近法。

迭代法的核心是建立迭代关系式。迭代关系式指明了前进的方式，只有正确的迭代关系式才能取得正确解。

来看一个示例。假设在空池塘中放入一棵水藻，该类水藻会每周长出三棵新的水藻，问十周后，池塘中有多少棵水藻？

该问题可以用数学方法来直接计算。这里来看看如何用迭代法求解。

第1周的水藻数量：1；

第2周的水藻数量：1＋1×3；

第3周的水藻数量：1＋1×3＋（1＋1×3）×3；

……

可以归纳出从当前周水藻数量到下一周水藻数量的迭代关系式。设上周水藻数量为x，从上周到本周水藻将增加的数量为y，本周的水藻数量为x′，那么在一次迭代中：

迭代开始时，水藻的数量为1，为迭代法的初始条件。

迭代次数为9（不包括第一周），为迭代过程的控制条件。

该示例实现的代码见代码1-19，迭代过程共循环9次，用while语句来循环实现迭代，一般用一轮循环来实现一次迭代。读者可以自己尝试改用for语句方式来实现迭代。

代码1-19　迭代法应用示例（迭代法.ipynb）

迭代法是求解机器学习问题的基本方法，有着广泛的应用，比如机器学习领域大名鼎鼎的梯度下降法就是一种以梯度来建立迭代关系式的迭代法。本节先用解方程的例子来说明它在数值计算领域的应用，为后续讨论梯度下降法打下基础。

用迭代法求下列方程的解：

该方程很难用解析的方法直接求解，而可应用迭代法来求解。如何建立迭代关系式呢？

在迭代法求解中，每次迭代都得到一个新的x值，将每次迭代得到的x值依序排列就可得到数列{xk}。设x0为初值。在用迭代法求解方程时有个常用的迭代关系式建立方法：先将方程f（x）＝0变换为x＝φ（x），然后建立起迭代关系式：

如果{xk}收敛于x∗，那么x∗就是方程的根，因为：

即当x＝x∗时，有f（x）＝x－φ（x）＝0。

按式（1-3）建立上例的迭代关系式为：

迭代的结束条件是实际应用时需要考虑的问题，在该例中没有明确的结束条件。在无法预估时，可采用控制总的迭代次数的办法；也可以根据数列{xk}的变化情况来判断，如将|xk＋1－xk|的值小于某个阈值作为结束的标准；还可以将两种办法结合使用。

用迭代法求解式（1-5）的示例代码见代码1-20。该示例采用控制总的迭代次数作为结束的条件。这里将初始值设为0，读者可以设为其他值来观察一下迭代过程，要注意的是，不同的初始值可能会导致数列{xk}不收敛。

代码1-20　迭代法求解方程示例1（迭代法.ipynb）

运行结果显示从第28次迭代开始，收敛于0.84592。

代码1-20的第1行导入了math库，并在第4行使用了它的指数函数。

math库包含丰富的数学函数，如果内置函数库不够用，可以到math库中去找合适的数学函数。

代码1-21给出了更常见的采用阈值的方法来控制迭代结束的示例，如果相邻两次迭代xk的差值小于指定的delta，则通过break语句退出迭代。

代码1-21　迭代法求解方程示例2（迭代法.ipynb）

运行结果显示在第28次循环退出迭代。

第8行使用了赋值运算符。

上述两个例子中的迭代关系式可以明确地用数学方法来描述。

还有一类重要的迭代法，它的迭代关系式不依赖问题的数学性能，而是受某种自然现象的启发而得到，称为启发式算法（Heuristic Algorithm），如爬山法、遗传算法、模拟退火算法、蚁群算法等。启发式算法是一种根据经验、以近似随机的试探来搜索空间的方法，它可以在可接受的计算成本内得到最好解，但不保证能得到最优解。

下面介绍用爬山法来寻找上述方程的解值。爬山法的思路很简单，它从起点开始对周边邻近点进行试探，如果有更好的解，则从该点开始进行新一轮的试探，直到没有更好的解为止。

爬山法求解式（1-5）的代码见代码1-22。

代码1-22　迭代法求解方程示例3（迭代法.ipynb）

第3行设定搜索的步长。

第5行设定搜索的范围。通过将0和1代入式（1-2）的左边，可知该方程的解应位于0和1之间。

第7行定义了与待求解方程对应的函数：。下面的代码就是要找到使该函数值为0的x值。

第13行和第17行是分别对当前点相隔delta的邻近点进行试探，如果有更好的点，就一直进行下去。注意到在试探中，对f(x)进行了取绝对值操作，因此，要爬的“山顶”就是f(x)为0的那一点。同样要注意到，此“山”是一座倒放着的“山”，因此，试探是比较新点的函数值是不是小于原来点的函数值。

随机设置初始点，通过多轮迭代，程序能够搜索到接近方程的解的值。求解的精度和迭代的次数与delta值和初始点有关。

由该示例可知，爬山法好像人在黑夜里爬山，无法看到周边的情况，但可以通过棍子来试探周边山体上升的位置，然后到该位置再一次试探周边的位置。易知，爬山法可能跑到局部最优点（3.1节将详细讨论，如图3-5所示），形象地说，就是可以爬到山峰，但不一定是最高的那座山峰。