（计算数学专业论文）多项式矩阵最小多项式的一种有效算法.pdf

大连理工大学硕士学位论文 摘要 方阵的最小多项式和特征多项式是线性代数中的一个基本概念，它的计算在自动化 控制、稀疏线性方程组的求解等其它领域都有重要的应用本文先叙述了对最小多项式 和特征多项式的国内外的研究历史和现状，然后给出了已有的计算常数矩阵特征多项 式、多项式矩阵的特征多项式和常数矩阵最小多项式的主要算法及其复杂性最后，我 们给出了一种计算多项式矩阵最小多项式或特征多项式的有效算法，它从低次项到高次 项逐项确定最小多项式的系数多项式算法利用一个随机向量和一个随机位移，对输入 矩阵没有任何条件限制我们把这一算法与已有的算法作了理论的复杂性分析，并对我 们的算法和c h t b 方法做了相应的数值实验，实验结果证实了这一算法的有效性本文 提出的算法具有这样的优点：既去掉了c h t b 方法的限制条件，又具有比c h a c m 方 法更低的计算复杂性 关键词：多项式矩阵；晟小多项式；特征多项式 多项式矩阵最小多项式的一种有效算法 a ne f f i c i e n ta l g o r i t h mf o rc o m p u t i n gm i n i m a l p o l y n o m i a l s o f p o l y n o m i a l m a t r i c e s a b s t r a c t t h em i n i m a lp o l y n o m i a lo fas q u a r em a t r i xi sab a s i cc o n c e p ti nl i n e a ra l g e b r aa n di t s c o m p u t a t i o nh a si m p o r t a n ta p p l i c a t i o n si na u t o m a t i cc o n t r o l ，s o l v i n gs p a r s el i n e a re q u a t i o n s ， c o m p u t i o no f t h ed e t e r m i n a n ta n do t h e r f i e l d s f i r s t l y ，t h i sp a p e rd e s c r i b e st h eh i s t o r ya n d s t a t e o ft h er e s e a r c ht ot h em i n i m a lp o l y n o m i a la n dt h ec h a r a c t e r i s t i cp o l y n o m i a la n dt h e ng i v e st h e m a i nm e t h o d sa n di t sc o m p u t a t i o n a lc o m p l e x i t i e sf o rc o m p u t i n gt h ec h a r a c t e r i s t i cp o l y n o m i a l a n do f a c o n s t a n t m a t r i x ，t h ec h a r a c t e r i s t i c p o l y n o m i a l o f a p o l y n o m i a l m a t r i x a n d t h e m i n i m a l p o l y n o m i a lo fap o l y n o m i a l f i n a l l y , w ep r e s e n ta ne f f i c i e n ta l g o r i t h mf o rc o m p u t i n gt h e m i n i m a l p o l y n o m i a lo f a p o l y n o m i a lm a t r i x i td e t e r m i n e st h ec o e f f i c i e n tp o l y n o m i a l s t e r mb y t e r mf r o ml o w e rt oh i g h e rd e g r e e b yu s i n gar a n d o mv e c t o ra n dr a n d o m l ys h j 伍n g ，t h i s a l g o r i t h mr e q u i r e sn oc o n d i t i o no ni n p u tm a t r i x c o m p a r i s o nw i t ho t h e ra l g o r i t h m si nb o t h t h e o r e t i c a lc o m p l e x i t ya n a l y s i sa n dc o m p u t a t i o n a lt e s t sa r eg i v e nt os h o wi t se f f e c t i v e n e s s c o n s i d e r i n g t h a to u ra l g o r i t h ma l s or e l e a s e dt h er e s t r i c t i o n sa d d e do nt h ei n p u tm a t r i xi nc h t b m e t h o dm i di ti so fl o w e rc o m p u t a t i o n a lc o m p l e x i t yc o m p a r i n gw i t hc h a c mm e t h o d ，o u r a l g o r i t h mi so n eo f t h eg o o dc a n d i d a t e sf o rt h ec o m p u t a t i o no ft h em i n i m a lp o l y n o m i a lo fa p o l y n o m i a lm a t r i x k e yw o r d s ：p o l y n o m i a lm a t r i x ；t h em i n i m a lp o b ，n o 瑚j a l ；t h ec h a r a c t e r i s t i cp o l y n o m i a l 一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：锰幸包日期：兰! 丝：主：兰车 大连理工大学硕士学位论文 1 综述 涨如 的稳定性，其中a 悬玎 箨阵，x j ? nb 是瓤向量，c 悬行嘲爨，“莉掣是常毂我们需要检 验是否爿的所有特征值都具有负的实部但是当a 的维数太1 于鼍时候，a 的特征值不能 准确计算，需要先计算a 的特征多项式，再剥用r o u t hh u r w i t z 稳跫陡准则【l 】判断是甭4 的 1 2 研究历史和现状 对于常数矩阵特征多项式的计算，已有许多研究主要算法有：f a d d e e v - l e v e r r i e r 方法 1 9 1 ，d a n i l e v s k i i 方法【1 0 】，l a g r a n g e 插值法i l “，以及一类先把矩阵做相似变换转换为一种特征 多项式容易计算的形式，再求特征多项式的方法，比如：h e s s e n b e r g 方法f 1 2 ，1 3 1 、f r o b e n i u s 方法1 1 z 13 1 、一种介于h e s s e n b e r g 形式和f r o b e n i u s 形式之间的方法f 1 3 】此外，还有针对具 体问题给出的方法，比如，一种适合于行列式q m c 方法的一种方法【1 4 】等 ( 1 ) f a d d e e v l e v e r r i e r 方法 f a d d e e v l e v e r r i e r 方法1 9 1 的思想最初是由u j tj l e v e r r i e r 在1 8 4 0 年提出的，之后，在 2 0 世纪4 0 年代j m s o u r i a u 1 5 和j s f r a m e 1 田对它重新发现并改进，5 0 年代， o a n t m a c h e r t ”l 利用多项式系数和它的根的幂和之间的联系也对这一算法的正确性进行了证 明1 9 6 3 年，d k f a d d e e v 和v n f a d d e e v a 1 8 】给出了f a d d e e v - l e v e r r i e r 方法1 9 9 3 年 g i l b e r th e l m b e r g 和p e t e rw a g n e r 9 在f a d d e e v - l e v e r r i e r 方法的基础上，讨论了c ( 凡) 0 的 多项式矩阵媛小多项式的一种有效算法 充分必要条件，并指出c ( ) 在矗的导数仍然可以用于确定特征向量或者在c ( ) = 0 时的 推广的特征向量，对f a d d e e v - l e v e r r i e r 方法做了进一步的完善 ( 2 ) 1 9 3 7 年，d a n i l e v s l d i 给出了d a n i l e v s k i i 方法i ，这种方法通过定义一种初等变换， 对输入矩阵反复执行初等变换最后把矩阵化为与其相似的f r o b e n i u s 标准型，最后得到矩 阵的特征多项式或最小多项式 ( 3 ) l a g r a n g e 插值法【“1 给定的7 + 1 个点，通过计算矩阵的特征多项式在这疗+ 1 个点的值，即计算行- i - 1 个行列 式的值，用l a g r a n g e 插值法确定矩阵的特征多项武 ( 4 ) 对矩阵作相似变换的方法 任意一个矩阵可以通过一系列相似变换转换为上h e s s e n b e r g 形式【1 2 】，这些交换可以 是正交变换或者部分主而的初等交换n n n ，4 以n n n n n 嗣特征参顶式，远吾于我酊织需 要求出矩阵的上h e s s e n b e r g 形的特征多项式即可，这可以很容易用遵携的方法得到如暴 上h e s s e n b e r g 形式中的次对角线上的元素都不为零，可以通过一系列相似变换变成 f r o b e i n u s 标准型1 1 2 1 ( 或者当矩眸为非减次矩阵的时候变换为友矩阵的形式乱这时矩阵的特 征多项式可以很容易得到1 9 8 2 年，j w a n g 和c c h e n 1 3 l 基于上面两种方法，给出了一种 通过相似变换先把矩阵化为一种介于h e n s s e n b e r g 形式和f r o b e n i u s 形式之间的形式，再计 算特征多项式的方法这个方法和h e n s s e n b e r g 方法相比公式更简单，和f r o b e n i u s 方法相 比数值更稳定 对于多项式矩阵，它的特征多项式或者最小多项式的计算也具有非常重要的实用价值 例如，在 1 9 2 0 1 中，要计算多项式矩阵的近似特征值，需要首先计算它的特征多项式到 目前为止，关于多项式矩阵特征多项式或最小多项式的计算的研究还很少虽然，计算常 数矩阵的很多方法理论上可以直接应用于多项式矩阵，但是，计算过程中计算最大公因子 来约化有理表达式需要大量的c p u 时间，随着计算过程的进行，公共分母会发生膨胀，这 样中间结果会需要越来越多的内存所以实际计算中这些方法是不可行的 由于f a d d e e v l e v e r r i e r 方法 9 1 应用于多项式矩阵时，计算过程中不包含多项式除法， 所以它可以直接用于多项式矩阵特征多项式的计算除此之外，还有光分式d a n i l e v s k i i 方 法【2 “、c h t b 方法i n 、c h a c m 方法吲 ( 1 ) 1 9 9 7 年，s m o r i t s u g u 和k k u r y a m a 2 l l 把b a r e i s s 的无分式消去的思想用于 d a n i l e v s k i i 方法，对d a n i l e v s k i i 方法作了改进，从而避免了d a n i l e v s k i i 方法中约化有理表 达式和中间结果发生膨胀所占用的c p u 时间和内存作者对不同大小的矩阵所作的实验 表明，这种进行无分式改进后的方法所用的c p u 时间比d a n i l e v s k i i 方法减少了7 0 - 2 大连理工大学硕士学位论文 ( 2 ) 19 9 9 年，t k i t a m o t o m j 基q ：c a l e y - h a m i l t o n 定理，给出了c h t b 方法，算法对输入 矩阵有条件限制：矩阵的常数部分要具有互不相同的特征值c h t b 方法的计算过程中除 了计算一个常数矩阵的逆和计算一次特征值和特征向量以外，只需要矩阵和向量的基本运 算 ( 3 ) 2 0 0 0 年，b oy u 和t k i t a m o t o 田 通过引进一个人工常数矩阵给出了基乎c a l e y - h a m i l t o n 定理的c h a c m 方法，算法对输入矩阵没有任何条件限制，计算过程中只需要基 本的矩阵运算 关于最小多项式的计算，d a n i e la u g o t 和p a u lc a m i o n e 2 】，d o u g l a s 。荫w i e d e m a n n t 3 和 e i r c hk a l t o f e n 4 】都有相关研究； 1 1。 ( 1 1 i1 9 8 6 年，d o u g l a sh w j e d e 哦d 曲咖在求解有限域上的稀疏线性方程组a x = 5 的算法 中，间接给出了蔷种诗算最小多项武的非确定性算法管翻南随机选敏酌蓟向量“，根据 b e r l e k a m p - m a s s e y 算法晖l 删先计算痒梦畎国，爿西羚盏酌最小多项式，威而得到矩阵a “类芋一 个向量b 的最小多项式厂 6 再根据这样一个结论： 对于随机地均一地选取的向量b ，艮，l c m ( f “，f “) = 厂4 的概率至少是a ( 厂4 ) 一k 一1 其中珐( 厂) = 兀( 1 - q 一埘) ，而且丸( 厂) 1 - l o g = 芒广了) iq 一1 就可以在很小的误差范匿内得到矩阵a 的最小多项式之屠，1 9 9 1 年，e r i c hk a t t o f e n l 4 l 又对 w i e d e m a n n 【3 】的算法作了一些改进 ( 2 ) 1 9 9 7 年，d a n i e la u g o t 和p a u lc a m i o n r 2 】给出了两种计算最小多项式的算法，第一种 算法以矩阵特征多项式的因式分解作为输入，在o ( n 35 ) 的计算复杂性内输出矩阵的最小多 项式和所有的特征子空间，第二种算法是先把矩阵化为s h i f l - h e s s e n b c r g 形式，通过一步步 迭代在o ( n 3 + 嘲行2 ) 的计算复杂性内得到最小多项式其中m 。是s h i f t - h e s s e n b e r g 形式的 一个参数，它的平均值是o ( 1 0 9 n ) 它的优点是不需要通过特征多项式，缺点是不能产生 足“到矩阵的特征子空间的分解文中d a n i e la u g o t 和p a u lc a m i o n 还把最小多项式计算 用于寻找矩阵的循环向量 1 3 本文的主要结果 论文在c h t b 方法的基础上，通过引入一个随机向量和一个随机位移，给出了种计 算多项式矩阵最小多项式的有效算法算法对输入矩阵没有任何条件限制，不需要计算特 征值和特征肉量，计算过程中只需要基本的矩阵运算理论的复杂性分柝表明，和除了 3 多项式矩阵最小多项式的一种有效算法 c h t b 方法以外的计算多项式矩阵特征多项式的已有算法相比较，我们的算法具有最低的 计算复杂性；和c h t b 方法比较，我们的算法又去掉了c h t b 方法中对输入矩阵的条件限 制，不需要计算特征值和特征向量，并和c h t b 方法一样都具有o ( n 3 ) 的计算复杂性事 实上，后面的数值实验表明我们的算法比c h t b 方法更有效，因为c h t b 方法中特征值和 特征向量的计算要耗费太量的时间，并且特征向量有可自岳是复数，使得c h t b 方法中有可 能包含复数运算，这都会影响计算效率鉴于( 2 3 】中作者对f a t l d e e v - l e v e r r i e r 方法，无分 式d a n i l e v s k i i 方法、c h t b 方法和c h a c m 方法所做的数值实验的结果表明，对子矩阵阶 数n 和多獗式矩阵中多项式的最高次数牙较巍的情形，e l _ i _ _ 隅方法的计算复杂性最低所 以，对于具有随机生成整系数的1 、2 、3 维的，4 、6 、8 、1 0 阶韵多项斌矩阵，我们只把我 们的算法和c h t b 方豫做了比较j 实验结果表明我们的算法比e h 娟方法计算时问更短， 另外，由于作者编稔瘩乎和所髑数学软稃的限制，我们恳做了基本算法的编程，并没有优 化算i 袁昕用的基本函数，故所编写的算法还焉法达至4 m a p l e 中已有的内部函数的效率 一4 大连理工大学硕士学位论文 2 数学基础 定义2 1 ：( 且一矩阵) 所谓4 一矩阵就是以五的复系数多项式为元素的矩阵，有时也称为多项式矩阵般 地，一个次数不超过m 的以阶4 一矩阵曰( ) 总可以写为 b ( 4 ) = 岛旯+ 马丑。+ + 最一j a + 最。， 其中，尽( i = 0 ，1 ，m ) 为，l 阶常数矩阵，称上式为a 一矩阵占( 的多项式写法。 定义2 2 ：( 允一矩阵的初等变换) 旯一矩阵的初等变换是指下面的三种变换： ( 1 ) 任两行互换； ( 2 ) 用数k 0 乘某行( 列) ： ( 3 ) 用4 的多项式伊( 旯) 乘莱行( 列) ，并加到另一行( 列) 上去 定理2 3 ：( s m i t h 标准型) 任意一个非零的j 的a 一矩阵彳( 都等价于下列形式的矩阵 一( 丑) 吒( 五) 4 ( a ) o o 称它为a ( 4 ) 的s m i t h 标准型，其中r 1 ，吐( 旯) ( f - 1 ，2 ，) 是首项系数为1 的多项式， 且 4 ( a ) 1 4 + 。m ) ( f = l ，2 ，r 一1 ) 定理2 4 ：丑一矩阵的s m i t h 标准型是唯一的 定义2 5 ：( 不变因子) s m i t h 标准型的主对角线上的非零元素画( 五) ，4 ( 五) 称为a 一矩阵一( 丑) 的不变因子 定义2 6 ：( 初等因子) 把矩阵a 的每个次数大于零的不变因子分解成互不相同的一次因式方幂的乘积，所 有这些一次匿l 式方幂斜目同的必须按出现的次数计算二) 祢为矩阵爿的初等因子 定义2 7 ：( j o r d a n 标准型) 5 多项式矩阵最小多项式的一种有效算法 形如 的方阵称为t f 阶j o r d a n 决， 的分块对角阵 以= 丑1 l a t k 。 其中a 可以是实数，也可以是复数由若干个j o r d a n 块组成 其中正( f _ 1 ，2 ，) 为阶j o r d a n 块 t 当= 时，称为r 阶j o r d a n 标准型，记为 j _ 1 定义2 8 ：( 零化多项式) & 4 t e ( a ) = 0 的旯的多项式妒( 兄) 称为矩阵4 的零化多项式( 般取首项系数为1 ) 定义2 9 ：( 最小多项式) 矩阵4 的次数最低的首项系数为1 的零化多项式称为a 的最小多项式，记为掰( 五) 定理2 1 0 ：多项式妒) 是矩阵彳的零化多项式的充要务件是m ( a ) i p ( 兄) 特别地，有 掰( 五) l 厂职) ，即4 的最小多项式是其特征多项式的因式 定理z 1 1 ：相似矩阵有相同的最小多项式 定理2 1 2 ：n 阶矩阵爿的最小多项式等于它的特征矩阵旯，一a 中的第一个不变因子吃( ) 因而 器= 塑铲= 铲d o m ( ad o c 饥 川( 丑)( a ) 7 推论2 1 3 ：方阵彳的特征多项式的根必是其最小多项式的根， 推论2 1 4 ：如果矩阵的特征值互异，则它的最小多项式就是特征多项式 定义2 1 5 ：( 特征多项式) 设a 为 阶方阵，矩阵旯，一a 称为爿的特征矩阵，其行列式d e t ( a i a ) 称为爿的特 征多项式，d e t ( m 一4 ) = 0 为a 的特征方程，其根称为4 的特征值( 或特征根) - 6 、jj 似 、 大连理工大学硕士学位论文 定义2 1 6 ：( k 阶迹) 在盯阶方阵a 中任取行次和列次相同的七行七列( 1 k s ”) ，4 9 q - 这k f t k 列交叉处的 元素按原位置组成的k 阶行列式之和，称为方阵4 的k 阶迹，记为t r a c e 1 即) ，即 气吒k t r a c e 叶1 ( 4 ) = 卜 嘲叩吐9 k - 一 ( 蠡= 1 ，2 ，疗) 其中4 ( 1 - - i t ，t n ；f ，s = l ，2 ，砖i i z 矗) 是位于a 中第行和第列的交叉处的 蠹靠 ?j 定理2 1 7 ：聆阶枣阵爿的特征多项式，积) = 1 1 2 z - a i 可踢焉成如下的形式 ，( 旯) = ( - 1 ；) 4 齿醯e 啪( ) 旯”一。， 。 = l 其中 t r a c e o ) = 1 ， t r a c e 障1 ( 爿) = l g q b “s ” 气，口l 气- 气* i 定理2 1 8 ：c a y l e y - h a m i l t o n 定理) 设，( ) 为矩阵的特征多项式，则f ( a ) = 0 定义2 1 9 ：( 友矩阵) 如下的q x q 方阵 a = o0 _ 0 a o - 0 a l 0 a 2 。 ； 1 一l 称为多项式厂( 五) = 旯。一q 一五叫一玎l 五一a 0 的友矩阵特别地，多项式厂( 五) = z a 0 的 友矩阵是( ) 发矩阵的特征多项式仍( 名) 和最小多项式仍( 都等于厂( 五) 定义2 2 0 ：( f r o b e n i u s 矩阵) 我们定义，f i i f r o b e n i u s 矩阵且为如下形式的矩阵 - 7 多项式矩阵最小多项式的一种有效算法 & = 阢一b 一：6 ，一， lo0 o1o 000 6 lb o 00 00 ： 10 定理2 2 1 ：( f r o b e i n u s 标准型或有理标准型) 用一个合适的正则矩阵s ，每个杆) ( 捍方阵a 都可以变换成如下的分块对角矩阵 s - 1 彳s = c l 毋c ：0 - o q ， 这称为a 的f r o b e n i u s 标准型( 有理标准型) 每个分块矩阵c j ( i = l ，p ) 是一个友矩阵 ( 或f r o b e n i u s 矩i 韵，并且c | + i 的最小多项式既。) 錾除g ：，的交小多项式珐，( 宄) 并且 f r o b e n i u s 标准型是存在的，由给定矩阵矗唯一确定。 定理2 2 2 ：( f r o b e i n u s 标准型和初等因子) 设除1 以，r 的初等因子按次数下降的顺序依次是e ，( n ，e 。( 兄) ，它们包含于特征矩 阵2 e a 的s m i t h 标准型中，囊a 果它的有理标准型r 有形式 r = c 1 0 c 2 0 o c p ， 每个分块矩阵c ( i = l ，p ) 是和初等因子q ( 丑) 相关的友矩阵，并且最小多项式 兜( a ) = ( 丑) ( f = 1 ，p ) 定义2 2 3 ：( 上h e s s e n b e r g 矩阵) 我们称形如 a = q lq 2q 3 呸l 吗2a 2 3 0 1 2 3 2 码3 00o 口1 p lq 。 a e 。月1t 2 2 h a 3 h 一11 2 3 。月 a n ，h 月 的矩阵为上h e s s e n b e r g 矩阵 定义2 2 4 ：( h o u s e h o l d e r 变换) 设r ”满足恻j ：- - 1 ，定义h r ”为 日= i - 2 珊7 则称h 为h o u s e h o l d e r 变换 定理2 2 5 ：设h 是如上定义的h o u s e h o l d e r 变换，那么日满足 - 8 大连理工大学硕士学位论文 ( 1 ) 对称胜：h 7 = h ； ( 2 ) 正交t t g ：h 7 h = ，： ( 3 ) 对合性：h 2 = 1 ； ( 4 ) 反舳陛：对任意的x r ”，h x 是x 关于的垂直超平面的镜像反射 定理2 2 6 ：设0 x r ”，则可以构造单位向量m r ”，使得h o u s e h o l d e r 变换h 满足 h x = 口岛， 其中1 2 = - + l l x l l ： 定义2 2 7 ：( g i v e n s 变换) 定义 其中c = c o s 0 ，s = s i n 0 ，易证g ( f ，k ，0 ) 是一个正交降我们称g ( i ，k ，目) 是g w e n s 变换 设z r ”，令y = g ( i ，k ，o ) x ，则有 y 2 c x i s x k ， y k2 一s x l + c x k ， yj = x i ，j 幸i ，k ， 因此，若要儿= 0 ，只要取 便有 c = 南产孝专，赢一2 赢 定义2 2 8 ：( g a u s s 变换) 记厶= i - l k e 女7 ，其中= ( o ，0l k + 1 ，t ) 7 ，即 9 - 多项式矩阵垃小多项式的- - v e 有效算法 厶= 一“ i 一“ 称这种类型的初等下三角矩阵为g a u s s 变换 定理2 2 9 ：若彳r “”的顺序主子矩阵a k r “( 女= 1 ，n - 1 ) 均非奇异，则存在唯一的 单位下三角阵l r “”和上_ c a 阵u r “8 使得a = l u 算法2 3 0 ：( 列主元g a u s s 消去法) f o rk = 1 ：行一l 确定p ( k p 珂) 使得 n ( p ，k ) i = m a x l a ( i ，七) l ：f = 七：h ) a ( k ，1 ：”) a ( p ，l ： ) ( 交换七行和p 彳亍) u ( k ) = p0 己录置换矩阵丑) i f a ( k ，t ) 0 a ( k + 1 ：7 ，k ) = a ( k + l ：h ，k ) , 4 ( k ，七) a ( k + 1 ：t ，k + 1 ：打) = a ( k + l ：行，k + l ：”) 一爿( 七+ 1 ：玎，k ) a ( 七，七+ l ： ) e l s e s t o p ( 矩阵奇异) e n d e n d 算法2 3 1 ：( 计算上h e s s e n b e r g 分解：h o u s e h o l d e r 变换法) f o rk = 1 ：n 一2 v ，冈= h o u s e ( a ( k + l ：n ，七) ) a ( k + l ：门，k ：盯) = ( i - v v 7 ) | 4 ( 七+ 1 ：i , k ：，彳) 爿( 1 ：t , k + 1 ：竹) = a ( 1 ：珂，i + l ：以) ( p v v 7 ) e n d - 1 0 大连理工大学硕士学位论文 3 计算矩阵特征多项式和最小多项式的主要算法 3 1 计算常数矩阵特征多项式的主要算法 3 1 1f a d d e e v - l e v e r r i e r 算法 设a 是一个系数在数域k 中的矩阵，a 的特征多项式可以由g i l b e r th e l m b e r g , p e t e r w a g n e r 和g e r h a r dv e l t k a m p 在【9 】中的计算矩阵的特征多项式和特征向量的f a d d e e v - l e v e r r i e r 方法得到这一方法的基本思想最初是由u j j l e v e r r i e r 在1 8 4 0 年提出的，在 2 d 世纪4 0 年代后期j m s o u r i a u 1 5 】和j s f r a m e 1 q 又对算法重新发现和改进，并利用友 矩阵的概念进行了证明之后g a n t m a c h e r l l 7 1 ，h 0 u s e h o l d e r 2 4 和d k f a d d e e v 1 ”也对这 方法作过改进f a d d e e v l e v e r r i e r 方法的公式非常的简洁并且容易在计算机上编程实现， 算法步骤如下： a l 擘a ， a k ：一t r a c 。e a k ( 1 七 ) ，( 3 1 ) k 4 “：= “( 4 + 吼，) ( 1 k 7 - 1 ) 令嘞= 1 ，则爿的特征多项式为( 丑) = d e t ( m - 4 ) = 吼五”如下的定理给出了算法成 k = o 立的证明： 定理3 1 ：设( 旯) = d e t ( a l 一彳) = 哪丑”是a 的特征多项式，并且定义矩阵 k = o 4 ( 0 k s 九一1 ) ，a k ( 0 k 仃) 和c ( 丑) 士a 下： 以= i ， a k = 4 + a k i ， a l = a ， 4 + 。= 爿( 4 + a ) ， n 一1 并且c ( 五) ：= “互， k = 0 那么( a ) c ( z ) = a d j ( ，一a ) ，五k ； ( b ) 吼= t r a c e ( a k ) n k ，0 k 珂一1 ； ( c ) 吼= - t r a c e ( a k ) k ，0 s k h 1 1 多项式矩阵最小多项式的一种有效算法 证明：( a ) 设矩阵风( 0 k 兰n 一1 ) 如下定义 a d j ( a l 一4 ) = 吐b ， 则有 ( ) ，= ( a i 一一) a ( 1 i ( ，一一) ， ”i = ( 2 i - 爿) 丑”鼠i b 。矿+ 茏a ”( 壤一彳最一1 ) _ 爿臻一i k = ok = o 女：i 因此 a o l = 岛( a o 釜1 ) ， a f t = 瓯一g 壤j ( 1 兰露蓉冉善i ) ， 嚷1 = - a b _ l ， 我们得到鼠= = 五 并且，通过对七进行推导( 利用归纳假设最一= 互一。) 段= 爿壤一l + a j = 题- l + a j = 魂+ 哝；墨( 1 s k - 珂t h e nb r e a k ： e l s e o p l + 1 ，) ： o p 2 ( k + 1 ，哌“j ) ： f o ri 扣1t o 后d o o p 3 ( i ，女+ l ，一乱) ： f o rf4 - - 七+ 2t o ，| d o o p 3 ( i ，七+ l ，一a j ) ： 七+ - 七+ 1 ： - 肋一七+ 1 ：( m r 是第p 个友矩阵块的大小) 我1 c 了可以通过把上面构算法应尉于单位矩阵j 得到变换矩阵最s 。：把包含在上面算 法中的行操作和列操作分开，把前者应用予单位矩阵墨，后者应用于另一个单位矩阵岛， 得到( 置斗斗s ，毛_ 呻s ) ，s 。彳s 就是省的有理标准型 例：珂= 4 的情形 a = 1 4 o0 o o 1d o1 函m m 以 大连理工大学硕士学位论文 这里+ 是关于口的有理表达式，是关于q 的多项式因为初等变换包含除法，所 以，中间过程产生的矩阵的元素一般是有理表达式但是我们注意到，友矩阵最右边一列 的元素等于a 的特征多项式( 旯) = d e t ( m - a ) 的系数一c f ( i = o ，n - 1 ) ，根据 d e t ( 2 , i 一嗄) 的计算规则，它们始终是关于d u 的多项式 通过应用上面的算法，我们得到了a 的有理标准型 r = c i 国岛o o c p = lq j 其中，每个c j 都是一个友矩阵，而且q + t 的最小多项式兜。) 可以整除c 的最小多项蕊 瘫，( ) 根据友矩阵的定义，g 的最小多项式允( ) 容易得到对于月的任一多项式 f ( r ) ，我们有 ，( r ) = 厂( c 1 ) 厂( c 2 ) ( 巴) 若，( 曩) 是零矩阵，则每个矩阵厂( c ) 应为零但是厂( c f ) 是零矩阵当且仅当，( 是 c l 的最小多项式允( 五) 的倍数，又因为每个允( 兄) 都能除尽允( 五) ，所以允( 五) 就是r 的 最小多项式相似矩阵有相同的最小多项式，所以矩阵爿的最小多项式是丸( 五) 我们的讨论表观当且仅当矩阵的有理标准型中只有一个友矩阵块，亦即矩阵是非减 次矩阵的时候，矩阵的最小多项式等于它的特征多项式 3 1 3 l a g ”g e 插值法 我们还可以通过l a g r a n g e 插值法“。来确定矩阵a 的特征多项式d e t ( a 1 一a ) 的系数 给定n + 1 个点五= 而( f = 0 , 1 ，玎) ，利用如下的公式 d e t ( 舡“) 2 丢na e t ”黟飘鲁，m 00 ，如 f 一 f 就可以得到a 的特征多项式可以看出，计算过程中只需要计算打+ 1 个行列式。如果用 一般的g a u s s 消去法，这个方法一共需要拧4 3 次乘( 除) 法 1 5 ll， 多项式矩阵皿小多项式的一种有效算法 3 ，1 4 对矩阵作相似变换的方法 3 1 。4 1 h e s s e n b e r g 方法 下面给出一种先把矩阵化为与之相似的h e s s e n b e r g 形式，再计算h e s s e n b e r g 阵特征多 项式的h e s s e n b e r g 方法他” 任一个矩阵4 都可以转换成形如 彳= a 1 h l 巴打一l q 。_ 00 i 0 吒 ( 3 2 ) 的h e s s e n b e r g 形式，这可以通过；系列相似鸾棼得至! ：1 因为相麟蓐育稠网麓特征多颓 式，茹臬我们用( 爿) 来表示_ 酶特征多项瓮，则) ；口) 所以我f ：】可1 2 _ 【角彳来并 算( 彳) 设互是彳的，阶前主子矩阵，( j ) = d e t ( s l , 一互) 是互的特征多项式，那么 ( 么) 可以通过如下方式递推得到： 0 ( s ) 皇1 ， l ( s ) = s d l i ， ，0 ) = o 一( k ) 卜1 ( 妇+ c t r 吐，i ，一2 ( 5 ) 一( k 2 ，t 砟一l ，一3 ( 占) + + ( 一1 ) 7 a i ，i 砟一l 如l ( s ) ， ，= 2 ，3 ，h 并且( = a 。( 5 ) ，( 0 可以通过把d e t ( j 一互) 按最后一列展并而得到 上面的a - - 9 j 的相似变换可以通过h o u s e h o l d e r 变换g i v e n s 变换或者列主元的 g a u s s 消去法而实现其中，使用g i v e n s 变换所需要的运算量大约是h o u s e h o l d e r 变换的 二倍，但是，如果4 有较多的零元素，则适当安排g i v e n s 交换的次序，也可以使运算量 大为减少另外，使用列主元的g a u s s 消去法可以节省计算量，但是数值稳定性较差 h e s s e n b e r g 方法大约需要次乘( 除) 法， 但是它的公式比f a d d e e v - l e v e r r i e r 方法复杂， 比f a d d e e v - l e v e r r i e r 方法需要的计算量要少， 编程会更复杂 3 1 4 2f r o b e n i u s 方法 如果( 3 2 ) 式中j 的t 0 ，i = 2 ，3 ，一，那么形如孑的h e s s e n b e r g 形式可以通过一系 1 6 、，h 嘶黪警：嘶 郎堕； 墼墨； k蔓o； 大连理工大学硕士学位论文 列相似变换变成f r o b e r f i u s 标准型或如下的友矩阵 a = 如码 00 l0 ： _ o0 a n ia n 一 00 0o 10 这可以通过把第n - i 列的( 一吒) 倍加到