迭代法求解常見方程及其在計(jì)算機(jī)中的實(shí)現(xiàn)

盧一荻

求解方程的解是數(shù)學(xué)學(xué)習(xí)和研究工作中常見難點(diǎn)問題，很多學(xué)科的最終問題都?xì)w咎于方程解的問題，但很多情況下解的存在性判斷和求解過程極其復(fù)雜，通常情況又依賴于計(jì)算機(jī)來判斷與求解。本文受一元二次方程的零點(diǎn)存在性判斷的啟發(fā)，調(diào)研相關(guān)資料，采用了迭代法實(shí)現(xiàn)對(duì)一元三次方程的根的求解及其計(jì)算機(jī)實(shí)現(xiàn)過程，并以此為基礎(chǔ)，將迭代法拓展到常見的線性方程組（三元一次方程組）的求解，并對(duì)其實(shí)現(xiàn)求解原理與計(jì)算實(shí)現(xiàn)過程進(jìn)行了闡述，為進(jìn)一步掌握數(shù)據(jù)與計(jì)算機(jī)的交叉應(yīng)用提供基礎(chǔ)。

1.引言

在初中剛開始接觸一元二次方程的時(shí)候，會(huì)發(fā)現(xiàn)帶入某值x1使得f(x1)＞0，而帶入x2時(shí)會(huì)發(fā)現(xiàn)f(x2)＜0，因?yàn)閒(x)是個(gè)連續(xù)函數(shù)，所以必定存在x0，在x1、x2之間，使得f(x0)=0，此時(shí)x0則是方程的其中一個(gè)根，這其實(shí)本質(zhì)就是連續(xù)方程的零點(diǎn)問題。實(shí)際上，大多數(shù)方程的解都具有一定的規(guī)律性，正是由于數(shù)學(xué)方程的解的規(guī)律性，使得利用計(jì)算機(jī)來判斷與求解方程的根具有可行性。而迭代法是常見方程求解的一般方法，如本文所要分析的一元三次方程求解和多元一次線性性方程組在計(jì)算機(jī)中的實(shí)現(xiàn)原理都源自于迭代思想。

本文結(jié)合對(duì)數(shù)學(xué)方程求解的興趣，在不斷探索方程根的特點(diǎn)過程中，受到連續(xù)函數(shù)零點(diǎn)判斷準(zhǔn)則啟發(fā)，對(duì)一元三次方程的根的判斷與求解在計(jì)算機(jī)中的實(shí)現(xiàn)原理和常見的線性方程組的迭代法進(jìn)行深入分析總結(jié)，為后續(xù)進(jìn)入大學(xué)對(duì)數(shù)學(xué)與計(jì)算機(jī)相關(guān)學(xué)科的深入學(xué)習(xí)奠定基礎(chǔ)。

2.迭代法介紹

迭代法是一種不斷用變量的舊值在一定迭代準(zhǔn)則下去逼近真實(shí)值的方法，通常都是借助計(jì)算機(jī)來完成，由于計(jì)算機(jī)運(yùn)算速度快，且在做重復(fù)性計(jì)算方面具有先天優(yōu)勢(shì)，只要通過計(jì)算機(jī)編寫特定程序，并按照迭代要求不斷重復(fù)執(zhí)行，即可最終得到真實(shí)值或近似真實(shí)值。本文在此主要介紹牛頓(Newton)迭代法、雅可比(Jacobi)迭代法和高斯-塞德爾(Gauss-Seidel)迭代法。

2.1 牛頓迭代法

作為經(jīng)典的方程近似求解方法，在實(shí)數(shù)解和復(fù)數(shù)解的求解應(yīng)用中得到了廣泛的應(yīng)用。其提出的背景是在解高次方程時(shí)遇到?jīng)]有確切求根公式，有時(shí)根的求解精度得不到有效保證，甚至是無法求解，因此尋找有效的方法求解方程的近似解對(duì)于科學(xué)研究和工程計(jì)算是十分重要的。

牛頓迭代法的思路是用曲線切線的零點(diǎn)逼近曲線零點(diǎn)，如對(duì)于任意方程f(x)=0，可以借助高中三個(gè)一元二次問題的思想進(jìn)行求解，即將方程的根看成是曲線的零點(diǎn)問題。其主要思想如下：

設(shè)方程f(x)=0的真實(shí)根為f(x0)=0，但由于無法精確算出，則根據(jù)牛頓迭代公式可以如下進(jìn)行迭代求解：

第一步：取（x0，f(x0)）附近的一個(gè)點(diǎn)（x1，f(x1)），并求該點(diǎn)的切線方程，y=f(x1)+ f＇(x1)(x-x1)。

第二步：求上述切線方程的零點(diǎn)，即令y=0，得到切線方程的零點(diǎn)x2=x1-f(x0)/ f＇(x0)，該x2便是比x1更接近于x0的近似解。

依次按照上述第一步與第二步繼續(xù)求解近似解對(duì)應(yīng)點(diǎn)的切線方程及其對(duì)應(yīng)的零點(diǎn)，則可以得到真實(shí)值x0對(duì)應(yīng)的近似解序列xn+1=xn-f(xn)/f＇(xn)。

從文獻(xiàn)調(diào)研來看，只要上述方程所對(duì)應(yīng)的函數(shù)f(x)是連續(xù)的，且對(duì)應(yīng)零點(diǎn)是孤立的，則一定存在一個(gè)區(qū)間范圍，只要選取的初始迭代值x1在該區(qū)間范圍，通過牛頓迭代法求解的近似解序列則一定逐步收斂到真實(shí)值x0。

2.2 雅可比(Jacobi)迭代法

上述的牛頓迭代法主要適用于一元方程，但是實(shí)際解決問題時(shí)由于可能遇到多元方程時(shí)，則并不好進(jìn)行牛頓迭代求解，因此后續(xù)又提出了雅可比迭代法和高斯-塞德爾迭代法。

雅可比迭代法主要的解決對(duì)象是多元一次方程組，如式（1）所示，n元一次方程有唯一解的充分條件是存在n個(gè)線性無關(guān)的等式?，F(xiàn)假設(shè)（1）中個(gè)式子線性無關(guān)，對(duì)應(yīng)的求解思想是：

雅可比迭代法求解多元一次方程，只要上述方程是n個(gè)線性無關(guān)的方程，該迭代算法便是收斂的。

2.3 高斯-塞德爾(Gauss-Seidel)

高斯-塞德爾迭代算法是基于雅可比迭代算法之上，是對(duì)雅可比迭代的一種優(yōu)化，因?yàn)檠趴杀鹊潜敬蔚?jì)算時(shí)采用的是變量值全是上次迭代結(jié)果，而高斯-塞德爾迭代算法的思想是在每次迭代計(jì)算時(shí)采用了最新值，其思想可以表示為式（3）所示。

每次代入算出的最新值，進(jìn)行迭代根據(jù)設(shè)定的精度值停止迭代，得到方程地根。相比雅可比迭代法，此種迭代法具有更快的收斂速度。

3.牛頓迭代法解一元三次方程及計(jì)算機(jī)實(shí)現(xiàn)流程

3.1 牛頓迭代法解一元三次方程案例

則按照2.1所述的牛頓迭代法有：

其迭代計(jì)算結(jié)果如表1所示。

表1 牛頓迭代法求解一元三次方程迭代結(jié)果

可見當(dāng)?shù)降?次就已經(jīng)接近真實(shí)值了，收斂速度整體令人滿意。

圖1 牛頓迭代法解一元多次方程的計(jì)算機(jī)軟件實(shí)現(xiàn)流程圖

3.2 牛頓迭代法解方程計(jì)算機(jī)實(shí)現(xiàn)流程

牛頓迭代法通過計(jì)算機(jī)編程實(shí)現(xiàn)是比較簡(jiǎn)單的，從文獻(xiàn)調(diào)研來看，用Matlab或C語言編程實(shí)現(xiàn)的較多，但其基本思路是一致的，如圖1所示。

4.雅可比與高斯-塞德爾迭代法求解多元一次方程及計(jì)算機(jī)實(shí)現(xiàn)流程

4.1 雅克比迭代法求解多元一次方程案例

例如：用雅可比迭代法求解下列方程組：

將方程組按雅可比方法寫成：

并進(jìn)行一般化處理得到：

表2 雅可比求解多元一次方程迭代結(jié)果

4.2 高斯-塞德爾迭代法求解多元一次方程案例

從2.2與2.3的原理描述可知，雅可比迭代法在計(jì)算時(shí)是用第k次的全部分量x(k)去迭代計(jì)算第k+1次的結(jié)果，進(jìn)而得到對(duì)應(yīng)的所有分量x(k+1)。但其實(shí)這是計(jì)算第i個(gè)分量xi(k+1)時(shí)，按照方程的順序，已經(jīng)通過迭代計(jì)算得到最新分量值，但卻沒有被得到利用。事實(shí)上，從直觀感覺上，那些最新計(jì)算出的分量應(yīng)該比舊的分量更優(yōu)。因此，高斯-塞德爾迭代法便是充分利用了那些最新計(jì)算出來的第k+1次近似，代入到后續(xù)的方程計(jì)算，見式（3）所示。對(duì)上述的三元一次方程組，則通過采用高斯-塞德爾迭代算法求解得到如表3所示的結(jié)果。

表3 高斯-塞德爾求解多元一次方程迭代結(jié)果

通過對(duì)比表1與表2可知，對(duì)于同一個(gè)多元一次方程組，采用高斯-塞德爾迭代法比雅可比迭代法收斂快，也就是說，如果目標(biāo)是達(dá)到同樣的精度，則高斯-塞德爾迭代法比雅可比迭代法所需的迭代次數(shù)要少。

4.3 雅可比與高斯-塞德爾迭代法計(jì)算機(jī)實(shí)現(xiàn)流程

和牛頓迭代法計(jì)算機(jī)編程實(shí)現(xiàn)類似，當(dāng)前文獻(xiàn)顯示的主要都是基于Matlab或C語言編程，整體思路如圖2所示。

圖2 雅可比與高斯-塞德爾迭代法解多元一次方程的計(jì)算機(jī)軟件實(shí)現(xiàn)流程圖

5.結(jié)論

方程的求解是實(shí)際工程應(yīng)用和科學(xué)研究所必須解決的計(jì)算問題，在大多數(shù)情況下方程求解并不會(huì)很容易，尤其是實(shí)際工程計(jì)算，往往帶有很多近似求解。本文介紹的迭代法求解方程的解是十分有用且具有重大工程應(yīng)用價(jià)值的方法理論，尤其是文章重點(diǎn)介紹的牛頓迭代法、雅可比迭代法和高斯-塞德爾迭代法是迭代求解問題的經(jīng)典理論，最后文章通過引入實(shí)際求解例子進(jìn)行了三種迭代求解案例的分析，考慮到迭代法求解過程簡(jiǎn)單，只要進(jìn)行簡(jiǎn)單的重復(fù)計(jì)算即可，所以文章特意對(duì)相應(yīng)的計(jì)算方法進(jìn)行了對(duì)應(yīng)計(jì)算機(jī)程序的實(shí)現(xiàn)流程分析，充分體現(xiàn)了數(shù)學(xué)思想在計(jì)算機(jī)實(shí)現(xiàn)的機(jī)理，為深入理解算法在計(jì)算機(jī)實(shí)現(xiàn)原理提供參考。