非负矩阵谱半径的brauer型估计

非负矩阵谱半径的brauer型估计

定义从a到（a）n，并记录从n到{1、n}、ri（a）=jnaij、ri（a）=jn，i}，aij，in。关于非负矩阵谱半径的估计,最早是Perron-Frobenius的结果:mini∈Nri(A)≤ρ(A)≤maxi∈Νri(A).虽然这个结果要早于Gerschorin定理,但它可看作是利用Gerschorin圆盘的右端点对ρ(A)作出估计,所以不妨仍然称其为Gerschorin型估计.Brauer利用Cassini卵形域给出了非负矩阵谱半径的Brauer型估计,改进了Perron-Frobenius的结果.M矩阵一个主要的等价表征指出M矩阵特征值的实部皆正,佟文廷推进了这一结果,得到M矩阵按模最小特征值是一个正数;张家驹证明了M矩阵的实部最小特征值也是其按模最小特征值,并给出这一特征值的估计式:mini∈Nri(A)≤ω0(A)≤maxi∈Nri(A).同理,这个估计也称为Gerschorin型的.之后,逄明贤进一步给出M矩阵最小特征值的Brauer型估计.本文利用Brauldi使用的通过有向图的推证方法以及文献引进的有向图的1-path覆盖,建立了非负矩阵的谱半径与M矩阵最小特征值的Brauldi型估计和改进的Brauer型估计,从而改进了文献中的相应结果.1a的内涵设Γ(A)表示A∈Cn×n的有向图,N是其节点集合,E(A)={ei,j|aij≠0,i,j∈N}是其有向边集合.有向边序列γ:ei1,i2,ei2,i3,…,eis-1,is,eis,i1,其中s≥2,且诸i1,i2,…,is互不相同,称为Γ(A)的简单回路,简记为γ:i1,i2,…,is,is+1=i1.简单回路的全体记为C(A).Γ+(i)={j∈N|j≠i,ei,j∈E(A)}表示i在Γ(A)中的后继集合.非空集合ν上的一个关系“≺”称为先序,如果“≺”满足:自反性与传递性,即a≺a,∀a∈ν;a≺b及b≺c蕴涵a≺c,a,b,c∈ν.引理1.1设Γ(A)是A的有向图,≺是N上的一个先序.若∀i∈N,Γ+(i)≠Ø,则在Γ(A)中存在一个简单回路γ:i1,i2,…,is,is+1=i1,使得l≺ij+1,∀l∈Γ+(ij)‚j=1,2,⋯,s.(1.1)定义1.1设γ:i1,i2,…,is,is+1(is+1=i1)∈C(A),η表示2与s的最大公约数,τ=s/η,则集合{ei1,i2,ei1+η,i2+η,…,ei1+(τ-1)η,i2+(τ-1)η}称为γ的奇1-path覆盖;集合{ei2,i3,ei2+η,i3+η,…,ei2+(τ-1)η,i3+(τ-1)η}称为γ的偶1-path覆盖.γ一个确定的1-path覆盖记为P1(γ).当s为正奇数时,γ的奇、偶1-path覆盖相同,即γ仅有一个包含其所有s条有向边的1-path覆盖.当s为正偶数时,γ有2个各包含其s/2条有向边的奇、偶1-path覆盖.定义1.2对Γ(A)中的每个γ∈C(A),取定一个1-path覆盖P1(γ),则称Ρ1(A)=∪γ∈C(A)Ρ1(γ)为Γ(A)的一个1-path覆盖.若A是n≥2阶的可约矩阵,则有置换阵P,使得ΡAΡΤ=(A11A12⋯A1Κ0A22⋯A2Κ⋮⋱⋱⋮0⋯0AΚΚ)‚2≤Κ≤n‚(1.2)其中Att为A的nt阶主子阵,其或为不可约矩阵,或是1阶零矩阵,Κ∑t=1nt=n.式(1.2)中右端矩阵称为A的约化法式.若不计Att的次序,法式(1.2)与P的选择无关,因此式(1.2)惟一地确定集合N={1,…,n}的划分N1,…,NK对应于A11,…,AKK的足码集合.当A为不可约矩阵或1阶零矩阵时,为统一,也记A=(A11),这时n1=n,N1=N.记α=∪nt≥2,1≤t≤ΚNt‚ΘA={aii为A的主对角元|i∈N\α},易见α={i∈N|i∈γ∈C(A)}.定义1.3A∈Cn×n,如果N=α,则A是弱不可约矩阵,记为A∈WI.对于一般矩阵,如果α≠Ø,则称A[α]为A的弱不可约核,记为Å.当α=Ø时,记Å=Ø.2raaaaa规定:maxØ=minØ=0.显然有:引理2.1设a1,…,an∈R,N={1,…,n},T⊆N.定义函数f(x)=∏i∈T(x-ai),则当x≥maxi∈T{ai}时,f(x)严格单调增加.定理2.1设A=(aij)≥0,对∀γ∈C(A),用rA(γ)表示方程∏i∈γ(x-aii)=∏i∈γRi(˚A)的大于maxi∈γ{aii}的实根,并记mrc(A)=max{minγ∈C(A)rA(γ),maxΘA}‚Μrc(A)=max{maxγ∈C(A)rA(γ),maxΘA}.则对A的谱半径ρ(A)有估计:mrc(A)≤ρ(A)≤Mrc(A).证明:(1)A为不可约矩阵.设x=(x1,…,xn)T>0是A的属于特征值ρ(A)的特征向量.在Γ(A)的节点集合N上定义先序≺:i≺j当且仅当xi≥xj.由引理2.1知,存在γ′:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得xl≥xij+1,∀l∈Γ+(xij)(j=1,…,s),于是由(ρ(A)-aijij)xij=∑p≠ijaijpxp=∑p∈Γ+(ij)aijpxp≥(∑p∈Γ+(ij)aijp)xij+1=Rij(A)xij+1,j=1,⋯,s‚可得s∏j=1(ρ(A)-aijij)s∏j=1xij≥s∏j=1Rij(A)s∏j=1xij+1,从而有s∏j=1(ρ(A)-aijij)≥s∏j=1Rij(A),即∏i∈γ′(ρ(A)-aii)≥∏i∈γ′Ri(A).(2.1)类似地,在Γ(A)的节点集合N上定义先序≺:i≺j当且仅当xi≤xj.由引理2.1知,存在γ″:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得xl≤xij+1,∀l∈Γ+(xij)(j=1,…,s).仿上可以得到∏i∈γ″(ρ(A)-aii)≤∏i∈γ″Ri(A).(2.2)再注意到ρ(A)≥maxi∈γ′{aii}及ρ(A)≥maxi∈γ″{aii},由引理2.1\,式(2.1)与(2.2)即可推出minγ∈C(A)rA(γ)≤rA(γ′)≤ρ(A)≤rA(γ″)≤maxγ∈C(A)rA(γ)‚即mrc(A)≤ρ(A)≤Mrc(A).(2)A为弱不可约矩阵.不妨设A已有法式(1.2),此时诸Att为阶数大于等于2的不可约矩阵.分两步证明:1)因为Ri(Å)=Ri(AKK),∀i∈NK.由(1)易知ρ(A)≥ρ(AΚΚ)≥mrc(AΚΚ)=minγ∈C(AΚΚ)rAΚΚ(γ)=minγ∈C(AΚΚ)rA(γ)≥minγ∈C(A)rA(γ).2)设t*使得ρ(A)=ρ(At*t*),由(1)易知ρ(A)=ρ(At*t*)≤Μrc(At*t*)=maxγ∈C(At*t*)rAt*t*(γ)=maxγ∈C(At*t*)rA(γ)≤maxγ∈C(A)rA(γ).综合1),2)有mrc(A)≤ρ(A)≤Mrc(A).(3)A为非弱不可约矩阵.注意到rA(γ)=rÅ(γ),C(A)=C(Å),由(2)知minγ∈C(A)rA(γ)=minγ∈C(Å)rÅ(γ)≤ρ(Å)≤maxγ∈C(Å)rÅ(γ)=maxγ∈C(A)rA(γ).因为ρ(A)=max{maxΘA,ρ(Å)},于是max{minγ∈C(A)rA(γ),maxΘA}≤ρ(A)≤max{maxγ∈C(A)rA(γ),maxΘA},即mrc(A)≤ρ(A)≤Mrc(A).注2.1因mcr(A),Mcr(A)与有向图有关,当A是可约矩阵时,传统的连续性推证方法不再有效,故可利用法式(1.2)完成证明.另外,在定理2.1中,rA(γ)必须通过Ri(Å)定义,而不能直接由Ri(A)定义.定理2.1中rA(γ)的计算比较复杂,下面给出一个在实际估计中更为方便的结果.定理2.2设A=(aij)≥0,P1(A)是Γ(A)的1-path覆盖.记rA(i,j)=12{aii+ajj+[(aii-ajj)2+4Ri(Å)Rj(Å)]12},mer(A)=max{minei,j∈Ρ1(A)rA(i,j),maxΘA},Μer(A)=max{maxei,j∈Ρ1(A)rA(i,j),maxΘA}.则对A的谱半径ρ(A)有估计:mer(A)≤ρ(A)≤Mer(A).证明:若证mer(A)≤mcr(A),只需证对∀γ∈C(A),存在ei,j∈P1(γ),使得rA(γ)≥rA(i,j).否则,存在γ:i1,i2,…,is,is+1(is+1=i1)∈C(A),使得rA(γ)<rA(i,j),∀ei,j∈P1(γ),注意到rA(i,j)是方程(x-aii)(x-ajj)=Ri(Å)Rj(Å)大于max{aii,ajj}的实根,由引理2.1知(rA(γ)-aii)(rA(γ)-ajj)＜Ri(A˚)Rj(A˚),∀ei,j∈Ρ1(γ).(2.3)将式(2.3)中各不等式相乘,有∏ei,j∈Ρ1(γ)(rA(γ)-aii)(rA(γ)-ajj)＜∏ei,j∈Ρ1(γ)Ri(A˚)Rj(A˚),即(∏i∈γ(rA(γ)-aii))δ＜(∏i∈γRi(A˚))δ,当s为奇数时,δ=2;当s为偶数时,δ=1.进而有∏i∈γ(rA(γ)-aii)＜∏i∈γRi(A˚),(2.4)再由引理2.1知,式(2.4)蕴涵rA(γ)<rA(γ),矛盾.同理可证Mcr(A)≤Mer(A).综上,由定理2.1即得mre(A)≤ρ(A)≤Mer(A).注2.2定理2.1可以看作是利用特征值分布的Brauldi区域的右端点对ρ(A)作出估计,故可称为Brauldi型估计.定理2.2则是改进的Brauer型估计,由于只需计算与简单回路中的边ei,j对应的rA(i,j),特别当简单回路的长度为偶数时,只需对回路中一半数量的边所对应的rA(i,j)进行计算,故计算量大为减少,同时精确度明显提高.定理2.1与定理2.2均优于Perron-Frobenius和Brauer的结果.3paa规定:maxØ=minØ=+∞.定理3.1设A=(aij)∈Rn×n为非奇异M矩阵,对∀γ∈C(A),用lA(γ)表示方程∏i∈γ(aii-x)=∏i∈γRi(A˚)的小于mini∈γ{aii}的实根,并记mcl(A)=min{minγ∈C(A)lA(γ),minΘA}‚Μcl(A)=min{maxγ∈C(A)lA(γ),maxΘA}.则对A的最小特征值ω0(A)有估计:mcl(A)≤ω0(A)≤Mcl(A).证明:设A=sI-B,B=(bij)n×n≥0,s>ρ(B),ρ(B)为B的谱半径.易见ω0(A)=s-ρ(B)>0,由定理2.1知,mcr(B)≤ρ(B)≤Mcr(B),从而s-Mcr(B)≤ω0(A)≤s-mcr(B).首先注意到aii=s-bii,i∈N,进而再由lA(γ)与rA(γ)定义易知,lA(γ)=s-rB(γ).可得mcl(A)=min{minγ∈C(A)lA(γ),minΘA}=min{minγ∈C(B){s-rB(γ)},s-maxΘB}=s-max{maxγ∈C(B)rB(γ),maxΘB}=s-Μcr(B).同理可得Mcl(A)=s-mcr(B),故mcl(A)≤ω0(A)≤Mcl(A).类似地,容易得到:定理3.2设A=(aij)∈Rn×n为非奇异M矩阵,P1(A)是Γ(A)的1-path覆盖.记lA(i,j)=12{aii+ajj-[(aii-ajj)2+4Ri(A˚)Rj(A˚)]12},mel(A)=min{minei,j∈Ρ1(A)lA(i,j),minΘA},Μel(A)=min{maxei,j∈Ρ1(A)lA(i,j),minΘA}.则对A的最小特征值ω0(A)有估计:mel(A)≤ω0(A)≤Mel(A).注3.1定理3.1与定理3.2分别是M矩阵最小特征值的Brauldi型估计和改进的Brauer型估计,它们均优于文献的结果.4b0.3,3,4,5-四氢-3,4,5-四氢-3,4,5-四氢-3,4,5-四氢-3,4,5-负矩阵2.例4.1考虑非负矩阵A=(8100012100015100012100018).经计算ρ(A)=8.18014.由Gerschorin型估计有4≤ρ(A)≤9.因为rA(1,2)=rA(1,4)=rA(2,5)=rA(4,5)=8.31662,rA(1,5)=9,rA(2,4)=4,rA(2,3)=rA(3,4)=6,rA(1,3)=rA(3,5)=8.56155.由Brauer型估计有4≤ρ(A)≤9.取P1(A)={e1,2,e2,3,e3,4,e4,5},由定理2.2,有6≤ρ(A)≤8.31662.考虑非奇异M矩阵B=9I-A,由Gerschorin型估计和Brauer型估计只能得到0≤ω0(B)≤5,取P1(B)={e1,2,e2,3,e3,4,e4,5},由定理3.2有0.68338≤ω0(B)≤3.事实上,ω0(B)=0.81986.例4.2考虑非负矩阵A=(10.600020.600030.60.6004).经计算ρ(A)=4.02080.由Gerschorin型估计有1.6≤ρ(A)≤4.6.因为rA(1,2)=2.28102,rA(1,3)=3.16619,rA(1,4)=4.11555,rA(2,3)=3.28102,rA(2,4)=4.16619,rA(3,4)=4.28102.由Brauer型估计有2.28102≤ρ(A)≤4