（计算数学专业论文）对称不定线性方程组bbk与bfp算法的松驰形式及特殊矩阵分析.pdf

摘要 矩阵计算和特殊矩阵分析在计算数学、数学物理、经济学物理学、生物学等 领域都有着广泛的应用本文对于对称不定矩阵楚列斯基分解过程中选主元策略， 非负矩阵的谱半径( 即p e r r o n 根问题) 和三对角矩阵逆元素的估计等重要问题进 行了分析和研究 首先针对对称不定线性方程组a x = b 求解的问题，讨论了b b k 算法和f b p 算法的松弛形式，即所谓的r b b k 和r f b p 算法这两种算法采用了比较灵活的 选主元策略，既能够较快的找出主元，又能够使得l d l r 分解中的l i l i i 。有界 其次根据三对角矩阵的特性，利用其逆矩阵可以分解成两个很特殊矩阵的乘 积，从个新的角度讨论了三对角矩阵逆矩阵元素的估计在本章最后给出了一种 算法实现了三对角矩阵逆矩阵的简便计算 最后给出了非负不可约矩阵谱半径上、下界的一种新的、简便的估计方法，在 结尾给出的数值例子显示了这种估计方法有非常好的效果 关键词；对称不定矩阵，l d 驴分解，三对角矩阵，非负不可约矩阵，p e r r o n 根 a b s t r a c t m a t r i xc o m p u t a t i o n sa n ds p e c i a lm a t r i xa n a l y s i sh a v ew i d ea p p l i c a t i o n si nc o l n - p a t a t i o n a lm a t h e m a t i c s ，m a t h e m a t i cp h y s i c s ，e c o n o m i c s ，p h y s i c s ，b i o l o g ya n d e t c t h i st h e s i ss t u d i e st h ep i v o t i n gs t r a t e g i e so fc h o l e s k yf a c t o r i z a t i o nf o rs y m m e t r i c i n d e f i n i t em a t r i c e s ，t h ee s t i m a t i o no fs p e c t r a lr a d i u sf o rn o n n e g a t i v ei r r e d u c i b l em a - t r i c e sa n dt h ee s t i m a t i o nf o rt h ee l e m e n t so ft h ei n v e r s eo ft h et r i d i a g o n a lm a t r i c e s f i r s t l y , w ed i s c u s st h er e l a x e df o r m so ft h eb b ka l g o r i t h ma n dt h ef b pa l - g o r i t h mf o rs o l v i n gt h es y m m e t r i ci n d e f i n i t es y s t e m sw i t hl i n e a re q u a t i o n sd i r e c t l y a n ds t a b l y t h e s et w oa l g o r i t h m sa d o p tf l e x i b l ep i v o ts l e c t i n gs t r a t e g y , w h i c hc a n f i n dap i v o tf a s ta n dm a k eil l l l b o u n d e di nt h e 工d 矿f a c t o r i z a t i o n s e c o n d l y , b a s e d o i lt h ef a c tt h a tat r i d i a g o n a lm a t r i xc a nb ef a c t o r i z e da st w o s p e c i a lm a t r i c e s ，w ed i s c u s st h e e s t i m a t i o nf o rt h ei n v e r s eo ft h et r i d i a g o n a lm a t r i c e s i nc h a p t e rt h r e e a n dw ep r o p o s ean e wm e t h o dt oe s t i m a t et h ee l e m e n t se f f i c i e n t l y f i n a l l y , a n e wm e t h o df o re s i t m a t i n gt h eu p p e ra n dl o w e rb o u n d sf o rt h es p e c - t r a lr a d i u so fan o n n e g a t i v em a t r i xi sp r o p o s e d t h ep r e s e n t e dn u m e r i c a le x a m p l e s s h o wt h ee f f e c t i v e n e s so ft h i sm e t h o d k e y w o r d s ：s y m m e t r i ci n d e f i n i t em a t r i x ，l d l tf a c t o r i z a t i o n ，t r i d i a g o n a lm a t r i x ， n o n n e g a t i v ei r r e d u c i b l em a t r i x ，p e r r o nr o o t i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：勿乜之 日期：弘咯，2 月忉日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：址导师签名：三兰池 日期：矽刁莎年j 乙月沙日 第一章绪论 1 1 引言 第一章绪论 矩阵是现代数学的个基本概念，用矩阵的理论和方法来处理复杂问题时形式 相对简洁，面对问题的刻画又相当深刻，因此矩阵成为科研领域不可缺少的数学工 具特殊矩阵在矩阵分析和矩阵计算中占有十分重要的地位，因为在实际中得到的 矩阵总会有这样或那样的特殊性质，对特殊矩阵的研究所取得任何实质性的进展， 都将会对计算数学乃至社会生产力的发展起着重要的推动作用因此，近年来，对 特殊矩阵的研究是国内外矩阵研究十分活跃和成果卓著的领域【1 ，2 ，3 】本文涉及 列三类特殊矩阵s 对称不定矩阵，三对角矩阵和非负不可约矩阵这三类矩阵问题 的来源相当丰富，在数学，经济学，生物学，现代物理学中的很多问题，尤其在近 似求解偏微分方程时都会涉及或归结为特殊矩阵分析和计算 矩阵计算的三类基本问题是【4 】： ( 1 ) 求解线性方程组，即给定t l 阶非奇异方阵a 和n 维向量b ，求一个竹维向 量茹使得 a x = 6 ： ( 2 ) 求解超定方程组的最小二乘解，即给定m n 矩阵a c m 和m 维向 量6 求n 维向量。使得 l l 血一6 0 2 = r a i n l i a r b l l = ：t ，r “) ( 3 ) 计算一个矩阵的特征值和特征向量，即给定一个方阵a ，求它的全部或部 分特征值，或者相应的特征向量 本文在第二章研究对称不定线性方程组求解问题，属于基本同题的第一类；第 _ - - t t 研究三对角矩阵逆元素估计的问题，这也属于基本问题的第一类；第四章研究 非负不可约矩阵谱半径估计的问题，这属于第三类基本问题 1 2 线性方程组求解 本节简述线性方程组求解的历史和现状，以便引出我们将要进行的对对称不定 1 电子科技大学硕士学位论文 线性方程组研究线性方程组求解分为两种方法；一是直接法，一是迭代法直接 法以g a i l s 8 清元为基础，其运算量稳定( 伊) ，但是数值较差【3 ，4 ，5 1 ，且当矩阵阶数 增加时，需要的运算量快速增长，矩阵的稀疏性也不能保持尽管如此，直接法对 中小型稠密线性方程组还是相当适用迭代法是现代数值代数研究的焦点之一陆 l o 】，主要有两类方法，一类是以对系数矩阵a 的有效分裂为基础，如经典的j a c o b i ， g a u a s - s i d e l ，s o r 等迭代法；一类是上世纪5 0 年代发展起来的k r y l o v 子空间方 法，如c g 方法，g m r e s 方法f 1 1 ，b i c g s t a b 方法等 迭代法在实际科学计算中的使用已相当普遍，但是随着问题规模和难度的加 大，很多问题仅用迭代法已经难以有效求解，于是预条件技术随之发展起来f 3 ，4 ， 8 ，1 2 1 所谓预条件。即是在线性方程组的两边同时乘上可逆矩阵p ，使原始问题变 为 p a x = p b ； 或者矩阵a 右乘可逆矩阵p ，原始问题变为 a p g = b ， 然后通过。= p 求出原方程组的解，这就分别是左右预条件 常用的预条件技术有s s o r 预条件，不完全分解方法( i c ，m v ) 1 3 ，稀疏近似 逆方法( m r ，a i n v ) 等等【1 4 - 1 9 在目前的研究成果看来，以不完全分解方法最 为有效，这类方法可以看作是直接法与迭代法的有效结合，因为不完全分解也是以 g a u s s 消元为基础，采用了不同的稀疏模式 改善直接法的数值稳定性的主要手段是选择合适的主元【3 】，对一般的矩阵列 选主元法就能有效的控制数值不稳定问题，但是对对称矩阵，为了保持矩阵的对称 性，需要采用对称选主元方法【3 ，2 0 ，2 1 ，2 2 】本文采用直接法求解对称不定线性 方程组，但是我们相信就象不完全分解预条件一样，好的直接法会对预条件有所贡 献 1 9 7 1 年a a s s e n 提出了一种稳定的方法( a a s s e n 算法) ，它进行如下分解f 2 3 】： p a p t = l t l t 其中l = ( b ) 是单位下三角阵，r 是三对角阵 p 是能使i 幻i 1 的置换阵 与此相对应， b l l n c h 和p l e t t 也在同年提出了对角选主元法( b l l n c h p a r l e t t 算 法) 【2 2 】，计算置换阵p 使得 p a p t = l d l t ， 2 第一章绪论 其中d 是由1 1 和2 2 的块构成的块对角矩阵同样，p 的选取使得下三角阵 工的元素满足i 1 两种分解方法都需要了n a 个浮点运算c n o p ) 分解完成后， 则可以在o ( n 2 ) 的工作量内求解出勘= 6 ： p a = 疆p 1l z = p b 。t w = z 。p v = ，：p y ； p a p r = l d l t ，l z = p b ，d w = z ，l t y = ，z = p y 这里以b u n c h - p a x l e t t 算法为例来说明其选主元过程假定 懈：( 善署) n 二。 其中p 1 是置换阵且s = 1 或2 如果a 是非零的，则总可以挑选这些量使e 非奇 异，从而我们可以写成 懈= ( g 刍。0 。) ( 言b 一品咿) ( oz ) 考虑到稳定性，s s 的主元e 应使得 = ( 的) = b c e - 1 中的元素翰被适当限界为此，设n ( 0 ，1 ) 已给定，定义z ，幻= m a 取j ( 1 8 巧1 ) ， 1 = m a x d l o h d ) b u n c h - p a r l e t t 选主元的方案如下： i f p l a z o 选取只使得i e l i = p l i 选取马使得i e 2 1 = 脚i 很容易验证，在此选主元方案下， i 嘞i 得到了有效的控制( 以上对a a s s e n 和b u n c h - p a r l e t t 等人工作的总结在文献【3 】中也有叙述) 但同时。我们也发现，该 电子科技大学硕士学位论文 选主元方案需要每步搜索整个矩阵，总共的比较量为d ( 舻) 在此基础上， b u n c h 和k a u f m a n 于1 9 7 7 年提出了b u n c h - k a u f m a n 算法【2 0 ，2 4 】，解决了比较过多的问 题但同时该算法不能有效控制忙| l 的界【2 0 】 为了解决b u n c h - k a u f m a n 算法中无界的问题，以及b u n c h - p a r l e t t 算法需要比 较次数太多的问题，a s h c r a f t ，g r i m e s ，和l e w i l 8 等人提出了有界b u n c h - k a u f m a n 算法( b b k ) 和快速b u n c h - p a r l e t t 算法( f b p ) 2 0 他们采用个聪明的折衷，即 寻找”局部最大”元素，有关详细情形请参阅文献【2 0 对大部分矩阵矩阵这两种 算法( b b k 和f b p ) 都能用较少的比较找到合适的主元，但是对某些矩阵，却需要 搜索整个矩阵才能找到主元，因此本文的目的之一就是改进b b k 和f b p 算法， 使之能有更广的适用范围 1 3 三对角矩阵逆元素的估计 兰对角矩阵在科学计算和矩阵理论中占有重要地位，比如在偏微分方程数值求 解和三次样条插值中都会涉及到三对角矩阵或块三对角矩阵，以及在其他很多科 学计算的中间过程会涉及到三对角矩阵的求解或其逆元素的估计鉴于三对角矩阵 的重要性，近年来对三对角矩阵快速求逆及对其逆元素的估计成为数值线性代数领 域的一个研究热点有很多学者在该研究课题上作出了相当出色的工作，比如文献 【2 5 - 3 0 在本文中我们假设三对角矩阵表示为 霸= t r i d i a g ( 如，如，c i ) = 6 l o l 0 凸1 6 2c 2 0 d 2b 3 000 000 0 0 0 一1 k n a b b e n 等人研究了对角占优的三对角矩阵逆元素的估计问题，得到了很优美 4 。 h 第一章绪论 的结论【2 5 】，我们在这里给出一部分他们的结论如果记 t ( i j ) ； kc 啦屯+ 1c + l 哟一2b 一1 叼一1 表示矩阵矗从第i 行到j 行，i 列到j 列的子矩阵 引理1 1n 阶三对角矩阵瓦= t r i d i a g ( a h ，6 ，q ) ，其伴随矩阵的元素可表示为： i ( 一1 ) 、j j - 1a k ) d e t t ( 1 ，i 。) d e t t ( j 1 神，i j 1 巧一1 ( 一1 ) i + j 1 j - ：1 钒) d e t t ( 1 j 一1 ) d e t t ( 一1 ) ，i j 其中d e f t ( 1 , 0 ) = 1 ，d e t t ( + 1 , n ) = 1 ，兀i 。+ l = 1 引理1 2 若a = ( ) 。是严格行对角占优矩阵，并且肫= 老朵l j 弗i 叼l ， i = 1 ，2 ，仇对a 的逆矩阵a _ 1 = 貉，有下式成立； 赢l 彘i 赢，i a , ，i j ； 定理1 3 给出了n a b b e n 的主要结论【2 5 】，该结论表示的逆元素的界比较简洁， 但是只对对角占优矩阵有效冉瑞生，黄廷祝等人【2 9 ，3 0 】研究了块三对角矩阵逆 的些性质在本文第三章，我们研究一般三对角矩阵逆元素的估计问题，得到了 其逆元素上下边界的种表达式 1 4 非负矩阵p e r r o n 根的估计 非负矩阵在经济数学，组合数学和控制论等领域有着广泛的应用【3 1 ，3 2 】，近年 来对非负矩阵的研究已成为矩阵理论中最活跃的领域之一尤其是对非负矩阵谱半 径的估计( p e r r o n 根问题) ，有众多学者致力于解决如何加快p e r r o n 根的计算速度 和提高其估计精度，3 4 ，3 5 】 5 蒸 电子科技大学硕士学位论文 设a = ( a i j ) “，记a 20 ，如果所有0 ，表示a 为非负矩阵我们首 先给出著名的f r o b e n i u s 定理，然后给出p e r r o n 补的定义 3 6 】，随即给出卢琳樟等 人在p e r r o n 的基础上得出的谱半径估计 定理1 4 f r o b e n i u s 3 2 设a c ”，a 20 ，则 m i n l i g 器1 p ( a ) m a x l _ i n 善1 ， m i n l s n 乏銎l p ( a ) m e , x l p ( a ) i ，p 【0 1 ) t n ， 那么 r f m ( p c ( a ，a 陋】) ) r m m ( a ) 其中r i ( a ) 表示a 第j 行的行和 本文第四章，我们讨论了另一种估计非负不可约矩阵谱半径的简单方法，并给 出数值例子验证了方法的有效性 7 电子科技大学硕士学位论文 第二章对称不定线性方程组b b k 和f b p 算法的松弛形式 2 1 引言 当a 是对称不定矩阵时，解a x = b 有三种著名的方法，他们是， a a s e n 算法【2 3 l ，b u n c h - k a u f m a n 算法【2 4 】和b u n c h - p a r l e t t 算法【2 2 】最近a s h c r a f t ， g r i m e s 和l e w i s 在文献【2 0 】中发展了有界的b u n c h - k a u f m a n 算法( b b k ) 和快速 b u n c h - p a r l e t t 算法( ，b p ) ，这两种方法都表现出了很强的竞争力 a a s e n 算法将a 分解为p a p t = 工t ，其中p 是一个置换矩阵，l 为单位下 三角矩阵，而t 为对称三对角矩阵然而，另外两种方法将a 分解为p a p 7 = l d l r ， 其中d 为块对角阵，其块的阶数为1 或2 我们的方法基于l d 三t 分解我们这 里先简要介绍一下b u n c h - k a u f m a n ，b u n c h - p a x l e t t ，b b k 和f b p 算法，然后很 自然地给出我们的算法 这些算法的不同点在于它们采用不同的选主元策略。因为如果不选主元。那么 l d 驴分解极可能发生主元为0 的情况b u n c h - p a r l e t t 从整个矩阵中选取主元，这 样能够得到一个向后稳定的分解，而且i t l l l o o 也是有界的但是人们在采用这个算法 时显得很犹豫，因为该算法需要太多的比较( 总共有o ( n 3 ) 次比较) b u n c h - k a u f m a n 仅从矩阵的两列中选择主元，这样总共就只需要d ( 舻) 次比较但是根据【2 0 】中的 论述，该算法却不能保证因子工中的元素时有界的b b k 和f b p 算法采取了一 个聪明的折衷办法，仅在第r 行和第i 列选取个局部的最大非对角元素 a s h c r a f t ，g r i m e s 和l e w i s 2 0 】发现在实际应用中。找到这样一个局部最大的 非对角元b b k 通常需要远远不到o ( n 2 ) 次比较他们对随机矩阵所作的测试表明 平均每找到一个主元所需要的比较次数不到2 5 n 次然而，快速b u n c h - p a r l e t t 比 b b k 算法要稍微慢些，因为该算法需要先找到对角线上的最大元，这就要更多的 列交换操作根据a s h c r a f t ，g r i m e sa n dl e w i s 的讨论，当考虑块分解时，分块的 f b p 算法和分块的b b k 算法相比，在整体上需要更少的工作量 他们也研究了b b k 和f b p 算法遇到的最坏情况，在本章中，我们采取放宽 主元选取条件的办法使之在任何情况下都能很快找到主元 8 第二章对称不定线性方程组b b k 和f b p 算法的松弛形式 2 2 有界b u n c h - k a u f m a n 算法的松弛形式 为了使l l l 0 有界同时又加快主元选取的过程，我们这里搜索局部几乎最大的非 对角元素而不是最大元素给定两个参数a 和卢，其中口 0 且0 卢1 ，下面 的算法描述了主元选取的过程我们用r b b k 来表示松弛的有界b u n c h - k a u f m a n 算法 r b b k 算法：( 该算法给出了选取第个主元的过程) m = 第一列非对角元的绝对值最大值； r = 第一列中第个绝对值最大元的行标； i f 仇= 0 不需要对第一列作任何操作； e l s e i fi a l l l 凹l 用o l l 作为主元；8 = 1 ；p = ，； f l a g = o ；i = 1 ；饥= m ； w h i l e ( n a g = 0 ) 7 r = 第r 列的绝对值最大值； r = 第r 列中第个绝对值最大元的行标； i f i o 什1 2 a 1 ； 用d r ，作为主元；s = l ；f l a g = l ； p 交换第行和第r 行； e l s e i f * 肌 用 ：a r t 作为主元；s = 。；f l a g = t ； p 交换第一行与第i 行，以及第二行与第r 行； = “乍= 7 r ； 说明1 如果a 可逆，则不会产生不可逆的主元( 1 1 主元时为0 ，或者2 2 电子科技大学硕士学位论文 时f 。“f 不可逆) 否则l d l t 分解中的d 将有不可逆的块，这会表明a 不 【j 可逆 说明2 当卢= 1 时，该算法退化为b b k 算法 这里，我们来分析随着小阶数的降低，r b b k 算法是如何有界的a s h c r a f t ， g r i m e s 和l e w i s 【2 0 】非常仔细地研究了b u n c h - k a u m a n 选主元策略的界，本章我 们用类似的分析方法得到r b b k 中产生的因子l 的界，用口和的函数来表示 在l d l t 分解的一个典型步骤中，消去第1 列后，如果主元是1 1 的， 那么我们处理的矩阵从a ( k ) 变成a ( + ”，如果主元为2 2 的则变成a ( + 2 ) 令肛 为矩阵a ( k ) 中的绝对值最大值，为低阶矩阵中1 ) 或a ( + 2 ) ) 的绝对值最 大值 第一种情况首先我们考虑a 忙) 第r 列的1 1 的主元口，。用幻表示三角 矩阵的元素那么有 诺+ 1 ) - 一訾，t r j n r b b k 保证了在p 的基础上不会有很大的增加 i 砖is + l 忑a l r _ a r i l b i + i 考 ， 那么，我们有 p + * 南 p ( + a l o r r i 口 同时 啦+ 1 = ：0 4 _ l r ， r 很明显，l 第r 列的元素有如下界， 妒1 l 五1 ，i r 第二种情况考虑2 2 的主元1 f ，经过消元步骤，我们得到 i l 芍= n 妇一 m ，t 铂，r ：芝 一1 ：】 = 啦，j 一曼堡生堡生二兰生粤耋尝王兰罢笋里尘二地，蟊n j t r 啦i 一略 。 第二章对称不定线性方程组b b k 和f b p 算法的松弛形式 如果产生的是个2x2 的主元，我们有下列等式与不等式。i i = m ，i l o m ，i n ”i d 佛且* 学在此基础上，可以得到 l 讲l 蚓+ i 业堕型絮等随i l + 业杀鸟铲 以及 ， 弘( 1 + 型- a 2 、； 现在考虑己中新产生的元素饥a n d “，其中，l ，r ： 【。t 缸， = 啦，t 北 工的元素显式表示为 f i ，i 。a , i a r r - - a r r i 0 4 , ，i t ，n “= 篙等皆，一扎r ， 很容易可以得到其界为： 陌托措 业7 7 - - a 2 7 i 7 , 端= 冈a + l ， 掣 鬻 噬丝篮丝：上生 3 飞盯j 刀万2 万虿 ( 这里，我们假设约减过程发生在行交换之前) 说明3 如果舻 卢s1 ，那么加在l i l l i 以及约减矩阵中的元素将会比较紧 2 3 快速b u n c h - p a r l e t t 算法的松弛形式 f b p 算法选主元策略的目标还是搜索局部非对角绝对值最大元，也就是寻找 使之是第r 行和第t 列的绝对值最大元但是该方法需要首先找到所有对角元 1 1 电子科技大学硕士学位论文 中的绝对值最大值该方法的松弛形式也象r b b k 算法一样是搜索几乎局部最大 值这里我们用r f b p 来表示船p 的松弛版本给定两个参数a 和卢，将r f b p 算法作如下描述 r b b k 算法：( 该算法给出了选取第一个主元的过程) = a ( k ) 对角线上绝对值最大元； = 第8 列非对角元绝对值最大值i f f = 0 不需要对第s 列进行任何操作； e l s e i f l o 。i 口 用口。作为1 1 的主元； = 8 ；m = ；f l a g = o ； w h i l e ( f l a g = o ) r = 第i 列第一个非对角绝对值最大元的行标； * = 第r 列的非对角绝对值最大值； i f 乍所 使用 ：a m r r t 作为z z 的主元； i = r m = i ； 说明当p = 1 时，该算法就变成了f b p 算法 当个对角元的绝对值大于它所在列最大元的个比例时就得到个1 1 的 主元而如果是第i 列中的最大元，又大于第r 列最大元的一个比例时就产生 一个2x2 的主元 对| 上圳的界以及约减矩阵中元素的增长的分析与对r b b k 算法的分析类似 经过分析我们得到当舻 j 的情况可以类似 的讨论例如，我们想得到i 坛：l 和l 屯j i 的上下界( i l 0 ，也就有 嘲罔， c 刁 第四章非负不可约矩阵谱半径的估计 更进一步 ，r = s u p 住) ( 8 ) 2 0 ，z o 同样有如下事实： j 勿q ，使得7 = 在以上分析的基础上可以得到如下引理 21 墨! ：! 堡! 殳a 是个n n 的非负不可约矩阵，如果6 , q 如式( 6 ) ，( 8 ) 中定 义，z l ，勿是上面提到的向量，那么有j = p ( a ) = ，y ，而施，忽是最1 对应的特征向 量，且有施= 眈2 ， r ， 0 ) 证明 我们仅证明6 = p ( a ) 且z 1 是6 对应的特征向量，引理的另一部分可 以类似地得到 因为a z l 疋，z l = 6 z l ，我们定义q = 6 z l - a z l ，于是有q 0 下面证明卵= 0 以保证a z l = 蹰 如果町0 ，于是得到 ( j + a ) “一1 叩= 6 ( j + a ) “一1 忽一( i + a ) “a z l 令z = ( j + a ) ”一1 施，因为( ，+ a ) ”一1 0 所以5 z a z 0 ，且z 0 也就是说存在扩，使得 扩 0 ) 成 立证毕 由上述讨论，我们很自然得到定理4 2 定理4 2 【3 7 】如果a 为个汀n 非负不可约矩阵，铷印，。 0 ，疋和 如式( 3 ) 和( 7 ) 中定义，我们有如下不等式； p ( 舢s 以( 9 ) 如果$ = ( 1 ，1 ，1 ) 7 ，( 9 ) 就变成了下面形式f 3 4 j ： r p ( a ) r 2 3 电子科技大学硕士学位论文 如何寻找z 使得在式( 9 ) 中的界更紧是这个方法的关键所在 定理4 3 如果4 是一个竹x n 的非负不可约矩阵，矿如式( 1 ) 中定义，那么 有下面不等式； r s p ( a ) 瓦- r ( 1 0 ) 等号成立当且仅当两个等号同时成立 证明首先，我们阐述为什么要选择矿 如果$ 是p ( a ) 对应的特征向量，那么= “a ) = 以一定成立因此我们就 要找个向量食指接近g 令 1 1 = m i n j l 茁j ，k ) ，如= r a i n j l x j z ，k n ， 由特征值的定义，一定有如下式子成立。 nn 啦i j = p ( a ) 。讪a 屯j x i = p ( a ) z b j = lj = 1 更进一步，我们有。 nn q 。j p ( a ) 瓤。，a i 玎z 。s p ( a ) 瓤， 因为r p ( a ) r ，所以可以说如果n 越大戤也就越大矿接近是很有希望 的 对任何i n 有， 墨竺：竺! 堕墨! 堕：堕墨 空：， z ：一霹 也就是r 同样也有瓦r 很容易证明等号成立当且仅当两个等号同时成立证毕 因为p ( a ) = p ( 月) ，我们可以对 t 进行类似讨论，于是得到下面的定理 定理4 4 如果a ，加，r ，冗如前面讨论中定义，这里定义 n n、r y = i ，m 2 ，一，) i = 1 = 1 i = 1 第四章非负不可约矩阵谱半径的估计 于是有下面的估计 碡= 呼 挈卜甲 挈) ，= 呼n 薹叼)铲= 乎 耋) ji = 。j m a x r ，1 , t ) m a x f i x ，碍) p ( a ) s m i n 如，碜) m i a r ，舻 ( 1 1 ) 证明简单 估计式( 1 0 ) 和( 1 1 ) 都很容易计算，而且也提高了估计的精度在第三节的例 子中有更多的解释 4 3 数值算例 例1 考虑下面8 8 阶的矩阵【3 3 】 a = 8 6 0 7 12 2 8 2 4 41 31 01 3 5 3 8 61 4 0 6 2 o 4 6 6 1 6 7 o 5 6 3 8 7 7 5 7 8 4 4 5 7 o 71 41 8 7 8 2 5 6 8