非精確牛頓法的一個Kantorovich型半局部收斂定理*

徐秀斌, 何 濛, 包振威

(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院,浙江 金華 321004)

0 引 言

本文將研究逼近方程

F(x)=0

(1)

的求解問題.式(1)中,F是定義在開凸集D?X→Y上的F可導(dǎo)算子,X,Y為Banach空間.

通過解一些特定方程可以解決實際應(yīng)用中的很多難題,比如動力系統(tǒng)中有關(guān)均差和導(dǎo)數(shù)的數(shù)學(xué)模型,它們的解通常代表著系統(tǒng)的穩(wěn)定狀態(tài).除少數(shù)特例外,一般可以通過迭代法解決這些問題,即從某個或某幾個初始點開始,產(chǎn)生一個逼近方程解的迭代序列，用以逼近所求的解.而迭代方法擁有相似的遞推結(jié)構(gòu),所以可以在廣義的大框架下進行討論.

本文將研究非精確Newton法(INNA):給定初始值x0,執(zhí)行以下步驟:

1)設(shè)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(xiàn)′(x0)-1rn‖≤ηn‖F(xiàn)′(x0)-1F(xn)‖1+β,

(4)

ηn≤η.

(5)

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

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

(6)

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

文獻[2]在式(6)的基礎(chǔ)上增加了中心Lipschitz條件

‖F(xiàn)′(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ā),引入條件

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

證明了非精確牛頓法的半局部收斂性.

1 半局部收斂性分析

先給出引理.

引理1設(shè)γ0>0,γ>0,η≥0,β≥1,s≥2.記

(8)

(9)

再定義函數(shù)

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)當(dāng)β≥1時,設(shè)存在參數(shù)γ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)當(dāng)β∈[0,1)時,假設(shè)存在d∈(0,1),滿足

則用d代替式(15)和式(16)中的δ,1)中的結(jié)論仍然成立.

證明 1)用數(shù)學(xué)歸納法證明

(17)

γ0tn+1<1,

(18)

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

當(dāng)選擇恰當(dāng)?shù)摩習(xí)r,式(17)和式(18)對n=0顯然成立,而式(16)對n=0也顯然成立.現(xiàn)假設(shè)式(16)～式(18)對n≤k-1(k≥1為一個固定的整數(shù))成立,則由式(14)知,

(19)

利用式(19)及上述假設(shè)得

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

(20)

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

(21)

再由式(10)知

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

(22)

再聯(lián)系式(21)知,式(18)對n=k的情形成立.

下證式(17)對n=k成立,即證

上式可寫為

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

結(jié)合式(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)上的函數(shù)列

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(shù)(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)中的結(jié)論仍然成立.引理2證畢.

2 半局部收斂定理

為敘述方便起見,引入(Hβ)條件:假設(shè)式(4)和式(5)成立,且當(dāng)β≥1 時,

(28)

當(dāng)β∈[0,1)時,存在d∈(0,1),滿足

下面介紹非精確牛頓法的半局部收斂定理.

定理1設(shè)D是X的開凸子集,F:D?X→Y是Fréchet可導(dǎo)的非線性算子.假設(shè)條件(Hβ)成立,且存在初始點x0∈D,α>0,γ0>0,γ>0(γ0≤γ),對于所有的x,y∈D有

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

‖F(xiàn)′(x0)-1F(x0)‖≤α;

(29)

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

(30)

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

(31)

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

(32)

證明 首先用數(shù)學(xué)歸納法證明

(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.

下面假設(shè)式(33)～式(35)對n≤k(k為固定的整數(shù))成立,則

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

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

‖F(xiàn)′(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(xiàn)′(x0)-1F(xk+1)‖≤‖F(xiàn)′(x0)-1(F(xk+1)-F(xk)-F′(xk)(xk+1-xk))‖+‖F(xiàn)′(x0)-1rk‖.

(39)

由式(31)和式(34)知

‖F(xiàn)′(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(xiàn)′(x0)-1rk‖≤η‖F(xiàn)′(x0)-1F(xk)‖1+β≤η(μ-1(tk+1-tk))1+β=ημ-(1+β)(tk+1-tk)1+β.

(41)

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

(42)

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

下面證明

η‖F(xiàn)′(x0)-1F(xk+1)‖1+β≤λ‖F(xiàn)′(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成立.

最后,利用優(yōu)序列相關(guān)技巧可由式(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.