廣義嚴(yán)格對(duì)角占優(yōu)矩陣的一種判別法

關(guān)晉瑞,任孚鮫

(太原師范學(xué)院數(shù)學(xué)系,山西 晉中030619)

1.引言

廣義嚴(yán)格對(duì)角占優(yōu)矩陣是一類很重要的特殊矩陣,在矩陣?yán)碚?數(shù)值分析,控制論及數(shù)理經(jīng)濟(jì)學(xué)中都有著廣泛的應(yīng)用[2?3,8,11,14?16].有關(guān)廣義嚴(yán)格對(duì)角占優(yōu)矩陣的判定一直是人們研究的一個(gè)重點(diǎn).近年來很多學(xué)者都對(duì)此問題作了深入的研究,得到了大量的成果[1,4?7,9?10,12?13].

為了方便討論,下面我們首先給出有關(guān)廣義嚴(yán)格對(duì)角占優(yōu)矩陣的一些基本概念,術(shù)語符號(hào)及常見結(jié)論.設(shè)A=(aij)∈Cn×n,記N={1,2,··· ,n},對(duì)任意的i ∈N,令以及

定義1.1[8,16]設(shè)A=(aij)∈Cn×n,若對(duì)任意的i ∈N,都有|aii|>ri(A),則稱A為嚴(yán)格對(duì)角占優(yōu)矩陣.若存在正對(duì)角矩陣D,使得AD為嚴(yán)格對(duì)角占優(yōu)矩陣,則稱A為廣義嚴(yán)格對(duì)角占優(yōu)矩陣.

定義1.2[16]設(shè)A=(aij)∈Cn×n,若存在置換矩陣P,使得

其中A11,A22分別為k×k,(n ?k)×(n ?k)的矩陣,1≤k < n,則稱矩陣A是可約的.否則稱A是不可約的.

定義1.3[8,16]設(shè)A=(aij)∈Cn×n不可約,若對(duì)任意的i ∈N,有|aii|≥ri(A),且至少有一個(gè)嚴(yán)格不等式成立,則稱A為不可約對(duì)角占優(yōu)矩陣.

定義1.4[16]設(shè)A=(aij)∈Cn×n,稱m(A)=(αij)∈Rn×n為A的判別矩陣,其中

下面是廣義嚴(yán)格對(duì)角占優(yōu)矩陣的幾個(gè)基本性質(zhì)[7?8,16].

引理1.1設(shè)A為廣義嚴(yán)格對(duì)角占優(yōu)矩陣,則對(duì)任意的i ∈N,有aii0.

引理1.2設(shè)A為廣義嚴(yán)格對(duì)角占優(yōu)矩陣,則N1(A)?.

引理1.3設(shè)A=(aij)∈Cn×n,則A為廣義嚴(yán)格對(duì)角占優(yōu)矩陣當(dāng)且僅當(dāng)AD為廣義嚴(yán)格對(duì)角占優(yōu)矩陣,其中D為正對(duì)角矩陣.

引理1.4設(shè)A是不可約對(duì)角占優(yōu)矩陣,則A為廣義嚴(yán)格對(duì)角占優(yōu)矩陣.

現(xiàn)有文獻(xiàn)中關(guān)于廣義嚴(yán)格對(duì)角占優(yōu)矩陣的判別法大多數(shù)都是直接法,但直接法判定范圍狹窄,復(fù)雜且不實(shí)用,相比之下,迭代判別法具有更大的優(yōu)勢(shì),并且可以充分利用計(jì)算機(jī)來實(shí)現(xiàn)[1,7].本文研究廣義嚴(yán)格對(duì)角占優(yōu)矩陣的迭代判別法,在第2節(jié)我們提出廣義嚴(yán)格對(duì)角占優(yōu)矩陣的一種迭代判別法,并證明了相應(yīng)的收斂性理論,在第3節(jié)中用數(shù)值算例展示了該判別法的有效性.

2.主要結(jié)果

文[13]提出如下一個(gè)廣義嚴(yán)格對(duì)角占優(yōu)矩陣的迭代判別法.

算法2.1

輸入：不可約矩陣A=(aij)∈Cn×n.

輸出：“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”或者“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”.

1) 若對(duì)某個(gè)i ∈N,有aii=0 ,“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止；否則

2) 令k=0,A0=A；

3) 對(duì)i ∈N,計(jì)算ti(Ak),及

若u ≥1,“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止；

若v ≤1,“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止；

否則計(jì)算Ak+1=AkDk,其中Dk=diag(d1,d2,··· ,dn),且

4) 令k=k+1,返回第3步.

該算法的優(yōu)點(diǎn)是運(yùn)算量小,每步迭代只需要O(n)的運(yùn)算量,而其他的一些判別法每步都需要O(n2)的運(yùn)算量.對(duì)于不可約廣義嚴(yán)格對(duì)角占優(yōu)矩陣,該算法具有良好的收斂性.

通過數(shù)值實(shí)驗(yàn)我們發(fā)現(xiàn)當(dāng)所要判別的矩陣不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣時(shí),算法2.1所需的迭代次數(shù)比較多,因此有待進(jìn)一步改進(jìn).通過對(duì)算法2.1的深入研究,我們發(fā)現(xiàn)其基本思想是不斷縮小占優(yōu)行對(duì)角元所在列元,從而最終得到矩陣是否為廣義嚴(yán)格對(duì)角占優(yōu)矩陣的結(jié)論.經(jīng)過分析我們認(rèn)為如果同時(shí)對(duì)占優(yōu)行對(duì)角元所在列進(jìn)行不斷縮小,以及對(duì)占劣行對(duì)角元所在列進(jìn)行不斷放大,這樣會(huì)取得更好的效果,避免了其缺陷.下面按照這個(gè)想法我們對(duì)算法2.1進(jìn)行改進(jìn).

設(shè)A=(aij)∈Cn×n不可約,構(gòu)造序列{Ak}如下：

依此類推,可以得到矩陣序列{Ak}.由構(gòu)造過程可以看到該矩陣序列元素的絕對(duì)值不斷變大.對(duì)于該矩陣序列,我們有下面的結(jié)論.

引理2.1設(shè)A=(aij)∈Cn×n不可約,若A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,對(duì)角線元素非零且判別矩陣m(A)非奇異,則對(duì)于上述構(gòu)造的矩陣序列{Ak},存在一個(gè)正整數(shù)K,當(dāng)k > K時(shí),有N1(Ak)=?.

證首先注意到當(dāng)k增加時(shí),集合N1(Ak)的元素個(gè)數(shù)不增,而N0(Ak)∪N2(Ak)的元素個(gè)數(shù)不減.這是因?yàn)?i ∈N1(Ak),設(shè)tp(Ak)=max1≤i≤nti(Ak),則tp(Ak)>1,且.從而

這樣有可能ti(Ak+1)≥1,進(jìn)而1(Ak+1).而對(duì)于當(dāng)i=p時(shí),很明顯i ∈N0(Ak+1),而當(dāng)ip時(shí),

其次,假設(shè)引理結(jié)論不成立,即對(duì)任意正整數(shù)k,都有N1(Ak)?.根據(jù)上面的分析則存在一個(gè)正整數(shù)l,使得?m >0,有N1(Al)=N1(Al+m).為了討論方便,不妨設(shè)N1(Al)={1,2,··· ,k},且

其中A11是k×k的.這樣Al的前k行是嚴(yán)格對(duì)角占優(yōu)行,且由上面假設(shè)對(duì)于任意m > l,Am的前k行也是嚴(yán)格對(duì)角占優(yōu)行.而根據(jù)引理的條件,Al的后n ?l行必存在嚴(yán)格對(duì)角占劣行,否則Al將是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,這與引理?xiàng)l件矛盾.類似的對(duì)于任意m>1,Am的后n ?k行必存在嚴(yán)格對(duì)角占劣行.這樣對(duì)于Al而言,當(dāng)l增大時(shí),對(duì)應(yīng)的子塊A12中的元素將不斷增大,但是由于前k行是嚴(yán)格對(duì)角占優(yōu)行,于是A12中的元素存在上界,從而必有極限.設(shè)

我們來看看最后極限結(jié)果中的B和C.容易證明Aω后n ?k列不會(huì)趨于無窮大,而且

因此Aω?zé)o嚴(yán)格對(duì)角占劣行.若Aω前k行存在嚴(yán)格對(duì)角占優(yōu)行,則Aω是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,與定理?xiàng)l件矛盾.若Aω前k行不存在嚴(yán)格對(duì)角占優(yōu)行,即有ti(Aω)=1,則m(Aω)奇異,從而m(A)也奇異,這也與定理假設(shè)矛盾.從而對(duì)于充分大k必有N1(Ak)=?.證畢.根據(jù)前面的分析以及上述定理,我們提出下面的判別法.

算法2.2

輸入：不可約矩陣A=(aij)∈Cn×n.

輸出：“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”或者“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”.

1) 若對(duì)某個(gè)i ∈N,有aii=0 ,“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止; 否則

2) 令k=0,B0=A,C0=A;

3) 對(duì)i ∈N,計(jì)算ti(Bk),及p=min1≤i≤nti(Bk),[q,qq]=max1≤i≤nti(Bk);

若p ≥1,“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止;

若q ≤1,“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止;

否則計(jì)算Bk+1=BkDk,其中Dk=diag(d1,d2,··· ,dn),且

4) 對(duì)i ∈N,計(jì)算ti(Ck),及[u,uu]=min1≤i≤nti(Ck),v=max1≤i≤nti(Ck)；

若u ≥1,“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止；

若v ≤1,“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”,停止；

否則計(jì)算Ck+1=CkDk,其中Dk=diag(d1,d2,··· ,dn),且

5) 令k=k+1,返回第3步.

下面我們分析算法2.2的收斂性.

定理2.1對(duì)任意給定的不可約矩陣A=(aij)∈Cn×n,假設(shè)判別矩陣m(A)非奇異,則算法2.2總是收斂的.

證若矩陣A對(duì)角線有零元素,則算法2.2直接可以停止.若矩陣A對(duì)角線無零元素,當(dāng)矩陣A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣時(shí),根據(jù)文[13]中的結(jié)論,算法2.2中第4步可以在有限步內(nèi)停止.當(dāng)矩陣A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣時(shí),根據(jù)引理2.1,算法2.2中第3步可以在有限步內(nèi)停止.證畢.

定理2.2對(duì)任意給定的不可約矩陣A=(aij)∈Cn×n,若算法2.2收斂,則它的結(jié)論是正確的.

證當(dāng)算法終止時(shí),有兩個(gè)輸出結(jié)果: “A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”和“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”.下面我們分情況討論.

當(dāng)輸出結(jié)果為“A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”時(shí),可能在第1、3或4步.若在第1步停止,則對(duì)某個(gè)i ∈N,有aii=0,根據(jù)引理1.1,A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣.若在第3步停止,則對(duì)任意i ∈N,有ti(Bk)≥1,即有N1(Bk)=?,根據(jù)引理1.2,Bk不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而由引理1.3,A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣.若在第4步停止,則對(duì)任意i ∈N,有ti(Ck)≥1,即有N1(Ck)=?,根據(jù)引理1.2,Ck不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而A不是廣義嚴(yán)格對(duì)角占優(yōu)矩陣.

當(dāng)輸出結(jié)果為“A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣”時(shí),可能在第3、4步.若在第3步停止,則對(duì)任意i ∈N,有ti(Bk)≤1,由于前面已經(jīng)處理了ti(Bk)≥1的情形,此時(shí)有ti(Bk)≤1,且至少有一個(gè)不等式是嚴(yán)格的,從而根據(jù)引理1.4,Bk是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣.若在第4步停止,則對(duì)任意i ∈N,有ti(Ck)≤1,由于前面已經(jīng)處理了ti(Ck)≥1的情形,此時(shí)有ti(Ck)≤1,且至少有一個(gè)不等式是嚴(yán)格的,根據(jù)引理1.4,Ck是廣義嚴(yán)格對(duì)角占優(yōu)矩陣,從而A是廣義嚴(yán)格對(duì)角占優(yōu)矩陣.證畢.

3.數(shù)值例子

本節(jié)中,我們通過幾個(gè)例子來檢驗(yàn)提出的判別法(算法2.2)的有效性,并與算法2.1進(jìn)行比較.實(shí)驗(yàn)用Matlab(R2012a),并在個(gè)人機(jī)上運(yùn)行.實(shí)驗(yàn)結(jié)果給出兩種算法的判別結(jié)果(GDDM),所需的迭代次數(shù)(IT)以及計(jì)算時(shí)間(CPU).實(shí)驗(yàn)的例子取自文[1,7].

例3.1考慮下列矩陣

實(shí)驗(yàn)結(jié)果見表格3.1.

表3.1 例3.1的實(shí)驗(yàn)結(jié)果

從實(shí)驗(yàn)結(jié)果可以看到,對(duì)于非廣義嚴(yán)格對(duì)角占優(yōu)矩陣,算法2.2所需要的迭代次數(shù)和計(jì)算時(shí)間明顯少得多,而對(duì)于廣義嚴(yán)格對(duì)角占優(yōu)矩陣,算法2.2比算法2.1在一些例子中所需要的迭代次數(shù)和計(jì)算時(shí)間也有一定的減少,因此我們的算法是很有效的.

以上我們提出一個(gè)廣義嚴(yán)格對(duì)角占優(yōu)矩陣的判別法,理論分析和數(shù)值算例顯示了該算法是有效的.本判別法的不足之處是依賴于矩陣的不可約性,對(duì)于可約矩陣則不能奏效.如何把我們的算法推廣到判別可約矩陣,則是我們今后的工作.