迭代算法原理及其Python编程实现

黄旭

摘 要：迭代算法是数学算法在计算机中应用的一个热点，也是计算机解决问题的一般思路，本文结合数学中二分法求根的原理，阐述了数学迭代算法的一般原理，并采用了Python加以实现，为进一步对数学算法理论和计算机的结合提供参考。

关键词：迭代算法;二分法;Python;计算机程序

中图分类号：TP31 文献标识码：A 文章编号：1671-2064（2019）18-0043-02

0 引言

求解方程的根不仅是在学校期间学习数学物理等学科的基本能力，更是今后从事科学研究、工程技术的基本技能。在现实应用中，方程通常都是基于物理原理建立的，不再是一些简单的表达式，也就是说实际中的求解问题十分复杂，有的甚至没有固定的求解方法。幸运的是，现在很多的问题都可以运用计算机进行求解，计算机除了会利用已有的公式求解之外，还擅长采用逐步迭代的方法得到近似解，这对科学研究与工程应用具有十分重要的作用[1]-[2]。

本文主要基于高中数学中对连续函数的根存在性角度出发，通过查找资料，可以采用较为简单的二分迭代算法去逼近真实根，就迭代算法进行了系统性的概括，并利用Python语言对一般的二分迭代算法进行了实现。

1 迭代算法原理分析

1.1 迭代算法概况

迭代算法[3]-[4]在平常计算的时候用的非常之多，但是以前用迭代算法求解方程的时候特别复杂。而随着计算机技术的发展，利用计算机进行迭代算法的计算速度很快，只需简单的命令即可让该算法不停地迭代，直到结果符合条件。这也就使得人们从繁杂的计算中解放出来。因此，目前迭代算法的使用也逐渐的增多，甚至成为最基本的一种方法。实际上，迭代算法的原理较为简单，它最主要的就是进行关系式的迭代。其基本含义为：不断地用求解出来的量去计算新的数值，直到最后的数值满足所求解的方程式，即停止迭代。

迭代算法一般用于求解最优化问题。它能够反复的迭代，直到最符合的那个值出现，并停止继续计算。在求解优化问题的时候，迭代算法会有一定的局限性。一是，最终的结果只是局部的最优解，并不是全局最优。二是，求解会陷入一个死循环。出现第一种原因的情况可能是在某个范围内该数值就是最优的，这个时候计算器就会断定这个数值就是方程式所需要的，即停止计算。这时候就需要设置好计算时的范围，尽可能的让计算机迭代多次，对所求的结果进行对比。出现第二种情况的原因是在给定的关系式以及数值范围内求不出符合最优解，计算机将会不停地迭代。

因此，我们在用迭代算法进行计算的时候需要注意这几点：首先要仔细的确认迭代变量的数值;其次是对迭代的次数进行设置，不能让该算法进入到死循环;再者在必要的情况下应尽量用较少的关系式去表示你的问题，减少计算器的运行量，因为计算器的运行内存也是有限制的，否则会出现程序终止的情况。

目前，迭代算法的类型非常多。例如：牛顿迭代算法、迭代最近点算法、二分法迭代算法等。本文主要对二分法迭代算法进行分析，利用简单的二分迭代算法求解方程，并且对二分迭代算法的实现进行了详细的阐述。

1.2 二分法原理剖析

二分法顾名思义，就是将某个数值一分为二。通常情况下，数据量较大的时候适合使用二分法进行计算。但需要注意的是，利用二分法求解的数据必须单调增或减并且不能有重复的数值。二分法基本思路为，先将数据排序（升或者降序都可以）对于给定的数据序列，从数据序列的中间进行拆分，拆分为前半部分和后半部分。如果当前拆分的数值是满足所有条件的值，那么可以停止拆分数据序列;如果当前拆分的数值不是满足的值，再判断是否小于拆分之后序列的后半段。如果是，则从前半部分数据序列中继续查找，否则从后半部分数据序列中继续查找。一直进行数据的拆分，直到找到满足所有条件的。其二分法基本思路定义用数学式子表达为：

比方说，假设，二分法的步骤就是将区间不断地进行拆分。

（1）将区间表示为区间，其中当时，则有。

（2）对于设，等于或者，其中表示区间的中点。

从上述二分法的定义中可以看出，它能够很好地将计算步骤不断地减半，极大的提高了运算速度和效率。

2 二分法的Python实现

2.1 二分法求解根式

在我们求解方程的时候，通常会利用现有的公式进行求解，即求根公式。但实际上，求根公式并不是对所有的方程都能适用，并且不一定求出来的结果正好就是精确的数值。很多时候求出来的结果都带有根式，这个时候想求解精确的数值解几乎是不可能的，而在某些情况下，必须要求求出某一精确数值。那么我们就需要求解一个近似值用于代替根式的值。求解某一数值的根式方法有二分法和牛顿法。

接下来本文主要对二分法求解根式进行详细的叙述。其基本求解原理就是不断地对求解的根式进行数值范围的缩小，直到能够找到所求根式能收敛某个数，即停止缩小范围，输出近似解。

本文先对二分法求解平方根进行分析，然后再运用到多次根式当中。二分法求解根式的具体步骤为：

（1）通过计算方程得出，求出其近似的数值解;

（2）令，求得，将与进行比较;

（3）情况1：当的时候，则记当前近似解区间的上限为。则继续向下进行数值取半，即。在重复步骤2，直到，得到近似解的下限为。此时近似解的区间为，即最终的近似解一定在该区间之内。然后再从该区间内继续按照步骤2进行取值，直到逐渐收敛至为止;

（4）情况2：当的时候，则记当前近似解区间的下限为。則继续向上进行数值取半，即。然后继续重复步骤2，直到，得到近似解的上限为。此时近似解的区间为，即最终的近似解一定在该区间之内。然后再从该区间内继续按照步骤2进行取值，直到逐渐收敛至为止。

案例1：求的近似解。

第一步，先取，求得，此时，求得区间上限为;

第二步，继续向下取值，令，此时，此时区间下限为;

第三步，令，此时，此时区间下限为;

第四步，重复第三步，重新取值，直到无限接近5，则值即为我们要求的根式值。

根据上述例子可以发现，如果使用手动进行计算，还是具有一定的复杂程度的。本文将利用Python软件[5]对二分法求解根式进行编程，实现计算机自动计算根式的解。

首先对二分法求解根式的基本思路进行转化。其基本思路框图1所示。

初始化：为所求根式;left为近似解区间的左区间值;right为近似解区间的右区间值。

根据该框图写出案例1的Python代码为：

Num=5

x=sqrt（Num）

x1=num/2

left=0

right=Num*1

count=1

while abs（x1-x）>0.00000001：

print count，x1

count+=1

if（x1**2>Num）：

right=x

x=left+（x1-left）/2

else：

left=x1

x1=right-（right-x1）/2

return y

print（sqrt（5））

另一种求解根式的方法是牛顿法，它是17世纪被提出来的，主要是用来求解近似值。该方法主要是利用单根附近有平方收敛的原理，来进行计算根式的近似值的。其牛顿迭代的公式为。在两种求解根式的方法中，二分法迭代次数要多于牛顿法。

2.2 二分法求解方程

在平常求解方程组的过程中，我们会遇到无法用求根公式得出方程的解，就必须按照一般解方程组的步骤求出方程的解。但是遇到比较复杂的方程式，手动解方程是一件非常耗费时间的事情，且结果不一定准确。本文介绍使用二分法来求解方程，最后给出用Python求解的具体思路。

本文先介绍用二分法求解函数的基本定义，在使用二分法求解方程的时候，需要注意几个条件，将求解的方程用函数的形式表达出来，则有函数在区间上为单调且连续的函数，同时满足，满足这几个条件的函数才能使用二分法进行求解。其具体求解思路如下：

步骤1，给定一个误差，即认为求出的解在误差多少的范围能是能被接受的;

步骤2，先求出区间的中点值，记为;

步骤3，将令，计算出的值;

步骤4，假设求出的的值为零，那么就是函数的零点，即使方程的解;如果，则需要进一步的判断：若，则令;若，则令;

步骤5，若，则可以认为方程的解等于或者。如果，则继续重复步骤2到步骤4。

实际上，该方法主要是在缩小方程解所在的区间，直到左右两区间的值无限接近，即认为左右两区间相等，且为方程的解。值得注意的是，用二分法求解方程，只能求出方程的一个单根。

案例2：求解。

根据二分法求方程解的步骤：

步骤1，给定一个误差;

步骤2，先求出区间的中点值，记为;

步骤3，将令，计算出。

由于，且，因此令。此时方程的解区间变为，然后继续重复步骤2到步骤4。直到，即停止计算。由于手工计算过于复杂，且计算时间慢。本文给出二分法求解方程的Python代码。其一般代码如下：

a，b，c，d=input（）.split（）

m，n=input（）.split（）

m=float（m）

n=float（n）

a=float（a）

b=float（b）

c=float（c）

d=float（d）

def f（x）：

return a*pow（x，3）+b*pow（x，2）+c*x+d

def erfen（m，n）：

if（（n-m）<0.0001）：

print（“{：.2f}”.format（（m+n）/2））

elif（f（m）*f（n）<0）：

if（f（（m+n）/2）==0）：

print（“{：.2f}”.format（（m+n）/2））

else：

if（f（（m+n）/2）*f（m）>0）：

m=（m+n）/2

erfen（m，n）

elif（f（（m+n）/2）*f（n）>0）：

n=（m+n）/2

erfen（m，n）

if（m

erfen（m，n）

elif（m==n）：

print（“{：.2f}”.format（m））

根据案例和程序，得出a=0，b=1，c=-11，d=10，m=-15，n=20。在运行上述程序之后，只需要在窗口输入：

0 1 -11 10

-15 20

即可得到最终结果为10.00。

3 结语

从本文给出例子的求解过程和求解结果中可以看出，通过二分法求方程的解，有且只有一个单根。但实际上，案例中的方程有两个解：1和10。并且在求解过程中解区间的取值也应该十分的注意，因为是随机取值，这就会导致方程的解不在该解区间内，最终导致求解方程组失败。因此，在用二分法求方程时，应该尽可能的将解区间的范围扩大，以免求解失败。另外，当给定的误差的值越小时，最终结果会越准确。

参考文献

[1] 张晓勇，王仲君.二分法和牛顿迭代法求解非线性方程的比较及应用[J].教育教学论坛，2013（25）：139.

[2] 吴梨娟.信息技术下二分法求解函数的零点个数探讨[J].高中数理化，2013（8）：10-11.

[3] 林永，陈浩.用二分法求解一元实系数多项式方程的全部实根[J].大学数学，2008，24（4）：88-90.

[4] 隋麗娜.利用高级语言实现数学中的二分法[J].人力资源管理，2010（6）：186.

[5] 王登岳，张宏伟.基于Python求解偏微分方程的有限差分法[J].计算机时代，2016（11）：14-16.