-
非负矩阵Perron根的理论在很多领域有重要应用.在实际中,常常需要估计非负矩阵的最大特征值,对于非负矩阵最大特征值上界的估计,文献[1-7]进行了广泛的研究.
为方便叙述,先给出一些记号.设n阶矩阵B≥0,ρ(B)表示非负矩阵B的谱半径,对i=1,2,…,n,ri(B)表示矩阵B的第i行行和,R(B)和r(B)分别表示矩阵B的最大行和与最小行和,C(B)和c(B)分别表示矩阵B的最大列和与最小列和.
设n阶矩阵B≥0,如果存在一个置换矩阵P∈Rn×n使得
PBPT=(CDOE) ,其中C和E分别是k,l阶方阵,k≥1和l≥1,则称B是可约矩阵,否则称B是不可约矩阵.Frobenius[1]给出了以下定理:
正矩阵是非负矩阵的子类,具有非负矩阵的所有性质. LEDERMANN W[4],OSTROWSKI A[5]和BRAUER A[6]在(1) 式的基础上给出了正矩阵最大特征值的界值定理.
M-矩阵和非负矩阵有着密切的关系.若A∈Rn×n,且A可表示为A=kI-B,I为n阶单位矩阵,B≥0,当k≥ρ(B)时,称A为M-矩阵.特别地,当k>ρ(B)时,称A为非奇异M-矩阵;当k=ρ(B)时,称A为奇异M-矩阵.文献[7]利用M-矩阵与非负矩阵的关系,改进了非负矩阵Perron根的上下界,得到了如下的结果:
定理1[7] 设A=kI-B,其中≥0,k>ρ(B),则有
因为
所以
从而可知定理1改进了Frobenius定理.
Crabtree[7]举了一个例子,设
B=(509306554) ,显然B是一个非负不可约矩阵,并且R(B)=14>ρ(B).应用定理1,取k=R(B),得ρ(B)<13.20.但是R(B)是满足定理4条件的最合适的数吗?换句话说,能否找到一个数k′,满足k′>ρ(B),并运用定理1得到ρ(B)更加精确的上界.本文针对此问题,在文献[7]的基础上将定理1推广到非负不可约矩阵,得到非负不可约矩阵Perron根更精确的上界.该方法对所有的非负不可约矩阵均适用,文末附以实例来说明该法的可行性和优越性.
全文HTML
-
定理2 设A=kI-B,其中B≥0且不可约,k>ρ(B),则A-1>0且A-1不可约.
证 因A=kI-B,其中B≥0,k>ρ(B),则有
因为B非负不可约,所以Bn>0,根据(3) 式可知A-1>0,并且正矩阵为不可约矩阵.
定理3 设A=kI-B,其中B≥0且不可约,k>ρ(B)且r(B)<R(B),则有r(A-1)<R(A-1).
证 显然r(A-1)≤R(A-1).只需证明r(A-1)≠R(A-1),此处采用反证法.假设r(A-1)=R(A-1),则
因此有k-R(B)=k-r(B),这与r(B)<R(B)矛盾,所以r(A-1)<R(A-1).
定理4 设A=kI-B,其中B≥0且不可约,k>ρ(B)且r(B)<R(B),则有
证 根据定理2和定理3知A-1非负不可约且r(A-1)<R(A-1),因此有
又因为
根据(5) 式可知
注1 本文中所有关于行和的定理对于列和也同样成立.
注2 在定理4中,ρ(B)严格小于
k−1R(A−1) ,这不同于定理1.考虑矩阵A=kI-B,其中k和ρ(B)满足定理4的条件,则有ρ(B)<k−1R(A−1) .设k′=k−1R(A−1)>ρ(B) ,构造矩阵A′=k′I-B,则A′是一个M-矩阵,再一次运用定理4,考虑到1R(A′−1)>0 ,得到如果按照此办法继续做下去将得到ρ(B)更加精确的上界.
例1 设
B=(509306554) ,r(B)<R(B)=14.Crabtree[7]已经得到了ρ(B)<13.20,此处运用定理4来改进B的Perron根的上界.
令k1=13.20,A1=k1I-B,应用定理4得ρ(B)<13.118 5.
令k2=13.118 5,A2=k2I-B,再次应用定理4得ρ(B)<13.109 6.
应用同样的方法,令k3=13.109 6,A3=k3I-B,有ρ(B)<13.108 6,实际上ρ(B)
≅ 13.108 5.注3 从上面的例子可以看出,对于非负不可约矩阵B,满足r(B)<R(B),令k1=R(B),A1=k1I-B,可以形成一个序列{An},n=1,2,…,其中An=knI-B,
kn=kn−1−1R(A−1n−1) ,当(1r(A−1n)−1R(A−1n))<ε 时停止迭代,此处ε是一个给定的充分小的正数.例2 设
B=(112233411) ,r(B)<R(B)=8,ρ(B)≅ 5.741 7.对于正矩阵B的Perron根的上界,有表 1的比较结果.
-
下面给出一个改进非负不可约矩阵Perron根上界的算法.对于非负不可约矩阵B,有r(B)≤ρ(B)≤R(B),如果r(B)=R(B),则有ρ(B)=r(B)=R(B),所以此处假设r(B)<R(B).
算法:
第一步:输入非负不可约矩阵B和一个充分小的正数ε,令n=0.
第二步:令k0=R(B),A0=k0I-B.
第三步:如果
(1r(A−1n)−1R(A−1n))≥ε ,计算kn+1=kn−1R(A−1n) 和An+1=kn+1I-B,令n=n+1,转到第三步.第四步:计算
kn−1R(A−1n) ,停止.例3 设
表 2给出了非负不可约矩阵B的Perron根的迭代次数和上界.
实际上ρ(B)
≅ 23.675 920 510 034 04.从上面的数值例子中可以看出应用该算法可以方便的得到精度比较高的Perron根的上界.
-
利用非负不可约矩阵与M-矩阵的关系,有效地改进了非负不可约矩阵Perron根的上界.在此基础上,给出计算非负不可约矩阵Perron根上界的一个算法,以上的数值例子表明利用该算法可以方便的得到精度比较高的Perron根的上界.