（计算数学专业论文）非负矩阵perron根上下界的估计.pdf

摘要 摘要 在工程计算中有时需要计算大型非负矩阵的特征值，但是计算其精确值比较 困难。因此，能由矩阵的某些元素或值估计出其特征值就很重要。本文通过不可 约非负矩阵的相似变换，产生出不同于原矩阵的行和和列和去估计原矩阵的p e r r o n 根，从而p e r r o n 根的上下界得到了优化。全文共分为五个部分。 首先为绪论主要介绍了选题背景及要解决的问题。 其次主要描述了非负矩阵p e r r o n 根的相关定理及发展现状。主要介绍了历史 上几种不同的计算p e r r o n 根的方法，著名的f r o b e n i u s 定理。 再次介绍了通过三种变换来估计p e r r o n 根的方法：一般相似变换估计某些特 殊矩阵p e r r o n 根、对称变换和矩阵的迹估计非负矩阵的p e r r o n 根、对角变换估计 非负矩阵p e i r o n 根。这三种方法都是在前人的基础上进行改进，改进后的方法在 文中给了数值例子加以验证。 接着分介绍了一种特殊的矩阵菲负p e r s y m m e t r i c 矩阵，此类矩阵p e r r o n 根的 估计可以通过经它得生成的一个对称矩阵的p e i r o n 根的估计来得到。在本文中给 出了计算非负p e r s y m m e t r i c 矩阵下界的一个序列。 最后分主要讨论分块非负不可约矩阵p e r r o n 根的界。将矩阵其分块后得到比 其阶数小的矩阵，利用得到的矩阵对原来矩阵p e h o n 根进行估计。通过分块，对 矩阵的阶数大大的降低了此种方法也是很好的估计p e r r o n 根的方法。 关键词：非负矩阵，p e r r o n 根，估计，不可约，变换 a b s r 蹦c t a b s t r a c t i ti s n e c e s s a r yt oc o m p u t ee i g e n v a l u e s o fm a t r i c e s ，b u ts o m e t i m e s ，i ti s v e r y d i f f i c u l tt oo b t a i nt h e i re x a c te i g e n v a l u e s t h e r e f o r e ，i ti sp a r t i c u l a r l yi m p o r t a n tt o l o c a lt h ee i g e n v a l u e sb ys o m ee l e m e n t sm a t r i c e s t h i sp a p e r ，b yu s i n gt h et h e o r yo f p e l i o n ，f r o b e n i u sa n ds o m et r a n s f o r m a t i o n s ，w eo b t a i naf e wr o w sa n dc o l u n m s w h i c ha r ed i f f e r e n c ef r o mb e f o r e b yt h e s er o w sa n dc o l u m n s ，w ec a no b t a i nb e t t e r e s t i m a t i o no ft h ep e l i o nr o o t s 1 h et e x ti n c l u d e s5p a r t s f i r s t ，w ei n t r o d u c et h eb a c k g r o u n do fc h o o s i n gt h i sr e s e a r c h a n dp r o b l e mf o r r e s o l v i n g t h es e c o n d w ei n t r o d u c es o m er e l a t e dt h e o r i e sa n dd e v e l o p m e n t sa b o u tp e r r o n r o o t a n di ti sf o c io nt h ei n f r o d u c t i o no fp e r r o n f r o b e n i u s t h et h i r d ，t h r e ek i n d so fm e t h o d sb ei n t r o d u c e d t h e s et h r e ek i n d so fm e t h o d sa r e a b a s e do nt h ef o r m e r s r e s u l t s a n de x a m p l e sa r eg i v e ni nt h et e x t t h ef o r t h ，ak i n do fs p e c i a lm a t r i c e s p e r s y m m e t r i ca r eg i v e n ，t h ee s t i m a t i o no ft h e p e l i o nr o o to ft h i sk i n do fm a t r i xc a nb ep a s st oe s t i m a t et h ep e r r o nr o o to fas y m m e t r y m a t r i x t h e l a s t ，b o u n d sf o rt h ep e r r o nr o o to f ( b l o c k ) n o n n e g a t i v em a t r i c e sb ed i s c u s s e d b yp a r t i t i o n i n gi n t ob l o c k s ，t h eo r d e ro ft h em a t r i xb el o w e r , s ot h i sm e t h o di sv e r y u s e f u 】 k e y w o r d s ：n o n n a t i v em a t r i c e s ，p e r r o nr o o t ，e i g e n v a l u e s ，i r r e d u c i b l e ，t r a n s f o r m a t i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：熬盏日期：加净i 肭日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 越芷一 导师签名：妞 日期：z 0 0 7 年月加曰 第一章绪论 第一章绪论 非负矩阵即元素非负的矩阵，在矩阵分析和矩阵计算中占有十分重要的地位。 非负矩阵谱半径估计即f c r r o n 根的估计，是非负矩阵中最重要的课题之一。在工 程上，矩阵的特征值具有广泛的应用，如大型桥梁或建筑物的振动问题；机械和 机件的振动问题；飞机机翼的颤振问题；无线电电子学及光学系统的电磁震、信 息系统、经济学中的一些问题与矩阵的特征值问题密切相关。在科学上，计算流 体力学、统计计算、量子力学、化学工程和网络排队的马尔可夫链模拟等实际问 题，最后都归结为矩阵的特征值问题。由于特征值问题在许多学科中具有广泛的 应用，因此矩阵特征值的界的估计及求解的理论研究等是当今计算数学和科学与 工程计算研究领域的重大课题。 非负矩阵的谱半径估计是由p c r r o n 发现并开创的，发现了具有正元素的方矩 阵的若干奇特的性质，不久f r o b c n i u s 进一步推广了p c r r o n 的成果，那就是从有正 元素的正矩阵的推广到非负元素的非负矩阵上去，特别是非负不可约的情形，得 到了著名的p e r r o n f r o b c n i u s 定理。这个定理是关于非负矩阵谱半径的一个优美结 果。自此以后，非负矩阵理论一阵是线性代数最活跃的领域之一，并且在数学的 许多分支以及社会科学和社会科学的许多领域都得到了大量的应用。 1 1p c r r o n 根上下界估计的基本思想 如何依赖非负矩阵的各元素来对它的p c 玎o n 根进行估计一直是矩阵计算中非 常重要和困难的问题。在这方面我们有著名的g c r s c h g o r i n 圆盘定理还有与之相关 的o s t r o w s k i 定理和b r a u e r 定理，以及我们经典的p c r r o n - f r o b e n i u s 定理。目前许 多新的研究方法已经应用于p c r r o n 根的估计当中去：我们可以利用矩阵的相似变 化来估计p e i r o n 根的取值范围，我们可以利用圆盘定理在二维的空间中画出特征 值的区域，还可以利用矩阵特征值和迹的关系进行大小估计，所有的这些方法可 以应用到不同的矩阵类。 由于对矩阵实行相似变换后特征值仍然是不变的，所以我们可以对满足某些 性质的非负矩阵，通过选择简单的相似变化来增大它的最小行和或者减小它的最 大行和来改进不等式。而且，如果相似变化前后的矩阵都是正矩阵，那么我们还 电子科技大学硕士学位论文 可以结合b r a u e r 不等式，得到4 的p e r r o n 根更好的估计。简单方便好实现的 p e r r o n 根的估计的方法一直是矩阵谱的估计的重要的研究的重要内容。用算法实 现p e r r o n 根的估计就是比实用的方法。文献f 3 】中构造了矩阵对角变换的算法来进 行p e r r o n 根的估计，这种方法很有效，并且可以得到任意想要的精确度。还有一 种算法就是一p e 肿n 余，最早是由m e y e r 提出并用于非负不可约矩阵的唯一标准 化特征向量的计算。l i n z h a n gl u 推广了这一概念，他用p e r r o n 余和p e r r o n 根 的关系构造了比较有效的算法，我们将在后面作定的介绍。 还有一种方法就是用迹来表示矩阵特征值，这是矩阵谱论的一个比较重要的 内容。从2 0 世纪8 0 年代以来，国内外已经有很多的成果。在用迹来估计特征 值中有以下几种主要的方法：从矩阵特征值的均值的标准差与矩阵迹的关系来确 定特征值的简单适用的上下界；从矩阵的迹与秩的关系来讨论矩阵的最大特征值； 由于前者没有后者那么多限制条件，因而其结果的适用范围很广在用矩阵的迹估 计矩阵特征值的方法中。 1 2 本文主要工作 本文首先介绍非负矩阵p e r r o n 根发展的历史及现状，然后分别沿用三种历史 上不同的方法：一般相似变换估计某些特殊矩阵p e r r o n 根，利用对称变换和矩阵 的迹估计非负矩阵的p e r r o n 根，对角变换估计非负矩阵p e r r o n 根。利用这几种方 法都得到了较为优越的结果，并给了数值例子加以验证。用前人的结果讨论了一 种特殊的非负p e r s y m m e t r i c 矩阵的p e r r o n 根的下界估计。最后讨论了分块非负不 可约矩阵p e r r o n 根，并给出了其下界估计的序列。 2 第二章非负矩阵p e r r o n 根的相关定理及发展现状 第二章非负矩阵p e r r o n 根的相关定理及发展现状 2 1 非负矩阵的p e r r o n 根 计算非负矩阵p e r f o r m 根一直是矩阵分析的一个重要课题之一。但是由于客观 条件的限制，往往直接计算是很难实现的，所以只有通过对p e r r o n 根上下界的计 算来对其进行估计。下面介绍一些基本的定义定理。 在本节中，我们设矩阵a t ( 4 口) r ，若n u 苫( ) o ，则称彳为非负( 正) 矩 阵。 定义2 1 1 嘲每行和每列都只有一个元素是1 ，其余的元素是零的方阵称为排 列阵( 或称置换阵) 。 定义2 i 2 设矩阵a ，h ，) c 一当以2 时，若有n 阶置换矩阵p 使得 l a p ：降4 ：1 【0 如j 其中4 。为，阶子方阵，如为露一，阶子方阵，1 s ，c 露，则称a 为可约阵，若a 非 可约阵，则称a 为不可约阵。 定理2 1 1 ( p e r r o n f r o b e n i u s ) 设4 一( 吩l 。苫。为不可约矩阵，则 1 ) a 有一个特征值r p ( a ) ； 2 ) 相应于r 1 p ( a ) 存在一个特征向量z ，0 ； 3 ) p ( a ) 随a 的任一元素之增加而增加； 4 ) p ( a ) 是彳的单重特征值。 定理2 1 1 嘲设4 。t a i , 1 0 为不可约矩阵，则 ， 玛i n 足一r s p ( 爿) r - m f 墨 ( 2 1 ) 其中r 一荟，l o ， 设m 一曲 稿畸倍 ，1 a , , - - a a ) 万i 幽k 咖埘k 如* + 胁“) ， f 2 - 言n ( 似一a - 7 ) 2 ) ，那么彳的p e n o n 根r 似) 满足 4 第二章非负矩阵p e i r o n 根的相关定理及发展现状 r ( a 、2 万+ f 0 为偶数) 1 ( h 为奇数) j 这些，都是对一股矩阵满足了莱些特殊条件后得到了对p e r r o n 根的估计，那 么还有一部分学者就致力于将非对称矩阵对称化的处理后再对它们的p e i r o n 根进 行估计。 2 2 2 对称化矩阵后估计p e r r o n 根 所谓把非对称矩阵对称化就是指设a 为n x n 阶非负矩阵，那么我们可以得到 一个矩阵s ) - ( s o ) ，其中岛一止口口。显然，s o ) 为对称矩阵，我们通过寻找 r ) ) 与r 似) 之间的关系和对r ( s 口) ) 进行估计来对原来的r 0 ) 进行估计。 y a m a m o t o 通过一系列的工作得到下面重要定理： 定理2 2 4 册设4 = a o ) 为n x n 矩阵，y ) 。呼套，h = f y ( 彳妒) 】2 ， & = e r s ( a 产) e n 】。，其中，一q 1 1 ) ，则 r 。 量圪r ) ： s o 毛s s i r 0 ) 。 显然，不等式( 2 3 ) 比( 2 2 ) 更优越些。 ( 2 2 ) ( 2 - 3 ) d a n i e lb s z y l d 通过研究也得到了一个很好的估计： 定理2 2 5 旧设a - ( ) 为阼n 矩阵，依一y p ( 彳2 汗，则可以得到 p 。s ns 以，似) ，若a 对角相似于一个对称矩阵，那么等式全部成立。 显然，d a n i e lb 是再前人y a m a m o t o 工作基础上，对p e r r o n 根界的估计进行 了优化。后来，ly u k o l i t i l i n a l 还有一个比较直观，直接的结论，该不等式很容 易直接得到对r 似) 下界的估计。 定理2 2 6 嘲设a 一( ) 为n x n 矩阵，以苫2 ，设口一m i n a u ，那么 之峄m 掣2 + 驴，肛爿为不可纵且至少含有黼其中 这两行至少有两个非零对角元，n 2 ，则不等式成立。 5 电子科技大学硕士学位论文 国内学者卢琳璋对p e 玎o n 根界的估计也做了不少工作，得到了不少好的结果， 他引用了t o m a s zs z u l c 对矩阵做近似变换的方法，对某些满足特殊条件的矩阵的 p c r r o n 根做了好的估计。 定理2 2 7 0 “设爿一( 4 口) o 为栉，l 矩阵，以o ，假设存在一下标对( 女，5 ) ， 使( 疗n n ”) a n 。，r t - r , o o 令1 0 。l a , , 口- 。a 。m + ，i ，n 。i i a = j l l j ，d 。吃一4 。一m n “， 则对任意0 m s m o ，以下不等式成立： p o ) 一a x t + 砒m 坤a x f 。r ，- m a s j o 若将条件再加强一些会得到更好的结果。假设矩阵a 除满足上述条件外，且对任 意的j r - ，i o r 螂 ，口， 0 ，那么对于上述m 0 则存在o m m 0 ， j d 口) s m a x z 警p ，眦一所t 磐) ) c ，赢，若对任意的，c 厅，口一，。，那对上述 ，p 口) s 。一m 罂魄日口，对于p e r r o n 根下界也得到类似的结论如下： 定理2 2 8 0 “设爿= ( 4 口) 0 为n 万矩阵，厅z o ，假设存在一下标对 ，s ) ， 姊n 训”o ，北令1 警驰小伊。嗍， 则对任意o 墨历，以下不等式成立： p o ) 之m i n 忙一枷r a i 川n t r + 脚n ) 。 若对任意的j 6t j l o r m j ， ，0 ，则存在o m m o ， p 口) 芑m i n 嚅p 。，m ，。i n f 。r ，, + 脚p ) ，若对任意的， 捍，o 则对上述m ， p o ) 2 血+ ，矩罂魄口 2 2 3 分块不可约矩阵的p e r r o n 根估计 1 9 8 1 年e m e t i cd c v t c h 在【1 1 】中对于非负不可约分块矩阵的p e f f o n 根上下界估 计给出了他的结果。 定理2 2 9 m 1 设爿， 4 t4 ： 4 ，如 4 t4 。 a 如 ： 4 。 6 为n 席阶不可约分块矩阵，其中呜 第二章非负矩阵p e f r o n 根的相关定理及发展现状 为吩雄，阶子矩阵， ，1 1 + 栉：+ ”+ 。，l 令r 口) 2 荟4 矿“， ( 鑫r 似) i 。雪2 b ，( 杰b 口) ) 。一搿 b ，令砌( 劬) 表示鸣最小( 大) 行和， p 口) 一( p 目v ，j = 1 tq o ) 。( 吗) u ；1 t ，贝0 ，( p “) ) s ，似) 蔓r ( q 口) ) ( 2 4 ) r ( 鑫b ，) 蔓r 。，s r ( 艺q 。，) ( 2 5 ) 不等式( 2 4 ) 中不等号与等号，有且仅有一个成立。( 2 4 ) 和( 2 5 ) 是从不同角度对分 块矩阵的p e i r o n 根进行估计。 2 0 0 5 年黄廷祝申淑谦等对不等式( 2 4 ) 进行了研究，得到了对非负不可约矩阵 p e r r o n 根上界的序列 定理2 2 1 0 ”设彳为n 阶非负不可约矩阵，则p ( a ) s n 主n s p o ， l i m p , 一p ( 4 ) ，其中n p i q 口) 7 ) 。 2 。2 4 利用p e r r o n 余估计非负不可约矩阵的p e r r o n 根 1 9 8 9 年m e y e r 为计算马尔可夫链的平稳分布向量构造了一个算法，在【1 2 】中 首次提出了非负不可约矩阵p e 仃o n 补的概念。 定义3 【1 3 1 设矩阵一是n x n 阶非负不可约矩阵，其谱半径为p ( a 1 ，集合 a c ，口一妒，声； k ，则矩阵彳的对角块矩阵彳陋】的p e r r o n 补是 p ( 一爿【a 】) = 彳【卢】+ 彳【卢，a i ( p ( a ) 一一【a 】) a a ，卢】。 并证明了其p e 玎o n 补为非负不可约矩阵。 后来卢琳璋等在【2 】中又构造了一类非负矩阵， n ( a i 爿k 】) - a ( o + 彳【卢，口】( 盯一a h ) 1 4 陋，芦】，t ，p ( 爿k 】) 此类我们则称为矩阵 4 的广义p e r r o n 补。 此类方法对p e r r o n 根研究就是利用p e f f o n 根及它的p e f f o n 补以及广义p e n o n 补之间的联系开展的。 定理2 2 ”“”设爿是非负不可约矩阵，其谱半径为p 似) ，集合 口c p ( 4 ) ，p ( 4 【a 】) f p 似) 后来他又对p e r r o n 补进行了研究得到了改进的估计 定理2 2 1 3 “町设存在一对实数f ，“，使得f p ( n l 爿k 】) ) 量“，t ) p ( 彳 ) ) ， 则 l n i n ) ，盔。 定理2 2 1 5 设彳为n 阶非负不可约矩阵 苫3 ，且，聃，若先取口使 r a 阐i n r a a ) 1 警o 取使s 一，t o ，m a x r j ( a ) ，贝j j p ( a ) s m a x t o ，z t o , a ， 其中刁，一( p f ( 爿1 4 口】) ) ，之，一，；。( a o l 4 p 】) ) 。 在【1 9 】中，作者指出当f 2 p ( a ) 时，不可约逆m 一矩阵矩阵的任意广义p e r r o n 补是不可约逆m 一矩阵。 以上就是关于p e n o n 根的相关定理的基本思路和方法，下一章主要介绍成 果以及改进。 8 第三章非负矩阵p e r r o n 根的上下界的估计 第三章非负矩阵p e r r o n 根的上下界的估计 3 1 一般相似变换估计某些特殊矩阵p e r r o n 根 在本节中，主要讨论对于满足某些特殊条件的矩阵，可以通过对它进行相似 变换得到一个新的矩阵，通过对新矩阵的p e r f o n 根的估计来对原矩阵的p e r r o n 根 进行估计。国内学者卢琳璋对p e r r o n 根界的估计也做了不少工作，得到了不少好 的结果，他引用了t o m a s zs z u l c 对矩阵做近似变换的方法，对某些满足特殊条件 的矩阵的p e r r o n 根做了好的估计，得到了下面一系列的定理。 3 1 1 相关足理 引理3 1 1 【1 “设爿，( n 口) o 是满足：假设存在一下标对( 七，s ) ，使 ( - a n ) a h o ，r k - r , 0 的矩阵，令： 。曲 警毋甓) ，帆叱叫 如果对于任，y = ，o ；。) ，n p ，o ，那么存在o m n 。，满足： 出，如a x b k - m 曾斗c ， 如果对于任意的j ( 栉) ，4 ，o ，那么上述的坍，使得： p ( 4 ) k 一嬲曾4 n 上面是对上界的估计，用同样的方法可以得到对下界的估计。 引理3 1 2 0 “设爿= ( ) z o 是满足：假设存在一下标对( 七，s ) ，使 ( d 口一口肚a h o ， 一吒 o 的矩阵，令： 9 电子科技大学硕士学位论文 m 。一曲 警，r a 删i n 酬一一一， 如果对于任意，p ) ，n p ，o ，那么存在o s mm o ，满足： 出，一协r 椭州嘧 ， 如果对于任意的j e i n i ，o 那么上述的m ，使得： p ( 4 ) + m 罂拇a i 3 1 2 主要结论 利用第二章的定理9 和定理1 0 以及上面引理的方法，可以将t o m a ss z u l c 在文 献【5 】中下面引理进行改进得到定理3 1 。 引理3 1 - 3 嘲设爿- ( a g ) 苫o 是厅x n 阶矩阵，n 苫2 ，令口一m 。i n 口“，则： 蚋m a x l r a + _ _ _ z a 华伊一 ， 若一苫3 且彳为不可约阵且至少有两行含有超过一个非零的非对角元素，则不 等式严格成立。 定理3 1 - 1 设彳一0 # ) o ，是雄万阶实矩阵，厅- - 2 ，令a 。乎， 卢- a 。i m a x a d 。假设存在一对下标 s ) 使得( 4 。一口a b 0 。其中七，s ，t 。定 义： m 呻k 斟蛩 “m i n l m i nk ) ，+ m a n h g 一七，j ) 4 ：一j a 。+ 缸。( f 一七) ， l a 。一m a 。( f s ) 1 0 第三章非负矩阵p e r r o n 根的上下界的估计 则 悯峄p + 【( 孚) 2 + a * a j i + m a a u 小 第一步，我们证明不等式( 3 2 ) ，令e 。是单位矩阵i 的第i 列。 设爿= b a b = ：) 则彳与彳相似，且它们仅在第j 行和第k 列不同。 n 盖一4 皿+ 缸j rj e 半+ 【华沓渺池】j 故( 3 - 2 ) 优于( 3 - 1 ) 。 3 1 3 数值例子 例3 1 1 设 a = 1 12 2 23 235 由引理3 1 1 ，删，等+ 雨两以1 2 3 。 由定理3 1 1 ，取k = 1 ， s = 2 ，则m = 0 5 可得 删，半+ 一7 6 1 6 。 这个结果比应用( 3 - 1 ) 结果有了很大的改进。 3 2 利用对称变换和矩阵的迹估计非负矩阵的p e r r o n 根 3 2 1 相关定理 引理3 2 1 啪设a - ( a 目) c “4 是h e r m i t e 阵，则 。( a x ，z ) - f 血 。呀莨芽。呀百 其中 为矩阵彳最大特征值。 l y u k o l o t i l i n a 在【9 】中，指出把a 进行对称变换得到一个新得矩阵 l s ( a ) - ( ) ，其中呀- ( a o n ，f 引理3 2 2 湖设a 是弹以非负矩阵，那么 第三章非负矩阵p e i r o n 根的上下界的估计 那么 r ( 彳) ，( s ( 爿) ) 引理3 3 3 嘲设4 是杯n 非负矩阵，设： 气= p ( 爿) e r ，t ( n 一，1 ) s ( 4 ) ；( ) 一( 厩) ， o q s f is ，( 爿) 并且若4 是循环指数为女，宓z 1 ，的非负不可约循环矩阵，那么： 舰( 华卜巾， 引理3 3 4 伽设a z o , 风。，( s ( 彳) ) ，那么： 岛n ns r 似) d a n i e b s z y l d 在【8 】并证明了fi s p i ，) 。 上面的两个引理都是利用了a 的对称变换矩阵s ) ，再看看第二章中提到的 下面两个定理： 定理2 2 2 嘲设a = 魄) 为n 阶非负矩阵，那么： r ( 么) z 疵h + n 戳 厅 、f j 即f ， y 弹一1 l o( 3 - 5 ) m 晌k 括 ，蛩 ， 万一曲k 瑰小”慨) ，霞4 剐) 2 ) o 那么a 的p e r r o n 根r ( 4 ) 满足下面的不等式： 其中t t - 五- + ( 丢开( 岬) 卜 第一步：定义一个矩阵口一( ) ， 一 啪， 那么我们可以得到c 一( 勺) 一b x a b 。显然c 于爿只有s 行和七列不同，并且它 第三章非负矩阵p e r r o n 根的上下界的估计 一+ 胁卢 f o rj e 1 , ，小 s ) c q n f 一肘f o r ，仙， 孔忙) ( 3 7 ) c 睹昌a s k - m a e , + m ( 4 嚣一m a b ) 通过c 的定义我们知道c 实一个非负矩阵。因为定理3 2 1 ，我们得到： 三 ，( c ) 芑丘+ ( 吾开( c c 一蠢，2 ) ) 7 其中石= 曲勺，利用( 3 5 ) ，0 6 ) 和m 的定义，可以得到： a 崔口 那么我们可以把( 3 7 ) 变换得到下面这种形式： r ( c ) 芑万+ ( 昙n ( c c d ，7 ) ) 2 因为a 相似于c ，那么： r 口，。rc c ， 开( ( 爿一万，) 7 ) 4 乃( ( c 一万，) 7 ) 因此， 土 ， ) 目，( c ) 乏万+ ( 昙乃( ( c 一刃尸) ) 。 i 万+ ( 三丹( 一刃，7 ) ) 7 利用与定理3 2 1 同样的证明方法我们可以得到q ：s s 因此下面的不等 式成立： 毛s 艿2 s s 墨r ) 第二步：接下来我们要i 正b y j ( 3 - 6 ) 至少要和( 3 4 ) 一样好根据万的定义和我们 的假设，可以看出： 石- m i n k ) i 。 设函数庐( f ) 1 7 电子科技大学硕士学位论文 三 妒( t ) r + ( 昙n ( 似一盯，。) ) 7 计算可以得到妒( f ) 2 0 ，那么妒( f ) 是一个增函数我们可以得到： 万+ ( 寺乃( c c 一万，z ) ) ；z nc ，+ ( 三z ，( 。t 一nc 口。，2 ) ) ； 证毕。 上面的两个定理我们都是通过最小的对角元呷n ) 得到的，下面我们通过矩 阵的迹来得到对r ) 的下界估计的一个序列。 定理3 2 3 设4 一瓴) 是n 阶非负实矩阵，那么： q s s s q s r 口) 撕州+ 朴一半旷 证明：通过( 3 - 3 ) 我们可以知道 r ( 爿) 一九( 4 ) 。半+ 九( b ) | | 降训口，l 还有， r ( 爿) 2 半 我们知道( 口) 非负，还可以得到： 。( b ) 一m ( 曰) 之l ( 口l 因此， 进而有： 玎( 九( 硼。之弘厂一开( 。一半) 第三章非负矩阵p e r r o n 根的上下界的估计 r ( 爿) t ( 4 ) 。半+ ( 丑) 己半+ 州似一型n ) 厂 下面我们将证明这个序列是递增的。设 ( 曰2 ) 一 ，那么， p 4 ) 一舒 n ( b 2 ) = 骞 ，乃( b 4 ) ；砉膏， 淞一睢a 肚隆一将) 2 ) 一# 耻吾酬 利用 2 + 1 2 现，因此， 三( ( n 一) 砉碍一z 荟 - ) 芝。， 昙乃( 曰4 ) 乏( 昙打( 口2 ) ) 。 那么就有qs ，因此该序列是一个递增的序列。 注3 2 1 ：因为相似变换不改变一个矩阵的迹，那么我们就不能再通过定理 3 2 3 相似于由定理3 2 1 推定理3 2 2 那样， n - - 个更好的定理推其他定理。 3 2 3 数值例子 a = 1 12 213 2 35 我们利用序n ( 3 6 ) ，如表( 3 1 ) 所示： 表3 - 1 r ( a ) - 7 5 3 1 1 。 七12 3456 成4 9 1 5 7 85 9 6 7 0 1 6 6 9 3 17 0 9 7 7 37 3 1 0 7 17 4 1 9 9 7 电子科技大学硕士学位论文 我们利用序y u ( 3 8 ) ，如表( 3 一) 所示： 表3 - 2 _ j 123456 v k6 0 1 5 16 4 0 7 76 8 6 9 9 7 1 8 6 2 7 3 5 5 77 4 4 2 7 因此成和都非常接近，似) ，更优于p 6 ，它们两个都比【4 】中得到的结果优 一些，其中【6 】的结果为，) 苫1 + 牺。 例3 2 2 设 ，21 01 4 2 l 7 11 1 1 21 1 1 表3 3 七 1 2 3 4 56 见1 2 3 5 7 81 3 6 1 51 4 3 8 8 61 4 9 2 81 5 3 2 7 21 5 5 6 9 9i 通过序列3 - 8 ，如表3 4 所示 表3 4 七 123456 n1 2 3 5 7 81 3 6 1 51 4 3 8 8 61 4 9 2 81 5 3 2 7 21 5 5 6 9 9 由定理3 2 2 ，取m = 1 1 4 ， c b z a b = l71 5 5 1 061 0 3 i21 1 1 4 2 9 表3 - 5 七123 45 6 1 2 4 1 6 41 3 6 9 1 91 4 5 1 7 61 5 1 2 1 21 5 5 5 5 81 5 8 0 5 6 显然优于以，并且比【5 - 6 】中的结果更好的接近真实值。 其中【5 】中结果为，似) 之1 + j 而，【6 】中结果为，) 七l + 圻页。 注3 2 2 ：在这个例子中，我们发现万= n 印( 气) = 1 ( 在定理3 2 2 中的定义) ， 所以通过序列3 - 6 和序列3 - 8 得到的结果是一样的。 第三章非负矩阵p e r r o n 根的上下界的估计 3 3 对角变换估计非负矩阵p e r r o n 根 在本节中我们要利用相似对角迭代来对非负矩阵的p e f r o n 根进行估计。 在文 2 0 e p ，w o l f g a n gb u n s e 指出了一种估计矩阵谱半径的方法那就是对角迭 代，在文中他就列出了1 3 种不同的对角变换。在文【2 2 】中，也讨论了一些对角变 换。特别对非负不可约的矩阵，作者得到了一种相对比较简单的对角变换。 在这里我们设掣代表a o 的第i 行的行和，也就是： 掣。荟4 a 0g = 1 ，席) ，霹。薹4 。k a = 1 ，n ) 我们还设： r 一r a i n 磷，r 一m a x 磷( f = 1 ，厅) 于是p e r r o n - - f r o b e n i u s 可以写为： r o r 似) s r o 若，o r o ，那么，口) - 一一r o 。所以在此我们就假设，o r o 。 在文 2 1 1 0 p ，作者做了一下假设： 巩= d i a g 咚：，s ：，s b 还有 4 。一d f l 4 b 一0 0 “l 。( f 一】，万) 对于非负矩阵彳一( ) 。满足a i i 0 ( f 一1 ，厅) ，得到了一列相似矩阵 4 ) ，还有 相应于这些相似矩阵的最小行和 ，) 和最大行和 形 。 3 3 1 主要结论 引理3 3 1 咖对于上述的序列 4 ) ， r ) ，以及 ， ，其中 时) 实单调递 减的序列并且有下界， ，) 是单调增加的序列并且有上界。 对于矩阵序列 4 ) ，按照【7 】中的相同定义，我们可以得到对非负矩阵p 踟 根估计的另外一些估计。 首先，我们构造矩阵列 4 一) ，我们知道彳的特征值 ( 彳) 和4 产的特征值 电子科技大学硕士学位论文 ( ) 满足： ( ) 一矿口) ( 3 - 9 ) 定理3 3 1 设爿一( 4 f ) 。并且) 0 ( f t l ，厅) ，下面的不等式成立： 占os 气s 量气s & “sr ) s p k + 1s 以s ns 岛 & 。( 叩( 嚣) ra 。( m x ( 露) ) 一 露矩阵者；露搿豆第f 行的行和： 厩一幽g ( 霹，s 2 ，o 一，鄙) ，厦- d i a g ( 鼋k ，霹，昂) 证明：由( 3 - 9 ) 我们得到： r ) 一( r ( 爿) ) 产 哗酽，) 峄酽 气墨， ) n 下面我们来证明矿和p 分别单调递增和单调递减。 墨恸勘。赢献扣) 盼确) ) 】( v s - 1 n ， 善善4 一吩【倒i 、留 八爿倒 门 = ( 薹耋：= ! ! 】竺( 耋圣= = ：) 荟善唧 = ( 薹圣：= ：! ) = ( 薹薹：) 荟 第三章非负矩阵p e r r o a 根的上下界的估计 s m a x避 幽 - ( 0 0 ) 2 因此我们得到n 墨岛- 又因为： 墨恸协赢艨即帅 善善4 【爿钉 八符笥 ，川 荟酗 竺：【薹耋：! ) 竺：( 耋耋：) 善峄善口一 = f t 舒 芑m m 善 一( ) 2 ， 我们又得到，芑。证毕。 下面我们来构造一个对角矩阵来对原矩阵进行相似变换得到不同于【2 1 】中的 矩阵序列。在此，我们定义： 见一妣g ：，d ：，) 其中， 以士 2 r 一s 并构造： 4 。- 绣4 d i 一瞄“x 。g - 1 ，舞) ( 一l o ) 通过非负矩阵爿一( l 。并且，0 0 一1 ，一) ，我们可以得到一个相似矩阵序列 电子科技大学硕士学位论文 4 ) ，还有相应于这个矩阵序列的最小行和序列 ，】和最大行和序列 彤) 。同 样的在此我们将证明经过不超过，( 1 s ss 丹) 次迭代后，最小行和事递增的序列， 而最大行和是递减的序列。通过这种对角变换，我们可以得到下面的一个定理： 定理3 3 2 设4 = ( ) 。是非负矩阵并且，o ( i = 1 n ) ，似) 是它的 p e r r o n 根。对序列 4 ) ， r k ) ，和 r ) ，下面结论成立： r ) 是单调递减的并且有下界， k ) 是单调递增的并有上界。 证明：由( 3 - 1 0 ) 可以得到： a 扩一( 耐一甜) 驯去) 乏( 勰一霹) 驯南) z ( 筹) 群 足义函数。 驴( f ) - ( 2 c - t ) t 对妒微分，我们立即可以看到：当f s c ，妒是一个单调递增的函数。我们还知道， ，一2 r t _ r ， 因此，我们可以得到： 磷“， 又因为： 牡薹弘( 肌掣k ，弘( 志) ( 勰一并) ；| ；苟( 杀) 字斟7 6 ；。 由伊“) 一( 2 c t ) t 的定义我们知道， 第三章非负矩阵p e r r o b 根的上下界的估计 磷“s r 根据( 3 - l o ) 和( 3 1 1 ) ，下面的不等式成立： ，s ，“4 s