一種基于病態(tài)問題的修正牛頓法

一種基于病態(tài)問題的修正牛頓法

王小朋,劉翔峰

(武漢理工大學(xué) 理學(xué)院，湖北 武漢 430070)

摘要：針對初值在真解附近，由牛頓法得到的最終迭代結(jié)果遠(yuǎn)離真值的這一類病態(tài)問題,在對已有修正牛頓法進行研究的基礎(chǔ)上，通過引入一個控制參數(shù)提出了一種新的修正牛頓法。進一步在完備的賦范線性空間中給出該修正牛頓法的收斂性證明與誤差估計。最后，數(shù)值實驗結(jié)果表明了這種新的修正牛頓法的有效性以及在收斂速度上的優(yōu)越性。

關(guān)鍵詞：完備的賦范線性空間；牛頓法；病態(tài)問題；Frechet可微

基金項目：國家自然科學(xué)基金項目(11201357)

作者簡介：王小朋(1989-),男,山西汾陽人,碩士生，主要研究方向為最優(yōu)化理論與應(yīng)用.

收稿日期：2014-04-11

文章編號：1672-6871(2015)01-0086-06

中圖分類號：O241.6

文獻標(biāo)志碼：A

0引言

眾所周知，無論是求解優(yōu)化問題還是方程組問題，牛頓法都是一種最為常見的有效算法。但是牛頓法在每一次迭代的過程中不僅需要n2個偏導(dǎo)數(shù)，而且還要Hesse矩陣的逆。為了克服牛頓法計算量大的缺陷，許多學(xué)者對牛頓法進行了一系列的改進，例如簡化的牛頓法、薩馬斯基技巧、阻尼牛頓法、牛頓下山法、離散的牛頓法、割線法、修正牛頓法[1-6]等。縱觀牛頓法的這些改進，其優(yōu)勢在于：第一，減少了原來牛頓法的計算量；第二，防止牛頓法在某一步迭代過程中出現(xiàn)偏導(dǎo)數(shù)不存在或Hesse矩陣奇異；第三，能夠解決初值在真解附近，但是牛頓法所得的最終迭代結(jié)果卻遠(yuǎn)離真值的這一類病態(tài)問題。對于這一類病態(tài)問題，就目前的研究現(xiàn)狀而言，其研究成果相對較少。文獻[1]雖然給出了一種求解這一類病態(tài)問題的修正牛頓法，但是仔細(xì)研究其算法證明和數(shù)值實驗，發(fā)現(xiàn)該算法在收斂性證明過程中較為復(fù)雜，當(dāng)取τk=2-k時算法收斂速度不是很快。本文將在原有修正牛頓法[1]的基礎(chǔ)上，通過限制牛頓方向與引入控制參數(shù)相結(jié)合的方式來探討這一病態(tài)問題的求解方法，從而給出一種新的修正牛頓法。

1迭代形式與算法

首先給出求解方程組g(x)=0的修正牛頓法迭代形式

(1)

對于上述提到的這一類病態(tài)問題可知：傳統(tǒng)的牛頓法是失效的，但是添加修正項之后的牛頓法[1-2]卻是收斂的。就牛頓法的迭代格式而言，可知式(1)中的

分別表示傳統(tǒng)牛頓法的方向與修正牛頓法的方向。由優(yōu)化理論知識可知：對于上述兩種算法之所以出現(xiàn)兩種相反結(jié)果的原因，可能是傳統(tǒng)牛頓法的方向問題導(dǎo)致了算法出現(xiàn)病態(tài)，而添加修正項之后的牛頓法，正是由于對方向進行了適當(dāng)?shù)男拚龔亩玫搅讼喾吹氖諗拷Y(jié)果。下文將在上述分析的基礎(chǔ)上通過修正牛頓方向與引入?yún)?shù)相結(jié)合的方式，提出一種新的修正牛頓法來克服文獻[1-2]中牛頓法的缺陷。

算法

步驟2利用迭代式

來求出x1。

2算法的收斂性分析

本節(jié)將在完備的賦范線性空間中給出算法1的收斂性證明。在此證明之前，首先給出完備的賦范線性空間中一些常用的定理。

引理1壓縮映射原理[7]：設(shè)D為完備的賦范線性空間B中的非空閉子集，g:D→D是壓縮的，即對任意的x,y∈D都有

則存在唯一的x*∈D，使得gx*=x*，即T在D內(nèi)存在唯一的不動點x*。

引理2Lagrange中值定理[8]：設(shè)X,Y分別為兩個完備的賦范線性空間，A?X，B?A，如果算子g:A→Y在B上是Frechet可微的，則存在λ∈(0,1)，使得

引理3設(shè)X,Y分別為兩個完備的實賦范線性空間，G為B(X,Y)中所有有界逆算子全體組成的一個集合，如果A∈G，且對于B(X,Y)中的元素B滿足

則有[5]B∈G，并有

引理4設(shè)X,Y分別為兩個完備的賦范線性空間，A為X中的連通開集，B?Y，且g為從A到B中的可微算子，則當(dāng)x∈A時，對于任意使得x+△x∈A的△x都有[9]

定理1設(shè)X,Y分別為兩個實的完備賦范線性空間，算子g:B(x0,r)?X→Y是Frechet可微的，并假設(shè)：

則方程g(x)=0在B(x0,r)中存在唯一解x*，且該修正牛頓法的迭代形式

(2)

收斂于x*，誤差估計為：

證明首先證明當(dāng)x∈B(x0,r)時，g′(x)-1存在且有界。

由假設(shè)條件(Ⅱ)可知：當(dāng)x∈B(x0,r)時，

由引理3知：當(dāng)x∈B(x0,r)時，g′(x)-1存在有界且滿足

及

其次，用第二數(shù)學(xué)歸納法來證，式(2)產(chǎn)生的序列{xn}都在B(x0,r)中而且還是收斂的。

(Ⅰ)顯然x0在B(x0,r)中，下證x1也在B(x0,r)中。

由g′(xk)=g′(xk-1)+g′(xk)-g′(xk-1)可知：

g′(xk)=g′(xk-1)[I+g′(xk-1)-1(g′(xk)-g′(xk-1))]，

即

g′(xk)-1=g′(xk-1)-1[I-(g′(xk)-g′(xk-1))g′(xk)-1]。

對上述等式兩邊同取范數(shù)并利用假設(shè)條件(Ⅱ)可得：

ak≤ak-1(1-Lαk-1ak-1)-1=ak-1(1-ηk-1)-1。

當(dāng)k=1時，

由假設(shè)條件(Ⅱ)可得:

且

故當(dāng)k=1時，結(jié)論顯然成立。

假設(shè)當(dāng)k=2,3,…,n-1時，結(jié)論都成立，下證當(dāng)k=n時，結(jié)論也成立。

‖g′(xn)-1(g(xn)-g(xn-1)-g′(xn-1)(xn-xn-1))+

故

(3)

綜上所述，迭代式(2)產(chǎn)生的序列{xn}都在B(x0,r)中，且收斂。

再次，證明序列{xn}的極限x*是方程g(x)=0在B(x0,r)中的唯一解。

由g(x)的連續(xù)性以及迭代式(2)可知：g(x*)=0，故x*為方程g(x)=0在B(x0,r)中的解。下證解的唯一性。

最后，證明誤差估計不等式。

在不等式(3)兩端同時令p→∞，則有：

3數(shù)值試驗

本節(jié)采用文獻[1-2,8，10]中的3個數(shù)值算例來說明所提算法是可行有效的，并將所求結(jié)果與文獻[1-2,8，10]中算法的數(shù)值結(jié)果進行對比，說明本文所提出的算法的收斂速度比文獻[1-2]中提出的算法的收斂速度快。在進行數(shù)值試驗過程中為方便計算，在算法的步驟3中取ε=10-10。

算例1

表1　算例1的數(shù)值結(jié)果

取與文獻[1-2]中相同的初始值x0=(1,0)′，相同的迭代終止準(zhǔn)則為10-10，其中，x0為迭代的初始點。

算例2

文獻[1-2,8]中給出了該算例的真解為x*=(0.3,2.8)′。用本文所給算法來計算算例2，相應(yīng)的數(shù)值結(jié)果如表2所示。

表2　算例2的數(shù)值結(jié)果

取與文獻[1-2]中相同的初始值x0=(0.1,0.1)′，相同的迭代終止準(zhǔn)則10-10。

文獻[1-2,8]的數(shù)值結(jié)果：取初始值x0=(0.1,0.1)′，當(dāng)ξ=(0.4，2.9)T時,迭代次數(shù)為32，方程g2(x)=0的解為xk+1=(0.299 4，2.836 9)T；當(dāng)ξ=(0.5，3.3)T時,迭代次數(shù)為32，方程g2(x)=0的解為xk+1=(0.500 0，3.141 6)T，顯然不是原問題的解。

算例3

文獻[1-2,8,10]中給出了該算例的真解為x*=(0.7,0.7)′。用本文所給算法來計算算例3，相應(yīng)的數(shù)值結(jié)果如表3所示。

表3　算例3的數(shù)值結(jié)果

取與文獻[1-2]中相同的初始值x0=(0.1,0.1)′，相同的迭代終止準(zhǔn)則為10-10。

文獻[1-2,8,10]的數(shù)值結(jié)果：取初始值x0=(0.1,0.1)′，當(dāng)ξ=(0.9，0.9)T時,迭代次數(shù)為33，方程g3(x)=0的解為xk+1=(0.700 0，0.700 0)T；當(dāng)ξ=(1.2，1.2)T時,迭代次數(shù)為34，方程g3(x)=0的解為xk+1=(0.700 0，0.700 0)T；當(dāng)ξ=(2.3，2.3)T時,迭代次數(shù)為36，方程g3(x)=0的解為xk+1=(0.700 0，0.700 0)T。

4結(jié)論

本文研究了初值在真解附近，但牛頓法最終迭代結(jié)果遠(yuǎn)離真值的一類病態(tài)問題，提出了一種新的修正牛頓法，在完備的賦范線性空間中證明了算法的有效性。數(shù)值試驗結(jié)果表明：該算法是可行而且有效的。

參考文獻：

[1]晁玉翠,韓波.求解非線性方程組的修正牛頓法研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2007.

[2]馬元婧,韓波.非線性方程組的一種修正牛頓法及其連續(xù)型[D].哈爾濱:哈爾濱工業(yè)大學(xué),2009.

[4]Francisco F,Andreas F,Markus H.An LP-Newton Method:Nonsmooth Equations,KKT Systems,and Nonisolated Solutions[J].Mathematical Programming,2013:DOI:10.1007/s10107-013-0676-6.

[5]Zhou F Q.An Analysis on Local Convergence of Inexact Newton-Gauss Method for Solving Singular Systems of Equations[J].The Scientific World Journal,2014:752673.

[6]Du S Q.Generalized Newton Method for a Kind of Complementarity Problem[J].Abstract and Applied Analysis,2014,2014:745981.

[7]時寶,王興平,蓋明久,等.泛函分析引論及其應(yīng)用[M].北京:國防工業(yè)出版社,2009.

[8]Han B,Zhang D L,Liu J Q.A New Class of Methods for Solving Nonlinear Equations[J].J Comput Appl Math,1994,51:107-111.

[9]蹇人宜.應(yīng)用數(shù)學(xué)中的泛函分析[M].北京:科學(xué)出版社,2013.

[10]Tewarson R P.Use of Smoothing and Damping Techniques in the Solution of Nonlinear Nonlinear Equations[J].SIAM Rev,1977,1:35-45.