計算非負不可約矩陣譜半徑的新算法

宋海洲,徐強,田朝薇

(華僑大學數(shù)學科學學院,福建泉州 362021)

計算非負不可約矩陣譜半徑的新算法

宋海洲,徐強,田朝薇

(華僑大學數(shù)學科學學院,福建泉州 362021)

設A=(ai,j)n×n為非負不可約矩陣,設計一種計算非負不可約矩陣譜半徑ρ(A)的通用迭代算法,并證明算法的收斂性.數(shù)值實驗表明,該算法比冪法迭代算法具有較快的收斂速度.

正矩陣;譜半徑;迭代方法;收斂性

非負矩陣在數(shù)值分析、圖論、計算機科學、控制論、管理科學等領(lǐng)域上有著極其重要的作用[1-4],而非負矩陣譜半徑的計算又是其核心問題之一.計算非負矩陣的譜半徑,通常采用冪法、正交三角矩陣(QR)算法,但這些算法迭代速度不快.本文設計一種計算非負不可約矩陣譜半徑的通用迭代方法.

1 算法的設計

設A=(ai,j)n×n為非負不可約矩陣,則迭代計算譜半徑ρ(A)的算法有如下4個步驟.

(4)若W2,k-W1,k>ε,更新R=maxiri(C),轉(zhuǎn)步驟(3);否則,令(W1,k+W2,k)/2為矩陣 A的近似譜半徑.

2 算法的收斂性

引理1[5]設B為正矩陣,X=(x1,x2,…,xn)T為 B對應ρ(B)的正特征向量,Y=(y1,y2,…, yn)T為BT對應ρ(B)的正特征向量.令c=(YTX)-1,則有

定理1 設B為n階正矩陣,X=(x1,x2,…,xn)T為B對應ρ(B)的正特征向量,記為Bk的第i行行和(i=1,2,…,n),記u1=…,n,并且有

證明 設Y=(y1,y2,…,yn)T為BT對應ρ(BT)的正特征向量,記c=(YTX)-1.由引理1,有

由此可證式(2)成立.證畢.

引理2[5]設A為n階非負不可約矩陣,B=(A+I)n-1,則B為n階正矩陣.

定理3 設B=(bi,j)是n階正矩陣,記ri(Bk)表示Bk的第i行行和(i=1,2,…,n,k=0,1,…=bi,m rm(Bk)(i,m=1,2,…,n;k=0,1,…),

證明 假設 X=(x1,x2,…,xn)T為B對應ρ(B)的正特征向量,則由定理1可得,對于任意i,m= 1,2,…,n,有

又因為對于任意i,m=1,2,…,n,任意k=0,1,2,…,有>0,故s=inf|k=0,1,…,i;m= 1,2,…,n}>0.

證明 易知AB=BA,故由Tk及tk的定義及引理4可得

再利用定理3,可得

利用上式及式(4),可得

由定理3可知,1-ns<1,而1-ns≥0是顯然的,故|1-ns|<1.利用上式遞推,可得

3 數(shù)值試驗

由非負不可約矩陣的算法求得的結(jié)果,如表1所示.

表1 例1中矩陣A的譜半徑表Tab.1 Table of matrix A′s spectral radius in examp le 1

對于例1中的矩陣A,采用冪法是求不出ρ(A)的.

采用冪法及非負不可約矩陣的算法,求A的譜半徑在精度要求下所需的迭代次數(shù),如表2所示.

表2 例2矩陣A的譜半徑的收斂速度比較表Tab.2 Table for the convergence rate comparison of matrix A′s spectral radius in examp le 2

從表2可以看出,所設計求非負不可約矩陣的算法比冪法收斂速度要快.

[1]盧琳璋,馬飛.非負矩陣perron根的上下界[J].計算數(shù)學,2003,25(2):58-64.

[2]殷劍宏.非負矩陣最大特征值的新界值[J].數(shù)值計算與計算機應用,2002,23(4):292-295.

[3]段復建,張可村.Z-矩陣最小特征值及特征向量的數(shù)值算法[J].2007,24(3):563-566.

[4]張鳳祥.非負矩陣最大特征值的平滑算法[J].高等學校計算數(shù)學學報,2001,23(1):45-55.

[5]蔣正新,施國梁.矩陣理論及其應用[M].北京:北京航空學院出版社,1998.

(責任編輯:陳志賢英文審校:張金順,黃心中)

A New Algorithm for the Spectral Radius of Non-Negative Irreducible Matrix

SONG Hai-zhou,XU Qiang,TIAN Zhao-w ei
(School of Mathematical Sciences,Huaqiao University,Quanzhou 362021,China)

Let A=(ai,j)n×nis a non-negative irreducible matrix,then a new algorithm for the spectral radiusρ(A)of the matrix A is designed in this paper.The convergence of the algorithm is also proved.It is show n that the algorithm has a rapid convergence rate by numerical experiment.

non-negative;irreducible;iterative method;convergence

O 241.6

A

1000-5013(2011)03-0348-04

2009-07-11

宋海洲(1971-),男,副教授,主要從事數(shù)學模型的研究.E-mail:hzsong@hqu.edu.cn.

福建省自然科學基金資助項目(Z0511028)