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

何金蘇, 吳阿凡, 沈衛平

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

?

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

何金蘇, 吳阿凡, 沈衛平

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

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

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

0 引 言

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

(1)

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

(2)

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

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

(3)

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

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

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

2)令xn+1=xn+sn;

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

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

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

(4)

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

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

(5)

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

(6)

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

1 預備知識

(7)

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

(8)

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

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

2 收斂性分析

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

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

(9)

則稱函數f在x0處滿足γ-條件.

(10)

其中,τ1,τ2是某些非負常數.

為了得到主要依賴于初始點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)生成的序列.

下面給出本文的主要結果.

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

(14)

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

(15)

(16)

為完成證明,需證明

(17)

(18)

下面用數學歸納法證明.當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)變為

最后一個不等式由式(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.因此,

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

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

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

3 數值例子

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

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

例1 設X=Y=R2,并分別將X和Y賦予l1-范數和l∞-范數.定義解析函數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估計γ和α的值,結果見表1.為了說明本文結果的有效性,考慮θn的不同取值,并用“T”和“F”表示式(15)的成立與失敗,結果見表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-),女,浙江金華人,教授.研究方向:數值逼近.

O241.5

A

1001-5051(2017)01-0009-08