求解非線性方程的牛頓迭代法

李曉輝 任偉和 程長勝

摘?要：本文主要講了求解非線性方程的牛頓迭代法。文章首先引入牛頓迭代法的公式、迭代函數。緊接著文章又介紹了牛頓迭代法的局部收斂性以及它的收斂速度，并通過數值實驗驗證了牛頓迭代法求解非線性方程的有效性。

關鍵詞：牛頓迭代法;局部收斂;收斂速度

中圖分類號：O010224??文獻標識碼：A

一、緒論

類似于線性方程組Ax=b求解的問題，非線性方程的一般問題可化為f（x）=y，即“對于什么樣的x的值，函數f取值為y”，這里可以暫且先把f當成單變量函數，通常把y移項并吸收進f，從而一般形式可記為f（x）=0，因此，一個一般的一元非線性方程的求解問題有如下形式：

給定函數f，尋找x（實的或復的），使得f（x）=0。若存在一點x*滿足該性質，稱x*是方程f（x）=0的根或函數的零點。這類問題稱為求根問題或求零點問題。

此外，方程的根的情況可分為單根和重根。一般的非線性方程的重數可以定義如下：

若f（x）=（x-x*）m·g（x）且g（x）≠0，其中，m為自然數，稱x*為f（x）的m重根，m=1時也稱單根。若區間[a，b]上有方程的一個實根，稱該區間為方程的一個有根區間，如果能把方程的有根區間的長度縮短到一定的范圍內，那么就求到了一個近似根，通常采用的都是數值求解的辦法，因此若假設要求有根區間長度為0（即求到精確解），這些數值求解的辦法通常都會產生一個逐漸逼近根的一個無窮序列。

求方程的近似根，一般要考慮如下幾個問題：

（1）根的存在性問題，即方程有沒有實根，有幾個根。

（2）有根區間的確定。本文介紹的算法通常是假設有根的前提下給出求近似根的方法，一般需要以別的輔助工具先確定有根區間。

（3）求出足夠近似的根，即在制定精度下縮小有根區間，或通過某些判別條件斷定近似根的精度。

二、Newton迭代公式的構造

簡單迭代是將非線性方程f（x）=0通過代數恒等變形，將原方程化成等價方程x=φ（x），從而形成迭代式xk+1=φ（xk）。

Newton迭代法則是將非線性方程f（x）=0在x0點展開，即f（x）=f（x0）+f′（x0）（x-x0）+f″（ξ）2！（x-x0）2，并令p（x）=f（x0）+f′（x0）（x-x0），用線性方程p（x）=0近似代替非線性方程f（x）=0，再從p（x）=0中解得x=x0-f（x0）f′（x0），并令x1=x0-f（x0）f′（x0）作為f（x）=0的根的第一級近似值。一般的，記：

xk+1=xk-f（xk）f′（xk）（2.1）

作為方程f（x）=0的根的第k+1級近似值，我們稱公式（2.1）為Newton迭代公式，其中xk為第k次迭代的初值。Newton迭代公式（2.1）也可以由加速迭代公式

xk+1=xk+f（xk）=φ（xk）

xk+1=ωkxk+1+（1-ωk）xk（2.2）

其中ωk=11-L稱為松弛因子，L=φ′（xk），ωk=11-φ′（xk）=-1f′（xk），將ωk=11-φ′（xk）=-1f′（xk）代入（2.2）的第二個式子即得xk+1=xk-f（xk）f′（xk），這就是Newton迭代公式，其迭代函數是φ（x）=x-f（x）f′（x）。

另外，Newton迭代公式還有一種推導形式：

假設非線性方程為：

f（x）=0（2.3），令y=f（x）（2.4）

它的反函數為：

x=F（y）（2.5）

如果方程（2.3）中左端函數f（x）在區間[a，b]上連續，有且只有一個實根，則有f（a）f（b）<0。

現在假設x=α是方程（2.3）的一個實根，其中α∈[a，b]，則有：

f（α）=0（2.6）

α=F（0）（2.7）

如果對反函數式（2.5）在y點展成泰勒級數，則根據式（2.7）有：

α=F（0）=F（y）+F′（y）（0-y）+F″（y）2（0-y）2+…（2.8）

如果取展開式（2.8）中的前兩項，可得：

α≈F（y）-F′（y）·y

再利用反函數與反函數的導數概念，即y=f（x），x=F（y），F′（y）=1f′（x），則有α≈x-f（x）f′（x），令φ（x）=x-f′（x）f（x），就可以得到方程（2.3）的等價形式為x=x-f（x）f′（x）.此式被稱為牛頓迭代式。在區間[a，b]上取一個初值x0，就可以得到牛頓迭代格式xn+1=xn-f（xn）f′（xn）。

三、Newton迭代法局部收斂性分析

定義3.1：（局部收斂）若存在x*的某鄰域R=x|x-x*<δ，對任意的x0∈R，由xk+1=φ（xk）所產生的點列收斂，則稱xk+1=φ（xk）在R上收斂于x*。

定理3.1（局部收斂判別定理）設xk+1=φ（xk），R=x|x-x*<δ，若φ（x）滿足：

（1）φ′（x）在R內連續;（2）φ′（x*）

q<1，

則有以下結論：

（1）xk+1=φ（xk）在R上唯一地收斂于x*;

（2）xk-x*

11-qxk+1-xk。

證明：由（1）φ′（x）在R內連續，由連續函數的性質，存在x*的某鄰域R=x|x-x*<δ，使對于任意x∈R成立φ′（x）

q<1，此外，對于任意x∈R，總有φ（x）∈R，這是因為φ（x）-x*=φ（x）-φ（x*）

x-x*，滿足逼和條件，又由于條件（2）滿足壓縮條件。由此可以得到與全局收斂判別定理相類似的結論。

推論3.1?Newton迭代法在單實根鄰近處局部收斂。

證明：設f（x）=0的一個單實根為x*，在Newton迭代公式中，φ（x）=x-f（x）f′（x），φ′（x）=f（x）f″（x）[f′（x）]2，φ′（x*）=f（x*）f″（x*）[f′（x*）]2，因為x*為f（x）=0的一個單實根，所以f（x）=（x-x*）ψ（x），且ψ（x*）≠0，而f′（x*）=（x-x*）ψ′（x*）+ψ（x*）=ψ（x*）≠0，所以φ′（x*）=0，由定理3.1和推論3.1知結論成立。

四、Newton迭代法的收斂速度

為了進一步研究收斂速度問題，我們引入階的概念。

定義4.1?設由迭代公式xk+1=φ（xk）得到迭代序列xk收斂于方程x=φ（x）的根x*，記ek=xk-x*，若limk→

ek+1ekp=c≠0（p>0），稱序列xk是p階收斂的。特別地，p=1時稱線性收斂，p>1時稱超線性收斂，p=2時稱平方收斂。顯然p越大，收斂速度越快。

定理4.1?設由迭代公式xk+1=φ（xk）得到迭代序列xk，若φ（p）（x）在所求的根x*的某個鄰域內連續，且φ′（x*）=…=φ（p-1）（x*）=0，φ（p）（x*）≠0，則迭代序列xk在所求的根x*的鄰域內是p階收斂。

證明：利用φ（xk）在x*的泰勒展開，并注意到xk+1=φ（xk），x*=φ（x*）和ek=xk-x*，

由φ（xk）=φ（x*）+φ′（x*）（xk-x*）+…+φ（p）（x*）p！（xk-x*）p+…，可得：

ek+1=φ′（x*）ek+…+φ（p）（x*）p！ekp+…

于是，根據階的定義式，若φ′（x*）≠0，則xk是一階收斂（線性收斂）;若φ′（x*）=…=φ（p-1）（x*）=0，φ（p）（x*）≠0，則xk是p階收斂。證畢。

上述定理告訴我們，迭代過程的收斂速度依賴于迭代函數φ（x）的選取。如果當x∈[a，b]時，φ′（x）≠0，則該迭代過程只可能是線性收斂。

對于牛頓公式，其迭代函數為φ（x）=x-f（x）f′（x），φ′（x）=f（x）f″（x）[f′（x）]2，假定x*是f（x）的一個單根，即f（x*）=0，f′（x*）≠0，則由上式知φ′（x*）=0，于是由定理4.1可知，牛頓法在根x*鄰近是局部平方收斂的。

由于牛頓法是局部收斂，因此牛頓法對初值要求比較嚴格，初值只有在根的附近才能保證收斂。實際上，常常用二分法或逐步搜索法選取好的初值。

定理4.2?設x*是f（x）=0的根，函數f（x）在x*的某一鄰域U（x*，δ），（0<δ<1）內具有二階連續導數，迭代函數為φ（x）=x-f（x）f′（x），當x∈U（x*，δ）時，φ（x）∈U（x*，δ），對于x0∈U（x*，δ），牛頓迭代公式產生的迭代序列為xk。如果φ′（x*）=f（x*）f″（x*）[f′（x*）]2<1，那么迭代序列xk收斂于x*;如果x*是f（x）=0的單根，那么迭代序列xk在x*的附近是二階收斂的，即平方收斂，且limk→

xk+1-x*（xk-x*）2=f″（x*）2f′（x*）;如果x*是f（x）=0的二重根，那么迭代序列xk在x*附近是一階收斂的，即線性收斂的，且重數越高收斂越慢。

定理4.3?設方程f（x）=0滿足下列條件：

（1）f（x）在區間[a，b]上的f′（x）與f″（x）均存在，且f′（x）與f″（x）的符號在區間[a，b]上均各自保持不變;

（2）f（a）f（b）<0;

（3）f（x0）f″（x0）>0，x0，x∈[a，b];

則方程f（x）=0在區間[a，b]上有且只有一個實根。由牛頓迭代格式計算得到的近似值序列收斂于方程f（x）=0的根。

五、牛頓迭代法的計算步驟

用牛頓迭代法解非線性方程f（x）=0的基本計算步驟是：

第一步：給出初始近似根及精度ε。

第二步：計算f0f（x0），f′0f′（x0），x1x0-f（x0）f′（x0）。

第三步：判斷若x1-x0<ε，則轉向第四步;否則x0x1，轉向第三步。

第四步：輸出滿足精度的根x，即α≈x，結束。

六、數值實驗

例1.用牛頓迭代法求方程xx=10的一個實根，精度要求為ε=10-6。

解：該方程的一個實根在2與3之間，即a=2，b=3。并且可以將原方程同解變換為f（x）=xlgx-1而f（a）=f（2）=2lg2-1<0，f（b）=f（3）=3lg3-1>0，因此方程滿足f（a）f（b）<0的條件，且f′（x）=lgx+lge>0，x∈[2，3]，f″（x）=lgex>0，x∈[2，3]，即f′（x）與f″（x）在區間[2，3]上各自保持符號不變，并且還可以看出f″（x）與f（3）同號，因此取x0=3，采用牛頓迭代格式xn+1=xn-f（xn）f′（xn），其計算結果如下表所示。

從上表可以看出，當n=3時，其迭代值已滿足精度要求，最后取實根的近似值為x=2.506184。

參考文獻：

[1]李慶揚.數值分析.武漢：華中科技大學出版社，1986.12.

[2]張光澄.實用數值分析.成都：四川大學出版社，2004.1.

[3]王金銘.數值分析.大連：大連理工大學出版社，2007.8.

[4]任玉杰.數值分析及其MATLAB實現.北京：高等教育出版社，2007.3.

[5]徐士良.數值方法與計算機實現.北京：清華大學出版社，2006.2.

[6]歐陽聯淵.計算機數值計算方法.北京：國防工業出版社，1997.1.

[7]薛毅.數值分析.北京：北京工業大學出版社，2005.3.

作者簡介：李曉輝（1984—?），女，碩士研究生，所學專業為計算數學，研究方向為最優化計算方法，多年來從事數學在各個領域的應用研究。