求解非線性方程組的Newton 型方法研究

徐 浩 司智勇

(1- 河南理工大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，焦作 454000;2- 燕山大學(xué)信息科學(xué)與工程學(xué)院，秦皇島 066000)

1 引言

Newton 迭代法是求解非線性方程組的一個(gè)重要方法，目前使用的很多其他類型的迭代法都是以Newton 法為基礎(chǔ)，在其上延伸與拓展之后得到的.研究Newton 型迭代法對(duì)現(xiàn)代非線性方程組的研究具有重要意義[1,2].本文利用文獻(xiàn)[3]的思想，結(jié)合非線性方程組的數(shù)值解法對(duì)現(xiàn)有的迭代法進(jìn)行改進(jìn)，得到了四類新的Newton 型迭代方法.數(shù)值實(shí)驗(yàn)表明，這四種迭代算法比Newton 法收斂速度更快.

2 格式的構(gòu)造

設(shè)F(x):D ?Rn →Rn，考慮非線性方程組

求解此類非線性方程組最基本的方法就是Newton 迭代法，Newton 迭代法是一個(gè)既簡(jiǎn)單又十分重要的方法.它的迭代格式為

以上為Newton 迭代法的n維迭代格式.

求解非線性方程的Newton 法是

文獻(xiàn)[3]中給出了一種求解非線性方程N(yùn)ewton 迭代法的改進(jìn)，迭代格式為，對(duì)r ∈[1/2,1][3,4]：

從幾何[5]上來看，這種迭代方式是將Newton 法中(xk,f(xk))點(diǎn)的切線改變成了另外一點(diǎn)

的切線，使得收斂速度更快.于是，我們將其直接推廣到n維，可以得到以下迭代方式，對(duì)r ∈[1/2,1]：

以上則為文中求解非線性方程組的第一種Newton 型迭代格式.此種方法相較于Newton 迭代法而言，每次迭代需要多求一次逆矩陣.雖然能加快收斂速度，但是計(jì)算量巨大.這種迭代方法對(duì)非線性方程適用，對(duì)于求解非線性方程組很可能計(jì)算量太大導(dǎo)致無法進(jìn)行.

簡(jiǎn)化的牛頓方法[6]又給了我們一種新的思路，就是以F′(x0)來替代F′(xk)，達(dá)到簡(jiǎn)化運(yùn)算的目的，即除了第一次需要求兩次逆矩陣之外，后面迭代都只需要進(jìn)行一次逆矩陣的計(jì)算.迭代效果來說，會(huì)相較文中第一種差.這種算法和Newton 迭代法的計(jì)算量基本相同，要比Newton 法要快.下面給出文中第二種迭代格式(r ∈[1/2,1])：

對(duì)上文進(jìn)行總結(jié)得出一般式

1)A=[F′(xk)]-1時(shí)，為Newton 迭代方法.

2)A=[F′(xk-(1-r)[F′(xk)]-1F(xk))]-1, k=0,1,···為文中第一種方法.

3)A=[F′(xk-(1-r)[F′(x0)]-1F(xk))]-1, k=0,1,···為文中第二種方法.

3 基于修正Newton 法的改進(jìn)

求解非線性方程組的修正Newton 迭代法為

它具有m+1 階斂速[6].取m=2，則有

于是，將此法與文中第一種方法結(jié)合，即可出現(xiàn)一種新的迭代方式

其中B= [F′(xk-(1-r)[F′(xk)]-1F(xk))]-1.相較于修正Newton 法而言，雖然增加了運(yùn)算量，但收斂速度更快.此為文中第三種迭代方法，得益于簡(jiǎn)化的牛頓方法.為了減少運(yùn)算量，我們馬上又可以得到文中第四種迭代方式，即將B中[F′(xk)]-1替換為[F′(x0)]-1，即可得到文中第四種迭代方法

綜上，得到一般式

1)B=[F′(xk-(1-r)[F′(xk)]-1F(xk))]-1時(shí)：

(a)m=1, r=1，此法即是Newton 法；

(b)m/=1, r=1，此法即為修正Newton 法；

(c)m=1, r/=1，此法即為文中第一種方法；

(d)m/=1, r/=1，此法為文中第三種方法.

2)B=[F′(xk-(1-r)[F′(x0)]-1F(xk))]-1時(shí)：

(a)m=1, r=1，此法即是Newton 法；

(b)m/=1, r=1，此法即為修正Newton 法；

(c)m=1, r/=1，此法即為文中第二種方法；

(d)m/=1, r/=1，此法為文中第四種方法.

4 算法分析

定理1(Newton 型迭代法的收斂定理)[6]假定F:D ?Rn →Rn在凸集D0?D上F可導(dǎo)，且滿足

成立，則對(duì)任何x,y ∈D0，有

則

對(duì)任意的x ∈D0滿足

其中μ, δ0, δ1≥0.

再由F在x0處F可導(dǎo)，故可選充分小的δ ＞0，使對(duì)任何x ∈S= ˉS(x0,δ)，有

又因?yàn)椤現(xiàn)′(x)-F′(x0)‖≤γ‖x-x0‖, ?x ∈S，所以由定理2 可知

定理4 若F:D ?Rn →Rn在凸集D0?D上F可導(dǎo)且滿足

則

對(duì)任意的x ∈D0滿足

其中μ, δ0, δ1≥0.

證明 因?yàn)锳(x0)非奇異，故可令β1=‖[A(x0)]-1‖ ＞0，由于A(x)在x0處連續(xù)，故對(duì)0＜? ＜(2β1)-1，存在δ ＞0，使當(dāng)x ∈S= ˉS(x0,δ)?S0時(shí)，有

再由F在x0處F可導(dǎo)，故可選充分小的δ ＞0，使對(duì)任何x ∈S= ˉS(x0,δ)，有

又因?yàn)椤現(xiàn)′(x)-F′(x0)‖≤γ‖x-x0‖, ?x ∈S，所以由定理2 可知

成立，則稱序列xk至少p階收斂.

定理6 假定F:D ?Rn →Rn在x*的開鄰域S0?D上F可導(dǎo)且F′(x*)非奇異，而x*為F(x)=0 的解，則存在閉球S= ˉS(x*,δ)?S0(δ ＞0)，使映像

對(duì)所有x ∈S有定義，且文中第一種方法生成的序列xk超線性收斂到x*.若還假定

α ＞0 為常數(shù)，則文中第一種算法的序列xk至少二階收斂.

證明 在定理5 中取A(x)=F′(x-(1-r)[F′(x)]-1F(x))，則映像

在球S ?S0上有定義且

于是ρ(G′(x*))=0＜1.由定理4 知xk收斂到x*且當(dāng)xk/=x*, k ≥k0時(shí)，有

所以，文中第一種Newton 型迭代法是超線性收斂的.由定理2 可知

于是有

因?yàn)镕′(x*)=A(x*)，所以得到以下表達(dá)式

取β=‖[A(x*)]-1‖ ＞0，由于A(x)在x*處連續(xù)，故對(duì)0＜? ＜(2β)-1，當(dāng)x ∈S=ˉS(x*,δ)?S0時(shí)，有‖A(x)-A(x*)‖≤?，由攝動(dòng)引理可知對(duì)x ∈S,[A(x)]-1存在，且

F在x*處F可導(dǎo)，故可選充分小δ ＞0，對(duì)任給x ∈S= ˉS(x*,δ)，有

α ＞0 為常數(shù)，則文中第二種算法的迭代序列{xk}至少二階收斂.

證明 在定理5 中取A(x)=F′(x-(1-r)[F′(x0)]-1F(x))，則映像

在球S ?S0上有定義且

于是ρ(G′(x*))=0＜1.由定理4 知xk收斂到x*且當(dāng)xk/=x*, k ≥k0時(shí)，有

所以，文中第二種Newton 型迭代法也是超線性收斂的.由定理2 可知

于是有

因?yàn)镕′(x*)=A(x*)，所以得到以下表達(dá)式

F在x*處F可導(dǎo)，故可選充分小δ ＞0，對(duì)任給x ∈S= ˉS(x*,δ)，有

由定義1 可知文中第二種方法收斂階至少為2.

定理8[6]若序列{xk}?Rn超線性收斂于x*，當(dāng)k ≥k0時(shí)，xk/=x*，則

定理9 若F:D ?Rn →Rn在x*的鄰域S(x*,δ)?D上F可微，且F′(x*)非奇異，x*是F(x)=0 的解，再假定對(duì)任何x ∈S，存在正常數(shù)γ，使

成立，則x*是文中第三種迭代方式生成序列{xk}的吸引點(diǎn)，且

同時(shí)，類推可有

證明 由定理6 可知映像

在球S1= ˉS(x*,δ1)?S上有定義并滿足

取c1=βγη(ηδ2+1)，它是一個(gè)不依賴k的常數(shù)，當(dāng)xk+1=G(xk)時(shí)，則有

即文中第三種方法當(dāng)m= 2 時(shí)收斂階至少為3，類推即可證明文中第三種方法收斂階至少為m+1.由定理8 可知‖xk,2-x*‖≤c1‖xk-x*‖3，于是

成立，即文中第三種方法至少m+1 階收斂.

定理10 若F:D ?Rn →Rn在x*的鄰域S(x*,S)?D上F可微，且F′(x*)非奇異，x*是F(x)=0 的解，再假定對(duì)任何x ∈S，存在正常數(shù)γ，使

成立，則x*是文中第四種迭代方式生成序列{xk}的吸引點(diǎn)，且

同時(shí)，類推可有

證明 由定理7 可知映像

在球S1= ˉS(x*,δ1)?S上有定義并滿足

取c2=βγη(ηδ2+1)，它是一個(gè)不依賴k的常數(shù)，當(dāng)xk+1=G(xk)時(shí)，則有

即文中第四種方法當(dāng)m= 2 時(shí)收斂階至少為3，類推即可證明文中第四種方法收斂階至少為m+1.由定理8 可知‖xk,2-x*‖≤c1‖xk-x*‖3，于是又有F′(x*)=A(x*)，所以有

成立.即文中第四種方法至少m+1 階收斂.

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

在本節(jié)中，我們給出一些數(shù)值實(shí)驗(yàn)結(jié)果，表明我們的算法的有效性和優(yōu)點(diǎn).

例1

我們?nèi)〕踔祒0=(108,109,9)T.幾種迭代法的數(shù)值實(shí)驗(yàn)結(jié)果如表1 至表5 所示.

表5 文中第二種方法的數(shù)值結(jié)果(取r =2/3)

表1 Newton 法的數(shù)值結(jié)果

表2 文中第一種方法的數(shù)值結(jié)果(取r =1/2)

表3 文中第一種方法的數(shù)值結(jié)果(取r =2/3)

表4 文中第二種方法的數(shù)值結(jié)果(取r =1/2)

由于文中第一、二種方法是在牛頓法基礎(chǔ)上進(jìn)行拓展，所以我們將第一、二兩種算法與牛頓法分別進(jìn)行比較.我們觀察表格發(fā)現(xiàn)r取值不同，算法迭代收斂的真解也不同，這是因?yàn)閞影響著算法的收斂速度，會(huì)出現(xiàn)初值相同但貼近不同真解的情況.從數(shù)值結(jié)果中可以發(fā)現(xiàn)兩種方法相較于牛頓法的36 步迭代步數(shù)均要少.同時(shí)，我們記錄了算法運(yùn)行的時(shí)間，如表6 所示.

表6 幾種算法的計(jì)算時(shí)間

由于文中第一種方法(取r= 2/3)和文中第二種方法(取r= 1/2)的真解與牛頓法真解不同，所以與牛頓法的結(jié)果進(jìn)行比較時(shí)無參考價(jià)值.我們看其他兩種都比牛頓法得出結(jié)果速度要快.

將第一種與第二種方法進(jìn)行比較，選取初值條件x0= (98,99,9)T, r= 1/2.發(fā)現(xiàn)文中兩種方法與牛頓法有相同真解(-0.4151,2.6039,3.1882)T.

由表7 可以發(fā)現(xiàn)，第一種方法較第二種方法迭代步數(shù)較少，計(jì)算時(shí)間較長(zhǎng).第二種方法迭代步數(shù)較多，計(jì)算時(shí)間較短.由此我們發(fā)現(xiàn)文中的算法當(dāng)?shù)綌?shù)與牛頓法相差較大的時(shí)候，文中兩種算法得出結(jié)果速度較快.而當(dāng)?shù)綌?shù)與牛頓法相差不大的時(shí)候，文中兩種方法得出結(jié)果速度與牛頓法持平甚至較牛頓法收斂慢，且文中第一種方法稍慢于文中第二種方法.

表7 r 取1/2 時(shí)文中第一、二種方法同Newton 法的迭代步數(shù)和計(jì)算時(shí)間

下面為修正牛頓法及由其拓展得出的文中第三、四種方法：取初值x0=(108,109,9)T，詳見表8 至表12.

表12 文中第四種方法數(shù)值結(jié)果(取r =2/3)

表8 修正Newton 法收斂結(jié)果

表9 文中第三種方法數(shù)值結(jié)果(取r =1/2)

表10 文中第三種方法數(shù)值結(jié)果(取r =2/3)

表11 文中第四種方法數(shù)值結(jié)果(取r =1/2)

由于文中第三、四種方法是在修正牛頓法基礎(chǔ)上進(jìn)行拓展，所以我們將第三、四種方法與修正牛頓法分別進(jìn)行比較.由于r= 1/2 時(shí)三種方法真解不同，所以我們?nèi)=2/3 的數(shù)據(jù)進(jìn)行比較.表13 為迭代步數(shù)及運(yùn)行時(shí)間的對(duì)比.

表13 r 取2/3 時(shí)文中第三、四種方法與修正牛頓法的迭代步數(shù)和計(jì)算時(shí)間

由表13 我們可以看出，文中第三、四種方法迭代步數(shù)和得出結(jié)果時(shí)間均優(yōu)于修正牛頓法.我們?cè)偃〕踔禇l件為x0= (45,96,9)T，進(jìn)行實(shí)驗(yàn)三個(gè)算法為相同真解(0,1.5492,0)T，表14 為三個(gè)算法對(duì)比.

表14 r 取1/2 時(shí)文中第三、四種方法與修正牛頓法的迭代步數(shù)和計(jì)算時(shí)間

同樣的，我們發(fā)現(xiàn)迭代步數(shù)相差不大的時(shí)候文中第三種方法也較修正牛頓法稍慢，而第四種稍快一點(diǎn).由此我們得出結(jié)論，初值條件離真解較遠(yuǎn)時(shí)，迭代步數(shù)較多，用文中第一、三方法更合適.而初值條件離真解較近時(shí)，迭代步數(shù)相差不多，用文中第二、四方法或者牛頓法與修正牛頓法更合適.下面我們來看看高階非線性方程組中四種方法的情形.

例2

由表15 我們可以得出類似的結(jié)論，即文中第一、三種方法加快了收斂速度，使得迭代步數(shù)相較傳統(tǒng)的Newton 法與修正Newton 法而言較少.而文中第二、四種方法在一、三方法的基礎(chǔ)上，從節(jié)省計(jì)算量的角度出發(fā)，雖然放慢了收斂速度，但同時(shí)加快了運(yùn)行速度.得出真解的速度比傳統(tǒng)的Newton 法與修正Newton 法更快.

表15 迭代步數(shù)和計(jì)算時(shí)間(文中四種方法r 均取1/2)