王信存,呂洪斌,商鈺瑩

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

1 引言與預(yù)備知識(shí)

非負(fù)矩陣在計(jì)算數(shù)學(xué)、線性規(guī)劃、計(jì)算機(jī)科學(xué)技術(shù)、自動(dòng)控制等領(lǐng)域應(yīng)用廣泛[1-3],非負(fù)矩陣最大特征值的估計(jì)與計(jì)算是非負(fù)矩陣?yán)碚撝械慕?jīng)典內(nèi)容,在數(shù)值代數(shù)中具有重要意義.

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

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

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

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

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

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

類似于文獻(xiàn)[7,9]的證明，有:

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

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

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

證畢.

類似文獻(xiàn)[7,9]的證明,有:

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

由引理3知

2 主要結(jié)果

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

由式(1),類似地有

進(jìn)一步有

因此,?i∈N,有

進(jìn)一步,?k∈+,有

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

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

3 算法及分析

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

算法1計(jì)算不可約非負(fù)矩陣最大特征值算法.

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

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

由定理2知,算法1適合所有不可約非負(fù)矩陣最大特征值的計(jì)算,且適用范圍廣、簡(jiǎn)單實(shí)用.

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

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

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

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

4 應(yīng) 用

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