蘇晨誠，陳 亮

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

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

蘇晨誠，陳 亮

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

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

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

0 引言

考慮非線性方程組

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

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

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

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

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

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

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

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

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

1 加速多步Levenberg-Marquardt算法

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

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

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

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

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

接下來，給出加速多步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 計算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不成立，則存在一個正數(shù)ε＞0，存在無限多k，使得

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

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

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

由（9）式知

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

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

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

意味著

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

通過（8）式，（9）式和（14）—（16）式知

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

3 數(shù)值試驗

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

下面的問題是由More等［10］給出的，該問題是通過非奇異問題的修正得來的，并具有如下形式［11］：

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

設(shè) p0=0.000 1，p1=0.25，p2=0.75，μ1=10-5，算法的停止條件是或者是迭代次數(shù)超過100（n+1），在表1和表2中，第3列表示初始點是x0，10x0，100x0，其中x0是由More等［10］給出的.“NF”和“NJ”分別表示函數(shù)的計算量和Jacobi矩陣的計算量，“NF+NJ*n”表示所有的計算量，因為Jacobi矩陣的計算量通常是函數(shù)計算量的n倍，如果迭代次數(shù)超過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ù)的計算量多，但是算法1節(jié)約大量的Jacobi矩陣的計算，該算法在現(xiàn)實生活中很有用，特別是對于大規(guī)模非線性問題來說.

4 結(jié)論

本文在求解非線性方程組的過程中，為了節(jié)約Jacobi矩陣的計算以及達(dá)到更高的收斂性，提出一種加速多步LM算法，該算法每步迭代不僅計算了LM步也近似計算了三步近似LM步，新的LM算法節(jié)約了更多的Jacobi矩陣的計算，對于大規(guī)模問題，該算法要比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

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

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