基于一類本原矩陣的非負矩陣Perron根的算法

王信存，呂洪斌，張 嬡

(1.遼東學院師范學院，遼寧 丹東 118003；2.北華大學數學與統計學院，吉林 吉林 132013)

基于一類本原矩陣的非負矩陣Perron根的算法

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

(1.遼東學院師范學院，遼寧 丹東 118003；2.北華大學數學與統計學院，吉林 吉林 132013)

利用矩陣的對角相似變換和Perron-Frobenius定理，給出了一類跡非零的不可約非負矩陣Perron根的簡單數值算法，該算法僅需在迭代的每一步選擇上次迭代矩陣的行和構成的正對角矩陣做矩陣的相似變換.同時通過適當的矩陣平移，此算法可適用于所有不可約非負矩陣Perron根的計算.

不可約非負矩陣；Perron根；數值算法

非負矩陣是非常重要的矩陣類，在數值分析、概率統計、組合分析、數理經濟等領域具有重要應用.[1-2]對非負矩陣Perron根的估計與計算是非負矩陣理論中的經典內容.[3]在無線網絡資源分配設計以及在研發相關策略時，非負矩陣Perron根的不同性質被證明對于理解不同優化對象的基本權衡關系至關重要.[4]關于非負矩陣Perron根的計算已有多種算法，如冪法[5]、基于冪法的本原矩陣最大特征值算法[6-7]、對角相似變換的迭代法[8-9]以及考慮參數選擇的對角相似迭代算法[10]等.本文將給出一類跡非零的不可約非負矩陣Perron根的數值算法，進一步給出不可約非負矩陣類的Perron根的數值算法.

1 預備知識

關于非負矩陣Perron根的界，有著名的Perron-Frobenius定理：

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

容易證明下述結果：

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

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

2 主要結果

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

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

(1)

由(1)式，類似地有

進一步有

?

因此，?i∈N，

進一步，?k∈Z+有

(2)

因此，對?i∈N，

對?k∈Z+，

類似情形(ⅰ)的討論有

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

故?i∈N，

進而?k∈Z+，

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

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

故有

即

Ax=ρ(A)x.

3 算法與數值例子

本文算法：

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

步驟2 如果rmax-rmin<ε，則轉至步驟4，否則轉至步驟3；

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

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

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

下面應用MATLAB給出一個例子分析算法.

例1

應用本文算法和文獻[7-8]的算法計算矩陣A的最大特征值的結果比較見表1.

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

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

[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] 王信存，呂洪斌.基于冪函數非負矩陣最大特征根的算法[J].吉林大學學報(理學版)，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] 呂洪斌.不可約非負矩陣譜半徑的數值算法[J].吉林大學學報(理學版)，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

國家自然科學基金資助項目(51178001).

王信存(1973—)，男，碩士，副教授，主要從事矩陣理論及其應用、數值代數、圖像處理研究；通信作者：呂洪斌(1964—)，男，博士，教授，主要從事矩陣理論及其應用、數值代數、數值計算研究.

O 241.6學科代碼110·21

A

(責任編輯：李亞軍)