γ-條件下非精確牛頓類方法的半局部收斂性*

何金蘇, 吳阿凡, 沈衛(wèi)平

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

?

γ-條件下非精確牛頓類方法的半局部收斂性*

何金蘇, 吳阿凡, 沈衛(wèi)平

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

研究了非精確牛頓類方法的收斂性問題.假設非線性算子滿足γ-條件,那么可以建立非精確牛頓類方法的半局部收斂條件;并且,給出一個數(shù)值例子說明了本文結(jié)果的有效性.

非精確牛頓類方法;γ-條件;非線性算子;半局部收斂性

0 引 言

設X和Y是Banach空間,Ω是X中的一個開凸集.設非線性算子f:Ω?X→Y有連續(xù)的F-導數(shù),記為f′.在Banach空間中求解非線性算子方程

(1)

是一個重要的課題,并且在數(shù)學理論和應用領域中都有著廣泛的應用.其中求解方程(1)的最主要方法就是牛頓法,其迭代形式為

(2)

牛頓法收斂性問題的研究通常分為兩類:局部收斂性問題的研究[1-3]和半局部收斂性問題的研究[1-5].研究牛頓法半局部收斂性問題中最著名的理論就是Kantorovich理論[6],它保證了牛頓序列在一個較弱的條件下收斂于方程的解.另一個重要的理論就是Smale的α理論[5],它提出了近似零點的概念,并建立了解析函數(shù)判斷初始點為近似零點的條件,該理論只依賴于初始點的選擇.特別地,文獻[2-3]通過利用優(yōu)序列找到了更好的α判據(jù),改進了Smale的α理論.而且,文獻[2]通過引進γ-條件的概念,再次討論了α判據(jù),推廣了Smale的點估計理論.

由式(2)可知,牛頓法要求計算f′(xn),以及精確地求解線性方程

(3)

但是,在實際計算中,牛頓法有時是無效的.因此,學者們提出了牛頓類方法和非精確牛頓法.牛頓類方法能夠避免精確計算導數(shù)f′(xn);非精確牛頓法采用線性迭代近似求解方程(3)代替精確求解,進而減少牛頓法的計算量.將牛頓類方法和非精確牛頓法結(jié)合所得到的方法就是非精確牛頓類方法.通常,非精確牛頓類方法的迭代形式為:

算法1:給定初始點x0,令n=0,1,2,…,執(zhí)行下列操作,直至{xn}收斂:

1)設rn為殘差項,xn為迭代值,求解sn,使其滿足Bnsn=-f(xn)+rn;

2)令xn+1=xn+sn;

3)令n=n+1,返回操作1).

其中,{Bn}是一列從X到Y(jié)的可逆算子,{rn}是Y中的一個序列(通常依賴于序列{xn}).

當Bn=f′(xn)(n∈N)時,算法1就為非精確牛頓法.眾所周知,非精確牛頓類方法的收斂性依賴于殘差{rn}.文獻[7]通過某種方式分析了局部收斂性,使得相應的殘差{rn}滿足‖rn‖/‖f(xn)‖≤ηn.文獻[8]考慮了相應的殘差控制

(4)

并得到了非精確牛頓類方法的局部收斂性結(jié)果.其中,{θn}為強制項.

受文獻[9-10]中非精確牛頓類方法求解逆特征值問題的啟發(fā),文獻[11]考慮殘差{rn}滿足

(5)

式(5)中,0≤β≤1.按照文獻[12]中的殘差條件的選取,可取式(5)中的β=1,即有

(6)

近幾年,對非精確牛頓法或修正的非精確牛頓類方法收斂性的研究較多[13-14].本文對非精確牛頓類方法的收斂性質(zhì)展開研究,利用滿足式(6)的殘差控制{rn},研究了在γ-條件下非精確牛頓類方法的收斂性,得到了非精確牛頓類方法的半局部收斂性定理;同時,給出了一個數(shù)值例子,說明本文結(jié)果的有效性.

1 預備知識

(7)

設{tn}是由牛頓類方法生成的序列,且其初始點為t0=0,定義

(8)

根據(jù)文獻[15]中的引理2.2可以描述序列{tn}的收斂性質(zhì).

引理2 假設式(7)成立.設t*是方程φ(t)=0的較小的非負解，則由式(8)生成的序列{tn}單調(diào)遞增并收斂于t*，同時tn+1-tn≤b,tn<2b,n∈N.

2 收斂性分析

設f:Ω?X→Y是具有一階連續(xù)和二階連續(xù)F-導數(shù)的算子,分別記為f′和f".并設x0∈Ω,且f′(x0)-1存在.

首先,給出γ-條件的定義及相關的引理.

(9)

則稱函數(shù)f在x0處滿足γ-條件.

(10)

其中,τ1,τ2是某些非負常數(shù).

為了得到主要依賴于初始點x0的收斂條件,取

(11)

設ω1≥1,ω2≥0,并假設序列{Bn}滿足:

(C2)‖f′(x0)-1(Bn-f′(xn))‖≤ω2‖f′(x0)-1f(xn)‖,n∈N.

設

(12)

(13)

并且,{tn}是由式(8)生成的序列.

下面給出本文的主要結(jié)果.

定理1 設f滿足γ-條件(9),取r=t*,并設

(14)

則由算法1生成的序列{xn}是有定義的,且收斂于f(x)=0的解x*,滿足

(15)

(16)

為完成證明,需證明

(17)

(18)

下面用數(shù)學歸納法證明.當n=0時,由α與b的定義可知

所以,當n=0時,式(17)成立.

由殘差公式(6)和式(11)可知

v‖f′(x0)-1f(xn)‖2.

(19)

因此,由條件(C1)、式(12)和式(19)有

ω1(α+v‖f′(x0)-1f(x0)‖2)=ω1(α+vα2).

從而,當n=0時,式(18)也成立.

‖f′(x0)-1(f′(xm-1)-Bm-1)(xm-xm-1)‖+‖f′(x0)-1rm-1‖.

(20)

下面證明

(21)

(22)

(23)

由式(18)(n=m-1)可得,

(24)

特別地,

所以,

(25)

且

因此,引理3成立.由式(9)和式(24)有

(26)

(27)

從而,式(26)變?yōu)?/p>

最后一個不等式由式(16)和式(25)可得.因此,式(21)成立.又由條件(C2)可知

‖f ′(x0)-1(Bm-1-f ′(xm-1))(xm-xm-1)‖≤

‖f ′(x0)-1(Bm-1-f ′(xm-1))‖5‖xm-xm-1‖≤

ω2‖f ′(x0)-1f(xm-1)‖5‖xm-xm-1‖.

再由式(18)(n=m-1)可得

‖f′(x0)-1(Bm-1-f′(xm-1))(xm-xm-1)‖≤

ω2‖f′(x0)-1f(xm-1)‖5‖xm-xm-1‖≤ω2(tm-tm-1)2.

另外,由式(19)和式(20)可得

因此,式(22)和式(23)均成立.將式(21)、式(22)和式(23)合并可得

且φ′(tm)=atm-1,所以

(28)

從而,當n=m時,式(17)成立.又由條件(C1)和式(19)有

ω1‖f′(xm)-1f′(x0)‖(‖f′(x0)-1f(xm)‖+v‖f′(x0)-1f(xm)‖2).

從而,

因此,由引理3和式(28)可得

從而,當n=m時,式(18)成立.綜上,定理1得證.

當Bn=f′(xn)(n∈N)時,條件(C1)和(C2)滿足ω1=1,ω2=0.因此,

那么,非精確牛頓法的收斂結(jié)果就可直接從定理1得到.從而有如下推論:

推論1 設f滿足γ-條件(9),取r=t*,并設

則由非精確牛頓法生成的序列{xn}是有定義的且收斂于f(x)=0的解x*,并滿足

3 數(shù)值例子

本文將引用文獻[12]中的例子說明定理1的有效性.為了方便,取ω1=1,ω2=0,則

并且,選取Pn=I,n∈N.

例1 設X=Y=R2,并分別將X和Y賦予l1-范數(shù)和l∞-范數(shù).定義解析函數(shù)f:X→Y為

設x0=(u,w)T∈X,則

(29)

式(29)中,

因此,

從而,

首先,通過取4個不同的初始點x0=(0.002,0.002)T,(0.002,-0.002)T,(0.01,0.035)T,(0.05,0.05)T估計γ和α的值,結(jié)果見表1.為了說明本文結(jié)果的有效性,考慮θn的不同取值,并用“T”和“F”表示式(15)的成立與失敗,結(jié)果見表2.

表1 γ值和α值的估計

表2 不同θn值對式(15)的T/F值

從表2可以看出,即使是同一初始點x0,在不同的θn值下也有不同的T/F值;同樣地,在同一θn值下,取不同的初始點x0,也得到不同的T/F值.

[1]Wang Xinghua.Convergence of Newton′s method and inverse function theorem in Banach space[J].Math Comp,1999,68(225):169-186.

[2]Wang Xinghua,Han Danfu.On the dominating sequencee method in the point estimates and Smale′s theorem[J].Sci China Ser A,1990,19(9):135-144.

[3]Wang Xinghua,Han Danfu.Criterionαand Newton′s method[J].Chinese Numer Math Appl,1997,19(2):96-105.

[4]Smale S.Complexity theory and numerical analysis[J].Acta Numer,1997,6(1):523-551.

[5]Smale S.Newton′s theory estimates from data at one point[M].New York:Spring-Verlag,1986.

[6]Kantorovich L V.On Newton′s method for functional equations[J].Dokl Akad Nauk,1948,59(7):1237-1240.

[7]Dembo R S,Eisenstant S C,Steihaug T.Inexact Newton methods[J].SIAM Numer Math,1982,19(2):400-408.

[8]Morini B.Convergence behaviour of inexact Newton methods[J].Math Comp,1999,68(228):1605-1613.

[9]Chan R H,Xue S F,Zhou H M.On the convergence rate of a quasi-Newton method for inverse eigenvalue problems[J].SIAM Numer Anal,1999,36(2):436-441.

[10]Chan R H,Chung H L,Xue S F.The inexact Newton-like method for inverse eigenvalue problem[J].BIT Numer Math,2003,43(1):7-20.

[11]Li Chong,Shen Weiping.Local convergence of inexact methods under the H?lder condition[J].Comp Appl Math,2008,222(2):544-560.

[12]Shen Weiping,Li Chong.Smale′sαtheory for inexact Newton methods under theγ-condition[J].Math Anal Appl,2010,369(1):29-42.

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

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

(責任編輯 陶立方)

The semi-local convergence for inexact Newton-like methods under theγ-condition

HE Jinsu, WU Afan, SHEN Weiping

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

It was studied the convergence problem of inexact Newton-like methods. Under theγ-condition, a semi-local convergence criterion for inexact Newton-like methods was established; furthermore, a numerical example was presented to illustrate the effectiveness of the results.

inexact Newton-like methods;γ-condition; nonlinear operator; semi-local convergence

10.16218/j.issn.1001-5051.2017.01.002

2016-04-27；

2016-06-11

國家自然科學基金資助項目(11571308)

何金蘇(1965-),女,浙江金華人,教授.研究方向:數(shù)值逼近.

O241.5

A

1001-5051(2017)01-0009-08