（应用数学专业论文）非负矩阵最大特征值的界的估计和算法.pdf

太原理工大学硕士研究生学位论文 非负矩阵最大特征值的界的估计和算法 摘要 非负矩阵谱理论在管理科学、数理经济学中有着广泛的应用。本文主 要在一些谱理论基础上研究非负矩阵的最大特征值的界的估计和算法问 题。主要内容为： 1 、简单介绍一些特殊非负矩阵的基础知识，简要综述了相关的谱理论。 2 、研究非负矩阵最大特征值界的估计，探讨了一些较好的结果，得到 一种新的估计，并证明了这个估计有较好的精度。 3 、提出了求不可约非负矩阵最大特征值的一种迭代算法，并证明了该 算法的收敛性定理和误差估计，最后通过实例说明了其有效性。 关键词：非负矩阵，不可约，最大特征值，界，估计，算法 太原理工大学硕士研究生学位论文 e s t i n 队t i n gt h eb o u n d sa n da l g o i u t h m f o rt 脏n l 气二】卫v 】_ me i g e n v ai ，u 吧 o ft h en o n n e g a t i v em a t i u x a bs t r a c t t h es p e c t r a lt h e o r yo fn o n n e g a t i v em a t r i xi sw i d e l yu s e di nt h ea r e a so f m a n a g e m e n ts c i e n c ea n dm a t h e m a t i c se c o n o m i c s t h i sp a p e ri n v e s t i g a t e st h e e s t i m a t i n g t h eb o u n d sa n d a l g o r i t h m f o rt h em a x i m u m e i g e n v a l u e o f n o n n e g a t i v em a t r i xo nt h e b a s i so fs o m es p e c t r a lt h e o r i e s t h em a i nc o n t e n t sa r e a sf o l l o w s ： 1 、t h eb a s i ck n o w l e d g eo fs o m es p e c i a ln o n n e g a t i v em a t r i c e s a r e i n t r o d u c e ds i m p l y , a n dt h er e l e v a n ts p e c t r a lt h e o r i e sa r es u m m a r i z e d 2 、t h eb o u n d sf o r t h em a x i m u me i g e n v a l u eo ft h en o n n e g a t i v em a t r i xa r e s t u d i e da n ds o m eg o o db o u n d sa r ec o n s i d e r e de s p e c i a l l y an e wb o u n do ft h e m a x i m u m e i g e n v a l u ea r eo b t a i n e d ，w h i c hi sp r o v e d t ob em o r ea c c u r a t e 3 、ai t e r a t em e t h o do ff i n d i n gt h em a x i m u me i g e n v a l u eo fi r r e d u c i b l e n o n n e g a t i v em a t r i x i s p r e s e n t e d ，a n d t h e c o n v e r g e n c et h e o r e ma n d e r r o r e s t i m a t i n go f t h i sa l g o r i t h ma r ep r o v e d a tl a s t ，t w oe x a m p l e sa r eg i v e nt os h o w t h a tt h en e wm e t h o di se f f e c t i v e i i i 太原理工大学硕士研究生学位论文 k e yw o r d s ：n o n n e g a t i v em a t r i x ，i r r e d u c i b l e ，m a x i m u me i g e n v a l u e ，b o u n d ， e s t i m a t i o n ，a l g o r i t h m i v 声明户明 本人郑重声明：所呈交的学位论文，是本人在指导教师的 指导下，独立进行研究所得的成果。队文中已经注明引用的内容 外，本论文不包含其他个人或集体已经发表或撰写过的科研成 果。对本文的研究做出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律现任由本人承担。 论支作者签名：主亟蕴蔓 日期： 泖奄。js 关于学位论文使用权的说明 本人完全了解太原理工大学有关保管、使用学位论文的规 定，其中包括：学校有权保管、并向有关部门送交学位论文的 原件与复印伯件；学校可以采用影印、缩印或其它复制手段复 制并保存学位论文；学校可允许学位论文被查阅或借阅；学 校可以学术交流为目的，复制赠送和交换学位论文；学校可以 公布学位论文的全部或部分内容( 保密学位论文在解密后遵守此 规定) 。 签名：卫正1 习 导师签名： 丕塾叠茎： 篚 热妒? 马is 日期：矽z 太原理工大学硕士研究生学位论文 序言 元素都是非负实数的矩阵称为非负矩阵。这类矩阵在数理经济学、运筹学、概率论、 计算机科学、管理科学、弹性系数的微振动理论等许多领域都有着广泛的应用。在非负 矩阵理论中，对其谱的研究是尤为重要的。特别地，非负矩阵的最大特征值在特征值估 计理论、广义逆矩阵、数值分析以及矩阵序列、矩阵级数的收敛分析、控制理论中都有 着极为重要的作用。所以，有关非负矩阵最大特征值问题则是非负矩阵谱理论的核心问 题之一。本文第一章中以非负矩阵的谱理论为线索简单介绍了一些特殊非负矩阵的基础 知识，第二章侧重非负矩阵最大特征值的估计，第三章则介绍了求不可约非负矩阵最大 特征值的一种迭代算法。 非负矩阵有一些值得注意的谱性质。1 9 0 7 年，p e r r o n 首先发现，任何一个行阶正 矩阵彳的谱半径p ( 彳) 是矩阵彳的特征值。f r o b e n i u s 在1 9 0 8 1 9 1 2 年间把p e r r o n 的结 论推广到非负矩阵特别是不可约非负矩阵的情形，从而使非负矩阵理论得到迅速发展， 然后，通过著名的矩阵论专家b r a u ea ，j o h n s o nc r ，o s t r o w s k ia 等卓有建树的工作， 现在已逐步形成比较完美的理论体系。本文第一章简单介绍了非负矩阵的定义及一些性 质，并以非负矩阵的一些重要谱理论贯穿其中，还对正矩阵、不可约非负矩阵及本原矩 阵这些较重要的非负矩阵作了较详细的引入。这一部分内容为以下各章打下了理论基 础。 第二章主要讨论对非负矩阵彳的最大特征值的界的估计问题。首先通过大量的文献 资料，比较了众多的对非负矩阵最大特征值界的估计的结果，将一些重要的结果罗列出 来。在研究学习文【1 8 和文 1 9 】时发现他们的估计不仅在形式上相对简单，而且精度很 高。这样在这两个结果的启发下，我们又引入一个更一般的矩阵 c = ( a l 彳2 + a 2 彳+ a 3 ，) ”1 ( a 1 ，a 2 ，a 3 是任意的正整数，i 为f i 阶单位矩阵) ，给出并证明 了形式上类似文【1 9 】的结果的一个新的估计，并在理论上证明了这个新估计较文【1 8 】和文 【1 9 】有较好的精确性。 太原理工大学硕士研究生学位论文 第三章主要介绍了求任意一个不可约非负矩阵最大特征值的一种迭代算法。根据矩 阵彳为不可约非负矩阵的充要条件( ，+ 么) ” 0 ( m 为自然数) ，取一个新的矩阵 b = ( j + 彳) ”，通过彳与b 之间的关系，对b 进行一些特殊的运算，进而得到一系列迭代 算法过程，最终可计算得到彳的最大特征值。本文论证了其收敛性，给出了其误差估计， 并通过实例说明了此迭代方法的有效性。 2 太原理工大学硕士研究生学位论文 第一章基础知识弟一早昼佃函大u 以 首先介绍有关定义和符号。设r ”表示实数域灭上所有刀元数组x = ( x 。，x ：，x 。) r 集 合构成的刀维向量空间。足”中元素x 称为n 维向量，实数x 。称为”维向量 x = ( x 。，x ：，x 。) r 的第f 个坐标。r ：表示r 。中坐标非负的玎维向量的集合。衅中的向 量x 称为n 维非负向量，记为x o ，如果非负向量x 的坐标都大于零，则称x 为正向量， 记为x o 。设r 瞰“( c 舭4 ) 表示实数r ( 复数c ) 上所有m x n 矩阵a = ( 口j j ) 。的集合。 如果矩阵a = ( 口 ，) 。的所有元素0 ，则称矩阵a 为非负矩阵，记为a 0 ，非负矩阵 a = ( ) 。中的所有元素 0 ，则称矩阵彳为正矩阵，记为么 0 1 。矩阵a = ( ) 肘。的 n 个特征值丑，允：，九组成的集合称为a 的谱，记为仃( 彳) ，即仃( 彳) = 饥，九，九 。 矩阵彳的玎个特征值的模的最大值称为彳的谱半径，记为p ( 彳) ，即 p ( 4 ) = m a x 轨i ，i 九：| ，i 九i ) ，记= 1 ，2 ，玎) 。 1 1 非负矩阵与正矩阵 定义1 1 1 1 1 设彳= ( 口 ) ，b = ( 6 ) r ”“，如果对所有的f ，都有吒，则记 为a b ；如果对所有的i ，都有口i i b 口，则记为a b 。 对任意矩阵彳= ( 口 ) c 舭“，本章中用h 表示4 的元素取模之后得到的非负矩阵， 即h = ( | 口 ，1 ) ；特别地，当x = ( x 。，x ：，) r c 。时，i 叫= ( i x 。i ，i x ：l ，l x n ) r 。记n 阶矩 阵4 = ( 口) 的k 次幂彳。的( f ，) 位置上的元素为谬，对一般n 阶矩阵，有下列性质 定理1 1 1 t 1 1 设a ，b ，c ，d 均为以阶矩阵，x 是n 维向量，则 ( 1 ) i 纠_ 0 ) ； ( 7 ) 如果a o ，x o 1 丑x 0 ，贝0a x o ； ( 8 ) 如果h b ，则：- 0 ，则 ( 1 ) p ( 彳) 为a 的正特征值，且存在正向量y r “使得a y = p ( 彳) y ； ( 2 ) a 的任何一个其他特征值九，都有 0 ，x 是彳对应于特征值p ( 彳) 的正特征向量，y 是 彳r 对应于特征值j d ( 彳) 的正特征向量，则 觊贴( 彳) ) 1 彳j 【= ( y r x ) x y 需要说明的是，定理1 1 3 的结论对一般的非负矩阵不一定成立。例如：4 阶非负矩 阵 a = 03 3 0 0 o 0 0 0 o 0 o 3 o 0 2 容易计算p ( 彳) = 3 ，并且彳对应于特征值p ( 彳) = 3 的特征向量为j c = ( a ，a ，卢，o ) r ，其中 0 9 ，卢可取正数，而p ( 彳) = 3 不是彳的单特征值，彳没有对应于特征值p ( 彳) = 3 的正特 征向量，并且彳有异于p ( 4 ) 的特征值允= 一3 使得= p ( 4 ) ，但p ( 彳) 仍是a 的特征 值，并且a 有对应于p ( 彳) 的非负特征向量。一般地，有如下结果 定理1 1 5 【2 1 ( 广义p e r r o n 定理) 设a r 咖，如果a 0 ，则p ( 彳) 为么的特征值， 而且其相应的特征向量x 0 。 1 2 不可约非负矩阵 定义1 2 1 设矩阵彳是n 阶矩阵，如果存在一个置换矩阵p r “4 ，使得b = 刚p r ， 则称矩阵彳同步于矩阵b 。 定义1 2 2 1 4 1 设n 阶方阵a 0 ，如果存在一个置换矩阵p r “，使得 剐尸r ：仁c l 0d 其中b 和d 分别为k ，阶方阵，k 1 和，l ，则称彳是可约矩阵；否则称彳是不可约 5 太原理工大学硕士研究生学位论文 矩阵。 由定义知，一阶方阵、正矩阵都是不可约矩阵。以后如没特别说明，我们所说的不 可约矩阵都是非零矩阵。从定义直接可得如下结论 定理1 2 1 【l l 设彳是n 阶矩阵，则 ( 1 ) 彳为不可约矩阵的充要条件是a r 为不可约矩阵。 ( 2 ) 如果彳是不可约非负矩阵，b 是, 阶非负矩阵，则彳+ b 是不可约非负矩 阵。 下面给出一个判断非负矩阵是否可约的办法。 定理1 2 2 t 5 】设n 阶矩阵a 0 ，则4 是不可约矩阵的充要条件是( j + 彳) ”1 o 。 设矩阵彳是不可约非负矩阵，下面利用矩阵彳构造一个函数来研究不可约非负矩阵 的结构性质和谱性质。 记r + 为全体非负实数的集合，h “= 衅一 o 。 定义1 2 3 t 6 】对任意的n 阶不可约非负方阵彳，下列两个从日“到尺的函数 聃) = 吵等 = 搿半一瓴， 几日” 若存在某个f ，使得x i = o 且( 出) i 0 ，则定义g 彳( x ) = 佃，称f ，g 为伴随于彳 的c o l l a t z w i e l a n d t 函数，简称为彳的c w 函数。 c w 函数具有的许多良好性质，被公认为是证明非负矩阵经典理论的好工具，为此， 将c w 函数的有关性质罗列如下。 定理1 2 3 叼设e ( x ) ，g ( x ) 是刀阶不可约非负矩阵彳的c w 函数，则 ( 1 ) 冗( x ) 及g 彳( 工) 都是零次齐次式，且l ( x ) 为有界函数； ( 2 ) 如果p 是满足血一肛0 ，x h “的最大实数，那么p e ( x ) ；如果仃是 满足a x - o x 0 ，x h 。的最小实数，那么仃g 一( x ) ； ( 3 ) 如果x h “，且y = ( ，+ 4 ) ”1 x ，那么巴( y ) 巴( x ) ，g ( y ) g ( x ) ； ( 4 ) l ( x ) s ，g ( x ) f ，其中s 、r 分别为a 的最大、最小列和。 6 太原理工大学硕士研究生学位论文 下面利用c w 函数的性质给出著名的p e r r o n f r o b e n i u s 理论的最基本( 也是最重要) 的结果。 定理1 2 4 【7 】设4 是玎阶不可约非负矩阵，则 ( 1 ) a 有一个正特征值，等于彳的谱半径p ( 么) ： ( 2 ) a 有一个对应于p ( 彳) 的正特征向量。 在许多文献中，将不可约非负矩阵的特征值p ( 彳) 叫做彳的p e r r o n 根，其对应的正 特征向量叫做彳的p e r r o n 向量，对不可约非负矩阵彳的p e r r o n 根与p e r r o n 向量，有 定理1 2 5 f 5 】设彳为非负不可约矩阵， ( 1 ) 若a x = p ( 4 ) x 与x 日“，则x o ，即x 为彳的p e 仃o n 向量。 ( 2 ) 若彳有非负特征向量x 对应于a 仃( 彳) ，则a = p “) ，即a 必为彳的 p e r r o n 根，且x 0 ，即x 必为彳的p e 玎o n 向量。 以下讨论不可约非负矩阵彳的谱半径的性质。 定理1 2 6 【4 1 设矩阵彳是力阶不可约非负矩阵，则么的谱半径j c i ( 彳) 是彳的特征方 程的单根。 由定理1 2 6 ，显然有下面的推论。 推论1 2 1 4 1 设矩阵彳是”阶不可约非负矩阵，p = p ( 彳) 是彳的谱半径，且止= p x ( x o ) ，则p 所对应的任意特征向量必为h ( 七0 ) 。 推论1 2 2 嗍设矩阵彳是甩阶不可约非负矩阵，p 是彳的谱半径，且 b ( p ) = 哪( 一彳) ，则双p ) o 。其中砷( 一彳) 是矩阵一彳的伴随矩阵。 为了改进定理1 2 4 的基本结果，给出w i e l a n d t 的一个结果，它是后面许多结论证 明的有力工具。 定理1 2 7 ( w i e l a n d t ) 【8 1 设彳是力阶不可约非负矩阵，b = ( 玩) 是玎阶复矩阵， ( 1 ) 若i 剧a ，则对任意p p ( 助，有 i 卢i p ( 彳) ( 1 2 1 ) 因而p ( b ) p ( 彳) 。 7 太原理工大学硕士研究生学位论文 ( 2 ) ( 1 2 1 ) 式中等式成立当且仅当b 有形式b = e i e d a d 一，其中 p 坩= , e p ( 彳) ，o 9 _ 1 ，则彳 称为具有指标k ( 1 ) 的循环矩阵( 或非本原矩阵) 。 显然任意正方阵一定是素矩阵，但反之未必，如彳= ( ? 言) 。 非负不可约矩阵的循环指标k 对了解该矩阵的谱结构至关重要。下面定理给出了如 何根据矩阵的特征多项式确定矩阵的循环指数。 定理1 3 1 【5 1 设玎阶不可约非负矩阵彳的循环指数为k ，且彳的特征多项式为 d e t ( 舡- a ) = r + q 刀1 + + 口 刀， 其中a f 0 ( i = 1 , 2 ，厅) ，力 r h 他 0 。则 太原理工大学硕士研究生学位论文 k = g c d ( 疗- n l ，玎l - r 2 ，胛 一l - n ) 其中g c d ( 刀一啊，n 1 一矗2 ，刀一n h ) 表示正整数n - n l ，n 1 一力2 ，l h 一】- n h 的最大公因 数。 上述定理指出，只要知道矩阵彳的特征多项式，就很容易求出彳的循环指标，而不 需要求出彳的所有特征值。这样，我们有如下判定不可约矩阵为素矩阵的简单办法。 推论1 3 1 【5 】迹为正的不可约非负矩阵彳是素矩阵。 下面结果提供素矩阵的一个重要特征。 定理1 3 2 ( f r o b e n i u s ) 7 1 设彳为非负矩阵，则么为素矩阵当且仅当存在一个正整 数m 使得a ” 0 。同时，若a 用 0 ，则对任意q m 有a q o 。 对r 阶非负素矩阵，有下列两个基本的谱性质。 定理1 3 3 t 1 】设4 为n 阶非负素矩阵，则 ( 1 ) p ( 彳) 为a 的正特征值，并且存在正向量x r ”使得a x = p ( 4 ) x ； ( 2 ) a 的任何一个其他特征值a ，都有 p ( 彳) ， ( 3 ) p ( 么) 是么的单特征值。 定理1 3 4 f 1 】设4 是”阶非负素矩阵，x 是么对应于特征值p ( 么) 的正特征向量，y 是彳r 对应于特征值p ( 彳) 的正特征向量，则 溉盼( 彳) 一1 么) = ( y r x ) x y 最后给出非负不可约矩阵的p e r r o n f r o b e n i u s 理论的第二部分。 定理1 3 5 1 7 1 设彳为n 阶不可约非负矩阵，其循环指标为k ， ( 1 ) 设模为p ( 彳) 的彳的k 个特征值是 = p ( 彳) e 谕，a 2 = p ( 彳) e i 0 2 ，九= p ( 彳) e i ， 这里，o g 0 2 o k 1 ，则存在置换矩阵p 使得p r 么尸具有如下形式： 9 太原理工大学硕士研究生学位论文 p a p l ： 0 a 1 2 0 0 0 a 2 3 0oo a i l 00 o 0 4 - 1 k 0 其中，块对角线上的零块都是方阵。 定理1 3 5 中，( 1 ) 和( 2 ) 很好地刻画出循环指标为k 的不可约非负矩阵么的谱结 构：若彳有特征值位于圆周h = 厂上，o ，p ( 彳) ，则此圆周上有彳的七个不同的特征 值，其重数相同，它们等分该圆周。( 3 ) 给出循环指标大于1 的非负不可约矩阵谱性质 与矩阵零元素分布之间的一种关系。 1 0 太原理工大学硕士研究生学位论文 2 1 主要结果 第二章非负矩阵最大特征值界的估计 非负矩阵最大特征值问题是非负矩阵理论中一个很重要的问题，关于其界的估计， 也有不少很好的结果。现在我们把其中几个重要的结果列出来。 设数和q 分别表示矩阵( 吩) 的第所亍行和与第_ 列列和，即 = 口鹰，c = 口茸，f ，= 1 , 2 ，刀 令厂= m ! n r , ，r = m a xr 。，即r ，分别表示矩阵a 的最大与最小行和。 定理2 1 1 1 9 1 ( f r o b e n i u s ) 如果彳= ( ) 脚是非负矩阵，p ( 彳) 为其最大特征值，则 有 ，p ( 彳) r 如果么是不可约矩阵，则当且仅当a 的所有行和相等时上式任何( 情况) 等号成立。 下面一个定理能够用来改进定理2 1 1 的界值。 定理2 1 2 ( h m i n e ) 1 0 】设彳= ( ) 是非负矩阵，具有正的行和 ，厂2 ，r n 和最大 特征值p ( 彳) ，则 m ，i n ( 1 百窆珏p 。这m c 吉喜v 定理2 1 3 ( w i e l a n d t ) 1 1 1 设a _ ( ) 是非负矩阵，z 是拧维列向量，z 。为其第i 个分量，p ( 彳) 为a 的最大特征值，则 曲 警陋刀卜挑m 叫等陋士 如果彳不可约，当且仅当z 是相对于p ( 彳) 的特征向量，则上式任何( 情况) 等号 成立。 太原理工大学硕士研究生学位论文 对于正矩阵来说，对其最大特征值的界，我们将得到更好的结果，下面的三个定理 充分说明了这一点。 定理2 1 4 ( l e d e r m a n n ) 【1 2 】设彳= ( 口 ) 。功是正矩阵，具有最大特征值p ( 彳) ，最大 行和尺与最小行和r ，以及 j d ( 彳) o ，一气 0 ， m o2 斗 a j ，j o k ，i q s ，m。，i卜n。i。口口。,，i，l，) d 2 一a ”+ m a i ，j 1 3 奎垦墨三查兰堡主堕窒生堂垡堡壅一 _ 一一 则对于任意的0 m m o ，以f 不等式成立： p ( 4 ) m i i l 也一所以m 协i n i ，+ m a j ，j j 定理2 1 1 1 0 6 设4 = ( ) 是满足定理2 1 1 0 的矩阵，m 。也如定理2 1 1 0 中定义， 如果对于任意的j 6 ，口，j o ，那么存在o m 所。满足 p ( 么) m i i l 白磐r j ，r m i n + m m 酣i n 口j ，。j 如果对于任意的歹( ，1 ) ，a j j o ，那么上述的m ，使得 那么 p ( 彳) k + 聊咖口 定理2 1 1 2 1 7 1 设a ( a o ) 。跏是非负不可约矩阵，胛是彳的非本原指数，p 是素数， m i n 罔斗舢栅 1 1 i n j 而且制不可约，当且仅当譬= 譬一= 百r n ( 2 ) 时，式任何c 情况，等号 成立。 ( 2 ) 若彳，可约，当且仅当存在置换矩阵尸，使得 且 p a p r = 0 a 1 2 00 0 0 0 a 2 3 0 0 1；i。 0 000 a p 一1 。p a p l 000 0 望坐：笪丝一：堡 r o ：，一。+ 。，r 口：，一，+ ：， r 口。- 1 ， 成立时，式任何情况等号成立。 这里，仃是由p 确定的置换，彳“+ l 是刀州矩阵，i = 1 ，2 ，p ，r - i p _ , p + 1 = 1 ( - f 标按模p 化简) ， m 0 = o ) 肌。= 酗k 2 ，栅刀= 圭i = 1 一 对于非负矩阵最大特征值的估计还有许多别的界值，本文不再一一列举。 1 4 太原理工大学硕士研究生学位论文 2 2 界的新估计 本节同样约定( 么) ，q ( 彳) 分别表示矩阵彳的第所j ：行和及第f 列列和，p ( 么) 表 示矩阵彳的最大特征值。首先给出两个已有结论： 定理2 2 1 【1 8 】设4 为拧阶非负不可约矩阵，若存在正整数七，使得 5 ( a ) o ( i = 1 , 2 ，行) ，贝0 叩篙驯跳m 籍 若存在正整数k ，使得q ( a ) o ( i = l ，2 ，刀) ，则 叩篙驯胚m 篙 定理2 2 2 【1 明设彳为刀阶非负不可约矩阵，b = ( + 彳) ”1 ，其中i 为”阶单位矩阵， 则对任何正整数七，有 m i nr ( a b k ) p ( 彳) m a x r , ( a b f k 一) ， ， l 丘一j n ( b 2 ) 疵! 攀刚) 雠! 攀 ， q ( b 2 ) - q ( b 2 ) 本节将这两个结果进行改进，得到一个更一般的估计，并且证明了这个新估计较上 面两个估计有更好的精确度。 下面介绍几个引理。 引理2 2 1 【1 9 】a 是刀阶矩阵，a r 是彳的转置矩阵，a 是彳的特征值，( x 1 ，x 2 ，x 。) r 与 ( y l ，y 2 ，y 。) r 分别是彳* o a7 对应于a 的特征向量，则 a x ，= c ，( 彳) ，a m = y ，( 4 ) 引理2 2 2 设彳是刀阶矩阵，则 ( 1 ) = r j ( a ) j = l 证明：由彳“1 = 州可证。 c m “1 ) = 口j ，c ( 彳) = l 1 5 太原理工大学硕士研究生学位论文 引理2 2 3 【1 9 1 设g l ，9 2 ，q 。是正数，p l , p 2 ，p 。是任意的实数，则 p ， m m = s p l + p 2 + + p 。 p ，i q 1 + q 2 + + q n 当且仅当所有的比值q ，相等时取等号。 ，p f s m a x 2 吼 定理2 2 3 设彳为玎阶非负不可约矩阵，c = ( 口1 a 2 + a 2 a + a 3 ，) “- 1 ( a l ，a 2 ，a 3 是任意 的正整数，j 为n 阶单位矩阵) ，则对任意正整数k ，有： 呼器纠跳m 鹣， 证明：以下简记p ( 彳) 为p ， p c 彳，m 盂琶昙警若专 i，i4 l l 设p ，7 2 ，) r 0 ，x - ( 五，x 2 ，矗) r o 分别是彳和彳r 对应于特征值j d 的 打一 特征向量，且yx ，= 1 ，yy ，= 1 ，易证 一一 i = li = l c y = ( a l p 2 + 口2 p + a 3 ) ( ”一1 ) l( c ) r x = ( 口l p 2 + a 2 p + 口3 ) k f - 1 ) x a c y2 p k ( 口l p 2 + 口2 p + a 3 ) o 一1 ) l 由引理2 2 1 知 p k ( a l p 2 + a 2 p + 口3 ) 肛1 ) k - i ( a l p 2 + t z2 p + a 3 ) 七。一1 则由毛= l 得： 于是 l = l 由引理2 2 3 得： ( 彳c ) r x = p ( a l p 2 + a 2 p + 口3 ) 七( ”一1 ) x 打开 j d ( a l p 2 + a 2 p + 口3 ) ( ”一1 ) = p k - 1 ( 口1 p 2 + 口2 p + 口3 ) o 一1 ) = p = 裁窘筹= 1 6 l ( 彳c ) 一( 彳h c ) t ( 彳。c ) t ( 么扣1 c ) 一 y 薯i ( 彳c ) j i = l t ( 彳b 1 c ) 器 nrr 脚。脚 瑚 一 太原理工大学硕士研究生学位论文 二= 二二一一一 z 珥n 勰p m 糕 叩勰洲班m 筹琶 叩筹洲挑峄筹警 定理2 2 4 设彳为，z 阶非负不可约矩阵，c = ( a l a 2 + a 2 a + a 3 ，) ”- 1 ( 口l ，a 2 ，a 3 为任 意的正整数，i 为玎阶单位矩阵) ，则对任意正整数尼，有： m 器细黔， 叩器呼n 稿 证明：令d = c = ( 吒) ，对任意手整数七， m p 勰呷黼呷篇叩m 黔呷耥 同理可证 产1 叩器叩揣 定理2 2 5 设a 为，2 阶非负不可约矩阵，曰= ( + 爿) 川，c = ( 口l a 2 + a 2 a + a 3 j ) 一， 其中为门阶单位矩阵，a l , a ：，口，为任意的正整数，则对任意的正整数七，有 峄器鲕鬻， 叩勰叩鬻 ( a b )i ( 么k - i a b ) m 警赫a b2 峄戈两k - i b 三5 峄 ( 卜1 。) 。 ( 4) 同理可得 m 口5 ( , 4 b 七 ! ：! 肌 5 ( b ) s m a ) ( m 双丛丝望= m a ) ( 螋 ， ( b 2 ) 一 ( b ) 幽堪i i l i n 坐堕 ，( 么扣1 b 。) 一 ) 1 7 太原理工大学硕士研究生学位论文 不妨设a 2 = a l + a 3 ， 则c = ( a l a 2 + 口2 a + a 3 j ) ”= ( 口l a + a 3 ，) “一1 ( 彳+ ，) ”一，令 = ( 口1 a + a 3 ，) = ( ，z ) 脚，则 m 黼呷害等器矧呷勰 = m a x l n r j ( a b ) n r j ( a 卜b ) = 1 m a xm a x 嘿：m a x 堪：m a ) 【一r f ( a b ；k ) ， ( 彳卜1 b 。)- ( 么卜1 8 2 ) ， ( 曰) 同理醌叩勰叩端呼鬻 注1将定理2 2 4 和定理2 2 5 中的行和换成列和结论仍成立，由这两个定理知定 理2 2 3 中的界值比定理2 2 1 和定理2 2 2 的结果要好。 注2 若彳是甩阶非负可约矩阵，则存在咒阶置换矩阵p ，使得 p a p t ： 东0 0 2 ， 鸣2 彳2 。i ，、m o 4 一j 其中主对角线上每块a 矗( 1 f 所) 为不可约阵或一阶零矩阵，这 时，p ( 么) = p ( 剐p r ) = m a x p ( 4 ) 。因此，对非负可约矩阵施行一定的置换后，同样 is j s m 可对其最大特征值进行估计。 1 8 太原理工大学硕士研究生学位论文 3 1 引言 第三章非负不可约矩阵最大特征值的一种迭代算法 非负矩阵的经典理论( p e r r o n f r o b e n i u s 理论) 证明了每个非负方阵彳都有一个非负 的特征值r ( a ) ，其数值不小于彳的任何一个特征值的模数，并且存在对应于，似) 的非 负特征向量。这个等于彳的谱半径的特征值r ( a ) 称为非负方阵彳的最大特征值，对应于 它的非负特征向量称为么的最大特征向量。由于非负矩阵的最大特征值及最大特征向量 在理论上，尤其在应用上的特殊重要性，因此有必要建立一些切实易行的旨在寻求任意 非负方阵的最大特征值与最大特征向量的数值方法。已有的幂法、c w 方法、p o v e r 方 法等都是不错的方法，本章继续提出一种新的迭代算法，现有必要将一些基础内容及符 号重述如下，并引出新的迭代方法。 当a 0 时，a 有一非负特征值刀满足r 川( a 为a 的任一特征值) ；当彳 o 时， 4 有一正特征值矿满足允 川( a 为a 的任特征值) 。则刀称为彳的最大特征值，用 刀( 彳) 表示矩阵彳的最大特征值r 。 若a 0 ，a 不可约，则存在自然数m ，使( ，+ 彳) ” 0 。令( + 彳) ”= b ，假设经过 某种迭代过程得到刀( b ) 。因为若a 为彳的特征值，x 0 为彳的与a 对应的特征向量，即： a x = 2 x ，便有：( ，+ 彳) r e x = ( a + 1 ) ”x 。所以，可依上式得到：刀似) = 阢( ，+ 彳) ，佃一l 。 因此，只要求得a 2 ( b ) ，就可求得非负不可约矩阵4 的最大特征值九( 彳) 。 对b o ，记： r = b o ( i = 1 ，2 ，”) j = l r = m a x r l ，= r a i nr f q = d i a g ( r l ，r 2 ，r 。) 当足 0 时，对b 施行如下运算，得到b ( 1 ) ： 1 9 太原理工大学硕士研究生学位论文 f ，置 l q 1 召q ：i lr 难乏驴2 二 也务( 兰 实际上，如果6 ：f o ，则1 o ，故：b 1 o 。 对b ( 1 再记： 必有： h 妒= 矿( f = 1 ，2 ，厅) j = l r ( 1 ) = m a x r i ( 1 ) ，( 1 ) = m i nr f 1 l 尺( 1 ) r ，( 1 ) r ( 兰：“定义 的意思) 式表明对b 施行的运算，使得b 的行和最大者往小处变，最小者往大处变的趋势。 当足 0 ( f = 1 ，2 ，刀) 时，必有足1 0 ( f = 1 ，2 ，刀) ，故可构造 q 1 = d i a g ( r l o ) , 掣，尺。1 ) 对b ( 1 进行如上的运算过程，得到b ( 2 、。 p 一b o ) ) - ( 铲茜) 兰( 一兰酽 pt j j 记：f q ( 1 ) 1 - 1 ：q - ( 1 ) ，上式变为： 盯。冶o b o ) _ ( b y o 茜江( b o 但) ) 蚰。 此过稗可一盲讲行下去。 迭代k 步时： 则一般迭代格式为： r = ( 扛1 ，2 ，刀) 尺( 七) ：m a x 尺二( ) ， ，( 七) = n a n r j ( ) q ) = d i a g ( r l ，尺。) b 】- 1 = q 哪， b ( ) = q 一( 一1 ) b ( 一1 ) q ( 一1 ) 叫叫雾) _ ( a ： 2 0 ( k = 1 , 2 ， ) 太原理工大学硕士研究生学位论文 当七= 0 时，可令：彳( o ) = a ，r ，o = r f ( f = 1 , 2 ，疗) ，r ( o ) = r ，( o ) = ，q o = q ， q 一( o ) = q ， 可证得： 尺( r ( 。一n ，厂( ，( 一1 ) 则对任意七，有： ，( 1 ) ，( 。) r ( 2 ) r ( 1 ) r 显然，r ( 。为单调下降的序列且有下界，( ) 为单调上升的序列且有上界，故两个序 列的极限都存在。 3 2 主要结果 3 2 1 重要定理 定理1 ：设b = ( 6 1 f ，) o ，置 o ( f = 1 ，2 ，疗) ，则当 l i m r ( ) ：l i m r ( ) 时，有： f ( b ) = l i m 尺( ) 证明：由迭代式b ( ) = q 一( 一1 b ( 一1 q ( - 1 ) 一b o ( k _ 1 ) r 气j ( ，k - o ，) = ( 知：b 与b ( ) 相似，故b 、b ( 具有相同的特征值， 于是： z ( b ) = 分( 召。) ( 七= 1 , 2 ，”) 由f r o b e n i u s 定理可得： 小r ( b ) 尺( ( 七= 1 , 2 ，刀) 令七一，两边取极限，可得： l i m ，( 七) ：l i m r ( ) = l i m ，( ) = r ( b ) 定理2 ：设召= ( 6 ：f ) o ，则有 太原理工大学硕士研究生学位论文 其中： ) 瑚们 o ，首先证下式成立： 肌一脚， 1 - 去i ，丕，”丢 其中：j = c ，= 卅冬鼍) ，r 0 ) = r j l ) , r o ) = r t ( 1 ) 若尺( 1 ) = ，( n ，则式显然成立。 若r ( 1 ，( n ，则r ， = 窆i r j j = l 一窆) f f i l 鲁t j j j = 喜c 冬一每冯 姬 窆j = l 笠r s2 去喜纠 嘉鲁2 去挚叫 故：争( 笠一笠) ：o 智r ，置 由足1 r 1 和上式知：j = j ( 1 ) ，n j 。 故 y ( 笠一笠) ：一y ( 一b s ) 一笠， 葛r s r tj 鼎jr sr t j 所以：秽) 一一) = 吾( 急一等，妻，( 百b s i 一鲁豫， r，丢c惫一每，+，丕c百bqejj 一鼍，、s1 、tl e “一、s1 、t 川叫善c 可b s j 每t ，j e j 1 j 刈叫”j e n - j 冬一乏j e j 等 。51 2 2 太原理工大学硕士研究生学位论文 c r r ， t 一去c ，丕，+ 吾， 式中，将i 换为k ，0 换为k - 1 ，可得： r ( ) 一，( ( r ( 一n 一，( 一1 ) 由聊( 的定义知： 历：( k - 1 ) j r ( 七1 一，( ) ( 尺( t n 一，( i l ) 南c ，丕，玎) + h ) j j j n j 南( 刖e 一，m ( k _ d + 若 = ( r f k - o _ r ( k - 1 ) h 一南。耖， 又 r ( 一r ( b ) 尺( n 一厂( ) 故结论成立。 注：估计误差r ( n r ( b ) 时，可以使用式，也可以使用式。 3 2 2 迭代算法格式及步骤 现将一些算式及记号重复如下： b ( 。) ：q 一( 一1 ) b ( - 1 ) q ( 一1 ) = ( 6 ( i - 1 ) 矿r ( k - o ) = ( q ( 。) = d i a g ( r l ( k ) , r 2 ，r 。) b 】- 1 = q m ， r 似) - 6 o = i 足( ) = m a x r j ( ) ，( ) = r n i n r j ( ) 2 3 ) ( 七= 1 , 2 ，) ( f = 1 , 2 ，1 ) d d - l 6 r【 d 卜 ( m 太原理工大学硕士研究生学位论文 这样，求非负不可约矩阵彳的最大特征值f ( 彳) 的步骤可简述如下： ( 1 ) 求自然数m ，使( ，+ 彳) 朋 0 。为确定m ，可顺次考查彳、彳2 、彳4 、彳8 、彳1 6 、 a “，求得m 。 ( 2 ) 令b = ( ，+ 4 ) ”，对b 按式进行迭代，求得r ( b ) ，即求得：r 【( ，+ 彳) ”j 。 因为由a x = ；t x ( x 0 ) 可推出： ( ，+ a ) x = ( a + 1 ) x 工0 可以得出：( j + 彳) ”x = ( a + 1 ) ”x f ( 彳) ：k ( b ) t 一1 即： r ( 彳) = 防( ，+ 彳) ”】击一1 3 3 数值例子 例l 设彳= 三三三 ，求彳的最大特征值。 f ，0 21 0 1 囱2 设彳= l 三：三i ，求彳的最大特征值( 精确到。0 1 ) i , o 10 l j 解：a 0 ，m 3 ，迭代到第6 步，得： 彳(16)=11：4品777 1：?0 6 1 。苫1 5 。吕0 0 14 8 0019 一：9 7 oon 6 7 9 i 1 1 i j 太原理工大学硕士研究生学位论文 故：f ( 彳) = 2 4 8 彳的最大特征值的精确值为：“彳) = 2 4 8 ，可得，a ( 么) = ，( 彳) 。因此，本文的迭代 算法切实易行。 2 5 太原理工大学硕士研究生学位论文 总