第46卷第4期2020年12月
延边大学学报(自然科学版)
J o u r n a l o fY a n b i a nU n i v e r s i t y (
N a t u r a l S c i e n c e )V o l .46N o .4
D e c .2020
收稿日期:20200928 *通信作者：陈亮(1977 )，男，博士，教授，研究方向为数值最优化和数值代数.基金项目：安徽省高校优秀青年骨干人才国外访问研修项目(G X GW F X 2019022)
；安徽省高校自然科学研究项目(K J 2020Z D 008,K J 2019A 0604)；安徽省省级质量工程项目(2019MO O C 158
)文章编号:1004-4353(2020)04-0302-07
一种改进的求解非线性方程组的
L e v e n b e r g -M a r q
u a r d t 方法伍珍香, 陈亮*, 周童
(淮北师范大学数学科学学院，安徽淮北235000)
摘要：通过修改L e v e n b e r g -M a r q u a r d t 参数，得到了一种改进的求解非线性方程组的L e v e n b e r g -M a r q u a r d t 算法.利用信赖域技术，在不必假设雅克比矩阵非奇异的局部误差界条件下，证明了该算法至少具有超线性收敛性.数值实验表明，该算法能有效求解非线性方程组问题.关键词：非线性方程组；局部误差界；二次收敛;L e v e n b e r g - M a r q u a r d t 中图分类号:O 221.1 文献标识码:A
An e w m o d i f i e dL e v e n b e r g -M a r q u a r d tm e t h o d f o r s y s t e m s o f n o n l i n e a r e q
u a t i o n s WUZ h e n x i a n g , C H E N L i a n g *
, Z HO U T o n g
(S c h o o l o f M a t h e m a t i c a lS c i e n c e s ,H u a i b e iN o r m a lU n i v e r s i t y ,H
u a i b e i 235000,C h i n a )A b s t r a c t :B y m o d i f y i n g t h e L e v e n b e r g -M a r q u a r d t p a r a m e t e r s ,w e o b t a i n a n e w c o n v e r g e n t L e v e n b e r g -M a r q u a r d t a l g o r i t h mf o r s o l v i n g t h e s y s t e m s o f n o n l i n e a r e q u a t i o n s .B y u s i n g t r u s t r e g i o n t e c h n i q
u e ,u n d e r t h e c o n d i t i o no f l o c a l e r r o rb o u n d s ,t h ec o n v e r g e n c eo f t h en e w L e v e n b e r g -M a r q u a r d tm e t h o d i ss h o w nt ob ea t l e a s t s u p e r l i n e a r l y w i t h o u t t h e n o n -s i n g u l a r i t y a s s u m p t i o no f t h e J a c o b im a t r i x .N u m e r i c a l e x p e r i m e n t s s h o w t h a t t h en e wa l g o r i t h mc a n s o l v en o n l i n e a r e q u a t i o n s e f f e c t i v e l y .K e y w o r d s :s y s t e m s o f n o n l i n e a re q u a t i o n s ;l o c a le r r o r b o u n d c o n d i t i o n ;l o c a lc o n v e r g e n c e ;L e v e n b e r g -
M a r q
u a r d t 0 引言
本文考虑如下非线性方程组
F (x )=0(1
)
的求解，其中F (x )ʒR n ңR n
是连续可微函数.
在本文中总假设方程(1)的解集为非空，记为X *，且㊃表示2范数.牛顿法是解方程组(1
)的一个较为有效的方法，该方法在每次迭代中使用的搜索方向为 d N k =-J -1k F k . (2
)其中F k =F (x k ),J k (J k =F ᶄ(x k ))是F (x )在x k 处的雅克比矩阵.当J (x )矩阵为L i p s h i t z 连续且为非奇异时，牛顿法产生的迭代点列二阶收敛于方程组(1)的解；但当J k 是奇异矩阵或者接近于奇异时,
牛
第4期伍珍香，等：一种改进的求解非线性方程组的L e v e n b e r g -M a r q u a r d t 方法顿步(2)无意义，即此时牛顿法不再适用.为此,L e v e n b e r g 和M a r q
u a r d t 提出了解决上述问题的一个有效方法 L e v e n b e r g -M a r q u a r d t 方法(简称L M 方法)[1-2
].L M 方法的试探步为 d k =-(J T k J k +λk I )-1J T k
F k ,(3
)其中λk (λk >0)是迭代参数.由式(3)显然可知：当λk =0且J k 为非奇异矩阵时，式(3)中的试探步d k
等价于牛顿步(2)；当J (x )在解为非奇异且L i p s h i t z 连续时,L M 法同样具有二阶收敛性.研究表明，迭代参数λk 的选取对L M 方法的收敛性具有重要作用.例如：取λk =F (
x k )2时,L M 法在局部误差界的条件约束下具有二阶收敛性[3]
.当采用信赖域技术且取λk =μ
k F (x k )时,L M 法在局部误差界的条件约束下具有局部二阶收敛性；但该选取在x k 远离解集时，因F k 较大,
因此此时L M 法的计算效率较低[4].取λk =μk F k 1+F k 时,L M 法在不必假设J k 为非奇异的局部误差界的条件约束下具有二阶收敛性, 并且可有效减小因x k 远离解集时F k 较大所产生的影响
通俗唱法的特点
[5
].为了节省雅克比矩阵的计算量，文献[6-8
]的作者还提出了多步迭代的方法，该方法有效地提高了计算效率.为了讨论L M 参数的取值范围，受文献[5]的启发，本文令λk =
μk F k δ1+F k
δ
,δɪ(0,2].显然，由该式可知当x k 远离解集时,F k 较大,
F k δ
1+F k
δ
趋近于1,λk 接近于μk ；当x k 接近于解集时,F k 趋向于0,λk 接近于μk F k
δ
.
定义价值函数ϕ(x )=F (x )2，则该函数在第k 次迭代的预测下降量(P r e d k )和实际下降量
(A r e d k )可定义为如下形式:
A r e d k =k
2
-F (x k +d k )2
,P r e d k =F k
2
-F k +J k
d k 2
.
(4
)其中d k 由式(3)得到，其比率为r k =A r e d k
P r e d k
.r k 决定是否接受步长d k ，以及用于调整新参数μk 的大小.
K.Am i n i 等[5]
研究发现,
采用非单调策略的算法比采用单调策略的算法效率更高，因此可将实际下降量表示为
췍A r e d k =F 2l (k )-F (x k +d k )2.
(5)其中
F l (k )=m a x 0ɤj ɤn (k
)
k -}{j ,(6
)k =0,1,2, ,n ;n (k )=m
i n N 0,}{k ,N 0是一个正整数.由式(6)可知，实际下降量的改变使得每次迭代得到的新点都与前n (k )次迭代中的最差的点进行比较，从而影响比率췍r k :
췍r k =
췍A r e d k
P r e d k
.(7
)1 算法
新修正的L M 法(算法1
)的计算步骤如下：步骤1 起始点x 0ɪR n
苏州娱乐场所整顿2019
，参数N 0>0,μ
0>m >0,ε>0,0<p 0<p 1<p 2<1,k ʒ=0.步骤2 如果J T
k
F k ɤε，则终止；反之，有 λk =
μk F k δ
1+F k
δ
,δɪ(0,2].(8
)步骤3 解方程(J T k F k +λk I )d =-J T
k F k ，求出d k .
步骤4 由式(4) (7)求出P r e d k ㊁췍A r e d k ㊁F l (k )㊁췍r k .
3
03
延边大学学报(自然科学版)
第46卷
步骤5 令x k +1=
x k +d k ,췍r k ȡp 0;x k ,췍r k <p {
.
步骤6 令μk +1=4μk ，如果췍r k <p 1;μk ，如果췍r k ɪp 1,p []2;m a x μk
4
,}
{m ，其他ìîíï
ïïï
ïï.步骤7 令k =k +1，然后转到第1步.算法1中要求μk ȡm ，其中m 是一个大于零的常数，即 μ
k ȡm ,∀k ɪΝ.(9
)这一要求可由步骤1给定的初始条件和步骤6满足.
2 局部收敛性
定义1 N 是R n 上的一个集合，使得N ɘX *ʂ∅.如果存在一个常数c (c >0)使得 F (x )ȡc d i s t (x ,X *),∀x ɪΝ, d i s t (x ,X )=
i n f y ɪX
y -x ,(10
)则称F (x )在N 上为方程(1
)提供了一个局部误差界.定义췍x k ɪX *,췍x k 表示X *中满足等式췍x k -x k =d
i s t (x k ,X *)的解.假设1[9
] (a )F (x )连续可微并且(x )在N (x *,b )上为方程(1
)可提供局部误差边界，其中0<b <1,N (x *,b )=x ɪR n |x -x *ɤ}{
b .(b )F (x )和J (x )在N (x *,b )上L i p s h i t z 连续可微，即存在两个常数L 1(L 1>0)和L 2(L 2>0)使: J (y )-J (x )ɤL 1y -x ,∀x ,y ɪN (x *,b );(11) F (y )-F (x )ɤL 2y -x ,∀x ,y ɪN (x *,b ).(12)由假设(a )和(b
)可知 F (y )-F (x )-J (x )(y -x )ɤL 1y -x
2
,∀x ,y ɪN (
x *,b ).(13
)引理1 在假设1成立的条件下，对所有充分大的k 都有d k ɤΟ(k -췍x k )
成立.证明 设φk (d )=F k +J k d 2
+λk d 2
.由式(3)可知d k 是φk 的极小值,
则再由式(8)㊁(9)㊁(12)㊁(13)以及F (췍x k )
=0可得 d k
2
ɤ
1λk φk (췍x k -x k )=1λkpc-based
(F k +J k (췍x k -x k )2+λk 췍x k -x k 2
)=
1+F k δ
μk F k δ
(k +J k (췍x k -x k )2)+췍x k -x k 2
ɤ
1+L δ2췍x k -x k δ
c m 췍x k -x k
δ(L 21췍x k -x k 4)+췍x k -x k
2
=Ο(췍x k -x k
2
).
引理2 在假设1成立的情况下，对所有充分大的k ，有:(a
)存在一个正的常数M >m ，使得 μ
k ɤM .(14)(b )m γ<λk ɤM L δ2췍x k -x k
δ
,γ=m i n
12,c 2
췍x k -x k }{
δ
.
(15
)证明 因引理2中的(a )在文献[5]中已有具体证明，故在此省略.下证引理2中的(b ).
对于任意4
03
第4期伍珍香，等：一种改进的求解非线性方程组的L e v e n b e r g -M a r q u a r d t 方法足够大的k ，由式(12)㊁(14)和F (췍x k )
=0有 λk =
μk F k δ1+F k
δ
ɤμk F k
δ
ɤM L δ2췍x k -x k
δ
万事无忧4
.
(16
)下面证明不等式的左半部分.若F k ɤ1，则F k
δ
ɤ1，因此1+F k
δ
ɤ2.
再根据式(8)㊁(9)和局部误差界的条件有λk =
μk F k δ
1+F k
δ
ȡμk
2
F k
δ
ȡ
m c 2
췍
x k -x k δ
.若F k >1，则1+F k
δ
<
2F k
δ
，因此λk =
μk F k δ
1+F k
δ
>μk
2ȡm 2
.
令γ=m i n 12,c 2췍x k -x k }{
δ
，于是有m γ<λk
.
再结合式(16)可得m γ<λk ɤM L δ2췍x k -x k
δ
，证毕.
下面利用奇异值分解(S V D )证明算法1的局部收敛性.设雅克比矩阵J (췍x
)
的奇异值分解为: J (췍x )=췍U 1,췍U []2췍σ1⋱
췍σr
0⋱
æè
çççççççççö
ø
÷÷÷÷÷
÷
÷÷÷0췍V T 1췍V T éëêêùûúú2
=췍U 1췍Σ1췍V T 1.其中췍σ1ȡ췍σ2ȡ ȡ췍σr >0,r a n k 췍Σ()1=r ,췍U =췍U 1,췍U []2和췍V =췍V 1,췍V []2是两个正交矩阵.
相应地，设J (x )的奇异值分解为
J (x )=
U ΣV T = (U 1,U 2,U 3)σ1
⋱
σr
σr +1
⋱
σr +q
⋱
梁丽芳0æè
ççççççççççççççöø
÷÷÷÷÷÷÷÷÷÷÷÷÷
÷0V T 1V T 2V T æè
çççöø÷÷÷3=U 1Σ1V T 1+U 2Σ2V T 2.(17
)其中,U =U 1,U 2,U []3和V =V 1,V 2,V []3是两个正交矩阵,Σ1=d i a g σ1,σ2, ,σ()r ,σ1ȡσ2ȡ ȡ
σr >0,Σ2=d i a g σr +1,σr +2, ,σr +()q ,σr +1ȡσr +2ȡ ȡσr +q >0
.将J k 的S V D 分解形式写成式(17)的形式，然后根据J k 的L
i p s h i z 连续性以及矩阵摄动理论[10]
，得 d i a g (Σ1-췍Σ1,Σ2,0)ɤJ k -췍J k ɤL 1췍x k -x k .因此有
Σ1-췍Σ1ɤL 1췍x k -x k ,Σ2ɤL 1췍x k -x k .
(18
)由于x }{k 可收敛到解集X *，因此可假设对于足够大的k 有L 1췍x k -x k ɤ
췍σr 2
，
进而根据式(17)有 Σ-11ɤ1췍σr -L 1췍x k -x k ɤ2췍σr
.(19
)引理3[5
] 在假设1成立的条件下,
对于充分大的k 有:(a )U 1U T 1F k ɤΟ췍x k -x ()k ;
5
03
延边大学学报(自然科学版)
第46卷
(b )U 2U T 2F k ɤΟ췍x k -x k
()2
.
证明 (a )和(b )的证明可参考文献[5]中的引理3.3的证明,
在此省略.定理1 在假设1成立的条件下，当δɪ0,()1时，算法1产生的序列x }{k 超线性收敛于方程组(1
)的解；当δɪ1,[]2时，序列x }{k 二阶收敛于方程组(1
)的解.证明 根据式(10)㊁(11)㊁(15
)和引理1有 d k =-V 1Σ21+λk ()I -1Σ1U T 1F k -V 2Σ22+λk ()I -1Σ2U T
2F k .
由式(15)㊁(19
)以及引理3有 F k +J k d k =F k -U 1Σ1Σ21+λk ()I -1Σ1U T 1F k -U 2Σ2Σ22+λk ()I -1Σ2U T 2F k = λk U 1Σ21+λk ()I -1U T 1F k +λk U 2Σ22+λk ()I -1U T 2F k .因此
F k +J k d k ɤλk Σ-21
U 1U T 1F k
+U 2U T
2F k ɤ
4L δ
1M 췍σ2r
Ο췍x k -x k 1+()δ
+Ο췍x k -x k ()2
=Ο췍x k -x k
1+()δ
+Ο췍x k -x k
()2
.
(20
)根据公式(10)㊁(11)㊁(12)㊁(19
)和引理1有 c 췍x k +1-x k +1ɤF (x k +1)=F (x k +d k )ɤF (x k )+J k d k +L 1d k 2
=
Ο췍x k -x k
1+()δ
+Ο췍x k -x k
()2
.
(21
)对于所有充分大的k ，有췍x k -x k =d i s t (x k ,X *)ɤ췍x k +1-x k ɤ췍x k +1-x k +1+d k .故由引理1知，对所有充分大的k ，有췍x k -x k ɤ2d k ɤΟ췍x k -x ()k ，所以d k =Ο췍x k -x ()k .
再由式(21)可知，若δɪ0,()1，则k +1=Οd k 1+()δ
；若δɪ1,[]2，则k +1=Οk
()2
.
即当δɪ0,()1时，迭代点列x }{k 超线性收敛于方程组(1)的解；当δɪ1,[]2时，点列x }{k 二阶收敛于方程组
(1
)的解.3 数值实验
为了验证算法1的有效性，本文利用试验对算法1和文献[5]中的算法2.1进行对比.
测验函数F (x )是标准非奇异函数，来源于文献[11].采用文献[12
]中的方式对测验函数进行改进，结果为: ^F (x )=F (x )-J (
x *)A (A T A )-1A T (x -x *).其中,A ɪR n ˑk
(1ɤk ɤn )是一个列满秩的矩阵,F (x *)=0.
显然^F (x )在x *处的雅克比矩阵为^J (x *)=J (x *)(I -A (A T A )-1A T )，且^F (x *)=0.注意到^F (x )的根未必是F (x )的根，因此本文选择令A =[1,1, ,1]T ɪR n ˑ1,
^J (x *)的秩为n -1.算法1与文献[5]中算法2.1的参数设置如下:p 0=10-4,p 1=0.25,p 2=0.75,N 0=5,μ
1=1,m =10-8.算法的停止条件是J T k
F k ɤ10-5，或者迭代次数超过1000次.两种算法的数值结果见表1.在表1中：第3列表示迭代初始点为-10x 0㊁-x 0㊁x 0㊁10x 0㊁100x 0，其中x 0是文献[11]中的标准初始点;N F 表示函数的计算次数;N J 表示雅可比矩阵的计算次数;N T (N T =N F +N J ˑn )负载均衡
表示计算的总数；在N S 中,Y 表示算法收敛到解x *,N 表示算法收敛到其他解.
从表1中可以看出，在大部分测试问题中，算法1中的函数的计算次数㊁雅可比矩阵的计算次数以
及总的计算次数大部分小于文献[5]中算法2.1的计算次数㊁雅可比矩阵的计算次数以及总的计算次数，由此说明算法1的计算量小于文献[5]中算法2.1的计算量，即算法1对非线性方程组的求解效率高于文献[5]中的算法2.1.
6
03
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议