廣義嚴格對角占優矩陣的一種判別法

關晉瑞,任孚鮫

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

1.引言

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

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

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

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

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

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

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

下面是廣義嚴格對角占優矩陣的幾個基本性質[7?8,16].

引理1.1設A為廣義嚴格對角占優矩陣,則對任意的i ∈N,有aii0.

引理1.2設A為廣義嚴格對角占優矩陣,則N1(A)?.

引理1.3設A=(aij)∈Cn×n,則A為廣義嚴格對角占優矩陣當且僅當AD為廣義嚴格對角占優矩陣,其中D為正對角矩陣.

引理1.4設A是不可約對角占優矩陣,則A為廣義嚴格對角占優矩陣.

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

2.主要結果

文[13]提出如下一個廣義嚴格對角占優矩陣的迭代判別法.

算法2.1

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

輸出：“A不是廣義嚴格對角占優矩陣”或者“A是廣義嚴格對角占優矩陣”.

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

2) 令k=0,A0=A；

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

若u ≥1,“A不是廣義嚴格對角占優矩陣”,停止；

若v ≤1,“A是廣義嚴格對角占優矩陣”,停止；

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

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

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

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

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

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

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

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

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

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

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

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

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

算法2.2

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

輸出：“A不是廣義嚴格對角占優矩陣”或者“A是廣義嚴格對角占優矩陣”.

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

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不是廣義嚴格對角占優矩陣”,停止;

若q ≤1,“A是廣義嚴格對角占優矩陣”,停止;

否則計算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不是廣義嚴格對角占優矩陣”,停止；

若v ≤1,“A是廣義嚴格對角占優矩陣”,停止；

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

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

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

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

證若矩陣A對角線有零元素,則算法2.2直接可以停止.若矩陣A對角線無零元素,當矩陣A是廣義嚴格對角占優矩陣時,根據文[13]中的結論,算法2.2中第4步可以在有限步內停止.當矩陣A不是廣義嚴格對角占優矩陣時,根據引理2.1,算法2.2中第3步可以在有限步內停止.證畢.

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

證當算法終止時,有兩個輸出結果: “A不是廣義嚴格對角占優矩陣”和“A是廣義嚴格對角占優矩陣”.下面我們分情況討論.

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

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

3.數值例子

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

例3.1考慮下列矩陣

實驗結果見表格3.1.

表3.1 例3.1的實驗結果

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

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