宋海洲,徐強(qiáng),田朝薇

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

計(jì)算非負(fù)不可約矩陣譜半徑的新算法

宋海洲,徐強(qiáng),田朝薇

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

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

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

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

1 算法的設(shè)計(jì)

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

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

2 算法的收斂性

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

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

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

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

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

定理3 設(shè)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,…),

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

又因?yàn)閷?duì)于任意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ù)值試驗(yàn)

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

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

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

采用冪法及非負(fù)不可約矩陣的算法,求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可以看出,所設(shè)計(jì)求非負(fù)不可約矩陣的算法比冪法收斂速度要快.

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

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

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

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

[5]蔣正新,施國梁.矩陣?yán)碚摷捌鋺?yīng)用[M].北京:北京航空學(xué)院出版社,1998.

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

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ù)學(xué)模型的研究.E-mail:hzsong@hqu.edu.cn.

福建省自然科學(xué)基金資助項(xiàng)目(Z0511028)