基于一類本原矩陣的非負(fù)矩陣Perron根的算法

王信存，呂洪斌，張 嬡

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

基于一類本原矩陣的非負(fù)矩陣Perron根的算法

王信存1，呂洪斌2，張 嬡2

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

利用矩陣的對(duì)角相似變換和Perron-Frobenius定理，給出了一類跡非零的不可約非負(fù)矩陣Perron根的簡(jiǎn)單數(shù)值算法，該算法僅需在迭代的每一步選擇上次迭代矩陣的行和構(gòu)成的正對(duì)角矩陣做矩陣的相似變換.同時(shí)通過(guò)適當(dāng)?shù)木仃嚻揭?，此算法可適用于所有不可約非負(fù)矩陣Perron根的計(jì)算.

不可約非負(fù)矩陣；Perron根；數(shù)值算法

非負(fù)矩陣是非常重要的矩陣類，在數(shù)值分析、概率統(tǒng)計(jì)、組合分析、數(shù)理經(jīng)濟(jì)等領(lǐng)域具有重要應(yīng)用.[1-2]對(duì)非負(fù)矩陣Perron根的估計(jì)與計(jì)算是非負(fù)矩陣?yán)碚撝械慕?jīng)典內(nèi)容.[3]在無(wú)線網(wǎng)絡(luò)資源分配設(shè)計(jì)以及在研發(fā)相關(guān)策略時(shí)，非負(fù)矩陣Perron根的不同性質(zhì)被證明對(duì)于理解不同優(yōu)化對(duì)象的基本權(quán)衡關(guān)系至關(guān)重要.[4]關(guān)于非負(fù)矩陣Perron根的計(jì)算已有多種算法，如冪法[5]、基于冪法的本原矩陣最大特征值算法[6-7]、對(duì)角相似變換的迭代法[8-9]以及考慮參數(shù)選擇的對(duì)角相似迭代算法[10]等.本文將給出一類跡非零的不可約非負(fù)矩陣Perron根的數(shù)值算法，進(jìn)一步給出不可約非負(fù)矩陣類的Perron根的數(shù)值算法.

1 預(yù)備知識(shí)

關(guān)于非負(fù)矩陣Perron根的界，有著名的Perron-Frobenius定理：

定理1設(shè)A=(aij)∈Nn，ρ(A)是A之Perron根，則有

容易證明下述結(jié)果：

引理1設(shè)A∈Nn不可約.?γ∈C(A)，記γ：i1→i2→…→ir→ir+1=i1，則?m∈Z+，有

引理3設(shè)A∈Nn不可約.如果aij>0，i，j∈N，則

2 主要結(jié)果

定理2設(shè)A∈Nn不可約，且存在i0∈N，使得ai0i0>0，ρ(A)是A之Perron根.則

因?yàn)锳不可約，所以其有向圖Γ(A)是強(qiáng)連通的.[1]又對(duì)?m∈Z+，A與A(m)有相同的零元模式，所以Γ(A(m))也是強(qiáng)連通的.對(duì)i0∈N，分以下幾種情況討論：

(1)

由(1)式，類似地有

進(jìn)一步有

?

因此，?i∈N，

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

(2)

因此，對(duì)?i∈N，

對(duì)?k∈Z+，

類似情形(ⅰ)的討論有

同樣，由A的不可約性，對(duì)?i∈N，i≠i0，類似上面的討論有

故?i∈N，

進(jìn)而?k∈Z+，

綜合情形(ⅰ)—(ⅲ)知定理為真.證畢.

注1對(duì)于不可約非負(fù)矩陣，若aii=0，?i∈N，則可記B=A+cI，c>0(I為單位陣).應(yīng)用定理1計(jì)算得ρ(B)=ρ(A)+c，因此定理1給出了所有不可約非負(fù)矩陣Perron根的算法.

故有

即

Ax=ρ(A)x.

3 算法與數(shù)值例子

本文算法：

步驟0 給出不可約非負(fù)矩陣A=(aij)n×n，ε>0，滿足trA>0；

步驟2 如果rmax-rmin<ε，則轉(zhuǎn)至步驟4，否則轉(zhuǎn)至步驟3；

步驟3 令D=diag(r1，r2，…，rn)，D-1AD∶=A，轉(zhuǎn)至步驟1；

步驟4 輸出ρ(A)=(rmax+rmin)/2.

對(duì)于不可約非負(fù)矩陣A，如果trA=0，則可取c>0(如取c=(rmax-rmin)/n)做矩陣平移，用上述算法計(jì)算B∶=A+cI的Perron根，則有ρ(A)=ρ(B)-c.

下面應(yīng)用MATLAB給出一個(gè)例子分析算法.

例1

應(yīng)用本文算法和文獻(xiàn)[7-8]的算法計(jì)算矩陣A的最大特征值的結(jié)果比較見表1.

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

由表1可知，本文算法與文獻(xiàn)[7-8]算法比較具有更加簡(jiǎn)單、高效的特點(diǎn).另外，根據(jù)定理1及本文算法，可以給出不可約非負(fù)矩陣之Perron向量的數(shù)值算法.

[1] BERMAN A，PLEMMONS R J.Nonnegative matrices in the mathematical sciences[M].New York：Society for Industrial and Applied Mathematics，1994：142-298.

[2] BAPAT R B，RAGHAVAN T E.Nonnegative matrices and applications[M].Cambridge：Cambridge University Press，1997：24-57.

[3] HORN R A，JOHNSON R C.Matrix analysis[M].New York：Cambridge University Press，2013：492-500.

[5] GOLUB G H，VAN LOAN G F.Matrix Computations[M].Baltimore：Johns University Press，1996：381.

[6] VARGA R S.Matrix iterative analysis[M].Berlin：Springer-Verlag，2000：52.

[7] DUAN F J，ZHANG K C.An algorithm of diagonal transformation for Perron root of nonnegative irreducible matrices[J].Applied Mathematics and Computation，2006，175：762-772.

[8] 王信存，呂洪斌.基于冪函數(shù)非負(fù)矩陣最大特征根的算法[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2017，55(3)：564-570.

[9] Bunse w.A Class of diagonal transformation methods for the computation of the spectral radius of a nonnegative irreducible matrix[J].SIAM J Numer Anal，1981，18(4)：694-704.

[10] 呂洪斌.不可約非負(fù)矩陣譜半徑的數(shù)值算法[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版)，2008，46(1)：6-12.

AnalgorithmforcalculatingPerronrootsofnonnegativematrixbasedonakindofprimitivematrix

WANG Xin-chun1，LYU Hong-bin2，ZHANG Yuan2

(1.Teachers College，Eastern Liaodong University，Dandong 118003，China；2.School of Mathematics and Statistics，Beihua University，Jilin 132013，China)

Using the diagonal similarity transformation and Perron-Frobenius theorem of matrix，a simple numerical algorithm for calculating Perron roots of a class of irreducible nonnegative matrix with nonzero trace is given.In this algorithm，it only needs to choose the positive diagonal matrix composed of the row sums of last iterative matrix in every step of the iteration and to do similarity transformation of matrix.At the same time，through proper matrix translation，this algorithm is applicable to the calculation of Perron roots of all irreducible nonnegative matrices.

irreducible nonnegative matrix；Perron root；algorithm

1000-1832(2017)04-0038-05

10.16163/j.cnki.22-1123/n.2017.04.008

2017-03-09

國(guó)家自然科學(xué)基金資助項(xiàng)目(51178001).

王信存(1973—)，男，碩士，副教授，主要從事矩陣?yán)碚摷捌鋺?yīng)用、數(shù)值代數(shù)、圖像處理研究；通信作者：呂洪斌(1964—)，男，博士，教授，主要從事矩陣?yán)碚摷捌鋺?yīng)用、數(shù)值代數(shù)、數(shù)值計(jì)算研究.

O 241.6學(xué)科代碼110·21

A

(責(zé)任編輯：李亞軍)