不可約非負(fù)矩陣的最大特征值估計(jì)

潘自康，任芳國(guó)

(陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，陜西西安710062)

不可約非負(fù)矩陣的最大特征值估計(jì)

潘自康，任芳國(guó)

(陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，陜西西安710062)

利用不可約非負(fù)矩陣和Collatz—Wielandt函數(shù)的性質(zhì)，給出了非負(fù)不可約矩陣最大特征值的一些界。比較這些界的大小，利用極限的思想得到了求非負(fù)不可約矩陣最大特征值的方法。利用這種方法可以去估計(jì)非負(fù)不可約矩陣最大特征值的大小，并通過(guò)計(jì)算和比較，驗(yàn)證了這種估計(jì)方法是可行的。

非負(fù)不可約矩陣；Collatz—Wielandt函數(shù)；最大特征值

非負(fù)矩陣在計(jì)算數(shù)學(xué)、圖論、線性規(guī)劃、自動(dòng)控制等許多學(xué)科領(lǐng)域有著廣泛的應(yīng)用，對(duì)其特征值的估計(jì)有著很重要的意義。它由Perrn發(fā)現(xiàn)，后來(lái)由Frobenius發(fā)展的關(guān)于非負(fù)矩陣最大特征值的一個(gè)優(yōu)美結(jié)果。[1]自此以后，A Brauer，O Taussky，R S Varga，A Ostrowski等人的杰出的工作，己經(jīng)形成了較為完善的理論。[2-4]非負(fù)矩陣?yán)碚撝凶畲筇卣髦档慕缰倒烙?jì)是該理論的核心問題之一，如果上下界能表示為矩陣元素的易于計(jì)算的函數(shù)，那么這種估計(jì)的價(jià)值就更高。由于非負(fù)矩陣最大特征值估計(jì)問題在很多學(xué)科中的廣泛應(yīng)用，近年來(lái)國(guó)內(nèi)學(xué)者開始研究這個(gè)問題，并提出了一些新的估計(jì)方法[5-6]，使計(jì)算更為簡(jiǎn)潔，結(jié)果更為精確。本文基于已有的研究成果，利用Collatz—Wielandt函數(shù)及其推廣，得到最大特征值的一系列上界和下界；并通過(guò)比較這些界的大小用求極限的方法得到一種非負(fù)不可約矩陣最大特征值的估計(jì)方法；通過(guò)計(jì)算來(lái)驗(yàn)證這些估計(jì)方法的可行性，并比較它們的精確程度。

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

為了敘述方便，我們對(duì)符號(hào)進(jìn)行如下約定。pn：表示非負(fù)數(shù)域上的n維列向量的集合；Mn(P)：表示非負(fù)數(shù)域上n×n矩陣的集合；AT：表示矩陣A的轉(zhuǎn)置；ri：表示矩陣A的第i行和；ci：表示矩陣A的第i列和。其他未加說(shuō)明的符號(hào)參見文獻(xiàn)[3]。

下面是與本文相關(guān)的幾個(gè)定義及引理。

定義1[2]設(shè)A=(aij)∈Rm×n，B=(bij)∈Rm×n，記B≥0，如果所有bij≥0；B＞0，如果所有bij＞0，B≥A，如果所有B-A≥0，B＞A，如果所有B-A＞0。若A≥0，則稱A為非負(fù)矩陣；若A＞0，則稱A為正矩陣。

定義2[3]每行和每列都只有一個(gè)元素為1，其余元素是零的方陣稱為置換矩陣。

定義3[3]設(shè)矩陣A∈Mn()P,如果存在一個(gè)置換矩陣P∈Rm×n使得

其中B和D分別是k，l階方陣，k≥1和l≥1，稱A是可約矩陣；否則稱A是不可約矩陣。

引理1[4]設(shè)A∈Mn(P)是不可約矩陣，n≥2。y∈Pn正好有k個(gè)坐標(biāo)為正，1≤k≤n-1，則(In+A)y的正坐標(biāo)的個(gè)數(shù)超過(guò)k個(gè)。

推論1[4]設(shè)A∈Mn(P)是不可約矩陣，y∈Pn且y≠0，則(In+A)y＞0。

引理2[4]設(shè)A∈Mn(P)是不可約矩陣，r是A的一個(gè)特征值。如果r≥0，則必有r＞0。

下面討論Collatz—Wielandt函數(shù)和不可約非負(fù)矩陣最大特征值的估計(jì)。

2 定理及證明

定義4[4]設(shè)A∈Mn()P是不可約矩陣，fA是從Pn到非負(fù)數(shù)的函數(shù)。

對(duì)任意向量x=(x1,x2,…,xn)∈Pn,且x≠0，fA被稱作關(guān)于A的Collatz—Wielandt函數(shù)。

定理1設(shè)A∈Mn(P)是不可約矩陣，fA是定義4中的的函數(shù)。則有

（i）fA是零次齊次函數(shù);

（ii）如果x∈Pn,且x≠0，和ρ是使Ax-ρx≥0成立的最大的實(shí)數(shù)，則ρ=fA(x);

（iii）如果x∈Pn,且x≠0。且y=(In+A)n-1x，則fA(y)≥fA(x);

（iv）fA可以在En中取得最大值；

（v）A存在一個(gè)特征值r=max{fA(x)|x∈En}使得，r≥|λi|，λi為A的任意特征值。此外，r對(duì)應(yīng)一個(gè)正的特征向量。

定理的證明參見文獻(xiàn)[4]。

定義5[4]設(shè)A∈Mn(P)是不可約矩陣，gA是從Pn到非負(fù)數(shù)的函數(shù)。

對(duì)任意向量x=(x1,x2,…,xn)∈Pn,且x≠0，當(dāng)存在xi=0， (Ax)i≠0 時(shí)，定義gA(x)=+∞。

可以看出gA是通過(guò)Collatz—Wielandt函數(shù)的推廣得到的，所以它具有與fA相似的一些性質(zhì)。

定理2設(shè)A∈Mn(P)是不可約矩陣，gA是定義5中的的函數(shù)。則有

（i）gA是零次齊次函數(shù);

（ii）如果x∈Pn,且x≠0，x和σ是使σx-Ax≥0成立的最小的實(shí)數(shù)，則σ=gA(x);

（iii）如果x∈Pn,且x≠0。且y=(In+A)n-1x，則gA(y)≤gA(x);

（iv）gA可以在En中取得最小值；

（v）A存在一個(gè)特征值r=min{gA(x)|x∈En}使得，r≥|λi|，λi為A的任意特征值。此外。r對(duì)應(yīng)一個(gè)正的特征向量。

定理3設(shè)A∈Mn(P)是不可約矩陣，r為A最大特征值，則對(duì)任意x∈Pn,且x≠0，有

證明：對(duì)任意x∈Pn,且x≠0，令

則z∈En。

由定理1（i）可知fA是零次齊次函數(shù)，所以

由定理2（v）可知r=max{fA(x)|x∈En}，所以

同理可得r≤gA(z)=gA(x)，所以不等式（1）得證。定理4設(shè)A∈Mn()P是不可約矩陣，r為最大特征值，B=(In+A)n-1，則有

證明：令y=Bx，則y=(In+A)n-1x。由定理2（iii）可知

又因?yàn)锽x∈Pn且Bx＞0，由定理3可知

所以，fA(x)≤fA(Bx)≤r

同理可得，r≤gA(Bx)≤gA(x)所以，不等式（2）得證。

定理5設(shè)A∈Mn()P是不可約矩陣，r為最大特征值，B=(In+A)n-1，則對(duì)任意的x∈Pn，x≠0，k∈N，有

且有

證明：對(duì)任意的x∈Pn，x≠0，k∈N。有Bkx∈Pn,Bkx＞0。由定理3可知

又因?yàn)锽k+1x=BBkx=(I+A)n-1Bkx，所以由定理1（iii）可知

即，fA(Bkx)是單調(diào)遞增的，且fA(Bkx)≤r。所以由單調(diào)有界定理[7]可得，

推論2設(shè)A∈Mn()P是不可約矩陣，r為最大特征值，B=(In+A)n-1，y為A的最大特征向量，且y∈En。則

解：由MATLAB計(jì)算可得，

由定理3可知，r∈[) 2,+∞。

由定理4可知,r∈[] 4,5.212 1。

由定理5可知,r∈[] 4.939 7,5.012 1。

由定理5和推論2可知,A的最大特征值r=5。對(duì)應(yīng)的最大特征向量

且y∈En。

最后，通過(guò)求A的特征方程，解得A的特征值分別為λ1=0,λ2=0,λ3=5并且λ3=5對(duì)應(yīng)的特征向量

所以，這種估計(jì)最大特征值和最大特征向量的方法是可行，并且是比較精確的。

下面用Collatz—Wielandt函數(shù)證明一些其他的估計(jì)方法。

定理6[1]設(shè)A∈Mn()P是不可約矩陣，r為最大特征值，則有

證明：由定理3可知fA(x)≤r≤gA(x)對(duì)任意的x∈Pn,x≠0成立，可令x=(1,1,…,1)T。則

所以式（6）得證。

又因?yàn)锳與AT有相同的最大特征值r，所以由定理3可知

對(duì)任意的x∈Pn,x≠0成立，同理可得，

所以式（7）得證。

定理7[5]設(shè)A∈Mn()P是不可約矩陣，r為最大特征值，B=(In+A)n-1，則有

證明：由定理4可得fA(Bx)≤r≤gA(Bx)，對(duì)任意的x∈Pn,x≠0成立，可令x=(1,1,…,1)T。則和定理6的證明方法類似，便可證得式（8）和式（9）也是成立的。

定理8[6]設(shè)A∈Mn(P)是不可約矩陣，r為最大特征值，B=(In+A)n-1，則有

證明：由定理5可得fA(Bkx)≤r≤gA(Bkx)，對(duì)任意的x∈Pn,x≠0成立，且有

可對(duì)任意的x∈Pn,x≠0,k∈N成立，令x=(1,1,…,1)T。則和定理6的證明方法類似，便可證得式（10-13）式也是成立的。

這樣，就可以不用向量x只用矩陣A和Bk=(In+A)(n-1)k，k∈N，對(duì)最大特征值進(jìn)行估計(jì)。

[1]FROBENIUS G.Uber matrizen aus nicht negativen elementen[M].Berlin:Sitzungsber konussAkad Wiss，1912：465-477.

[2]ROGER A H,CHARLS R J.Matrix analysis[M].Cambridge University Press，1990，1：347-374.

[3]BERMAN A，PLEMMONS R J.Nonnegative matrices in the mathematical sciences[M].New York:Academic Press，1979：26-59.

[4]HENRYK M.Nonnegative matrices[M].New York:Wiley，1988：5-20.

[5]王忠全.非負(fù)矩陣譜半徑的估計(jì)[J].宿州學(xué)院學(xué)報(bào)，2008（4）：99-100.

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

Estimation for the Maximal Eigenvalue of Irreducible Nonnegative Matrix

PAN Zikang,REN Fangguo
(College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062,Shaanxi,China)

In the paper,based on the property of irreducible nonnegative matrix and Collatz-Wielandt function,we derive some bounds for the maximal eigenvalue of irreducible nonnegative matrix.The method of seeking for the maximal eigenvalue of irreducible nonnegative matrix is given by the size of these bounds and the idea of limit.We can use this method to estimate the maximal eigenvalue of irreducible nonnegative matrix.It is proved that this estimation is feasible by calculating and comparing.

irreducible nonnegative matrix;Collatz-Wielandt function;maximum eigenvalue

O151.21

A

1672-2914（2015）02-0035-04

2014-12-08

國(guó)家自然科學(xué)基金項(xiàng)目(11171201)；陜西省自然科學(xué)基金項(xiàng)目（2011JM1007）。

潘自康（1984-），男，河北邯鄲市人，陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院碩士研究生，研究方向?yàn)榫仃囌摗?/p>

任芳國(guó)，副教授，E-mail：rfangguo@sohu.com。