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

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

1.引言

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

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

定義1.1[8,16]設(shè)A=(aij)∈Cn×n,若對任意的i ∈N,都有|aii|>ri(A),則稱A為嚴(yán)格對角占優(yōu)矩陣.若存在正對角矩陣D,使得AD為嚴(yán)格對角占優(yōu)矩陣,則稱A為廣義嚴(yán)格對角占優(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不可約,若對任意的i ∈N,有|aii|≥ri(A),且至少有一個嚴(yán)格不等式成立,則稱A為不可約對角占優(yōu)矩陣.

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

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

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

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

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

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

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

2.主要結(jié)果

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

算法2.1

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

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

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

2) 令k=0,A0=A；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法2.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.數(shù)值例子

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

例3.1考慮下列矩陣

實驗結(jié)果見表格3.1.

表3.1 例3.1的實驗結(jié)果

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

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