求解非线性方程组的新的信赖域方法①
2017-05-18唐江花
唐江花
(安徽新华学院通识教育部，安徽合肥230088)
求解非线性方程组的新的信赖域方法①
唐江花
(安徽新华学院通识教育部，安徽合肥230088)
通过将信赖域技巧与Levenberg-Marquardt算法有效结合到一起，进而提出新的信赖域方法，进而证明了新方法的全局收敛性，并且在局部误差界等条件下得到该算法的收敛阶为2δ2+δ,其中δ∈(1/2,1)并且给出了数值结果，在证明新方法的相关收敛性结果时，同时进行了数值实验，并验证了新的信赖域方法的可行性.
非线性方程，全局收敛性，新的依赖域方法
0 前言
考虑非线性方程组
F(x)=0，
(1)
其中F(x):Rn→Rm是连续可微的函数.文中定义X*作为F(x)的非空解集，‖·‖代表2-范数，F(x)具有非线性特点.
Levenberg-Marquardt(LM)方法[1-5]在求解非线性方程组的方法中是比较经典的一种方法，其迭代步为
(2)
将它当作是Guass-Newton方法的一种修正，将参数λk进行引入，进而克服Guass-Newton法中矩阵J(x*)必须满秩的要求.
Fang[6-8]两步牛顿法的启示下，同时为了节约雅克比矩阵的计算，提出了一种改进的LM算法(MLM)，该算法的提出，不仅可以对经典的LM步进行计算，还可以对近似LM步进行计算.
(3)
此种算法由于局部误差阶条件的原因拥有3阶收敛性.
与此同时，Yang[7]在文献[6]的基础之上，为了使雅克比矩阵的计算更加节约以及拥有更快的收敛速度，提出了一种高阶的LM算法(HMLM)，又添加了一步接近于LM步.
(4)
此种算法受到局部误差阶条件，拥有4阶收敛性.
Chen[9]为了可以有效地掌控步长，对Fan和Yank的研究思想进行整合后提出了一种高阶的修正LM算法.
(5)
受此启示，在求解非线性方程组时为了减少更多的Jacobi矩阵计算，本文将在文献[9]研究思想之上再增添一步近似LM步，
(6)
进而得出一种新的Levenberg-Marquardt算法.
1 非线性方程组的改进信赖域算法的提出
式(1)的目标函数为
Φ(x)=‖F(x)‖2.
(7)
提出了一个信赖域半径趋于0的信赖域算法.对于下面的子问题通过迭代进行求解.
(8)
得出试探步.
下文为文献[10]中的信赖域算法.
算法1 (1)设x1∈Rn,0
计算Δk+1=μk+1‖Fk+1‖δ.
(4)令k=k+1由此转到第二步.
此种算法是全局收敛的，它的收敛速度在局部误差有界的条件下为2δ.
本文提出的新的信赖域算法是在Levenberg-Marquardt方法的启示上所提出来的，新的信赖域算法在每次迭代中首先对下面的子问题进行求解
(9)
得到dk，令yk=xk+dk,进行求解
(10)
(11)
Predk=‖Fk‖2-‖Fk+Jkdk‖2+‖F(yk)‖2-‖F(yk)+Jkdk‖2，
(12)
而将实际下降量和预估下降量之间的比值rk定义为
(13)
新的信赖域的算法如下所示.
算法2 (1)设x1∈Rn,0
(14)
(3)取
(15)
计算
Δk+1=μk+1‖Fk+1‖δ.
(16)
(4)令k:=k+1并且转到第(2)步.
(17)
通过上面计算的结果得出下面的引理.设dk为式(9)的解，则预估下降量有如下估计
(18)
2 新Levenberg-Marquardt算法的全局收敛性的验证
接下来对新算法的全局收敛性进行讨论，为了得到全局收敛性结果，做出如下情形假设:
情形1F(x)是连续可微的，且F(x)和Jacobian矩阵J(x)是Lipschitz连续的，也就是说，存在正常数L1和L2使得
‖J(y)-J(x)‖≤L1‖y-x‖, ∀x,y∈Rn
(19)
和
‖F(y)-F(x)‖≤L2‖y-x‖, ∀x,y∈Rn.
(20)
定理1在假设情形1的条件下，由算法忍.忍产生的迭代序列满足
(21)
证明由情形1，我们可以得到
‖F(y)-F(x)-J(x)(y-x)‖≤L1‖y-x‖2, ∀x,y∈Rn.
(22)
我们用反证法证明.假设定理结论不正确，则存在一个正常数∈>0和无穷多个k使得
(23)
令I={k|rk≥c1)}.则有
(24)
由(19)和(20)知
(25)
第一种情况，若I有限，由式(17)知，对充分大的k有μk+1=c3μk.由于c3<1，我们得到
(26)
第二种情况，若r无限，则由(17)知
(27)
(28)
由于当k∉I时，c3<1且μk+1=c3μk.所以当I是无限时，这时式中式依旧成立.即
(29)
由‖Fk+1‖≤‖Fk‖,‖dk‖≤Δk且Δk=μk‖Fk‖δ,由式(7)和式(29)可以得到
(30)
此外，由式(8)和式(30)可得
(31)
=part1+part2+part3.
(32)
因此，由于part1和part2收敛到.，我们只需证明part3收敛到0.
由于
(33)
3 数值实验
表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] 路娜. 非线性方程组的改进信赖域算法[D].上海：上海交通大学,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
安徽省高等数学教学团队(2016jxtdx03)；安徽省高等数学名师工作室(2014msgzs168)；安徽新华学院第八批骨干教师培养对象(2015xgg29)；校级科研项目(2016zr003)资助
褚正清，E-mail：798116049@qq.com.
O
A
1672-6634(2017)01-0038-06
