ω條件下Ulm-like方法的收斂性*

沈衛(wèi)平, 徐麗華, 周文靜

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

0 引 言

設(shè)X和Y是Banach空間,D是X空間中的開子集,f:D?X→Y是具有連續(xù)Fréchet導(dǎo)數(shù)f′的非線性算子.本文考慮非線性算子方程

f(x)=0

(1)

的求解問題.該問題是計(jì)算數(shù)學(xué)的理論基礎(chǔ),也是現(xiàn)代科學(xué)計(jì)算的核心問題之一.求解該問題最經(jīng)典的方法是牛頓法.給定初始點(diǎn)x0∈D,牛頓法的迭代公式為

xk+1=xk-f′(xk)-1f(xk),k=0,1,2,….

(2)

由于重要的理論基礎(chǔ)和廣泛的應(yīng)用背景,牛頓法的收斂性得到了廣泛研究[1-5].

隨著現(xiàn)代科學(xué)計(jì)算的發(fā)展,在應(yīng)用領(lǐng)域中遇到的計(jì)算問題越來越復(fù)雜.另一方面,正如式(2)所示,牛頓迭代法的每一步迭代均要計(jì)算f′(xk)及求解Jacobian方程

f′(xk)(xk+1-xk)=-f(xk),

這就導(dǎo)致牛頓法的計(jì)算效率低,尤其當(dāng)f′(xk) 階數(shù)較大時(shí).為了避免求解Jacobian方程,文獻(xiàn)[6-8]提出了非精確牛頓法,即只求出Jacobian方程的近似解;文獻(xiàn)[9-12]則使用了Ulm方法,給定初始值x0∈D,B0∈L (Y,X)(L(Y,X)表示Y到X的線性有界算子空間),Ulm 方法的迭代格式為

其中,k=0,1,2,….當(dāng)Fréchet導(dǎo)數(shù)f′在方程的解附近滿足Lipschitz條件時(shí),文獻(xiàn)[13]證明了Ulm方法在避免求解Jacobian方程的同時(shí)還能保持二階收斂速度.

近年來,Ulm方法被用來求解逆特征值問題和逆奇異值問題[14-15],這兩類問題最后都被歸結(jié)為非線性方程的求解.但在實(shí)際求解中,因?yàn)閁lm方法在每次迭代中仍然需要求f′,所以當(dāng)涉及的矩陣階數(shù)較大時(shí),計(jì)算會很費(fèi)時(shí).為了克服這個(gè)缺點(diǎn),文獻(xiàn)[16]提出了Ulm-like方法,即用滿足一定條件的Ak+1近似代替f′(xk+1),從而可以避免求Jacobian矩陣,提高計(jì)算效率.給定x0∈D,B0∈L (Y,X),Ulm-like方法迭代公式為

式(3)中,k=0,1,2,….文獻(xiàn)[16]主要證明了Fréchet導(dǎo)數(shù)f′在方程解附近滿足Lipschitz條件時(shí),Ulm-like方法具有二階收斂速度;以文獻(xiàn)[16]為基礎(chǔ),文獻(xiàn)[17]將f′在解附近滿足的條件推廣到H?lder條件,且此時(shí)Ulm-like方法具有超線性收斂速度.

Lipschitz條件或H?lder條件是分析迭代法收斂性時(shí)常用的假設(shè)條件,但并不是所有方程都會滿足二者之一的.下面的Hammerstein型非線性積分方程[18]即為一個(gè)例子:

其中:-∞

ω(θ)=∑mi=1Kiθpi,并要求ω是定義在[0,+∞)上連續(xù)非減的函數(shù),且ω(0)≥0[19-21].此外,假設(shè)存在常數(shù)p∈(0,1],使得ω(tθ)≤tpω(θ)對任意的t∈[0,1]和任意的θ>0都成立.在這些條件下,文獻(xiàn)[19]分析了牛頓法的半局部收斂性,并證明了其R-收斂階至少為1+p.

本文研究Ulm-like方法的局部收斂性.在ω條件下,證明了由Ulm-like方法產(chǎn)生的序列是超線性收斂的,并且給出了收斂球的半徑估計(jì).注意到當(dāng)ω(θ)=Lθ,L>0時(shí),該條件便轉(zhuǎn)化為Lipschitz條件,此時(shí)可得到文獻(xiàn)[16]中的結(jié)論;當(dāng)ω(θ)=Kθp,K>0,p∈(0,1]時(shí),ω條件即為(K,p)-H?lder條件,此時(shí)可得到文獻(xiàn)[17]中的結(jié)果.最后通過數(shù)值例子驗(yàn)證了本文得到的收斂性結(jié)果.

1 收斂性分析

設(shè)非線性算子f:D?X→Y有連續(xù)Fréchet導(dǎo)數(shù)f′,x*∈D是非線性方程(1)的解,B(x*,r)?D表示在X中以x*為中心、r>0為半徑的開球.假設(shè)f′(x*)-1存在且f′在B(x*,r)內(nèi)滿足下列ω條件:

‖f′(x)-f′(y)‖≤ω(‖x-y‖), ?x,y∈B(x*,r).

(4)

式(4)中,ω是定義在[0,+∞)上連續(xù)非減的函數(shù),且ω(0)≥0.另外,假設(shè)存在常數(shù)q∈(1,2],使得函數(shù)ω滿足以下條件:

ω(tθ)≤tq-1ω(θ), ?t∈[0,1], ?θ∈(0,+∞).

(5)

設(shè){xk}是由Ulm-like方法(式(3))產(chǎn)生的序列,又設(shè){Ak}?L (X,Y).對任意的k=0,1,2,…,Ak滿足

‖Ak-f′(xk)‖≤γk‖f(xk)‖q-1.

(6)

(7)

則有如下引理(該引理對定理1的證明起到關(guān)鍵作用):

引理1假設(shè)f′及函數(shù)ω滿足式(4)和式(5),又設(shè)k為任一自然數(shù)且Ak滿足式(6).若xk∈B(x*,R),則

1)‖Ak-f′(xk)‖≤γηq-1‖xk-x*‖q-1;

結(jié)合式(4)、函數(shù)ω的非減性及η的定義,可推得

再由式(6)、式(9)及γ的定義可知,

‖Ak-f′(xk)‖≤γk‖f(xk)‖q-1≤γηq-1‖xk-x*‖q-1,

(10)

于是結(jié)論1)成立.

下證結(jié)論2)也成立.注意到‖xk-x*‖

‖Ak-f′(x*)‖≤‖Ak-f′(xk)‖+‖f′(xk)-f′(x*)‖≤

γηq-1‖xk-x*‖q-1+ω(‖xk-x*‖)≤

γηq-1‖xk-x*‖q-1+‖xk-x*‖q-1ω(1)≤[ω(1)+γηq-1]Rq-1.

進(jìn)一步,由R的定義可得

‖f′(x*)-1‖‖Ak-f′(x*)‖≤‖f′(x*)-1‖[ω(1)+γηq-1]Rq-1<1.

從而,根據(jù)Banach引理可知Ak可逆,并且

再由ρ的定義得結(jié)論2)成立.引理1證畢.

下面給出主要結(jié)論.在ω條件(式(4))下,Ulm-like方法的收斂階為q,即超線性收斂到解x*.為此,假設(shè)μ>0且設(shè)初始值B0滿足

‖I-B0A0‖≤μ.

(11)

定理1設(shè)x*∈D是非線性方程(1)的一個(gè)解,且Jacobian矩陣f′(x*)可逆.假設(shè)f′及函數(shù)ω分別滿足式(4)與式(5).若對任意非負(fù)整數(shù)k式(6)成立,則存在常數(shù)δ,μ>0,使得對任意的x0∈B(x*,δ)和任意滿足式(11)的B0,由Ulm-like方法產(chǎn)生的序列{xk}超線性收斂到x*.此外,對任意非負(fù)整數(shù)k,下面2個(gè)估計(jì)式成立:

式(12)和式(13)中,τ>0是一個(gè)常數(shù).

證明 令

則0<τ<1顯然成立.另外,設(shè)δ,μ滿足

下面利用數(shù)學(xué)歸納法證明式(12)和式(13)對任意非負(fù)整數(shù)k均成立.首先,由x0∈B(x*,δ)知‖x0-x*‖<δ.再結(jié)合式(15)中δ滿足的條件進(jìn)一步可知當(dāng)k=0時(shí)式(12)成立.另一方面,從式(11)和式(15)可推出

注意到0

由式(16),qm>1及式(14)可知

根據(jù)引理1(k=m),有

xm+1-x*=xm-x*-Bm(f(xm)-f(x*))=

由式(16)可得

由0<τ<1,1

故結(jié)合式(17)與式(19),有

其次,由式(17)、式(21)及式(18)可知

‖I-Bmf′(xm)‖≤‖I-BmAm‖+‖Bm‖‖Am-f′(xm)‖≤

再者,根據(jù)ω條件(式(4)、式(5))及式(16)有

于是把式(21)～式(23)代入式(20)便得

即式(12)對k=m+1成立.

下面考慮‖I-Bm+1Am+1‖的估計(jì).由式(3)可得

I-Bm+1Am+1=I-(2Bm-BmAm+1Bm)Am+1=[I-BmAm+Bm(Am-Am+1)]2.

于是

‖I-Bm+1Am+1‖≤2‖I-BmAm‖2+2‖Bm‖2‖Am+1-Am‖2.

(24)

因?yàn)椤瑇m+1-x*‖

其次,從式(4)、式(5)和式(12)(k取m,m+1)可推出

‖f′(xm+1)-f′(xm)‖≤‖f′(xm+1)-f′(x*)‖+‖f′(xm)-f′(x*)‖≤

ω(‖xm+1-x*‖)+ω(‖xm-x*‖)≤‖xm+1-x*‖q-1ω(1)+‖xm-x*‖q-1ω(1)≤

于是,結(jié)合式(25)、式(26)及式(18)可得

‖Am+1-Am‖≤‖Am+1-f′(xm+1)‖+‖f′(xm+1)-f′(xm)‖+‖Am-f′(xm)‖≤

最后,將式(17)、式(21)及式(27)代入式(24),有

‖I-Bm+1Am+1‖≤2‖I-BmAm‖2+2‖Bm‖2‖Am+1-Am‖2≤

注意:第3個(gè)不等式成立是因?yàn)橛?

綜上所述,式(12)與式(13)對任意非負(fù)整數(shù)k均成立.定理1證畢.

特別地,若函數(shù)ω分別為ω(θ)=Lθ(L>0),ω(θ)=Kθp(K>0,0

推論1設(shè)x*∈D是非線性方程(1)的一個(gè)解,且Jacobian矩陣f′(x*)可逆,并假設(shè)f′在B(x*,r)內(nèi)滿足Lipschitz條件.若對任意非負(fù)整數(shù)k,

‖Ak-f′(xk)‖≤γk‖f(xk)‖,

則存在常數(shù)δ,μ>0,使得對任意的x0∈B(x*,δ)和任意的滿足式(11)的B0,由Ulm-like方法產(chǎn)生的序列{xk}平方收斂到x*.此外,對任意非負(fù)整數(shù)k,下面2個(gè)估計(jì)式成立:

其中,τ>0是一個(gè)常數(shù).

推論2設(shè)x*∈D是非線性方程(1)的一個(gè)解,且Jacobian矩陣f′(x*)可逆,并假設(shè)f′在B(x*,r)內(nèi)滿足(K,p)-H?lder條件.若對任意非負(fù)整數(shù)k,

‖Ak-f′(xk)‖≤γk‖f(xk)‖p,

則存在常數(shù)δ,μ>0,使得對任意的x0∈B(x*,δ)和任意的滿足式(11)的B0,由Ulm-like方法產(chǎn)生的序列{xk}超線性收斂到x*.此外,對任意非負(fù)整數(shù)k,下面2個(gè)估計(jì)式成立:

其中,τ>0是一個(gè)常數(shù).

2 數(shù)值實(shí)驗(yàn)

下面將通過數(shù)值實(shí)驗(yàn)驗(yàn)證上面得到的理論結(jié)果.考慮下面的Hammerstein型非線性積分方程:

式(28)中,g(s,z)是格林函數(shù),即

顯然,求式(28)等價(jià)于求解方程f(x)=0.其中:

f:D?C[0,1]→C[0,1];

本文將利用n個(gè)節(jié)點(diǎn)的Gauss-Legendre求積公式

表1 節(jié)點(diǎn)和對應(yīng)求積系數(shù)的取值

若用xi表示x(zi),i=1,2,…,n,則式(28)等價(jià)于非線性方程

式(29)中:

于是式(29)可寫成

f(x)=x-Cu=0,f:Rn→Rn.

(30)

容易驗(yàn)證

表2 誤差‖xk-x*‖2隨迭代次數(shù)的變化情況