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

摘要 摘要 非负矩阵即所有元素都为非负实数的矩阵。这类矩阵在数理经济学，管理科 学，计算机科学，工程学上有着广泛的应用。在非负矩阵的理论中，计算其最大 的特征值非常重要。但是对于阶数较高的矩阵，直接求出其最大特征值比较困难， 因此对其进行估计就很重要。在这方面有很多很好的结果。本文将在一些经典结 果的基础上进行进一步的改进，利用非负矩阵的行和和列和的关系来进行估计， 从而得到了进一步的结论。 本文分为四章。其中第一章给出了非负矩阵的定义和一些基本的性质。第二 章给出了非负矩阵最大特征值估计的一些经典的结果。第三章是本文的结论，在 一定条件下对p r o b e n i u s 定理进行了改进。通过关系式 p 。= p ”f ( p ) f ( p ) 和三个引理，用行和与列和的比值的关系对p 进行估计。第四章介绍了e 2 1 3 和e 2 2 3 的两种方法。4 1 介绍了用分块的方法，把n 阶矩阵化为阶数较低的矩阵，从而 得到了比f r o b e n i u s 定理更大的下界和更小的上界。4 2 介绍了通过适当的选择 矩阵a 的p e r r o n 补，从而使得非负矩阵的阶数降低但是谱半径保持不变，并在 此基础上得到了改进的算法4 3 对各种算法进行了比较，给出了算例。 关键词：非负矩阵p e r r o n 根不可约p e r r o n 余谱半径 a b s t i 认c t a b s t r a c t a n o n n e g a t i v em a t r i xi sam a t r i xt h a ta l l i t se l e m e n t sa r en o n n e g a t i v er e a l n u m b e r s t h i sk i n do fm a t r i xi sw i d e l yu s e di nm a t h e m a t i c a le c o n o m i c s ，m a n a g e m e n t s c i e n c e ，c o m p u t e rs c i e n c ea n de n g i n e e r i n g i nt h et h e o r yo fn o n n e g a t i v em a t r i c e s ，i ti s v e r yi m p o r t a n tt oc o m p u t et h e i rm a x i m u me i g e n v a l u e s b u ti t i sv e r yd i f f i c u l tt o c o m p u t et h ee i g e n v a l u e so fm a t r i c et h o s eh a v eh i g ho r d e r s ，s oi ti sv e r yi m p o r t a n tt o g e tt h ee s t i m a t i o no f t h e m t h e r ea r em a n yg o o dr e s u l t so nt h a t t h i sp a p e rw i l lh a v ea i m p r o v e m e n to fs o m ec l a s s i cr e s u l t s ，u s i n g t h es u m so fr o w sa n dc o l u m n st o e s t i m a t e ，g e tab e t t e rt h e o r y t h i sp a p e rh a sf o u rc h a p t e r s t h ec h a p t e r1w i l lg i v es o m eb a s i cd e f i n i t i o n sa n d p r o p e r t i e so fn o n n e g a t i v em a t r i c e s t h ec h a p t e r 2w i l lg i v es o m ec l a s s i cr e s u l t sa b o u t t h ee s t i m a t i o no ft h em a x i m u me i g e n v a l u e so fn o n n e g a t i v em a t r i c e s t h ec h a p t e r3 i st h ec o n c l u t i o no ft h i sp a p e r i ti m p r o v e st h ef r o b e n i u s 。t h e o r yu n d e rs o m e c o n d i t i o n sb yt h ee q u a l i t y p “= p ”f ( p ) f ( 户) a n dt h r e el e m m a s ，e s t i m a t epb yt h er e l a t i o n s h i po ft h es u m so fr o w sa n d c o l u m n s c h a p t e r 4i n t r o d u c et h em e t h o d so f 【2 1 】a n d 【2 2 】4 1 i n t r o d u c et h em e t h o d f o rp a r t i t i o n i n gam a t r i xi n t oas m a l l e rm a t r i xa n dg e tb e t t e rl o w e ra n du p p e rb o u n d s 4 2i n t r o d u c et h em e t h o dt h a tg e tai m p r o v e m e n tb yc h o o s i n gap r o p e rp e r r o n c o m p l e m e n to fa ，r e m a i nt h es p e c t r a lr a d i u so fa a n dr e d u c et h eo r d e ro fa i n4 3 n u m e r i c a le x a m p l e sa r eg i v e na n da l g o r i t h ma r ec o m p a r e d k e yw o rd s ：n o n n e g a t i v e m a t r i xp e r r o nr o o ti r r e d u c i b l ep e r r o nc o m p l e m e n t s p e c t m lr a d i u s i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：吴潺睇 z p d 罗年月中曰 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： “、 l 内部5 年( 最长5 年，可少于5 年)； l ；秘密l o 年( 最长1 0 年，可少于1 0 年) ； ；机密 k 2 0 年( 最长2 0 年，可少于2 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：吴觏学 2 0 0 9 年舌月于日 第一章非负矩阵的基本概念 第一章非负矩阵的基本概念 如果一个矩阵的所有元素都是非负实数，则称这个矩阵为非负矩阵。非负矩 阵在经济学，概率统计，最优控制，计算机，工程学上有着广泛的应用。在非负 矩阵的理论中，对最大特征值的估计尤其重要，是非负矩阵的重要理论之一。 非负矩阵的系统研究是p e r r o n 从1 9 0 7 年的工作开始的，他首先发现了正矩 阵的若干特殊性质，这些结论在不久后由f r o b e n i u s 进一步推广到了非负矩阵， 特别是非负不可约矩阵的情形，得到了著名的p e r r o n - f r o b e n i u s 定理。到了上 世纪中期，通过a b r a u e r ，0 t a u s s k y ，rs v a r g a ，a 0 s t r o w s k i 等人的工作，形 成了非负矩阵的系统的理论。从此，对非负矩阵的研究成了数值代数的最活跃的 领域之一，并且在数学的许多分支，自然科学工程和社会科学的许多领域得到了 。重要的应用。 1 1 非负矩阵和正矩阵 设r ”表示实数域r 上所有n 元数组x = ( x ，x 2 9o o ，k ) t 构成的n 维向量空间。 设胪表示实数域r 上所有m x n 矩阵a 2 ( a u ) 一的集合。如果矩阵a = ( a u ) 嗽。的 所有元素a 日0 ，则称矩阵a 为非负矩阵，记为a o 。如果a 日 0 ，则称a 为 正矩阵，记为a 0 。矩阵a 2 ( a 日) 似。的n 个特征值五，五，丸组成的集合称为a 的谱，记为o r ( a ) ，即仃( a ) = 互，五，五) 。矩阵a 的特征值的模的最大值称为 a 的谱半径，记为p ( 内，即 p ( 砷= m a x i i ，i 五i ，i 1 ) 定义1 1 1 1 】设a 2a o ，b = “，如果对于所有的i , j 都有a o ， 则记a b 。 对任意矩阵 a _ - ( a i j ) c 肭， 用ia i 表示a 的元素取模之后得到的非负矩阵，即ia l = ( i a 。i ) 。 第一章非负矩阵的基本概念 定理1 1 1 【2 】( p e r r o n ) 设a er 僦，如果a 0 ，则， ( 1 ) p ( 訇为a 的正特征值，且存在正向量y r n 使得a y = p ( a ) y ， ( 2 ) 对于a 的任何一个其他的特征值，都有i 五i 户( 砷， ( 3 ) p ( 砷是a 的单特征值。 这个定理对于一般的非负矩阵并不一定成立， 比如设矩阵 a = 0 b b0 0 0 0 0 0 0 0 0 b o 0a 其中0 a b ，由计算可知，矩阵a 的特征多项式为 f ( a ) = ( 力一a ) ( 名一b ) 2 ( 五+ b ) ，( 1 1 ) 所以户( a ) = b ，并且a 有对应于特征值p ( 訇的特征向量 盯= ( s ，s , t ，0 ) ， 其中s , t 可以取正数，但是夕( 啕= b 不是a 的单特征值，a 没有对应于特征值 夕( 砷= b 的正特征向量，并且a 有异于b 的特征值力= - b 使得i 五i _ p ( 砷。 一般的，有以下的结论： 定理1 1 2 【5 】设a 妒，如果a 0 ，则户( 訇为a 的特征值，且有特征向 量x 0 定理1 1 3 ( k yf a n ) 3 】设a = ( a 日) 似。为n 阶复矩阵，b = 峨) 似。为n 阶非负矩 阵，且满足 ia i o ； ( 3 ) p ( 内随着a 的任何一个元素的增加而增加； ( 4 ) p ( 匈是a 的单特征值。 其中，我们将非负不可约矩阵的特征值夕( 匈称为a 的p e r r o n 根，其对应的 向量称为a 的p e r r o n 向量。 定理1 2 3 6 】设a 为非负不可约矩阵，则 ( 1 ) 若a x = p ( 内x ，其中x 非负且x 0 ，则x 0 ，即x 为a 的p e r r o n 向量。 ( 2 ) 若a x = 2 x ，其中x 非负且x 0 ，则a = p ( 訇，即力为a 的p e r r o n 根，且 x 0 ，即x 为a 的特征向量。 定理1 2 4 【6 】若a 为1 1 阶非负不可约矩阵，则尸( a ) 为a 的单特征值，且a 的所有模为户( a ) 的特征值也是单重的。a 有一个对应于户( a ) 的正特征向量口， 且a 的任何一个非负特征向量都与甜线性相关。 定义1 2 2 5 1 设a 为非负不可约矩阵，则模等于户( a ) 的a 的特征值的个数 称为a 的循环指标。若k _ l ，则称a 为原矩阵。设a 为非负不可约矩阵，则a 3 第一章非负矩阵的基本概念 为原矩阵的充要条件是存在一个正整数m 使得a m 0 。 定理1 2 5 【5 】设a 为n 阶原矩阵，则 ( 1 ) 夕( 匈为a 的正特征值，并且存在正向量x er n 使得a x = p ( 内x ； ( 2 ) 对于a 的任何一个其他的特征值名，有i 见i s 2 ， 使得 吨n ( a ) + i 户( 匀m a x r i ( 鹤一e ( 2 7 ) 因此o s t r o w s k i 的结果好于l e d e r m a n n 的结果。 对于正矩阵b r a u e r 基于同样的思路，提出了种新的方法，即通过选择适 当的相似变换( 由于相似变换不改变矩阵的特征值，从而保证了相似变换的 p e r r o n 根的值不变) ，从而得到了， m i nr i ( 内+ r ( h 1 ) p ( 訇m a x r i ( 绚- r ( 1 一二) ，( 2 8 ) 其中栌m 。i n ， g=r-2r+rz-4r(r-r)，h：-r+2r+,jr2+4r(r-r) 。 2 ( r 一7 7 )2 7 定理2 4 1 1 4 1 设a 2 ( a o ) 帅是非负矩阵，n 2 ，r i - z a 日为a 的第i 行行和， j = l 若存在一对下标( 1 ( ，s ) ，使得 ( a k k a s , s ) a k 。 0 ，r k r s 0 ， 设 一i n t a k , k - - a s , s ，r a 一i n 剐a i k a i ，a - 泌， i a k s a 0 【，。jj 则对于任意的0 m sm o ，以下不等式成立， 6 ( 2 9 ) 、rj 、， j 屯 m一 黜 已， rl xamdm + l ，j、【 xamv i 砷 p 的意 任于对 果 如 第二章非负矩阵谱半径的经典结果 那么存在o m m o 使得 j y = j ：r j = r 眦) ，a j ，s o ， 户( 内m a x 嘴r j ，k m m 乒i ，na ：，s ) 0 ，那么对于上述的m ， 尸( 今r m a xm 熙a j s e n ( 2 1o ) 定理2 5 【1 4 】设a = ( a 日) 似。是非负矩阵，n 2 ，= a d 为a 的第i 行行和， 若存在一对下标( 1 ( ，s ) ，使得 i 发m o = m i n a s ，s a k k a k s ( a 。，。一a k , k ) a k 。 o ，r s r k o 则对于任意的o m m o ，以下不等式成立， p ( a ) m i n r s m d ，唑 r j + m 如) ) 如果对于任意的j 艿，a j ，； 0 ，那么存在 使得 0 m m o ， j = l 夕( a ) m i n 嘧r j ，+ m m 脚i na j , s ) ， 如果对于任意的j ，a j ，。 0 ，那么对于上述的m ， 尸( 内+ m 恕a j ，s 7 ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) 、，j 、，j 生 ，j、【 m 如 m 吣 第三章用行和比与列和比估计谱半径 第三章用行和与列和比估计谱半径 对于非负矩阵最大特征值的估计，有著名的f r o b e n i u s 定理，本章将在这个 定理的基础上进行改进。 定理3 1 【8 】( f r o b e n i u s ) 如果a = ( a ；) 似。是非负矩阵，p ( 内为其最大特征值， 则有 m i n ( 内夕( 砷m a x r i ( a ) ， ( 3 1 ) 先给出几个引理 引理3 1 1 5 1 设p l ，p 2 ，p 。是任意实数，q 。，q 2 ，q n 是任意正数，则 m i n 旦里! 旦2 ：旦g m a x 旦， q iq l + q 2 + + c 1 q i 当且仅当所有的旦相等时等号成立。 q i ( 3 2 ) 引理3 2 【1 5 】设a 是n 阶矩阵，岔是a 的转置矩阵，名是a 的特征值， x = ( 一，毪，代) t 与( y 1 ，y 2 ，y n ) t 分别是a 和 对应于五的特征向量，则 阵。 nnnn 力x = k c ；( a ) ，名x = y i ( 内 ( 3 3 ) 引理3 3 设a ，b 是n 阶矩阵，则 r i ( a b ) = a u r j ( b ) ，c i ( a b ) = a j i c j ( b ) ( 3 4 ) j = lj = l 设a 是非负矩阵，f ( x ) 是系数为非负实数的多项式，则f ( a ) 也是非负矩 下面我们利用等式 p m ：= p m f ( p ) f ( p ) 和三个引理来对f r o b e n i u s 定理进行改进。 ( 3 5 ) 第三章用行和比与列和比估计谱半径 则 定理3 2 设a 是n 阶非负矩阵，f ( x ) 是系数为非负实数的多项式，且满足 l ( f ( a ) ) 0 ，c i ( f ( 内) o ( i = l ，2 ，n ) ， c 中等挚u m ey i = z r i ( a m tf ( 疋) ) i = l i = l f ( p e 誓= 墨c i ( f ( 砷) i - - ii = 1 f ( 尸) y i = y i i ( f ( 灯) ) 罨c ；( a m f ( a ) ) p ”= 旦f 一， k c ；( f ( 匈) j 三l ( 3 8 ) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) ( 3 1 2 ) 觚n 等等矿如a x 筹导， c i ( f ( a ) c i ( f ( a ) 、 ( 叩等等) l ，( 蚓m a x 等等) i ，“ 9 第三章用行和比与列和比估计谱半径 nx ( a m f ( a ) ) p “= 一， (314)n， 。 、一 k ( f ( 啕) 根据引理3 1 可得 m i n51 竺! ! 型p m m a x 圣! 竺! ! 型 【t 【砷【f ( 砷 即 ( 叩等等) l ，( 峒m 精筹) 1 ，”口 ( 3 - 1 5 ) 取m = l 可以得到如下的推论 推论3 1 设a 是n 阶非负矩阵，f ( x ) 是系数为非负实数的多项式，且满足 e ( f ( a ) ) o ，c i ( f ( a ) ) 0 ( i = l ，2 ，n ) ， 则 唧n 揣r i 酬釉m a x 揣， ( 3 1 6 ) t ( f ( 砷) 一7t ( f ( a ) ) 7 m i n 掣p ( a ) m a x 螋( 3 1 7 ) t c i ( f ( 匈) 一7- c i ( f ( 匈) ”7 定理3 3 设a 是n 阶非负矩阵，f ( x ) 是系数为非负实数的多项式，且满足 i ( f ( 神) 0 ，c i ( f ( a ) ) o ( i = 1 ，2 ，n ) ， 则对于任意的正整数m 有 m i n 型掣m i n ( 型竺! 塑丝) m a x ( 5 1 竺! ! 垡! ) m a ) 墨( 笪! 箜2 l ( f ( a ) )、( f ( a ) ) 7 i 、( f ( a ) ) 7l ( f ( 内) ( 3 1 8 ) 证明： 等等= 志缸删等等( f ( a ) )( f ( a ) ) 智“”、”( f ( a ) 志缸蛳a x 帮，= 揣m a x c 等警， 以此类推，可得 l o 第三章用行和比与列和比估计谱半径 所以 同理可得 m a x ( 垦! 竺! ! 生2 ) m a x 圣! 笪! 坐2 t 、l ( f ( a ) ) 7l ( f ( a ) ) ( 3 1 9 ) m i n 嘿m i n ( 黑) - ，m ( 3 2 0 ) e ( f ( 匈)i 、( f ( a ) ) 7 、7 定理3 4 设a 是i l 阶非负矩阵，与( x ) ，f a x ) 是系数为非负实数的多项式， f ：( x ) 整除f a x ) ，f ：( x ) = ( x ) ( x ) ， r i ( f ：i ( a ) ) o ，c i ( f ：i ( a ) ) o ( i = 1 ，2 ，n ；j = l ，2 ，3 ) 。 则对于任意的正整数m 有， m i n r | i ( a mf 2 ( a ) ) m 1 n 墨! 竺墨! 鱼2 m a x 圣! 竺! 型m a 】【圣! 竺蔓! 业 i ( ( a ) ) t i ( f ；( 内) i ( ( 訇) t i ( ( 内) 证明：因为 丘( x ) = ( x ) ( x ) ，且( 訇= ( ) 啪， 所以 ( a m f ；( 匈) ( e ( a ) ) s ；。( a m 丘( a ) ) l ( ( a ) e ( 内) 窆s ；。( ( a ) ) t = l 设口= ts i t 0 ) ，因为( ( a ) ) 0 ，所以口非空， 所以 ，f 、s i 。r t ( a m ( a ) ) 篆等2 器s i e ( f i ( a ) ) 。( ( a ) ) ( 3 2 1 ) ( 3 2 2 ) m a x ! 垒：叁! 型2 m a x 墨! 竺垦! 箜2 ：m a x 圣! 竺蔓! 箜2 ( 3 2 3 ) t e a ( 鸽( a ) )塔话n ( 鸽( a ) ) t r i ( 鸽( a ) ) 、7 第三章用行和比与列和比估计谱半径 所以 同理可得 所以 m 篆r i ( 等鲕篆等 ( 3 2 4 ) t ( 匈) t ( 丘( 砷) 、7 叫n 丛r i ( f i 等( 叩篆等 ( 3 2 5 ) t a ) ) t l ( ( 匈) 、7 m i n r i ( a m f 2 ( a ) ) m i n 圣! 垒! 垒2 m a ) 【墨! 竺! 垒2 m a x 垦! 竺垒! 箜2 t r i ( ( a ) ) t l ( f i ( a ) ) i 巧( ( 内) i r i ( ( a ) ) 根据以上的定理可以得到如下的推论 推论3 2 设a 是n 阶非负矩阵，若存在正整数k ，使得 r i ( a k ) 0 ( i = 1 ，2 ，n ) ， 则 叩鬻纠内m a x 鬻， 若存在正整数k ，使得 e i ( a k ) 0 ( i = l ，2 ，n ) ， 则 叩糟纠钧m a x 鬻 推论3 3 设a 是n 阶非负矩阵，i 为n 阶单位矩阵b = i + a ， 则对于任何正整数k ，有 叩鬻r ib 刑砷m 鬻r i ， ( 。) 、7 i ( b 。) 叩鬻c i 纠a ) m a x 等c ib ( b 。) 一7i ( 。) ( 3 2 6 ) ( 3 2 7 ) ( 3 2 8 ) ( 3 2 9 ) 推论3 4 设a 是n 阶非负矩阵，i 为n 阶单位矩阵c = n i + a ) ，若存在正整 数k 使得 1 2 第三章用行和比与列和比估计谱半径 则 则 e ( c 。) 0 ，q ( c 。) 0 ，( i - l ，2 ，n ) ， 叩鬻刑砷m p 鬻， ( 3 3 0 ) 叩鬻纠a ) m 觜 ( 3 1 3 ) 推论3 5 设a 是n 阶非负矩阵，若存在正整数k ，使得 ( a ! ) o ，c i ( a ? ) 0 ，( i = l ，2 ，n ) ， ( 叩糟) l m 因为p ( 砷是未知的，所以a 的最大行和所在的行并不一定能使得p ( a n 岱】) 也 是最大行和。把p i 看成是尸( 的函数， 则 旧飞1 4a u - r ( a ) - ， 所以p i 是p ( 匈的增函数。 解i 1 个不等式 删钳臀， 或者 尸( 砷2 一( a 址+ t a j k ) 夕( a ) + r j a l d 【一a i k r ( a ) 0 ，( 4 2 9 ) 设 b = a i k i a k k , c i2 a 奴一a i k r ( a ) ， 则所有解区间的上界d 尸( a ) = d - ( 4 3 。) d 保证了夕( a ) 的估计是由p ( a a 【口】) 的最大行和得来的 类似的，可以得到一个较好的下界。 定理4 2 3 【2 2 】设a 是一个n 阶非负不可约矩阵，谱半径为p ( a ) 。如果第k 第四章几种算法的比较 行是最大行和，设甜= k ，则p ( n 口】) 的最小行和大于等于a 的最小行和， 即 r ( a ) r ( p ( n 口】) ) 夕( p ( n 盯】) ) = 户( 内 ( 4 3 1 ) 因此，可以得到一个较大的最小行和。 算法1 ： 1 计算所有的行和r i ( 砷，置 r ( 绚= 吧i n r i ( a ) 。设y = li t , = r ( a ) ) ，l ( n ) ，d = 一 ( 4 3 2 ) 2 从y 中取出一个元素并赋值给k ，然后把这个元素从y 中删除。设 i t = k ) ，声= ( n ) 口。 3 设 b = a 址+ t a i k , c i = a 址一a i k r ( 砷， d = m i n 学坠学，d ) ( 4 3 3 ) l e 口， 4 如果y 非空，转第2 步，否则d 即所要求的上界。 算法2 ： 1 计算所有的行和( 砷，置 r ( 内= m a x r i ( a ) ， 设 y = lq = r ( a ) ) ，l ( n ) ，d = o ( 4 3 4 ) 2 从y 中取出一个元素并赋值给k ，然后把这个元素从y 中删除。设 口= k ) ，f l = ( n ) c r 。 3 设b = a k k + - a i k ，c i = r i a r , x a i k r ( 砷， 唑掣b i , + f i b 乒：- 4 c i ，d ) ( 4 3 5 ) 4 如果y 非空，转第2 步，否则d 即所要求的下界。 2 l 第四章几种算法的比较 4 3 算法的比较 例1 用m a t l a b 随机生成一个3 0 0 0 阶的矩阵( 矩阵的元素大于等于0 小于等 于5 ) ，最大特征值为18 2 3 5 4 7 2 。 表4 1 根据定理 下界的估计值上界的估计值运算时间( s ) f r o b e n i u s 定理 13 6 2 5 8 4 3 2 6 3 4 9 4 5 2 8 5 2 推论3 3 ，k = l 15 6 3 4 7 7 5 2 1 6 5 4 7 5 6 1 2 3 9 推论3 3 ，k = 21 7 5 6 3 2 1 719 6 2 3 4 7 21 8 5 3 推论3 3 ，k = 3 1 8 2 1 3 6 7 2l8 2 6 4 3 8 52 7 8 5 h m i n c 定理 14 2 6 3 7 9 5 2 3 5 7 4 9 6 29 2 7 b r a u e r 定理16 5 3 2 7 5 82 4 5 3 7 8 6 l1 2 3 2 l e d e r m a n n 定理 l7 5 3 9 4 3 52 3 6 4 9 2 5 31 3 2 6 o s t r o w s k i 定理 1 8 1 6 3 4 7 22 13 5 3 6 7 l 1 3 7 5 分块方法 1 8 1 5 6 2 4 318 3 5 4 2 3 82 3 5 4 p e r r o n 余方法 1 7 5 3 1 2 9 518 7 5 3 9 4 21 5 3 6 例2 用m a t l a b 随机生成一个3 6 0 0 阶的元素服从o 一1 平均分布的矩阵，最大 特征值为2 8 5 2 2 9 3 4 。 表4 2 根据定理下界的估计值上界的估计值 运算时间( s ) f r o b e n i u s 定理 16 7 5 3 6 9 53 5 6 7 3 9 4 2 9 2 6 推论3 3 ，k = l 2 6 3 5 3 6 9 22 9 3 5 6 3 9 21 6 3 4 推论3 3 ，k = 2 2 8 3 2 5 7 4 62 8 5 8 3 6 2 72 3 7 6 推论3 3 。k = 3 2 8 5 1 3 6 7 22 8 5 3 3 6 9 43 9 7 6 h m i n c 定理 18 6 7 3 2 8 231 2 5 6 9 2 49 5 3 b r a u e r 定理 17 2 6 3 9 4 5 2 8 6 5 3 6 7 21 0 2 6 l e d e r m a n n 定理18 6 5 3 9 6 42 6 8 2 9 5 1 61 2 5 2 o s t r o w s k i 定理 19 2 5 3 6 7 22 4 5 3 9 7 5 61 3 8 5 分块方法 2 8 2 7 3 6 9 2 2 8 6 4 39 4 21 8 5 7 p e r r o n 余方法 2 1 6 2 1 4 5 63 2 6 9 4 5 7 29 7 5 第四章几种算法的比较 例3 取一个工程上产生的一个6 0 0 0 阶的非负矩阵，最大特征值为6 4 5 7 8 2 。 表4 3 根据定理下界的估计值上界的估计值运算时间( s ) f r o b e n i u s 定理 2 6 3 4 1 6 9 3 6 5 2 4 2 3 5 2 推论3 3 ，k = l5 3 6 2 9 47 5 3 6 8 53 5 9 2 推论3 3 ，k = 2 6 2 6 3 5 26 7 8 6 3 55 3 5 4 推论3 3 ，k = 36 3 9 7 5 46 5 3 7 1 66 5 3 l h m i n c 定理3 2 5 6 9 39 1 4 2 3 72 6 3 4 b r a u e r 定理 3 6 8 4 5 18 6 3 2 5 82 8 6 4 l e d e r m a n n 定理4 2 5 3 9 1 7 2 3 6 9 4 2 9 2 5 o s t r o w s k i 定理4 6 5 3 2 l6 5 3 2 7 62 9 8 7 分块方法6 1 3 2 4 56 8 7 5 6 24 6 5 3 p e l l r o n 余方法5 8 6 2 7 37 2 3 2 4 92 7 9 2 可以看出，通过矩阵的行和和列和比来估计非负矩阵的谱半径精确度还是很 高的，但是所需要的运算量比4 1 和4 2 中的大。因此，研究精确度高运算量小 的估计方法是很有必要的。 参考文献 参考文献 【1 】戴华。矩阵论。北京：科学出版社2 0 0 1 8 ，2 8 3 6 【2 】p e r r o no z u rt h e o r i ed e ru b e rm a t r i z e n 【j 】m a t h a r m , 1 9 0 7 ，6 4 ：2 4 8 - 2 6 3 【3 】r o t h b i u muga l g e b r a i ce i g e n s p a c e so fn o u n e g a t i v em a t r i c e s l i n e a na l g e b r aa p p l 19 7 5 ( 1 2 ) ，2 8 1 2 9 2 【4 】黄廷祝，杨川胜。特殊矩阵分析与应用。北京：科学出版社2 0 0 7 ，2 6 5 2 【5 】陈公宁。矩阵理论与应用。北京：科学出版社2 0 0 7 ，6 2 8 3 【6 】蔡大用。数值代数。北京：清华大学出版社1 9 8 7 ，2 7 - 4 3 【7 】7w i e l a n d t u n z e r l e g b a r e , n i c h en e g a t i v em a t r i c e s 【j 】m a t h0 , 5 2 ：6 4 2 - 6 4 8 【8 】d c a o b o u n d s o n e i g e n v a l u e s a n dc h r o m a t i c n u m b e r 【】l i n e a ra l g e b r a a p p l ，1 9 9 8 ，2 7 0 ：1 - 1 3 【9 】h m i n e n o n n a t i v em a t r i c e s w i l e y , n e w y b r k ，1 9 9 8 ，1 1 1 8 ，2 1 3 6 【10 j r a b r u a l d ia n dh j r y s e r c o m b i n a t o r i a lm a t r i xt h e o r y 【嗍，c a m b r i d g eu n i v e r s i t y p r e s s , n e wy o r k , 19 91 ，5 3 7 8 【1l 】w l e d e r r n a n n b o u n d sf o rt h eg r e a t e s tl a t e n tr o o to fap o s i t i v em a t r i x j l o n d o nm a t h s o c 19 5 0 1 1 5 ：2 6 5 2 6 8 12 1a o s t r o w s k i b o u n d sf o rt h eg r e a t e s tl a t e n tr o o to fap o s i t i v em a t r i x j l o n d o nm a t h s o c 1 9 5 2 ，2 7 ：2 5 3 2 5 6 1 3 】a b r a u e r t h et h e o r e m so f l e d e m a n na n do s t r o w s k io np o s i t i v em a t r i c e s ，d u k em a t h j 1 9 5 7 2 4 ：2 6 5 2 7 4 【1 4 】卢琳章，马飞。非负矩阵p e w o n 根的上下界。计算数学，2 0 0 2 ，2 5 ( 2 ) ：1 9 3 1 9 8 【1 5 】殷剑宏。非负矩阵最大特征值的新界值【j 】。数值计算与计算机应用，2 0 0 2 ，2 3 ：2 8 2 2