求解非線性方程組的加速多步Levenberg-Marquardt算法

蘇晨誠(chéng)，陳 亮

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

求解非線性方程組的加速多步Levenberg-Marquardt算法

蘇晨誠(chéng)，陳 亮

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

求解非線性方程組時(shí)，為了節(jié)省Jacobi矩陣的計(jì)算，在信賴域中提出一種加速多步Levenberg-Marquardt算法，該算法在每次迭代時(shí)不僅計(jì)算了經(jīng)典的LM步，還使用先前計(jì)算過(guò)的Jacobi矩陣計(jì)算三步近似的LM步，節(jié)省了計(jì)算量，提高了計(jì)算效率，數(shù)值試驗(yàn)表明，該算法具有有效性.

非線性方程；Levenberg-Marquardt算法；全局收斂性；信賴域

0 引言

考慮非線性方程組

是連續(xù)可微的函數(shù).在本文中，定義X*是F(x)的非空解集，‖?‖表示2-范數(shù)，由于的非線性特征，問(wèn)題（1）可能沒(méi)有解.

Levenberg-Marquardt（LM）方法［1-5］是求解非線性方程組較為經(jīng)典的方法之一，其迭代步為

它可以看成是Guass-Newton方法的一種修正，通過(guò)引入一個(gè)參數(shù)λk來(lái)克服Guass-Newton法對(duì)于矩陣J(x*)必須滿秩的要求.

為了節(jié)約雅克比矩陣的計(jì)算，F(xiàn)an［6,8］受兩步牛頓法的啟發(fā)，提出了一種改進(jìn)的LM算法（MLM），該算法不僅計(jì)算經(jīng)典的LM步，還計(jì)算一步近似LM步

該算法在局部誤差階條件下具有3階收斂性.

相似地，為了節(jié)約更多的雅克比矩陣的計(jì)算以及得到更快的收斂速度，Yang［7］在文獻(xiàn)［6］的基礎(chǔ)上提出了一個(gè)高階的LM算法（HMLM），又增加了一步近似LM步

該算法在局部誤差階條件下具有4階收斂性.

Chen［9］為了控制步長(zhǎng)，在結(jié)合了Fan和Yang思路的基礎(chǔ)上，提出一種高階的修正LM算法受此啟發(fā)，為了在求解非線性方程組的過(guò)程中節(jié)約更多的Jacobi矩陣計(jì)算，本文將在文獻(xiàn)［9］思路的基礎(chǔ)上再增加一步近似LM步，

從而得到一種新的加速多步Levenberg-Marquardt算法.

1 加速多步Levenberg-Marquardt算法

首先，通過(guò)信賴域的方法給出新的加速多步LM算法，取

作為式（1）的優(yōu)值函數(shù)，定義Φ(x)的實(shí)際下降量為

文獻(xiàn)［6-8］已經(jīng)證明了式（2）—（4）成立

結(jié)合不等式（2）—（5）有

這意味著定義的預(yù)測(cè)下降量dk一直是非負(fù)的.

接下來(lái)，給出加速多步Levenberg-Marquardt算法：

算法1 加速多步Levenberg-Marquardt算法（NAMLM）

步驟1 給定x1∈Rn，ε≥0，u1＞m＞0，0＜p0≤p1≤p2＜1，k：=1.

可得dk，令yk=xk+dk.求解

步驟3 計(jì)算rk=Aredk/Predk，令

步驟4 取

令k=k+1，轉(zhuǎn)步驟2.

2 加速多步Levenberg-Marquardt算法的全局收斂性

在給出加速多步LM算法的全局收斂性之前，先給出下面一些假設(shè).

假設(shè)1 F(x)是連續(xù)可微的函數(shù)，F(xiàn)(x)和它的Jacobi矩陣是利普希茨連續(xù)的，因此，存在正常數(shù)L1和L2使得

和

由利普希茨條件可得

定理2 在假設(shè)3.1的條件下，加速多步Levenberg-Marquardt算法在有限迭代步將收斂并滿足

證明 利用反證法.設(shè)定理2不成立，則存在一個(gè)正數(shù)ε＞0，存在無(wú)限多k，使得

令T1，T2是如下指標(biāo)集

很容易得到T1指標(biāo)集是無(wú)限集，接下來(lái)考慮T2指標(biāo)集是有限集還是無(wú)限集.

情形1T2是有限集，則集合也是有限集，令是T3中最大的指標(biāo)，則當(dāng)時(shí)，有xk+1=xk.定義集合

由（9）式知

因此，由（8）式、（10）式及以上4個(gè)不等式可得

這意味著rk→1，隨著 μk的更新知，當(dāng)k充分大時(shí)，存在一個(gè)正常數(shù)＞m使得 μk＜，這與（13）式矛盾.所以當(dāng)T2為有限集時(shí)，假設(shè)不成立.

情形2 T2是無(wú)限集，由（6）式和（9）式知

意味著

根據(jù)dk的定義，有

通過(guò)（8）式，（9）式和（14）—（16）式知

與情形1同理可得rk→1，因此當(dāng)k充分大時(shí)，存在一個(gè)正常數(shù)＞m使得μk＜，這與（19）式矛盾.

3 數(shù)值試驗(yàn)

本節(jié)將通過(guò)計(jì)算一些非奇異問(wèn)題來(lái)測(cè)試算法1（NAMLM），并將其與經(jīng)典LM算法，F(xiàn)an［8］提出的AMLM算法以及Chen［9］提出的NMLM算法進(jìn)行比較.

下面的問(wèn)題是由More等［10］給出的，該問(wèn)題是通過(guò)非奇異問(wèn)題的修正得來(lái)的，并具有如下形式［11］：

其中F(x)是標(biāo)準(zhǔn)的非奇異函數(shù)，x*是它的根，并且A∈Rn×k是滿列秩，1≤k≤n.顯然，(x*)=0并且秩為n-k，該問(wèn)題的一個(gè)缺點(diǎn)是的根有可能不是的根.本文選擇的秩分別為n-1和n-2.

設(shè) p0=0.000 1，p1=0.25，p2=0.75，μ1=10-5，算法的停止條件是或者是迭代次數(shù)超過(guò)100（n+1），在表1和表2中，第3列表示初始點(diǎn)是x0，10x0，100x0，其中x0是由More等［10］給出的.“NF”和“NJ”分別表示函數(shù)的計(jì)算量和Jacobi矩陣的計(jì)算量，“NF+NJ*n”表示所有的計(jì)算量，因?yàn)镴acobi矩陣的計(jì)算量通常是函數(shù)計(jì)算量的n倍，如果迭代次數(shù)超過(guò)100（n+1），用“-”表示.“OF”表示迭代是向上溢出或向下溢出的.

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

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

從表1和表2中可以看出，算法1總是優(yōu)于或相似于LM算法、AMLM算法與NMLM算法，盡管函數(shù)的計(jì)算量多，但是算法1節(jié)約大量的Jacobi矩陣的計(jì)算，該算法在現(xiàn)實(shí)生活中很有用，特別是對(duì)于大規(guī)模非線性問(wèn)題來(lái)說(shuō).

4 結(jié)論

本文在求解非線性方程組的過(guò)程中，為了節(jié)約Jacobi矩陣的計(jì)算以及達(dá)到更高的收斂性，提出一種加速多步LM算法，該算法每步迭代不僅計(jì)算了LM步也近似計(jì)算了三步近似LM步，新的LM算法節(jié)約了更多的Jacobi矩陣的計(jì)算，對(duì)于大規(guī)模問(wèn)題，該算法要比LM算法、AMLM算法以及NMLM算法具有更好的表現(xiàn)形式.

［1］LEVENBERG K.A method for the solution of certain non-linear problems in least squares［J］.Quarterly of Applied Mathmatics，1944，2（1）：164-168.

［2］MARQUARDT D W.An algorithm for least-squares estimation of nonlinear parameters［J］.Journal of the Society for Industrial and Applied Mathematics，1963，11：431-441.

［3］MORé J J.The Levenberg–Marquardt algorithm［C］//Lecture Notes in Mathematics，1977，11（1）：101-110.

［4］MORé J J.Recent developments in algorithms and software for trust region methods［M］.Springer Berlin：Mathematical Programming the State of the Art，1982：258-287.

［5］CHEN Liang.A high-order modified Levenberg-Marquardt method for systems of nonlinear equations with fourth-order convergence［J］.Applied Mathematics and Computation，2016，24：78-83.

［6］FAN Jinyan.The modified Levenberg-Marquardt method for nonlinear equations with cubic convergence［J］.Mathematics of Computation，2012，81（277）：447-466.

［7］YANG Xiao.A higher-order Levenberg–Marquardt method for nonlinear equations［J］.Applied Mathematics&Computation，2013，219（7）：10682-10694.

［8］FAN Jinyan.Accelerating the modified Levenberg-Marquardt method for nonlinear equations［J］.Mathematics of Computation，2014，83：1173-1187.

［9］CHEN Liang.A modified Levenberg-Marquardt method with line search for nonlinear equations［J］.Computational Optimization&Applications，2016，65（3）：1-27.

［10］MORé J J，GARBOW B S，HILLSTROM K E.Testing unconstrained optimization software［J］.ACM Transactions on Mathematical Software，1981，7（1）：17-41．

［11］SCHNABEL R B，F(xiàn)RANK P D.Tensor methods for nonlinear equations［J］.Siam Journal on Numerical Analysis，1984，21（5）：815-843.

An Accelerating Multistep Levenberg-Marquardt Method for System of Nonlinear Equations

SU Chencheng，CHEN Liang
（School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China）

In this paper，we present an accelerating multistep Levenberg-Marquardt（NAMLM）method for system of nonlinear equations to save more Jacobian calculations.At every iteration，not only LM step but also three approximate LM steps，which used the previous calculated Jacobian，are computed.The global convergence is given by the trust region technique.Numerical result shows that the accelerating multistep LM algorithm performs very well and save many Jacobian calculations.

nonlinear equations；Levenberg-Marquardt method；global convergence；trust region

O 221.1

A

2095-0691（2017）01-0024-07

2016-09-29

國(guó)家自然科學(xué)基金項(xiàng)目（61300048）；安徽省自然科學(xué)基金資助項(xiàng)目（1508085MA14）；安徽省高校優(yōu)秀青年人才支持計(jì)劃；安徽省高等教育振興計(jì)劃重大教學(xué)改革研究項(xiàng)目（2014ZDJY058）；安徽省省級(jí)質(zhì)量工程項(xiàng)目（2014JYXM161，2015JYXM157）；淮北師范大學(xué)校級(jí)質(zhì)量工程項(xiàng)目（2015ZYJS185，JY15118）

蘇晨誠(chéng)（1991- ），女，安徽合肥人，碩士生，研究方向?yàn)閿?shù)值最優(yōu)化.通信作者：陳 亮（1977- ），男，江蘇射陽(yáng)人，博士，副教授，研究方向?yàn)閿?shù)值最優(yōu)化.