沈衛(wèi)平, 王 悅

(浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

(1)

稱c*為該逆特征值問題的解.該逆特征值問題的應(yīng)用十分廣泛,如逆Strum-Liouville′s問題、逆Toeplitz eigenvalue問題、核光譜和分子光譜問題、反振弦問題等[4-16].

眾所周知,求解該逆特征值問題等價(jià)于求解如下非線性方程組問題[17-18]：

基于這種等價(jià)關(guān)系,求解一般非線性方程組的牛頓法可用于求解該逆特征值問題[19].雖然牛頓法的收斂速度是二階的，但它的每一個(gè)迭代步驟中均需要計(jì)算矩陣A(ck)的特征向量.當(dāng)矩陣的規(guī)模n很大時(shí),就需要很大的運(yùn)算量.因此,文獻(xiàn)[19]提出了求解逆特征值問題的牛頓類方法及Cayley變換法.相較于牛頓法,這2種方法在保持二階收斂速度的同時(shí),又避免了求解特征向量.之后,很多學(xué)者針對(duì)這2種方法的收斂性及其非精確形式進(jìn)行了研究[1-2,20].除了上述提到的方法外,還有一些方法在降低運(yùn)算的難度與加強(qiáng)算法的穩(wěn)定性方面也有顯著的成效,例如文獻(xiàn)[3,21]中的Ulm類方法.

但這些方法僅僅具有局部收斂性,只有在解的附近選取初值才能保證迭代序列收斂.基于文獻(xiàn)[19]中的Cayley變換法,文獻(xiàn)[22]提出了一種求解逆特征值問題的全局性算法.即使初值離解很遠(yuǎn),該全局算法產(chǎn)生的迭代序列也能收斂.一個(gè)自然的問題是,能否基于文獻(xiàn)[1,19]中的(非精確)牛頓類方法,構(gòu)造一種新的具有全局收斂性質(zhì)的(非精確)牛頓類方法.

本文提出了一種用以求解逆特征值問題的全局性非精確牛頓類方法.不同于文獻(xiàn)[22]中的全局算法,本文的全局算法通過反冪法獲得近似特征向量,并采用經(jīng)典回溯法進(jìn)行全局化.在一定的條件下,給出了該全局算法的收斂性分析,并證明了它的收斂階.最后,通過數(shù)值例子驗(yàn)證了該算法的全局收斂性質(zhì)及其收斂階.

1 全局性非精確牛頓類方法

算法1全局性的非精確牛頓類方法

ρ(c0)=[ρ1(c0),ρ2(c0),…,ρn(c0)]T=[λ1(c0),λ2(c0),…,λn(c0)]T;

計(jì)算雅可比矩陣J(c0),其元素為

求解雅可比方程

J(c0)c1=λ*.

(2)

2)對(duì)于k=1,2,…直到ck收斂,具體步驟如下：

①非精確求解方程

(3)

(4)

且令ρ(ck)=[ρ1(ck),ρ2(ck),…,ρn(ck)]T.

④計(jì)算近似雅可比矩陣Jk,其元素為

⑤非精確求解雅可比方程

(5)

其中,

(6)

⑦若

(7)

⑧計(jì)算下一個(gè)迭代點(diǎn):ck+1=ck+Δck.

注1本文提出的算法與文獻(xiàn)[22]中的算法的最大區(qū)別在于得到近似特征向量的方式不同.本文的算法利用反冪法得到近似特征向量,而文獻(xiàn)[22]的算法則是基于Cayley變換求得近似特征向量.

2 收斂性分析

[J(c)]ij=(qi(c))TAjqi(c), 1≤i,j≤n.

需要引進(jìn)下面幾個(gè)引理.其中,引理1的證明可參閱文獻(xiàn)[23]中的定理4.7;引理2及引理3的證明分別類似于文獻(xiàn)[22]中的引理4及引理6;引理4及引理5的證明分別類似于文獻(xiàn)[1]中的引理4.1及引理4.2.為了節(jié)省篇幅,將其證明省略.

引理1[23]任意ε>0,存在充分小的正數(shù)δ0,對(duì)任意k∈N,當(dāng)‖Δck‖≤δ0時(shí),

‖ρ(ck+Δck)-ρ(ck)-JkΔck‖≤ε‖Δck‖.

‖ρ(ck)-λ*+JkΔck‖≤ηk‖ρ(ck)-λ*‖;

(8)

‖ρ(ck+Δck)-λ*‖≤(1-t(1-ηk))‖ρ(ck)-λ*‖.

(9)

引理3[22]假設(shè)k∈N且近似雅可比矩陣Jk可逆,則

‖Δck‖≤τk(1-ηk)‖ρ(ck)-λ*‖.

(10)

引理4[1]設(shè)k∈N且設(shè)γ為任意正數(shù).若

則

(11)

引理5[1]存在正數(shù)δ1,ξ0與γ,對(duì)任意k∈N,當(dāng)‖ck-c*‖≤δ1時(shí),下列式子成立：

(12)

‖qi(ck)-qi(c*)‖≤ξ0‖ck-c*‖, 1≤i≤n;

(13)

(14)

命題1設(shè)K1為任意正整數(shù),則存在正數(shù)δ2及ξ(不依賴于K1),若

(15)

且

‖ck-c*‖≤δ2, ?k≥K1,

(16)

則對(duì)任意k≥K1,式(12)、式(14)及下面2個(gè)式子成立：

(17)

(18)

證明設(shè)正數(shù)ξ0,γ及δ1為引理5中的常數(shù).令

(19)

下證ξ及δ2即為滿足命題1結(jié)論的常數(shù).為此,假設(shè)式(15)及式(16)成立.由式(16)及δ2的定義,并利用引理5可知,對(duì)任意k≥K1,式(12)～式(14)均成立.接下來利用數(shù)學(xué)歸納法證明對(duì)任意k≥K1,式(17)與式(18)成立.為簡(jiǎn)便起見,設(shè)1≤i≤n.顯然,由式(15)知,當(dāng)k=K1時(shí),式(17)成立.根據(jù)范數(shù)的三角不等式,有

(20)

于是,結(jié)合式(15)和式(13)(k=K1+1)可得

(21)

進(jìn)一步,再利用式(16)和δ2的定義,容易推得

從而,當(dāng)k=K1時(shí),式(18)成立.

假設(shè)當(dāng)k≤l-1時(shí),式(17)及式(18)成立.于是,應(yīng)用引理4并結(jié)合式(12)(k=l),有

(22)

因此,結(jié)合式(13)及ξ的定義,可得

也就是說,當(dāng)k=l時(shí),式(17)成立.注意到當(dāng)k=l時(shí),式(18)的證明完全類似于其k=K1時(shí)的證明,考慮到篇幅問題,筆者省略了這部分的證明.于是,命題1得證.

為了證明全局性非精確牛頓類方法的全局收斂性和收斂階,需要引入下面3個(gè)引理.其中,引理6的證明可以參閱文獻(xiàn)[1]中的引理4.4;引理7及引理8 的證明可以分別參閱文獻(xiàn)[22]中的推論7和引理9.

引理6[1]對(duì)任意k∈N,由算法1產(chǎn)生的近似雅可比矩陣Jk滿足

(23)

引理7[22]設(shè)k∈N.若ρ(ck)-λ*≠0且近似雅可比矩陣Jk可逆,則當(dāng)算法1中步驟⑦的內(nèi)循環(huán)停止時(shí),

(24)

(25)

下面給出本文的主要定理.

(26)

則當(dāng)k→∞時(shí),ck→c*且ρ(ck)→λ*,并且序列{ck}至少具有β階的收斂速度.

下面利用反證法證明序列{ck}的收斂性.假設(shè)當(dāng)k→∞時(shí),ck→/c*,則存在δ5∈(0,δ4)和子列{ckt},使得ckt?B(c*,δ5),t=1,2,….又因?yàn)閏*是序列{ck}的聚點(diǎn),故存在序列{kj}?N,使得當(dāng)j→∞時(shí),ckj→c*.選擇lj>0滿足kj+lj

結(jié)合式(25)可知,對(duì)任意的k≥K2,

(27)

又因?yàn)閏k+1=ck+Δck,所以存在充分大的正整數(shù)K3≥K2,對(duì)任意的j≥K3,有

(28)

其中倒數(shù)第2個(gè)不等式可由引理3推得.由式(9)易得

因此,

(29)

另一方面,因?yàn)閠,ηk∈(0,1),所以由式(9)可知

‖ρ(ck+1)-λ*‖≤‖ρ(ck)-λ*‖, ?k∈N.

因此,

(30)

于是,結(jié)合式(28)～式(30),有

(31)

又因?yàn)楫?dāng)j→∞時(shí),有ckj→c*,所以,‖ρ(ckj)-λ*‖-‖ρ(ckj+1)-λ*‖→0,得到矛盾.因此,假設(shè)不成立.從而,當(dāng)k→∞時(shí),ck→c*.

接下來證明當(dāng)k→∞時(shí),ρ(ck)→λ*.由定理1條件并應(yīng)用命題1可得,對(duì)任意k≥K2,式(12)、式(14)、式(17)及式(18)成立.于是,應(yīng)用引理4,當(dāng)k≥K2+1時(shí),

(32)

因?yàn)?/p>

(33)

因此,利用式(12)、式(32)及式(33),對(duì)任意k≥K2+1,

(34)

又因?yàn)?/p>

(35)

因此,由式(34)和式(35)可推出

‖ρ(ck)-λ*‖≤ρ‖ck-c*‖, ?k≥K2+1.

(36)

rk=JkΔck+ρ(ck)-λ*.

(37)

那么，根據(jù)算法1中的步驟⑤可知

(38)

注意到Δck=ck+1-ck和Jkck=ρ(ck).將這2個(gè)式子代入式(37),計(jì)算可得

Jk(ck+1-c*)=rk-(Jkc*-λ*).

(39)

‖ck+1-c*‖≤2‖J(c*)-1‖(‖rk‖+‖Jkc*-λ*‖).

(40)

應(yīng)用引理6,并結(jié)合式(17)及條件ck∈B(c*,δ4),有

(41)

另一方面,利用式(38)、式(6)和式(36),容易推得

(42)

將式(41)與式(42)代入式(40),可得

從而,序列{ck}的收斂速度至少是β階的.定理1證畢.

3 數(shù)值算例

下面將通過若干個(gè)數(shù)值例子驗(yàn)證全局性非精確牛頓類方法的理論結(jié)果.例1研究了逆Toeplitz 特征值問題[16],例2考慮了Toeplitz-plus-Hankel逆特征值問題[7].

所有的數(shù)值實(shí)驗(yàn)均采用Matlab中的qmr函數(shù)求解算法1中的式(2)、式(3)及式(5).另外，當(dāng)

給定的精確解與精確特征值向量分別為

c*=(2,3,4,5,6)T,λ*=(-5.236 1,-1.587 6,-0.763 9,-0.555 5,18.143 1)T.

例1考慮以下3個(gè)不同的初始值：1)c0=(1,2,3,4,5)T;2)c0=(21,38,46,63,81)T;3)c0=(150,159,168,170,180)T.表1～表3列出了在這3個(gè)初始值下,該全局算法的數(shù)值實(shí)驗(yàn)結(jié)果.

表1 初值為c0=(1,2,3,4,5)T的數(shù)值實(shí)驗(yàn)結(jié)果

表2 初值為c0=(21,38,46,63,81)T的數(shù)值實(shí)驗(yàn)結(jié)果

表3 初值為c0=(150,159,168,170,180)T的數(shù)值實(shí)驗(yàn)結(jié)果

給定的精確解與精確特征值分別為:

c*=(15,16,17,18,19)T,λ*=(-59.951 4,-24.048 5,-19.696 4,23.258 6,53.437 7)T.

考慮以下3個(gè)不同的初始值：1)c0=(31,32,33,34,35)T;2)c0=(35,45,60,80,95)T;3)c0=(150,159,168,175,185)T.表4～表6列出了在這3個(gè)初始值下,該全局算法的數(shù)值實(shí)驗(yàn)結(jié)果.

表4 初值為c0=(31,32,33,34,35)T的數(shù)值實(shí)驗(yàn)結(jié)果

表5 初值為c0=(35,45,60,80,95)T的數(shù)值實(shí)驗(yàn)結(jié)果

表6 初值為c0=(150,159,168,175,185)T的數(shù)值實(shí)驗(yàn)結(jié)果

從上面2個(gè)例子的數(shù)值實(shí)驗(yàn)結(jié)果可以看出,即使初始值沒有靠近問題的解c*,由算法1產(chǎn)生的序列{ck}依然能收斂至c*,這恰好說明了本文所提出的非精確牛頓類算法的收斂性具有全局性質(zhì).同時(shí),從表1～表6中的數(shù)據(jù)也可以看出序列{ck}的超線性收斂性質(zhì).