求解大型廣義絕對(duì)值方程的Picard-SS迭代法

尹曉霞,李 旭

(蘭州理工大學(xué)理學(xué)院,甘肅 蘭州 730050)

考慮求解大型廣義絕對(duì)值方程 (GAVE)

Ax-B|x|=b,

(1)

其中:A,B∈n×n與b∈n都是給定的矩陣和向量,|x|=(|x1|,…,|xn|)T∈n表示對(duì)x的每個(gè)分量取絕對(duì)值。當(dāng)B是單位矩陣時(shí),GAVE 特殊化為絕對(duì)值方程 (AVE):

Ax-|x|=b。

(2)

許多科學(xué)計(jì)算和工程應(yīng)用領(lǐng)域中的優(yōu)化問(wèn)題[1]都?xì)w結(jié)為求解GAVE(1),該方程的一個(gè)重要研究來(lái)源是如下的線性互補(bǔ)問(wèn)題LCP(q,M)[2]:

對(duì)于給定的矩陣M∈n×n和向量q∈n,求一對(duì)實(shí)向量z,ω∈n使得

z≥0,ω=Mz+q≥0,zTω=0。

(3)

根據(jù)文獻(xiàn)[3-5],線性互補(bǔ)問(wèn)題 (3) 可轉(zhuǎn)化為如下 GAVE:

(M+I)x-(M-I)|x|=q,

在理論分析方面,最早是由Mangasarian給出了GAVE(1)解存在的充分條件,隨后一些學(xué)者改進(jìn)和豐富了解的存在性理論[6-8]。在數(shù)值算法方面,除了早期的有限逐次線性化方法[9]、整數(shù)規(guī)劃法[10]和符號(hào)一致算法[11],Mangasarian通過(guò)引入非線性項(xiàng)|x|的次梯度,提出了廣義Newton(GN)迭代法。之后為了進(jìn)一步提高計(jì)算效率,產(chǎn)生了一些改進(jìn)GN的迭代法,如廣義Traub迭代法[12]、修正GN迭代法[13]、松弛GN迭代法[14]等,但這些方法都有一個(gè)很大的缺陷,每一步迭代都需求解不同系數(shù)矩陣的線性系統(tǒng),從而導(dǎo)致計(jì)算成本很高。

為了克服這一問(wèn)題,針對(duì)GAVE(1),Rohn等[15]提出了非常高效的Picard迭代法:

Ax(k+1)=B|x(k)|+b,k=0,1,2,…,

(4)

其中:x(0)=A-1b是初始估值。

鑒于Picard迭代中的每一個(gè)線性系統(tǒng)的系數(shù)矩陣都是A,因此可以利用矩陣分裂方法高效求解這些子系統(tǒng)。Salkuyeh給出了一個(gè)很好的范例,并結(jié)合著名的Hermitian和反Hermitian分裂(HSS)迭代法[16],提出了求解AVE(2)的Picard-HSS迭代法[17]。收斂性分析表明Picard-HSS迭代法的收斂性與初值的選取無(wú)關(guān),數(shù)值實(shí)驗(yàn)表明Picard-HSS迭代法比Picard迭代法和GN迭代法更高效。最近,Miao等學(xué)者利用單步HSS(SHSS)迭代法[18]提出了求解AVE(2)的Picard-SHSS迭代法[19]。

針對(duì)求解非Hermitian正定線性系統(tǒng),Bai等[20]提出的Shift分裂(SS)迭代法是一種相較于HSS和SHSS迭代法更加高效的算法,尤其是針對(duì)條件數(shù)很大的情形?；谶@一點(diǎn),將Picard迭代法作為外迭代,對(duì)于每一步外迭代對(duì)應(yīng)的線性系統(tǒng),將SS迭代法作為內(nèi)迭代求解器,建立求解GAVE(1)的Picard-SS迭代法,并且給出該方法的收斂性分析,最后通過(guò)數(shù)值算例檢驗(yàn)Picard-SS 迭代法的可行性和高效性。

1 Picard-SS迭代法的建立

針對(duì)非Hermitian正定線性系統(tǒng)

Ax=b,

(5)

Bai等[20]利用A的Shift分裂(SS)

提出了如下求解線性系統(tǒng)(5)的Shift分裂(SS)迭代法:

算法1(SS迭代法)對(duì)于給定的任意初始向量x(0)∈n，l=0,1,2,…,利用下述迭代格式計(jì)算x(l+1)直到迭代序列n收斂:

(αI+A)x(l+1)=(αI-A)x(l)+2b,

(6)

式(6)中α為給定的正常數(shù)。

將SS迭代法運(yùn)用到Picard迭代法的每一個(gè)子迭代線性系統(tǒng)(4),建立如下求解GAVE(1)的 Picard-SS迭代法。

算法2(Picard-SS迭代法)設(shè)A∈n×n是非Hermitian對(duì)稱正定矩陣,B∈n×n。對(duì)于給定的任意初始估值x(0)∈n,k=0,1,2,…,利用迭代格式計(jì)算x(k+1)∈n直到迭代序列滿足停止準(zhǔn)則:

(1) 設(shè)x(k,0):=x(k);

(2) 對(duì)于l=0,1,2,…,lk-1,應(yīng)用如下SS迭代法求解得到x(k,l+1):

(αI+A)x(k,l+1)=(αI-A)x(k,l)+2(B|xk|+b),

(7)

其中:α為給定的正常數(shù);

(3) 令x(k+1):=x(k,lk)。

注1與HSS迭代法[16]相比,SS迭代法式(7)的優(yōu)勢(shì)在于單步迭代;與SHSS迭代法相比,SS迭代法式(7)的優(yōu)勢(shì)在于無(wú)條件收斂。因此Picard-SS迭代法在更短時(shí)間內(nèi)得到迭代解,從而可以大大降低計(jì)算成本。

注2在算法2中,若取B為單位矩陣,則得到求解AVE(2)的Picard-SS迭代法。

2 收斂性分析

為了后續(xù)討論方便,記

首先將Picard-SS迭代法的內(nèi)迭代式(7)等價(jià)改寫(xiě)為以下形式:

x(k,l+1)=T(α)x(k,l)+G(α)(B|x(k)|+b),

(8)

這里

T(α)=M(α)-1N(α),G(α)=M(α)-1。

進(jìn)一步可將式(8)改寫(xiě)為

x(k+1)=T(α)lkx(k)+

(9)

根據(jù)文獻(xiàn)[21]中引理2.1,對(duì)于內(nèi)迭代矩陣T(α)有如下引理:

引理1設(shè)A∈n×n是非Hermitian正定矩陣,記ρ(T(α))為T(mén)(α)的譜半徑,則有

ρ(T(α))≤‖T(α)‖2≤

‖(αI+A)-1(αI-A)‖2<1。

接下來(lái)給出并證明Picard-SS迭代法的收斂性定理。

定理1設(shè)A∈n×n是非Hermitian正定矩陣,B∈n×n是非奇異矩陣。令η=‖A-1B‖2<1,則GAVE(1) 存在唯一解x*。對(duì)任意的x(0)∈n以及任意正整數(shù)序列設(shè)若

(10)

則由Picard-SS迭代法生成的迭代序列x(k)收斂于精確解x*。

證明為方便討論,將GAVE等價(jià)改寫(xiě)為如下形式的AVE:

B-1Ax-|x|=B-1b。

根據(jù)條件η=‖A-1B‖2<1,由文獻(xiàn)[4]中的命題4可得,以上方程有唯一解x*。

由于唯一解x*也滿足不動(dòng)點(diǎn)方程

(αI+A)x*=(αI-A)x*+2(B|x*|+b),

(11)

同樣可將式(11)等價(jià)改寫(xiě)為

(12)

式(9)與式(12) 相減,得

x(k+1)-x*=T(α)lk(x(k)-x*)+

(13)

因?yàn)棣?T(α))<1,有

(I-T(α)lk)(I-M(α)-1N(α))-1M(α)-1=

(I-T(α)lk)A-1,

(14)

將式(14)代入式(13)得

x(k+1)-x*=T(α)lk(x(k)-x*)+

(I-T(α)lk)A-1B(|x(k)|-|x*|)=

T(α)lk[(x(k)-x*)-A-1B(|x(k)|-

|x*|)]+A-1B(|x(k)|-|x*|),

(15)

對(duì)式(15)兩邊同取2-范數(shù),可得

‖x(k+1)-x*‖2≤(‖T(α)lk‖2(1+η)+

η)‖x(k)-x*‖2。

根據(jù)條件(10)有

容易得到以下的殘量更新形式以方便實(shí)際計(jì)算。

算法3(Picard-SS迭代法的殘量更新形式)設(shè)A∈n×n是非Hermitian對(duì)稱正定矩陣,B∈n×n。對(duì)于給定的任意初始估值x(0)∈n,k=0,1,2,…,利用下述迭代格式計(jì)算x(k+1)∈n直到迭代序列滿足停止準(zhǔn)則:

(1) 設(shè)s(k,0):=0,b(k)=B|x(k)|+b-Ax(k);

(2) 對(duì)于l=0,1,2,…,lk-1,應(yīng)用如下SS迭代法求解得到s(k,l+1):

(αI+A)s(k,l+1)=(αI-A)s(k,l)+b(k),

其中:α為給定的正常數(shù);

(3) 令x(k+1):=x(k)+s(k,lk)。

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

通過(guò)外迭代步數(shù) (記作ITout)、內(nèi)迭代步數(shù) (記作ITint) 和CPU時(shí)間 (單位為秒,記作CPU)3個(gè)指標(biāo)比較Picard-HSS和 Picard-SS迭代法求解GAVE (1) 的計(jì)算效率。由于SS迭代法是單步迭代,為了公平比較,我們將SS迭代法也寫(xiě)成兩步迭代的格式計(jì)內(nèi)迭代步數(shù),數(shù)值實(shí)驗(yàn)實(shí)現(xiàn)平臺(tái):Matlab,Intel(R) Core(TM) i5 processor (2.20 GHz,4 GB RAM),在算法實(shí)現(xiàn)時(shí),取初值x(0)=(1,0,1,0,…,1,0,…)T,外迭代停止標(biāo)準(zhǔn)為

內(nèi)迭代停止標(biāo)準(zhǔn)為

為塊三對(duì)角矩陣,

S=Tridiag(-1.5,4,-0.5)=

為三對(duì)角矩陣,n=m2且z*=(1.2,1.2,…,1.2,…)T是LCP(q,M)的唯一解。因此

x*=(-0.6,-0.6,…,-0.6,…)T

是GAVE(1)的精確解。

對(duì)于不同的規(guī)模n,表1和表2分別列出了當(dāng)μ=4和μ=10時(shí)兩種迭代法的數(shù)值結(jié)果,包括實(shí)驗(yàn)最優(yōu)迭代參數(shù)、內(nèi)外迭代步數(shù)以及CPU時(shí)間。

表1 μ=4的數(shù)值結(jié)果Table 1 Numerical results with μ=4

表2 μ=10的數(shù)值結(jié)果Table 2 Numerical results with μ=10

從表1和表2容易看出,隨著問(wèn)題規(guī)模n的增大,無(wú)論是內(nèi)外迭代步數(shù)還是CPU時(shí)間,Picard-SS迭代法都要明顯優(yōu)于Picard-HSS迭代法。因此可知,Picard-SS迭代法是求解GAVE(1)的一種非常高效的方法。

4 結(jié)論

對(duì)于求解大規(guī)模廣義絕對(duì)值方程,研究利用Picard內(nèi)迭代線性系統(tǒng)的系數(shù)矩陣的Shift分裂(SS),提出了相比現(xiàn)存迭代法更加高效的Picard-SS迭代法，詳細(xì)分析了該方法的收斂性,并且通過(guò)數(shù)值實(shí)驗(yàn)驗(yàn)證了其有效性和優(yōu)越性。