求解非線性方程組的新的信賴域方法①

唐江花

(安徽新華學(xué)院通識(shí)教育部，安徽合肥230088)

求解非線性方程組的新的信賴域方法①

唐江花

(安徽新華學(xué)院通識(shí)教育部，安徽合肥230088)

通過將信賴域技巧與Levenberg-Marquardt算法有效結(jié)合到一起，進(jìn)而提出新的信賴域方法，進(jìn)而證明了新方法的全局收斂性，并且在局部誤差界等條件下得到該算法的收斂階為2δ2+δ,其中δ∈(1/2,1)并且給出了數(shù)值結(jié)果，在證明新方法的相關(guān)收斂性結(jié)果時(shí)，同時(shí)進(jìn)行了數(shù)值實(shí)驗(yàn)，并驗(yàn)證了新的信賴域方法的可行性.

非線性方程，全局收斂性，新的依賴域方法

0 前言

考慮非線性方程組

F(x)=0，

(1)

其中F(x):Rn→Rm是連續(xù)可微的函數(shù).文中定義X*作為F(x)的非空解集，‖·‖代表2-范數(shù)，F(xiàn)(x)具有非線性特點(diǎn).

Levenberg-Marquardt(LM)方法[1-5]在求解非線性方程組的方法中是比較經(jīng)典的一種方法，其迭代步為

(2)

將它當(dāng)作是Guass-Newton方法的一種修正，將參數(shù)λk進(jìn)行引入，進(jìn)而克服Guass-Newton法中矩陣J(x*)必須滿秩的要求.

Fang[6-8]兩步牛頓法的啟示下，同時(shí)為了節(jié)約雅克比矩陣的計(jì)算，提出了一種改進(jìn)的LM算法(MLM)，該算法的提出，不僅可以對經(jīng)典的LM步進(jìn)行計(jì)算，還可以對近似LM步進(jìn)行計(jì)算.

(3)

此種算法由于局部誤差階條件的原因擁有3階收斂性.

與此同時(shí)，Yang[7]在文獻(xiàn)[6]的基礎(chǔ)之上，為了使雅克比矩陣的計(jì)算更加節(jié)約以及擁有更快的收斂速度，提出了一種高階的LM算法(HMLM)，又添加了一步接近于LM步.

(4)

此種算法受到局部誤差階條件，擁有4階收斂性.

Chen[9]為了可以有效地掌控步長，對Fan和Yank的研究思想進(jìn)行整合后提出了一種高階的修正LM算法.

(5)

受此啟示，在求解非線性方程組時(shí)為了減少更多的Jacobi矩陣計(jì)算，本文將在文獻(xiàn)[9]研究思想之上再增添一步近似LM步，

(6)

進(jìn)而得出一種新的Levenberg-Marquardt算法.

1 非線性方程組的改進(jìn)信賴域算法的提出

式(1)的目標(biāo)函數(shù)為

Φ(x)=‖F(xiàn)(x)‖2.

(7)

提出了一個(gè)信賴域半徑趨于0的信賴域算法.對于下面的子問題通過迭代進(jìn)行求解.

(8)

得出試探步.

下文為文獻(xiàn)[10]中的信賴域算法.

算法1 (1)設(shè)x1∈Rn,00，M》C4μ1,Δ1=‖F(xiàn)1‖δ,k:=1.

計(jì)算Δk+1=μk+1‖F(xiàn)k+1‖δ.

(4)令k=k+1由此轉(zhuǎn)到第二步.

此種算法是全局收斂的，它的收斂速度在局部誤差有界的條件下為2δ.

本文提出的新的信賴域算法是在Levenberg-Marquardt方法的啟示上所提出來的，新的信賴域算法在每次迭代中首先對下面的子問題進(jìn)行求解

(9)

得到dk，令yk=xk+dk,進(jìn)行求解

(10)

(11)

Predk=‖F(xiàn)k‖2-‖F(xiàn)k+Jkdk‖2+‖F(xiàn)(yk)‖2-‖F(xiàn)(yk)+Jkdk‖2，

(12)

而將實(shí)際下降量和預(yù)估下降量之間的比值rk定義為

(13)

新的信賴域的算法如下所示.

算法2 (1)設(shè)x1∈Rn,00，M》C4μ1,Δ1=μ1‖F(xiàn)1‖δ,k:=1.

(14)

(3)取

(15)

計(jì)算

Δk+1=μk+1‖F(xiàn)k+1‖δ.

(16)

(4)令k:=k+1并且轉(zhuǎn)到第(2)步.

(17)

通過上面計(jì)算的結(jié)果得出下面的引理.設(shè)dk為式(9)的解，則預(yù)估下降量有如下估計(jì)

(18)

2 新Levenberg-Marquardt算法的全局收斂性的驗(yàn)證

接下來對新算法的全局收斂性進(jìn)行討論，為了得到全局收斂性結(jié)果，做出如下情形假設(shè):

情形1F(x)是連續(xù)可微的，且F(x)和Jacobian矩陣J(x)是Lipschitz連續(xù)的，也就是說，存在正常數(shù)L1和L2使得

‖J(y)-J(x)‖≤L1‖y-x‖, ?x,y∈Rn

(19)

和

‖F(xiàn)(y)-F(x)‖≤L2‖y-x‖, ?x,y∈Rn.

(20)

定理1在假設(shè)情形1的條件下，由算法忍.忍產(chǎn)生的迭代序列滿足

(21)

證明由情形1，我們可以得到

‖F(xiàn)(y)-F(x)-J(x)(y-x)‖≤L1‖y-x‖2, ?x,y∈Rn.

(22)

我們用反證法證明.假設(shè)定理結(jié)論不正確，則存在一個(gè)正常數(shù)∈>0和無窮多個(gè)k使得

(23)

令I(lǐng)={k|rk≥c1)}.則有

(24)

由(19)和(20)知

(25)

第一種情況，若I有限，由式(17)知，對充分大的k有μk+1=c3μk.由于c3<1，我們得到

(26)

第二種情況，若r無限，則由(17)知

(27)

(28)

由于當(dāng)k?I時(shí)，c3<1且μk+1=c3μk.所以當(dāng)I是無限時(shí)，這時(shí)式中式依舊成立.即

(29)

由‖F(xiàn)k+1‖≤‖F(xiàn)k‖,‖dk‖≤Δk且Δk=μk‖F(xiàn)k‖δ,由式(7)和式(29)可以得到

(30)

此外，由式(8)和式(30)可得

(31)

=part1+part2+part3.

(32)

因此，由于part1和part2收斂到.，我們只需證明part3收斂到0.

由于

(33)

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

表1 r(J(x*))=n-1

[1]LevenbergK.Amethodforthesolutionofcertainnon-linearproblemsinleastsquares[J].QuarterlyofAppliedMath-matics，1944,2(1):164-168.

[2]MarquardtDW.Analgorithmforleast-squaresestimationofnonlinearparameters[J].JournaloftheSocietyforIn-dustrialandAppliedMathematics，1963，11:431-441.

[3]MoreJJ.TheLevenherg-Marquardtalgorithm[C].//LectureNotesinMathematics，1977，11(1):101-110.

[4]MoreJJ.Recentdevelopmentsinalgorithmsandsoftwarefortrustregionmethods[M].SpringerBerlin:MathematicalProgrammingtheStateoftheArt, 1982.

[5]ChenLiang.Ahigh-ordermodifiedLevenherg-Marquardtmethodforsystemsofnonlinearequationswithfourth-orderConvergence[J].AppliedMathematicsandComputation,2016,24:78-83.

[6]FanJinyan.ThemodifiedLevenherg-Marquardtmethodfornonlinearequationswithcubicconvergence[J].MathematicsofComputation,2012,81(277):447-466.

[7]YangXiao.Ahigher-orderLevenherg-Marquardtmethodfornonlinearequations[J].AppliedMathematics&Computa-tion, 2013，219(7):10 682-10 694.

[8]FanJinyan.AcceleratingthemodifiedLevenherg-Marquardtmethodfornonlinearequations[J].MathematicsofComputa-tion,2014,83:1 173-1 187.

[9]ChenLiang.AmodifiedLevenherg-Marquardtmethodwithlinesearchfornonlinearequations[J].ComputationalOptimi-zation&Applications,2016,65 (3):1-27.

[10]FanJY.ConvergenceRateofTheTrustRegionMethodforNonlinearEquationsUnderLocalErrorBoundCondition,COAP,2006，34:215-227

[11]FanJY.AmodifiedLevenberg-Marquardtalgorithmforsingularsystemofnonlinearequations[J].JournalofComputationalMathematics, 2003,21:625-636

[12]FanJinyan.AcceleratingthemodifiedLevenherg-Marquardtmethodfornonlinearequations[J].MathematicsofComputa-tion, 2014,83:1 173-1 187.

[13]ChenLiang.AmodifiedLevenherg-Marquardtmethodwithlinesearchfornonlinearequations[J].ComputationalOptimi-zation&Applications,2016,65(3):1-27.

[14]MoreJJ,GarbowBS,HillstromKE.Testingunconstrainedoptimizationsoftware[J].ACMTransactionsonMathematicalSoftware，1981,7(1):17-41

[15]SchnabelRB,FrankPD.Tensormethodsfornonlinearequations[J] .SiamJournalonNumericalAnalysis，1984,21(5):815-843.

[16] 路娜. 非線性方程組的改進(jìn)信賴域算法[D].上海：上海交通大學(xué),2014.

The New Trust Region Method for Solving the System of Nonlinear Equations

TANG Jiang-hua

(Department of General Education, Anhui Xinhua University, Hefei 230088，China)

Through the combine of the new trust region technique and Levenberg-Marquardt algorithm together, it put forward a new trust region method. It proved that the global convergence of the new method, and under the local error bound condition it obtained the convergence order of the algorithm 2δ2+δ,andδ∈(1/2,1),andthenumericalresultsarepresented.Itnotonlyprovedtherelevantconvergenceresultsofthenewmethod,butalsogavethenumericalexperiments,andverifiedthefeasibilityofthenewtrustregionmethod.

nonlinear equation，global convergence，new domain dependent method

2016-11-06

安徽省高等數(shù)學(xué)教學(xué)團(tuán)隊(duì)(2016jxtdx03)；安徽省高等數(shù)學(xué)名師工作室(2014msgzs168)；安徽新華學(xué)院第八批骨干教師培養(yǎng)對象(2015xgg29)；校級科研項(xiàng)目(2016zr003)資助

褚正清，E-mail：798116049@qq.com.

O

A

1672-6634(2017)01-0038-06