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

李曉輝 任偉和 程長勝

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

關(guān)鍵詞：牛頓迭代法;局部收斂;收斂速度

中圖分類號：O010224??文獻(xiàn)標(biāo)識碼：A

一、緒論

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

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

此外，方程的根的情況可分為單根和重根。一般的非線性方程的重?cái)?shù)可以定義如下：

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

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

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

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

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

二、Newton迭代公式的構(gòu)造

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

Newton迭代法則是將非線性方程f（x）=0在x0點(diǎn)展開，即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迭代公式，其迭代函數(shù)是φ（x）=x-f（x）f′（x）。

另外，Newton迭代公式還有一種推導(dǎo)形式：

假設(shè)非線性方程為：

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

它的反函數(shù)為：

x=F（y）（2.5）

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

現(xiàn)在假設(shè)x=α是方程（2.3）的一個實(shí)根，其中α∈[a，b]，則有：

f（α）=0（2.6）

α=F（0）（2.7）

如果對反函數(shù)式（2.5）在y點(diǎn)展成泰勒級數(shù)，則根據(jù)式（2.7）有：

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

如果取展開式（2.8）中的前兩項(xiàng)，可得：

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

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

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

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

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

（1）φ′（x）在R內(nèi)連續(xù);（2）φ′（x*）

q<1，

則有以下結(jié)論：

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

（2）xk-x*

11-qxk+1-xk。

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

q<1，此外，對于任意x∈R，總有φ（x）∈R，這是因?yàn)棣眨▁）-x*=φ（x）-φ（x*）

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

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

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

四、Newton迭代法的收斂速度

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

定義4.1?設(shè)由迭代公式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?設(shè)由迭代公式xk+1=φ（xk）得到迭代序列xk，若φ（p）（x）在所求的根x*的某個鄰域內(nèi)連續(xù)，且φ′（x*）=…=φ（p-1）（x*）=0，φ（p）（x*）≠0，則迭代序列xk在所求的根x*的鄰域內(nèi)是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+…

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

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

對于牛頓公式，其迭代函數(shù)為φ（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*鄰近是局部平方收斂的。

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

定理4.2?設(shè)x*是f（x）=0的根，函數(shù)f（x）在x*的某一鄰域U（x*，δ），（0<δ<1）內(nèi)具有二階連續(xù)導(dǎo)數(shù)，迭代函數(shù)為φ（x）=x-f（x）f′（x），當(dāng)x∈U（x*，δ）時，φ（x）∈U（x*，δ），對于x0∈U（x*，δ），牛頓迭代公式產(chǎn)生的迭代序列為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*附近是一階收斂的，即線性收斂的，且重?cái)?shù)越高收斂越慢。

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

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

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

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

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

五、牛頓迭代法的計(jì)算步驟

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

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

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

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

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

六、數(shù)值實(shí)驗(yàn)

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

解：該方程的一個實(shí)根在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）在區(qū)間[2，3]上各自保持符號不變，并且還可以看出f″（x）與f（3）同號，因此取x0=3，采用牛頓迭代格式xn+1=xn-f（xn）f′（xn），其計(jì)算結(jié)果如下表所示。

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

參考文獻(xiàn)：

[1]李慶揚(yáng).數(shù)值分析.武漢：華中科技大學(xué)出版社，1986.12.

[2]張光澄.實(shí)用數(shù)值分析.成都：四川大學(xué)出版社，2004.1.

[3]王金銘.數(shù)值分析.大連：大連理工大學(xué)出版社，2007.8.

[4]任玉杰.數(shù)值分析及其MATLAB實(shí)現(xiàn).北京：高等教育出版社，2007.3.

[5]徐士良.數(shù)值方法與計(jì)算機(jī)實(shí)現(xiàn).北京：清華大學(xué)出版社，2006.2.

[6]歐陽聯(lián)淵.計(jì)算機(jī)數(shù)值計(jì)算方法.北京：國防工業(yè)出版社，1997.1.

[7]薛毅.數(shù)值分析.北京：北京工業(yè)大學(xué)出版社，2005.3.

作者簡介：李曉輝（1984—?），女，碩士研究生，所學(xué)專業(yè)為計(jì)算數(shù)學(xué)，研究方向?yàn)樽顑?yōu)化計(jì)算方法，多年來從事數(shù)學(xué)在各個領(lǐng)域的應(yīng)用研究。