王 銘, 何金蘇, 沈衛(wèi)平

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

0 引 言

Banach空間中非線性算子方程

f(x)=0

(1)

的求解問題在數(shù)學(xué)理論及應(yīng)用領(lǐng)域上有著較為廣泛的應(yīng)用.其中, f是從實(shí)的或復(fù)的Banach空間X的某個(gè)凸區(qū)域D到同型空間Y的連續(xù)Fréchet可微的非線性算子.通常在求解非線性方程(1)時(shí),最常用的方法是Newton法，具體的迭代公式為

xn+1=xn-f′(xn)-1f(xn).

(2)

關(guān)于Newton法的收斂性分析通常可以分為2種類型:局部收斂性分析和半局部收斂性分析.局部收斂性分析是指先假設(shè)方程(1)的解x*存在,然后找到以x*為球心的一個(gè)鄰域D,使得式(2)產(chǎn)生的序列在D內(nèi)收斂[1-3].半局部收斂性分析則在沒有假定方程組解存在的情況下,只根據(jù)初始近似x0滿足的局部條件,就可以確保迭代序列的收斂性[1-4].在Newton法的半局部收斂性分析所得的結(jié)果中,最為著名的是Kantorovich定理[5],它為有界的二階可導(dǎo)算子f "或者一階可導(dǎo)Lipschitz連續(xù)算子提供了簡單易懂的收斂準(zhǔn)則.另外一個(gè)重要的定理是Smale′sα理論[6].至于利用優(yōu)序列的方法考慮Newton法的收斂性[1-2,4,6],王興華等[2]找到了最好的α判據(jù),徹底改進(jìn)了Smale′sα理論.而且,文獻(xiàn)[6]引進(jìn)了γ-條件,再次討論了α判據(jù),對Smale的點(diǎn)估計(jì)理論作了推廣.

由式(2)知,使用Newton法求解方程(1)時(shí),每步迭代都需要精確地求解方程

f′(xn)(xn+1-xn)=-f(xn).

(3)

從實(shí)際計(jì)算角度看,有時(shí)會(huì)使得Newton法無效,尤其當(dāng)f ′(xn)很大且稠密時(shí).但可采用線性迭代求解方程(3)的近似解,不用直接精確地求解方程(3),這樣可以大大減少計(jì)算量.這種方法稱為非精確Newton法.通常,非精確Newton法具有如下形式:

算法1給定初始近似x0,令n=0,1,…,開始執(zhí)行如下步驟,直到序列收斂:

1)設(shè)rn為殘差而xn為迭代值,求解sn,使其滿足

f′(xn)sn=-f(xn)+rn;

2)xn+1=xn+sn;

3)令n=n+1,重新返回步驟1.

其中,{rn}是Y中的序列.

非精確Newton法的收斂性取決于{rn}的選擇,一般情況下，條件不同,殘差的選擇也會(huì)有所差異.關(guān)于非精確Newton法的局部收斂性,文獻(xiàn)[7]給出了最基本的結(jié)果.Argyros[8]在文獻(xiàn)[7]的基礎(chǔ)上,假設(shè)f "滿足Lipschitz條件,分析了非精確Newton法的局部收斂性.文獻(xiàn)[9]用仿射不變條件‖f ′(xi)-1ri‖≤vi‖f ′(xi)-1f(xi)‖(i=0,1,…)替代文獻(xiàn)[8]中的條件‖rn‖≤ηn‖f(xn)‖,使得非精確Newton法亦具有仿射不變性.

至于半局部收斂性分析,文獻(xiàn)[10]在假設(shè)f ′(x)滿足Lipschitz連續(xù)下,采用控制‖f ′(x0)-1rn‖≤‖f ′(x0)-1f(xn)‖ηn分析了非精確Newton法的半局部收斂性.文獻(xiàn)[11]為使改進(jìn)的非精確Newton法具有仿射不變性,條件和控制分別選用‖f ′(y)-1(f ′(x+t(y-x))-f ′(x))‖≤L‖y-x‖和‖rn‖≤vn‖f ′(xn)-1f(xn)‖.文獻(xiàn)[12]分析了在γ-條件[3]下非精確Newton法的半局部收斂性,同時(shí)給出了Smale型收斂準(zhǔn)則,首次采用滿足如下條件的殘差{rn}:

(4)

本文采用滿足式(4)的殘差控制{rn},通過引入中心γ0-條件和γ-條件,得到了比文獻(xiàn)[12]更精確的誤差估計(jì)及更優(yōu)的半局部收斂性定理.

1 預(yù)備知識

首先,引入γ-條件[3]及中心γ0-條件.

(5)

則稱f關(guān)于x0在U(x0,r)?X上滿足γ-條件.

(6)

(7)

則稱f關(guān)于x0在U(x0,r)上滿足中心γ0-條件.

(8)

由定義2知,γ0≤γ.

下面給出證明非精確Newton法半局部收斂性所需要的相關(guān)結(jié)果.

為方便起見,令

(9)

(11)

p*≥r*.

(12)

證明 由ψ和φ的定義知

ψ(t)≤φ(t);

(13)

(15)

(16)

令

易知,g′(x)>0,從而g(x)關(guān)于x單調(diào)遞增.由γ0≤γ,有g(shù)(γ0)≤g(γ).比較式(14)和式(15),有

ψ′(t)≤φ′(t).

(17)

所以,p*≥r*.引理2證畢.

引理3[1]若

(18)

則函數(shù)φ有2個(gè)零解

(19)

且滿足

λ

引理4若

(20)

成立,則式(10)定義的ψ有2個(gè)零解s*和s**,且

λ

由式(20)及引理3知,h(t)=0有2個(gè)正解.記較小的正根為h*,則λ

綜上,可得λ

下面定義2個(gè)序列:令t0=s0=0,{tn}和{sn}由以下迭代產(chǎn)生:

(22)

引理5[1]令t*由式(19)所定義,且{tn}由式(21)產(chǎn)生.若式(18)成立,則

tn

引理6假設(shè)式(20)成立.令s*是ψ在區(qū)間[0,p*]上的零點(diǎn),且{sn}由式(22)產(chǎn)生,那么

sn

(23)

從而{sn}單調(diào)遞增且收斂于s*.

證明 用數(shù)學(xué)歸納法證明式(23).當(dāng)n=0時(shí),s0=0,s1=λ,由引理4知,s0<λ

ψ(sn)>0.

(24)

由式(17)知,-ψ′(t)≥-φ′(t).又因?yàn)棣铡鋰?yán)格遞增且φ′(r*)=0,所以,由引理4知

-ψ′(sn)≥-φ′(sn)>-φ′(r*)=0.

(25)

由式(25)和式(24)可得

因此,式(23)對所有的n≥0成立.這就意味著{sn}單調(diào)遞增且收斂到一點(diǎn),設(shè)為υ.易知υ∈[0,p*]且υ是函數(shù)ψ的一個(gè)零點(diǎn)(令式(22)中n→∞).注意到s*是函數(shù)ψ在區(qū)間[0,p*]上唯一的零點(diǎn),由此可知υ=s*,所以{sn}單調(diào)收斂于s*.引理6證畢.

2 收斂性分析

(26)

(27)

‖xn+1-xn‖≤sn+1-sn;

(28)

‖xn-x*‖≤s*-sn,n=0,1,….

(29)

證明 用數(shù)學(xué)歸納法證明對所有的k≥0,有

(30)

‖xk+1-xk‖≤sk+1-sk;

(31)

(32)

由定理1的假設(shè)知,式(30)對k=0成立.由算法1知,

‖x1-x0‖≤‖f′(x0)-1f(x0)‖+‖f′(x0)-1r0‖.

‖z-x0‖≤‖z-x1‖+‖x1-x0‖≤s*-s1+s1-s0=s*-s0.

因此,式(31)、式(32)對k=0成立.現(xiàn)假設(shè)式(30)～式(32)對所有滿足k≤n的正整數(shù)k成立,那么

‖xn+θ(xn+1-xn)-x0‖≤sn+θ(sn+1-sn)≤s*,θ∈(0,1).

由式(9)、式(16)、引理4及引理6有

(33)

令引理1中的x=xn+1,則

(34)

由式(14)得

再根據(jù)式(34)有

‖f′(xn+1)-1f′(x0)‖≤-ψ′(sn+1)-1.

(35)

由算法1知

‖+‖f′(x0)-1rn‖=I1+I2.

(36)

接下來分別估計(jì)I1和I2.首先,由γ-條件知

因?yàn)槭?31)、式(32)對所有滿足k≤n的正整數(shù)k成立,所以

(37)

下面估計(jì)I2.因?yàn)閒 ′(x0)-1f ′(xn)=I+f ′(x0)-1(f ′(xn)-f ′(x0)),故由式(7)知

(38)

由算法1有

‖f′(x0)-1f′(xn)(xn+1-xn)‖≥‖f′(x0)-1f(xn)‖-‖f′(x0)-1rn‖.

因?yàn)槭?30)對k≤n成立,所以由式(4)得

‖f′(x0)-1f′(xn)(xn+1-xn)‖≥‖f′(x0)-1f(xn)‖-η‖f′(x0)-1f(xn)‖2≥

進(jìn)一步可以得到

(39)

結(jié)合式(4)有

注意到sn

(40)

根據(jù)式(36)、式(37)及式(40)有

結(jié)合式(9)、式(10)及式(22)可得

(41)

這就證明了式(30)對所有的k≥0成立.

根據(jù)算法1知

‖xn+2-xn+1‖=‖f ′(xn+1)-1f ′(x0)(-f ′(x0)-1f(xn+1)+f ′(x0)-1rn+1)‖≤

‖f ′(xn+1)-1f ′(x0)‖(‖f ′(x0)-1f(xn+1)‖+‖f ′(x0)-1rn+1‖)≤

由式(22)、式(35)及式(41)可得

因此,式(31)對所有的k≥0成立.

‖μ-xn+1‖≤‖μ-xn+2‖+‖xn+2-xn+1‖≤s*-sn+2+sn+2-sn+1=s*-sn+1,

綜上,式(30)、式(32)對所有k≥0成立.

因此,y*=x*.定理1證畢.

0≤sn≤tn;

0≤sn+1-sn≤tn+1-tn;

0≤s*-sn≤t*-tn.

注3本文沒有給出與文獻(xiàn)[12]一致的Smale型收斂準(zhǔn)則,要得出相關(guān)結(jié)論,還需要做進(jìn)一步的研究.

參考文獻(xiàn):

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

[2]王興華，韓丹夫.點(diǎn)估計(jì)中的優(yōu)序列方法以及Smale定理的條件和結(jié)論的最優(yōu)化[J].中國科學(xué)：A 數(shù)學(xué),1990,19(9):135-144.

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

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

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

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

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

[8]Argyros I K.Focing sequence and inexact Newton iterates in Banach space[J].Appl Math Lett,2000,13(1):77-80.

[9]Ypma J T.Local convergence of inexact Newton methods[J].SIAM Numer Anal,1984,21(3):583-590.

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

[11]白中治，童培莉.不精確Newton法與Broyden法的仿射不變收斂性[J].電子科技大學(xué)學(xué)報(bào),1994,23(5):535-540.

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