Processing math: 100%

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

非负不可约矩阵Perron根的上界

上一篇

下一篇

钟琴, 周鑫. 非负不可约矩阵Perron根的上界[J]. 西南大学学报(自然科学版), 2017, 39(10): 75-78. doi: 10.13718/j.cnki.xdzk.2017.10.011
引用本文: 钟琴, 周鑫. 非负不可约矩阵Perron根的上界[J]. 西南大学学报(自然科学版), 2017, 39(10): 75-78. doi: 10.13718/j.cnki.xdzk.2017.10.011
Qin ZHONG, Xin ZHOU. Upper Bound for the Perron Root of a Nonnegative Irreducible Matrix[J]. Journal of Southwest University Natural Science Edition, 2017, 39(10): 75-78. doi: 10.13718/j.cnki.xdzk.2017.10.011
Citation: Qin ZHONG, Xin ZHOU. Upper Bound for the Perron Root of a Nonnegative Irreducible Matrix[J]. Journal of Southwest University Natural Science Edition, 2017, 39(10): 75-78. doi: 10.13718/j.cnki.xdzk.2017.10.011

非负不可约矩阵Perron根的上界

  • 基金项目: 国家自然科学基金面上项目(11471225);四川省教育厅科研项目(13ZB0357);四川大学锦江学院青年教师科研项目(QNJJ-2017-A09)
详细信息
    作者简介:

    钟琴(1982-),女,四川自贡人,副教授,主要从事矩阵理论及其应用的研究 .

  • 中图分类号: O151.21

Upper Bound for the Perron Root of a Nonnegative Irreducible Matrix

  • 摘要: 非负矩阵在数学物理、控制论、电力系统理论等领域有广泛的应用.非负矩阵Perron根的估计是矩阵分析理论研究中的重要问题.利用M-矩阵与非负矩阵之间的关系,给出计算非负不可约矩阵Perron根上界的一种新算法,数值例子表明该算法具有可行性.
  • 非负矩阵Perron根的理论在很多领域有重要应用.在实际中,常常需要估计非负矩阵的最大特征值,对于非负矩阵最大特征值上界的估计,文献[1-7]进行了广泛的研究.

    为方便叙述,先给出一些记号.设n阶矩阵B≥0,ρ(B)表示非负矩阵B的谱半径,对i=1,2,…,nri(B)表示矩阵B的第i行行和,R(B)和r(B)分别表示矩阵B的最大行和与最小行和,C(B)和c(B)分别表示矩阵B的最大列和与最小列和.

    n阶矩阵B≥0,如果存在一个置换矩阵PRn×n使得PBPT=(CDOE),其中CE分别是kl阶方阵,k≥1和l≥1,则称B是可约矩阵,否则称B是不可约矩阵.

    Frobenius[1]给出了以下定理:

    R(B)ρ(B)r(B) (1)

    正矩阵是非负矩阵的子类,具有非负矩阵的所有性质. LEDERMANN W[4],OSTROWSKI A[5]和BRAUER A[6]在(1) 式的基础上给出了正矩阵最大特征值的界值定理.

    M-矩阵和非负矩阵有着密切的关系.若ARn×n,且A可表示为A=kI-BIn阶单位矩阵,B≥0,当kρ(B)时,称AM-矩阵.特别地,当kρ(B)时,称A为非奇异M-矩阵;当k=ρ(B)时,称A为奇异M-矩阵.文献[7]利用M-矩阵与非负矩阵的关系,改进了非负矩阵Perron根的上下界,得到了如下的结果:

    定理1[7]  设A=kI-B,其中≥0,kρ(B),则有

    k1r(A1)ρ(B)k1R(A1) (2)

    因为

    k1R(A1)R(B)

    所以

    ρ(B)k1R(A1)R(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根更精确的上界.该方法对所有的非负不可约矩阵均适用,文末附以实例来说明该法的可行性和优越性.

    定理2  设A=kI-B,其中B≥0且不可约,kρ(B),则A-1>0且A-1不可约.

      因A=kI-B,其中B≥0,kρ(B),则有

    A1=1k(I1kB)1=1k(I+1k2B2++1knBn+) (3)

    因为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),则

    r(A)=1r(A1)=1R(A1)=R(A)

    因此有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),则有

    ρ(B)<k1R(A1) (4)

      根据定理2和定理3知A-1非负不可约且r(A-1)<R(A-1),因此有

    ρ(A1)<R(A1) (5)

    又因为

    1ρ(A1)=λmin(A)=kρ(B)

    根据(5) 式可知

    kρ(B)>1R(A1)

    注1  本文中所有关于行和的定理对于列和也同样成立.

    注2  在定理4中,ρ(B)严格小于k1R(A1),这不同于定理1.考虑矩阵A=kI-B,其中kρ(B)满足定理4的条件,则有ρ(B)<k1R(A1).设k=k1R(A1)>ρ(B),构造矩阵A′=kI-B,则A′是一个M-矩阵,再一次运用定理4,考虑到1R(A1)>0,得到

    ρ(B)<k1R(A1)=k1R(A1)1R(A1)<k1R(A1)

    如果按照此办法继续做下去将得到ρ(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-Bkn=kn11R(A1n1),当(1r(A1n)1R(A1n))<ε时停止迭代,此处ε是一个给定的充分小的正数.

    例2  设B=(112233411)r(B)<R(B)=8,ρ(B)5.741 7.

    对于正矩阵B的Perron根的上界,有表 1的比较结果.

    表 1  正矩阵B的Perron根的上界比较结果
    文献来源
    文献[1] ρ(B)<8 ρ(B)<7
    文献[4] ρ(B)<7.866 1 ρ(B)<6.925 9
    文献[5] ρ(B)<7.654 7 ρ(B)<6.816 5
    文献[6] ρ(B)<7.464 2 ρ(B)<6.701 6
    定理4 ρ(B)<6.326 1(k=R(B)=8) ρ(B)<5.952 4(k=C(B)=7)
    ρ(B)<5.927 5(k=6.326 1) ρ(B)<5.782 8(k=5.952 4)
     | Show Table
    DownLoad: CSV

    下面给出一个改进非负不可约矩阵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(A1n)1R(A1n))ε,计算kn+1=kn1R(A1n)An+1=kn+1I-B,令n=n+1,转到第三步.

    第四步:计算kn1R(A1n),停止.

    例3  设

    B=(444150257813837624110236267034728455 ),r(B)<R(B)

    表 2给出了非负不可约矩阵B的Perron根的迭代次数和上界.

    表 2  非负不可约矩阵B的Perron根的迭代次数和上界比较
    迭代次数 ε 上界
    3 0.1 23.694 443 419 257 60
    5 0.01 23.676 989 461 682 54
    6 0.001 23.676 177 391 547 14
    8 0.000 1 23.675 935 345 756 37
    10 0.000 01 23.675 921 366 852 62
    11 0.000 001 23.675 920 715 944 82
    13 0.000 000 1 23.675 920 521 926 16
     | Show Table
    DownLoad: CSV

    实际上ρ(B) 23.675 920 510 034 04.从上面的数值例子中可以看出应用该算法可以方便的得到精度比较高的Perron根的上界.

    利用非负不可约矩阵与M-矩阵的关系,有效地改进了非负不可约矩阵Perron根的上界.在此基础上,给出计算非负不可约矩阵Perron根上界的一个算法,以上的数值例子表明利用该算法可以方便的得到精度比较高的Perron根的上界.

  • 表 1  正矩阵B的Perron根的上界比较结果

    文献来源
    文献[1] ρ(B)<8 ρ(B)<7
    文献[4] ρ(B)<7.866 1 ρ(B)<6.925 9
    文献[5] ρ(B)<7.654 7 ρ(B)<6.816 5
    文献[6] ρ(B)<7.464 2 ρ(B)<6.701 6
    定理4 ρ(B)<6.326 1(k=R(B)=8) ρ(B)<5.952 4(k=C(B)=7)
    ρ(B)<5.927 5(k=6.326 1) ρ(B)<5.782 8(k=5.952 4)
    下载: 导出CSV

    表 2  非负不可约矩阵B的Perron根的迭代次数和上界比较

    迭代次数 ε 上界
    3 0.1 23.694 443 419 257 60
    5 0.01 23.676 989 461 682 54
    6 0.001 23.676 177 391 547 14
    8 0.000 1 23.675 935 345 756 37
    10 0.000 01 23.675 921 366 852 62
    11 0.000 001 23.675 920 715 944 82
    13 0.000 000 1 23.675 920 521 926 16
    下载: 导出CSV
  • [1] VARGA R S. Matrix Iterative Analysis [M]. 2版.北京:科学出版社, 2006: 36.
    [2] 钟琴, 周鑫, 牟谷芳.非负矩阵谱半径的上界估计[J].西南大学学报(自然科学版), 2017, 39(6): 50-53. doi: http://www.cnki.com.cn/Article/CJFDTOTAL-XNND201706008.htm
    [3] 廖辉.矩阵特征值估计的一个改进结果[J].西南大学学报(自然科学版), 2013, 35(6): 46-49. doi: http://www.cnki.com.cn/Article/CJFDTOTAL-XNND201306009.htm
    [4] doi: http://www.ams.org/mathscinet-getitem?mr=37821 LEDERMANN W. Bounds for the Greatest Latent Roots of a Positive Matrix [J]. Journal of the London Mathematical Society, 1950, 25(4): 265-268.
    [5] doi: http://www.ams.org/mathscinet-getitem?mr=37821 OSTROWSKI A. Bounds for the Greatest Latent Root of a Positive Matrix [J]. London Mathematical Society, 1952, 27(1): 253-256.
    [6] BRAUER A. The Theorem of Ledermann and Ostrowski on Positive Matrices [J]. Duke Math J, 1957, 24(2): 265-274. doi: 10.1215/S0012-7094-57-02434-1
    [7] CRABTREE D E. Applications of M-matrices to Nonnegative Matrices [J]. Duke Math J, 1966, 33(1): 197-208. doi: 10.1215/S0012-7094-66-03324-2
  • 期刊类型引用(3)

    1. 张晓凤,陈付彬,罗欢. 矩阵Hadamard积与Fan积的特征值新界. 西南师范大学学报(自然科学版). 2022(07): 1-6 . 百度学术
    2. 陈付彬. M-矩阵Fan积的新不等式. 西南师范大学学报(自然科学版). 2020(08): 1-5 . 百度学术
    3. 邓波,苏雪丽,任小敏. 基于圈收缩的图的(Sum-)Balaban指标. 西南师范大学学报(自然科学版). 2019(04): 7-10 . 百度学术

    其他类型引用(0)

  • 加载中
    Created with Highcharts 5.0.7访问量Chart context menu近一年内文章摘要浏览量、全文浏览量、PDF下载量统计信息摘要浏览量全文浏览量PDF下载量2024-032024-042024-052024-062024-072024-082024-092024-102024-112024-122025-012025-0201234Highcharts.com
    Created with Highcharts 5.0.7Chart context menu访问类别分布HTML全文: 84.2 %HTML全文: 84.2 %摘要: 15.8 %摘要: 15.8 %HTML全文摘要Highcharts.com
    Created with Highcharts 5.0.7Chart context menu访问地区分布其他: 4.9 %其他: 4.9 %Beijing: 9.3 %Beijing: 9.3 %Boulder: 0.5 %Boulder: 0.5 %Brooklyn: 0.5 %Brooklyn: 0.5 %Changsha: 0.5 %Changsha: 0.5 %Chiyoda: 0.5 %Chiyoda: 0.5 %Chongqing: 1.1 %Chongqing: 1.1 %Haidian: 4.9 %Haidian: 4.9 %Madison: 1.1 %Madison: 1.1 %Mountain View: 29.0 %Mountain View: 29.0 %Quincy: 4.4 %Quincy: 4.4 %Xiangtan: 0.5 %Xiangtan: 0.5 %XX: 0.5 %XX: 0.5 %Zhengzhou: 0.5 %Zhengzhou: 0.5 %上海: 0.5 %上海: 0.5 %北京: 0.5 %北京: 0.5 %十堰: 2.2 %十堰: 2.2 %天津: 1.1 %天津: 1.1 %扬州: 1.1 %扬州: 1.1 %江门: 0.5 %江门: 0.5 %深圳: 9.8 %深圳: 9.8 %漯河: 1.1 %漯河: 1.1 %芒廷维尤: 19.1 %芒廷维尤: 19.1 %芝加哥: 3.3 %芝加哥: 3.3 %邯郸: 1.1 %邯郸: 1.1 %郑州: 1.1 %郑州: 1.1 %其他BeijingBoulderBrooklynChangshaChiyodaChongqingHaidianMadisonMountain ViewQuincyXiangtanXXZhengzhou上海北京十堰天津扬州江门深圳漯河芒廷维尤芝加哥邯郸郑州Highcharts.com
表( 2)
计量
  • 文章访问数:  999
  • HTML全文浏览数:  559
  • PDF下载数:  73
  • 施引文献:  3
出版历程
  • 收稿日期:  2016-11-15
  • 刊出日期:  2017-10-20

非负不可约矩阵Perron根的上界

    作者简介: 钟琴(1982-),女,四川自贡人,副教授,主要从事矩阵理论及其应用的研究
  • 四川大学 锦江学院数学教学部,四川 彭山 620860
基金项目:  国家自然科学基金面上项目(11471225);四川省教育厅科研项目(13ZB0357);四川大学锦江学院青年教师科研项目(QNJJ-2017-A09)

摘要: 非负矩阵在数学物理、控制论、电力系统理论等领域有广泛的应用.非负矩阵Perron根的估计是矩阵分析理论研究中的重要问题.利用M-矩阵与非负矩阵之间的关系,给出计算非负不可约矩阵Perron根上界的一种新算法,数值例子表明该算法具有可行性.

English Abstract

  • 非负矩阵Perron根的理论在很多领域有重要应用.在实际中,常常需要估计非负矩阵的最大特征值,对于非负矩阵最大特征值上界的估计,文献[1-7]进行了广泛的研究.

    为方便叙述,先给出一些记号.设n阶矩阵B≥0,ρ(B)表示非负矩阵B的谱半径,对i=1,2,…,nri(B)表示矩阵B的第i行行和,R(B)和r(B)分别表示矩阵B的最大行和与最小行和,C(B)和c(B)分别表示矩阵B的最大列和与最小列和.

    n阶矩阵B≥0,如果存在一个置换矩阵PRn×n使得PBPT=(CDOE),其中CE分别是kl阶方阵,k≥1和l≥1,则称B是可约矩阵,否则称B是不可约矩阵.

    Frobenius[1]给出了以下定理:

    正矩阵是非负矩阵的子类,具有非负矩阵的所有性质. LEDERMANN W[4],OSTROWSKI A[5]和BRAUER A[6]在(1) 式的基础上给出了正矩阵最大特征值的界值定理.

    M-矩阵和非负矩阵有着密切的关系.若ARn×n,且A可表示为A=kI-BIn阶单位矩阵,B≥0,当kρ(B)时,称AM-矩阵.特别地,当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根更精确的上界.该方法对所有的非负不可约矩阵均适用,文末附以实例来说明该法的可行性和优越性.

  • 定理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)严格小于k1R(A1),这不同于定理1.考虑矩阵A=kI-B,其中kρ(B)满足定理4的条件,则有ρ(B)<k1R(A1).设k=k1R(A1)>ρ(B),构造矩阵A′=kI-B,则A′是一个M-矩阵,再一次运用定理4,考虑到1R(A1)>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-Bkn=kn11R(A1n1),当(1r(A1n)1R(A1n))<ε时停止迭代,此处ε是一个给定的充分小的正数.

    例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(A1n)1R(A1n))ε,计算kn+1=kn1R(A1n)An+1=kn+1I-B,令n=n+1,转到第三步.

    第四步:计算kn1R(A1n),停止.

    例3  设

    表 2给出了非负不可约矩阵B的Perron根的迭代次数和上界.

    实际上ρ(B) 23.675 920 510 034 04.从上面的数值例子中可以看出应用该算法可以方便的得到精度比较高的Perron根的上界.

  • 利用非负不可约矩阵与M-矩阵的关系,有效地改进了非负不可约矩阵Perron根的上界.在此基础上,给出计算非负不可约矩阵Perron根上界的一个算法,以上的数值例子表明利用该算法可以方便的得到精度比较高的Perron根的上界.

参考文献 (7)

目录

/

返回文章
返回