對角相似變換下的非負矩陣最大特征值算法

王信存,呂洪斌,商鈺瑩

(1.遼東學院 師范學院,遼寧 丹東 118003；2.北華大學 數(shù)學與統(tǒng)計學院,吉林 吉林 132013)

1 引言與預備知識

非負矩陣在計算數(shù)學、線性規(guī)劃、計算機科學技術、自動控制等領域應用廣泛[1-3],非負矩陣最大特征值的估計與計算是非負矩陣理論中的經典內容,在數(shù)值代數(shù)中具有重要意義.

設Mn()和Mn()分別表示實數(shù)域和復數(shù)域上的n×n階矩陣集合,N={1,2,…,n},+表示正整數(shù)集合.設A=(aij)∈Mn(),記表示矩陣A的有向圖,C(A)表示Γ(A)的簡單回路集合,σ(A)表示矩陣A的譜集,表示矩陣A的譜半徑,表示n階正對角矩陣的集合,E表示單位矩陣.若A=(aij)∈Mn(),且aij≥0(i,j∈N),則稱A為非負矩陣,記為A∈Mn(+).設A∈Mn(+),由Perron-Frobenius定理[1,4]知ρ(A)∈σ(A),稱為非負矩陣A的最大特征值,也稱ρ(A)為非負矩陣A的Perron根.對A=(aij)∈Mn(+),α∈,記A(α)=A+αE,ri(A(α))=ri(A)+α∶=ri(α),i∈N.

定義1[1,4]設矩陣A=(aij)∈Mn(),如果存在n階置換矩陣P,使得其中A11為r×r階矩陣(1≤r

設A=(aij)∈Mn(+)不可約，Ax=ρ(A)x,x∈n,則x可取為正向量，且當‖x‖1=1時稱x為A的Perron向量[4].

目前,關于不可約非負矩陣最大特征值的計算已有很多成果,如: 文獻[5]給出了13種具體算法,對不可約非負矩陣最大特征值的計算進行了系統(tǒng)研究；文獻[6-7]的算法適用于不可約非負矩陣,但涉及指數(shù)運算；文獻[8-10]給出的算法適用于一類不可約非負矩陣,即對角元素均非零或至少有一個非零元素的本原矩陣.本文給出一類基于對角相似變換的不可約非負矩陣最大特征值和對應特征向量的算法,結果表明,該算法計算簡潔,并適用于所有不可約非負矩陣.

定理1(Perron-Frobenius定理)[4]設A=(aij)∈Mn(+),ρ(A)是A的最大特征值,則

設A=(aij)∈Mn(+)是不可約的,記不妨設r(0)

類似于文獻[7,9]的證明，有:

引理1設A=(aij)∈Mn(+)不可約,?γ∈C(A),記γ:i1→i2→…→ir→ir+1=i1,則?m∈+,有

引理2設A=(aij)∈Mn(+)不可約,ρ(A)是A的最大特征值,不妨設r<ρ(A)

證明：由定理1,顯然有r(m)≤ρ(A)≤R(m),m∈+∪{0},而

證畢.

類似文獻[7,9]的證明,有:

引理3設A=(aij)∈Mn(+)不可約,如果aij>0(i,j∈N),則

由引理3知

2 主要結果

定理2設A=(aij)∈Mn(+)不可約,ρ(A)是A的最大特征值,則在上述矩陣序列和記號下,有

由式(1),類似地有

進一步有

因此,?i∈N,有

進一步,?k∈+,有

下面考慮不可約非負矩陣A=(aij)∈Mn(+)的Perron向量的數(shù)值算法.記

定理3設A=(aij)∈Mn(+)不可約,ρ(A)是A的最大特征值,則n是A的相應于ρ(A)的正特征向量,進而可得A的相應于ρ(A)的Perron向量.

3 算法及分析

根據(jù)上述迭代矩陣的構造過程和定理2,下面給出本文的算法.

算法1計算不可約非負矩陣最大特征值算法.

輸入: 不可約非負矩陣A=(aij)∈Mn(+),0<ε<1；

步驟3) 令di=ri+θ(rmax-ri),D=diag(d1,d2,…,dn),D-1AD∶=A,轉步驟1).

由定理2知,算法1適合所有不可約非負矩陣最大特征值的計算,且適用范圍廣、簡單實用.

例1隨機構造循環(huán)指數(shù)為3的不可約非負矩陣:

對于矩陣A,文獻[8,10]的算法不能直接應用,而文獻[9]的算法需考慮矩陣A+E6.表1列出了應用本文算法、文獻[5]的第九個算法(取γ=0.8)和文獻[9]的算法計算矩陣A最大特征值的迭代次數(shù)比較結果.

表1 不同算法計算ρ(A)的迭代次數(shù)比較

由表1可見,本文算法不但適用于所有不可約非負矩陣最大特征值及對應特征向量的計算,而且參數(shù)的選擇更方便,并且在適當?shù)膮?shù)選擇下效率較高.

4 應 用

設A=(aij)∈Mn(),若則稱A為嚴格對角占優(yōu)矩陣[3-4]；若有正對角矩陣D=diag(d1,d2,…,dn),使得AD為嚴格對角占優(yōu)矩陣,則稱A為廣義嚴格對角占優(yōu)矩陣.設A=(aij)∈Mn(),其中: ?i∈N,aii>0;?i≠j,i,j∈N,aij<0.則A可寫成A=sI-B,s>0,B∈Mn(+).如果s>ρ(B),則稱A為非奇異M-矩陣[1,3].這是M-矩陣的一個等價表征[1,3],且M-矩陣的按模最小特征值是一個正數(shù).設A=(aij)∈Mn(),記m(A)=(mij)∈Mn(),其中: ?i∈N,mii=|aii|;?i≠j,i,j∈N,mij=-|aij|.則稱m(A)為A的比較矩陣[3].設A=(aij)∈Mn(),則A為廣義嚴格對角占優(yōu)矩陣的充要條件是A的比較矩陣m(A)為非奇異M-矩陣[3].因此,若A=(aij)∈Mn()為M-矩陣,將A寫成A=sI-B,s>0,B∈Mn(+),則M-矩陣的最小特征值為s-ρ(B).因此,由M-矩陣的等價表征,應用非負矩陣最大特征值和對應特征向量的算法可以給出廣義嚴格對角占優(yōu)矩陣(M-矩陣)的迭代判別法、M-矩陣最小特征值及其對應特征向量的算法.