迭代算法原理及其Python編程實現(xiàn)

黃旭

摘 要：迭代算法是數(shù)學(xué)算法在計算機中應(yīng)用的一個熱點，也是計算機解決問題的一般思路，本文結(jié)合數(shù)學(xué)中二分法求根的原理，闡述了數(shù)學(xué)迭代算法的一般原理，并采用了Python加以實現(xiàn)，為進一步對數(shù)學(xué)算法理論和計算機的結(jié)合提供參考。

關(guān)鍵詞：迭代算法;二分法;Python;計算機程序

中圖分類號：TP31 文獻標(biāo)識碼：A 文章編號：1671-2064（2019）18-0043-02

0 引言

求解方程的根不僅是在學(xué)校期間學(xué)習(xí)數(shù)學(xué)物理等學(xué)科的基本能力，更是今后從事科學(xué)研究、工程技術(shù)的基本技能。在現(xiàn)實應(yīng)用中，方程通常都是基于物理原理建立的，不再是一些簡單的表達式，也就是說實際中的求解問題十分復(fù)雜，有的甚至沒有固定的求解方法。幸運的是，現(xiàn)在很多的問題都可以運用計算機進行求解，計算機除了會利用已有的公式求解之外，還擅長采用逐步迭代的方法得到近似解，這對科學(xué)研究與工程應(yīng)用具有十分重要的作用[1]-[2]。

本文主要基于高中數(shù)學(xué)中對連續(xù)函數(shù)的根存在性角度出發(fā)，通過查找資料，可以采用較為簡單的二分迭代算法去逼近真實根，就迭代算法進行了系統(tǒng)性的概括，并利用Python語言對一般的二分迭代算法進行了實現(xiàn)。

1 迭代算法原理分析

1.1 迭代算法概況

迭代算法[3]-[4]在平常計算的時候用的非常之多，但是以前用迭代算法求解方程的時候特別復(fù)雜。而隨著計算機技術(shù)的發(fā)展，利用計算機進行迭代算法的計算速度很快，只需簡單的命令即可讓該算法不停地迭代，直到結(jié)果符合條件。這也就使得人們從繁雜的計算中解放出來。因此，目前迭代算法的使用也逐漸的增多，甚至成為最基本的一種方法。實際上，迭代算法的原理較為簡單，它最主要的就是進行關(guān)系式的迭代。其基本含義為：不斷地用求解出來的量去計算新的數(shù)值，直到最后的數(shù)值滿足所求解的方程式，即停止迭代。

迭代算法一般用于求解最優(yōu)化問題。它能夠反復(fù)的迭代，直到最符合的那個值出現(xiàn)，并停止繼續(xù)計算。在求解優(yōu)化問題的時候，迭代算法會有一定的局限性。一是，最終的結(jié)果只是局部的最優(yōu)解，并不是全局最優(yōu)。二是，求解會陷入一個死循環(huán)。出現(xiàn)第一種原因的情況可能是在某個范圍內(nèi)該數(shù)值就是最優(yōu)的，這個時候計算器就會斷定這個數(shù)值就是方程式所需要的，即停止計算。這時候就需要設(shè)置好計算時的范圍，盡可能的讓計算機迭代多次，對所求的結(jié)果進行對比。出現(xiàn)第二種情況的原因是在給定的關(guān)系式以及數(shù)值范圍內(nèi)求不出符合最優(yōu)解，計算機將會不停地迭代。

因此，我們在用迭代算法進行計算的時候需要注意這幾點：首先要仔細(xì)的確認(rèn)迭代變量的數(shù)值;其次是對迭代的次數(shù)進行設(shè)置，不能讓該算法進入到死循環(huán);再者在必要的情況下應(yīng)盡量用較少的關(guān)系式去表示你的問題，減少計算器的運行量，因為計算器的運行內(nèi)存也是有限制的，否則會出現(xiàn)程序終止的情況。

目前，迭代算法的類型非常多。例如：牛頓迭代算法、迭代最近點算法、二分法迭代算法等。本文主要對二分法迭代算法進行分析，利用簡單的二分迭代算法求解方程，并且對二分迭代算法的實現(xiàn)進行了詳細(xì)的闡述。

1.2 二分法原理剖析

二分法顧名思義，就是將某個數(shù)值一分為二。通常情況下，數(shù)據(jù)量較大的時候適合使用二分法進行計算。但需要注意的是，利用二分法求解的數(shù)據(jù)必須單調(diào)增或減并且不能有重復(fù)的數(shù)值。二分法基本思路為，先將數(shù)據(jù)排序（升或者降序都可以）對于給定的數(shù)據(jù)序列，從數(shù)據(jù)序列的中間進行拆分，拆分為前半部分和后半部分。如果當(dāng)前拆分的數(shù)值是滿足所有條件的值，那么可以停止拆分?jǐn)?shù)據(jù)序列;如果當(dāng)前拆分的數(shù)值不是滿足的值，再判斷是否小于拆分之后序列的后半段。如果是，則從前半部分?jǐn)?shù)據(jù)序列中繼續(xù)查找，否則從后半部分?jǐn)?shù)據(jù)序列中繼續(xù)查找。一直進行數(shù)據(jù)的拆分，直到找到滿足所有條件的。其二分法基本思路定義用數(shù)學(xué)式子表達為：

比方說，假設(shè)，二分法的步驟就是將區(qū)間不斷地進行拆分。

（1）將區(qū)間表示為區(qū)間，其中當(dāng)時，則有。

（2）對于設(shè)，等于或者，其中表示區(qū)間的中點。

從上述二分法的定義中可以看出，它能夠很好地將計算步驟不斷地減半，極大的提高了運算速度和效率。

2 二分法的Python實現(xiàn)

2.1 二分法求解根式

在我們求解方程的時候，通常會利用現(xiàn)有的公式進行求解，即求根公式。但實際上，求根公式并不是對所有的方程都能適用，并且不一定求出來的結(jié)果正好就是精確的數(shù)值。很多時候求出來的結(jié)果都帶有根式，這個時候想求解精確的數(shù)值解幾乎是不可能的，而在某些情況下，必須要求求出某一精確數(shù)值。那么我們就需要求解一個近似值用于代替根式的值。求解某一數(shù)值的根式方法有二分法和牛頓法。

接下來本文主要對二分法求解根式進行詳細(xì)的敘述。其基本求解原理就是不斷地對求解的根式進行數(shù)值范圍的縮小，直到能夠找到所求根式能收斂某個數(shù)，即停止縮小范圍，輸出近似解。

本文先對二分法求解平方根進行分析，然后再運用到多次根式當(dāng)中。二分法求解根式的具體步驟為：

（1）通過計算方程得出，求出其近似的數(shù)值解;

（2）令，求得，將與進行比較;

（3）情況1：當(dāng)?shù)臅r候，則記當(dāng)前近似解區(qū)間的上限為。則繼續(xù)向下進行數(shù)值取半，即。在重復(fù)步驟2，直到，得到近似解的下限為。此時近似解的區(qū)間為，即最終的近似解一定在該區(qū)間之內(nèi)。然后再從該區(qū)間內(nèi)繼續(xù)按照步驟2進行取值，直到逐漸收斂至為止;

（4）情況2：當(dāng)?shù)臅r候，則記當(dāng)前近似解區(qū)間的下限為。則繼續(xù)向上進行數(shù)值取半，即。然后繼續(xù)重復(fù)步驟2，直到，得到近似解的上限為。此時近似解的區(qū)間為，即最終的近似解一定在該區(qū)間之內(nèi)。然后再從該區(qū)間內(nèi)繼續(xù)按照步驟2進行取值，直到逐漸收斂至為止。

案例1：求的近似解。

第一步，先取，求得，此時，求得區(qū)間上限為;

第二步，繼續(xù)向下取值，令，此時，此時區(qū)間下限為;

第三步，令，此時，此時區(qū)間下限為;

第四步，重復(fù)第三步，重新取值，直到無限接近5，則值即為我們要求的根式值。

根據(jù)上述例子可以發(fā)現(xiàn)，如果使用手動進行計算，還是具有一定的復(fù)雜程度的。本文將利用Python軟件[5]對二分法求解根式進行編程，實現(xiàn)計算機自動計算根式的解。

首先對二分法求解根式的基本思路進行轉(zhuǎn)化。其基本思路框圖1所示。

初始化：為所求根式;left為近似解區(qū)間的左區(qū)間值;right為近似解區(qū)間的右區(qū)間值。

根據(jù)該框圖寫出案例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世紀(jì)被提出來的，主要是用來求解近似值。該方法主要是利用單根附近有平方收斂的原理，來進行計算根式的近似值的。其牛頓迭代的公式為。在兩種求解根式的方法中，二分法迭代次數(shù)要多于牛頓法。

2.2 二分法求解方程

在平常求解方程組的過程中，我們會遇到無法用求根公式得出方程的解，就必須按照一般解方程組的步驟求出方程的解。但是遇到比較復(fù)雜的方程式，手動解方程是一件非常耗費時間的事情，且結(jié)果不一定準(zhǔn)確。本文介紹使用二分法來求解方程，最后給出用Python求解的具體思路。

本文先介紹用二分法求解函數(shù)的基本定義，在使用二分法求解方程的時候，需要注意幾個條件，將求解的方程用函數(shù)的形式表達出來，則有函數(shù)在區(qū)間上為單調(diào)且連續(xù)的函數(shù)，同時滿足，滿足這幾個條件的函數(shù)才能使用二分法進行求解。其具體求解思路如下：

步驟1，給定一個誤差，即認(rèn)為求出的解在誤差多少的范圍能是能被接受的;

步驟2，先求出區(qū)間的中點值，記為;

步驟3，將令，計算出的值;

步驟4，假設(shè)求出的的值為零，那么就是函數(shù)的零點，即使方程的解;如果，則需要進一步的判斷：若，則令;若，則令;

步驟5，若，則可以認(rèn)為方程的解等于或者。如果，則繼續(xù)重復(fù)步驟2到步驟4。

實際上，該方法主要是在縮小方程解所在的區(qū)間，直到左右兩區(qū)間的值無限接近，即認(rèn)為左右兩區(qū)間相等，且為方程的解。值得注意的是，用二分法求解方程，只能求出方程的一個單根。

案例2：求解。

根據(jù)二分法求方程解的步驟：

步驟1，給定一個誤差;

步驟2，先求出區(qū)間的中點值，記為;

步驟3，將令，計算出。

由于，且，因此令。此時方程的解區(qū)間變?yōu)椋缓罄^續(xù)重復(fù)步驟2到步驟4。直到，即停止計算。由于手工計算過于復(fù)雜，且計算時間慢。本文給出二分法求解方程的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））

根據(jù)案例和程序，得出a=0，b=1，c=-11，d=10，m=-15，n=20。在運行上述程序之后，只需要在窗口輸入：

0 1 -11 10

-15 20

即可得到最終結(jié)果為10.00。

3 結(jié)語

從本文給出例子的求解過程和求解結(jié)果中可以看出，通過二分法求方程的解，有且只有一個單根。但實際上，案例中的方程有兩個解：1和10。并且在求解過程中解區(qū)間的取值也應(yīng)該十分的注意，因為是隨機取值，這就會導(dǎo)致方程的解不在該解區(qū)間內(nèi)，最終導(dǎo)致求解方程組失敗。因此，在用二分法求方程時，應(yīng)該盡可能的將解區(qū)間的范圍擴大，以免求解失敗。另外，當(dāng)給定的誤差的值越小時，最終結(jié)果會越準(zhǔn)確。

參考文獻

[1] 張曉勇，王仲君.二分法和牛頓迭代法求解非線性方程的比較及應(yīng)用[J].教育教學(xué)論壇，2013（25）：139.

[2] 吳梨娟.信息技術(shù)下二分法求解函數(shù)的零點個數(shù)探討[J].高中數(shù)理化，2013（8）：10-11.

[3] 林永，陳浩.用二分法求解一元實系數(shù)多項式方程的全部實根[J].大學(xué)數(shù)學(xué)，2008，24（4）：88-90.

[4] 隋麗娜.利用高級語言實現(xiàn)數(shù)學(xué)中的二分法[J].人力資源管理，2010（6）：186.

[5] 王登岳，張宏偉.基于Python求解偏微分方程的有限差分法[J].計算機時代，2016（11）：14-16.