非精确牛顿法的一个Kantorovich型半局部收敛定理*

徐秀斌, 何 濛, 包振威

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

0 引 言

本文将研究逼近方程

F(x)=0

(1)

的求解问题.式(1)中,F是定义在开凸集D⊂X→Y上的F可导算子,X,Y为Banach空间.

通过解一些特定方程可以解决实际应用中的很多难题,比如动力系统中有关均差和导数的数学模型,它们的解通常代表着系统的稳定状态.除少数特例外,一般可以通过迭代法解决这些问题,即从某个或某几个初始点开始,产生一个逼近方程解的迭代序列，用以逼近所求的解.而迭代方法拥有相似的递推结构,所以可以在广义的大框架下进行讨论.

本文将研究非精确Newton法(INNA):给定初始值x0,执行以下步骤:

1)设rn为残差,xn为迭代值,解出sn,使之满足

F′(xn)sn=-F(xn)+rn.

(2)

2)xn+1=xn+sn.

3)若满足误差控制条件,则程序停止;否则,令n=n+1,返回步骤1).

其中: {rn}⊂Y,且通常由序列{xn}决定.若rn=0,则得到Newton迭代法

xn+1=xn-F′(xn)-1F(xn),n≥0,x0∈D.

(3)

非精确牛顿法在多种条件下的局部和半局部收敛性已被广泛研究[1-9].文献[9]利用以下残差控制式(4)、式(5)及Lipschitz条件(6),分析了非精确牛顿法的收敛性:

‖F′(x0)-1rn‖≤ηn‖F′(x0)-1F(xn)‖1+β,

(4)

ηn≤η.

(5)

式(4)和式(5)中:{ηn}为一个序列;η≥0;β≥0.

‖F′(x0)-1[F(x)-F(y)]‖≤γ‖x-y‖.

(6)

式(6)中:γ>0;x,y∈D.

文献[2]在式(6)的基础上增加了中心Lipschitz条件

‖F′(x0)-1[F(x)-F(x0)]‖≤γ0‖x-x0‖,

(7)

式(7)中γ0≤γ,得到了比文献[9]更加精确的误差估计.文献[5]使用了条件

‖A(x0)-1(F(y)-F(x)-F′(x)(y-x))‖≤v(x,y)‖y-x‖β,β≥1,

证明了牛顿类方法的半局部收敛性.本文受文献[5]的启发,引入条件

‖F′(x0)-1(F(y)-F(x)-F′(x)(y-x))‖≤γ‖y-x‖s,s≥2,

证明了非精确牛顿法的半局部收敛性.

1 半局部收敛性分析

先给出引理.

引理1设γ0>0,γ>0,η≥0,β≥1,s≥2.记

(8)

(9)

再定义函数

f(t)=b(1-δ)tβ+2γ0t-2(1-δ);

(10)

g(t)=ats-2+γ0δt+btβ-δ.

(11)

证明 由式(10)知,

f′(t)=b(1-δ)βtβ-1+2γ0>0,t≥0,

g′(t)=a(s-2)ts-3+γ0δ+bβtβ-1>0,t≥0,

为得到半局部收敛定理,还需要下面的引理:

引理21)当β≥1时,设存在参数γ0>0,γ>0(γ0≤γ),α>0,η≥0,满足

(12)

α≤p0,

(13)

则序列

(14)

非减,且有上界t**,收敛到它的上确界t*∈[0,t**],其中

(15)

μ,a,b如式(8)所定义.

同时,误差估计式为

0≤tn+1-tn≤δ(tn-tn-1)≤…≤δnμα.

(16)

2)当β∈[0,1)时,假设存在d∈(0,1),满足

则用d代替式(15)和式(16)中的δ,1)中的结论仍然成立.

证明 1)用数学归纳法证明

(17)

γ0tn+1<1,

(18)

以及式(16)对任意的n≥0均成立.

当选择恰当的α时,式(17)和式(18)对n=0显然成立,而式(16)对n=0也显然成立.现假设式(16)～式(18)对n≤k-1(k≥1为一个固定的整数)成立,则由式(14)知,

(19)

利用式(19)及上述假设得

0≤tk+1-tk≤δ(tk-tk-1)≤…≤δkμα,

(20)

即式(16)对n=k成立.进而,由式(15)和式(20)得

(21)

再由式(10)知

γ0μα≤γ0μp0≤γ0p<1-δ.

(22)

再联系式(21)知,式(18)对n=k的情形成立.

下证式(17)对n=k成立,即证

上式可写为

a(tk+1-tk)s-1+b(tk+1-tk)β+γ0tk+1δ-δ≤0.

结合式(20)和式(21),即证明

a(δkμα)s-1+b(δkμα)β+γ0δ(δk+δk-1+…+1)μα-δ≤0.

(23)

由于k≥1,s≥2,β≥1且δ<1,所以式(23)等价于

aδk(μα)s-1+bδ(μα)β+γ0δ(δk+δk-1+…+1)μα-δ≤0.

(24)

为证式(24),需建立定义在[0,1)上的函数列

hk(t)=a(μα)s-1tk-1+γ0(1+t+…+tk)μα+b(μα)β-1,k≥1.

由于

hk(t)=a(μα)s-1tk-1-a(μα)s-1tk-2+a(μα)s-1tk-2+γ0(1+t+…+tk)μα+b(μα)β-1=

hk-1(t)+h(t)tk-2μα,

(25)

式(25)中,h(t)=a(μα)s-2t-a(μα)s-2+γ0t2,所以h(t)有唯一正根δ.其中,δ如式(9)所示.在式(25)中令t=δ,则

hk(δ)=hk-1(δ)=…=h1(δ).

因此，只需证明

h1(δ)=a(μα)s-1+γ0(1+δ)μα+b(μα)β-1≤0.

(26)

利用式(11)中g(t) 的定义及式(13)有

g(μα)=a(μα)s-2+γ0δ(μα)+b(μα)β-δ≤g(p1)=0.

(27)

故由式(22)和式(27)知

h1(δ)=g(μα)+[γ0μα-(1-δ)]<0.

所以,式(26)成立.

综上所述,式(16)～式(18)对n≥0均成立,所以序列{tk}有界非减且收敛于上确界t*.

2)用d代替式(17)、式(18)和式(23)中的δ,即可得1)中的结论仍然成立.引理2证毕.

2 半局部收敛定理

为叙述方便起见,引入(Hβ)条件:假设式(4)和式(5)成立,且当β≥1 时,

(28)

当β∈[0,1)时,存在d∈(0,1),满足

下面介绍非精确牛顿法的半局部收敛定理.

定理1设D是X的开凸子集,F:D⊂X→Y是Fréchet可导的非线性算子.假设条件(Hβ)成立,且存在初始点x0∈D,α>0,γ0>0,γ>0(γ0≤γ),对于所有的x,y∈D有

F′(x0)-1∈L(Y,X);

‖F′(x0)-1F(x0)‖≤α;

(29)

‖F′(x0)-1(F′(x)-F′(x0))‖≤γ0‖x-x0‖;

(30)

‖F′(x0)-1(F(y)-F(x)-F′(x)(y-x))‖≤γ‖y-x‖s;

(31)

‖xn-x*‖≤t*-tn.

(32)

证明 首先用数学归纳法证明

(33)

‖xn+1-xn‖≤tn+1-tn;

(34)

(35)

由α,μ及t1的定义知,式(33)对n=0成立.由(INNA)、式(8)、式(14)、式(29)和条件(Hβ)有

‖x1-x0‖=‖-F′(x0)-1F(x0)+F′(x0)-1r0‖≤

(36)

‖z-x0‖≤‖z-x1‖+‖x1-x0‖≤t*-t1+t1-t0=t*-t0.

下面假设式(33)～式(35)对n≤k(k为固定的整数)成立,则

‖xk+θ(xk+1-xk)-x0‖≤tk+θ(tk+1-tk)≤t*,θ∈[0,1].

由式(30)、式(21)和式(22)得

‖F′(x0)-1[F′(xk+1)-F′(x0)]‖≤γ0‖xk+1-x0‖≤γ0tk+1≤γ0t*<1.

(37)

由式(37)及Banach引理知F′(xk+1)-1存在,故

(38)

由INNA可以得到

F(xk+1)=F(xk+1)-F(xk)-F′(xk)(xk+1-xk)+rk.

于是

‖F′(x0)-1F(xk+1)‖≤‖F′(x0)-1(F(xk+1)-F(xk)-F′(xk)(xk+1-xk))‖+‖F′(x0)-1rk‖.

(39)

由式(31)和式(34)知

‖F′(x0)-1(F(xk+1)-F(xk)-F′(xk)(xk+1-xk))‖≤γ‖xk+1-xk‖s≤γ(tk+1-tk)s.

(40)

由式(4)、式(5)及式(33)有

‖F′(x0)-1rk‖≤η‖F′(x0)-1F(xk)‖1+β≤η(μ-1(tk+1-tk))1+β=ημ-(1+β)(tk+1-tk)1+β.

(41)

利用式(39)～式(41)得

(42)

即式(33)对n=k+1成立.

下面证明

η‖F′(x0)-1F(xk+1)‖1+β≤λ‖F′(x0)-1F(xk+1)‖.

(43)

由式(42)和条件(Hβ)知

(44)

即式(43)成立.进而,由(INNA)、式(4)、式(5)、式(8)、式(38)、式(42)和式(43)得到

‖xk+2-xk+1‖=‖[F′(xk+1)-1F′(x0)][F′(x0)-1(F(xk+1)+rk+1)]‖≤

(45)

即说明式(34)对n=k+1成立.

‖z-xk+1‖≤‖z-xk+2‖+‖xk+2-xk+1‖≤t*-tk+2+tk+2-tk+1=t*-tk+1,

即式(35)对n=k+1成立.

最后,利用优序列相关技巧可由式(34)推出式(32).定理2证毕.

参考文献：

[1]Dembo R S,Eisenstat S C,Steihaug T.Inexact Newton methods[J].Numer Anal,1982,19(2):400-408.

[2]Argyros I K,Ren Hongmin.Kantorovich-type semilocal convergence analysis for inexact Newton methods[J].Comput Appl Math,2011,235(9):2993-3005.

[3]Guo Xueping.On semilocal convergence of inexact Newton methods[J].Comput Math,2007,25(2):231-242.

[5]Argyros I K,Hilout S.Majorizing sequences for iterative procedures in Banach spaces[J].Journal of Complexity,2012,28(5/6):562-581.

[6]Argyros I K,Hilout S.Weak convergence conditions for Inexact Newton-type methods[J].Appl Math Comput,2011,218(6):1-10.

[7]Argyros I K,Khattri S K.Weaker Kantorovich type criteria for inexact Newton methods[J].Comput Appl Math,2014,261(9):103-117.

[8]Shen Weiping,Li Chong.Convergence criterion of inexact methods for operators with Hölder continuous derivatives[J].Taiwanese Journal of Math,2008,12(7):1865-1882.

[9]Shen Weiping,Li Chong.Kantorovich-type convergence criterion for inexact Newton methods[J].Appl Numer Math,2009,59(7):1599-1611.