不可微方程的广义牛顿法的收敛性分析

詹铜霞 徐秀斌 郭晓梅

(浙江师范大学 数学系，浙江 金华321004)

0 引言

设D是Rn的一个开凸子集,令H是D⊆Rn到Rn的非线性算子,求解非线性方程

H(x)=0

(1)

的近似解是一个重要的问题.目前,在H是Fréchet可导的情况下,牛顿法是求解非线性方程(1)的最有效方法之一,其迭代式为:

xn+1=xn-H′(xn)-1H(xn),n=0,1,2,... .

(2)

然而,当H不可导时,牛顿迭代法就不能用来求非线性方程(1)的近似解.在许多不可微方程的研究中,有两类重要的方法:一类是用差商来替代导数H′,如弦割法[1]:

xn+1=xn-[xn,xn-1;H]-1H(xn),n=0,1,2,... .

(3)

还有一类是用B-次微分来替代导数H′[2-6],Qi和Sun在文献[2]中构造了广义牛顿法:

xn+1=xn-Vn-1H(xn),n=0,1,2,... ,

(4)

其中Vn∈∂BH(xn).

在研究过程中人们发现,当H分解为可导部分F和不可导部分G,即

H(x)=F(x)+G(x)=0

(5)

时,会得到更好的收敛结果[7,8].Catinas在文献[9]中,构造了新的迭代法:

xn+1=xn-(F′(xn)+[xn,xn-1;G])-1H(xn),n=0,1,2,... .

(6)

受文献[9]的启发,本文构造迭代法:

xn+1=xn-(F′(xn)+Vn)-1H(xn),n=0,1,2,... ,

(7)

其中Vn∈∂BG(xn),来求非线性方程(5)的解.当F为零时,方法(7)就是方法(4),当G为零时，方法(7)就是牛顿法.另外,当H为某些特殊的函数时,如非线性方程组:

从计算量上看,计算Vn比[xn,xn-1;G]少.

1 预备知识

• B-次微分[3]:根据Rademacher理论,G的局部连续性意味着G是几乎处处可导.令DF为G的可导点集,则∂BG(x)={limxi→xG′(xi),xi∈DF}就叫做G在点x处的B-次微分.

2 局部收敛性

为了得到算法(7)的局部收敛性,需要下面的假设:

设x*∈D是H的一个解,即H(x*)=0.

(II)G在x*处满足假设A1;

注:在ω1是非减函数的情况下,条件(V)中h总是存在,如h(t)=1.我们也可以考虑h(t)=supz>0ω1(tz)/ω1(z).

定理1 设F是Fréchet可导,G是局部Lipschitz连续函数但不可导.假设(I)-(V)成立,令r:=sup{t∈(0,r1):β[Tω1(t)+λ1+ω1(t)+ω2(t)]<1},则对于任意的x0∈B(x*,r),算法(7)产生的序列{xn}⊆B(x*,r)且收敛到方程H(x)=0的解x*.

此次改革，优化了部门内设机构设置，完成了中央下达的人员编制精简20%的任务。同时还进一步规范了部门机关党务与干部人事管理机构设置的中央纪委监察部派驻纪检监察机构设置。

证明对n=0,1,2,...,令Ln=F′(xn)+Vn,其中Vn∈∂BG(xn).由(I),(III),(IV)和ω1,ω2的非减性,得到

-[G(x0)-G(x*)-V0(x0-x*)]}.

所以,从(II),(III)和(V),得到

这意味着x1∈B(x*,r).

假设下面的论断对n成立:

(in)xn∈B(x*,r);

所以xn+1∈B(x*,r).由数学归纳法知论断(in),(iin),(iiin)对所有的n都成立.从而算法(7)产生的序列{xn}⊆B(x*,r)且收敛到x*.定理证毕.

定理2 设F是Fréchet可导,G是局部Lipschitz连续函数但不可导.假设(I),(III)-(V)成立,令R:=sup{t∈(0,r2):β[Tω1(t)+λ2tp+ω1(t)+ω2(t)]<1},且G在点x*处满足假设A2,则对于任意的x0∈B(x*,R),算法(7)产生的序列{xn}⊆B(x*,R)且超线性收敛到方程H(x)=0的解x*.

证明与定理1的证明类似,易得:

所以{xn}⊆B(x*,R)且超线性收敛到x*.定理证毕.

参考文献:

[1]Hernández M A,Rubio M J.A new type of recurrence relations for the secant method[J].International journal of computer mathematics,1999,72(4): 477-490.

[2] Qi L,Sun J.A nonsmooth version of Newton's method[J].Mathematical programming,1993,58(1-3): 353-367.

[3] Qi L.Convergence analysis of some algorithms for solving nonsmooth equations[J].Mathematics of operations research,1993,18(1): 227-244.

[7] Hernández M A,Rubio M J.The Secant method for nondifferentiable operators[J].Applied mathematics letters,2002,15(4): 395-399.

[8] Hernández M A,Rubio M J.A modification of Newton's method for nondifferentiable equations[J].Journal of computational and applied mathematics,2004,164: 409-417.

[9] Catinas E.On some iterative methods for solving nonlinear equations[J].Revue d'analyse Numerique et de theorie de l'approximation,1994,23(1): 47-53.