（应用数学专业论文）最大公因式求解算法和矩阵的逆次特征值问题研究.pdf

浙江大学硕上学位论文 摘要 多项式的最大公因式求解问题是一个代数问题，又是在实际应用中充满活力 的问题。本文在绪论中介绍了多项式最大公因式求解的一般过程，回顾了同行学 者近年来对该问题的一些研究成果和方法。近年来，由于实际问题的需要，对矩 阵反问题特别是特征值反问题的研究成为当今计算数学中一个非常活跃的课题。 本文在绪论中对矩阵的反问题和矩阵的逆特征值问题的产生背景及实际应用作 了阐述，提出了该问题的数学模型及同行学者对该问题的研究进展。 在第二章中，首先提出了对给定的若干多项式采用系数矩阵表示的方法，通 过引入矩阵的第一、第二斜消变换这样的新概念，给出了用斜消变换( 结合初等 行变换) 求解最大公因式的新思路、新方法。本文对此方法作了完整的理论推导 并提供了具体的例子说明。 在第三章中，本文对矩阵的一类逆特征值问题进行了研究，针对次特征值、 次特征向量概念，提供了矩阵的逆次特征值问题模型，讨论了一类线性流形上次 反对称矩阵的逆次特征值问题。本文对此问题给出了解存在的条件，并给出了解 的通式。本文在对问题的理论推导中，充分利用了次单位矩阵的作用，提供了将 次反对称矩阵的逆次特征值问题转为反对称矩阵的逆特征值问题来解决的新思 路。 在第四章中，以第二章作为理论基础，提供了分别依据第一斜消法、第二斜 消法求解最大公因式的算法实现过程( 具体为算法1 、算法2 ) ，实现了最大公因 式求解的计算机编程处理，使多项式组的最大公因式的求解变得快速、简便、实 用。文中给出了算法实现的具体实例。 在第五章中，本文对自己今后的研究方向及具体的工作作了展望。 浙江大学硕士学位论文 a b s t r a c t t h ew a yt oe v a l u a t et h eg r e a t e s tc o m m o nf a c t o ro fs o m ep o l y n o m i a l si saa l g e b r a p r o b l e m ，w h i c hi sa l s of u l lo fv i g o ri nt h ep r a c t i c a la p p l i c a t i o n i nc h a p t e ro n eo ft h i s p a p e r ，t h ea u t h o ri n t r o d u c e st h et y p i c a lw a y t oe v a l u a t et h eg r e a t e s tc o l i l l t l o nf a c t o ro f s o m ep o l y n o m i a l sa n ds o m er e s u l t st h a ta r es t u d i e db yt h es c h o l a r so ft h es a m et r a d e ， i nt h er e c e n ty e a r s ，a st h er e q u i r e m e n to ft h ep r a c t i c e ，t h es t u d y i n gt ot h ei n v e r s e p r o b l e m sf o rm a t r i c e se s p e c i a l l yf o rt h ee i g e n v a l u eo fm a t r i c e sh a sb e c o m eas u b j e c t t h a ti sv e r ya c t i v ei nt h ec a l c u l a t i o nm a t h e m a t i c sn o w a d a y s i nc h a p t e ro n eo ft h i s p a p e r , t h ea u t h o rs e t sf o r t ht h eb a c k g r o u n da n dp r a c t i c eo ft h i sp r o b l e m ，g i v et h e m a t h e m a t i c sm o d e la n di n t r o d u c e st h ea c h i e v e m e n t sw h i c ha r es t u d i e db yt h e s c h o l a r so f t h es a m et r a d e i nc h a p t e rt w oo ft h i sp a p e r , f i r s t l yt h ea u t h o rg i v e st h em a t r i xe x p r e s sf o rs o m e p o l y n o m i a l s ，a d v a n c e st h en e wc o n c e p to ft h ef i r s ta n ds e c o n do b l i q u ee l e m e n t a r y o p e r a t i o no fm a t r i c e s t h e ng i v e san e ww a yt oe v a l u a t et h eg r e a t e s tc o m m o nf a c t o r o fs o m ep o l y n o m i a l s t h ea u t h o rp r o v i d e st h et h e o r yp r o o fa n dt h ee x a m p l et ot h e m e t h o d i nc h a p t e rt h r e eo ft h i sp a p e r , t h ea u t h o rs t u d i e st h ei n v e r s ep r o b l e m sf o rm a t r i x e i g e n v a l u e b a s e do i lt h ec o n c e p to fs e c o n d a r ye i g e n v a l n ea n ds e c o n d a r ye i g e n v e c t o r , t h ea u t h o rg i v e st h em o d e lf o r 也ei n v e r s ep r o b l e r no fs e c o n d a r ye i g e n v a l u eo ft h e m a t r i x ，d i s c u s s e s t h ei n v e r s e p r o b l e m s o f s e c o n d a r ye i g e n v a l u e f o r a n t i s k e w - s y m m e t r i cm a t r i c e so nal i n e a rm a n i f o l d t h en e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sa n de x p r e s s i o no ft h es o l u t i o no ft h e s ep r o b l e m si sg i v e n b yu s i n gt h e s e c o n d a r y u n i t m a t r i x ，t h e i n v e r s e p r o b l e m o fs e c o n d a r y e i g e n v a l u e o f a n t i s k e w s y m m e t r i ci ss o l v e d i nc h a p t e rf o u ro ft h i sp a p e r , b a s e do nt h et h e o r yo fc h a p t e rt w o ，b ya p p l y i n gt h e o b l i q u ee l e m e n t a r yo fm a t r i x o rt h es e c o n do b l i q u ee l e m e n t a r yo fm a t r i x ，t h e a l g o r i t h mf o rs o l v i n gt h eg r e a t e s tc o n n n o nf a c t o ri sp r e s e n t e d t h u st h es o l v i n go f t h e g r e a t e s tc o m m o nf a c t o rb e c o m e sf a s ts i m p l ea n dp r a c t i c a l a tl a s t ，ae x a m p l ea b o u t t h ep r a c t i c eo f t h ea l g o r i t h mi sg i v e n i nc h a p t e rf i v eo ft h i sp a p e r , t h ea u t h o rl o o k sa h e a dh i sd i r e c t i o no ft h es t u d y w o r ki nt h ef u t u r e 1 1 1 浙江大学硕十学位论文 致谢 在论文完成之际，本人在此向所有关心我的老师、同学和家人致以最真诚的 感谢。 本文是在汪国昭教授的悉心指导下完成的。在论文完成过程中，经汪国昭老 师的耐心传授和精心指导，使我在应用数学知识分析解决问题方面收获良多。藉 此论文完成之际，对导师曾给予的学术上的指导和其余方面的关心帮助致以衷心 的感谢。 感谢论文中参考文献的作者；感谢审阅、评审、指导我的硕士学位论文的专 家、老师；还要感谢其他所有在工作和生活中予我以帮助的我的同事、朋友。 最后，对一直关心和鼓励我的妻、儿致以深深的谢意，对一直默默祝福我的 双亲致以深切的谢意。 浙江大学硕士学位论文 最大公因式求解算法和矩阵的逆次特征值问题研究 1 1 引言 第一章绪论 最大公因式求解是多项式理论中的核心部分，是一个一直受到人们关注的古 老而又始终充满活力的研究内容。从其应用角度考虑，曲线求交及光滑拼接，求 等高线以及参数曲面隐式化等是计算机辅助几何设计( c a g d ) 中的基本问题， c a g d 中大量涉及曲线的相交，而最大公因式求解计算在曲线求交问题方面起了 相当重要的作用，因而对其求解算法的研究一直是人们感兴趣的重要内容 本文的第一部分工作主要研究一元多项式组的最大公因式的求解方法，并据 此给出相应的最大公因式求解的程序设计算法和具体的程序实现。为了说明这些 方法，本章在后面首先概要介绍一下多项式最大公因式相关知识，并简单介绍一 下国内外同行的研究情况 实际问题中有很多问题可以归结为数学中的矩阵的反问题及特征值的反问 题，逆特征值问题在结构动力学、分子光谱学、结构设计、参数识别、航空工程、 自动控制等许多领域都有重要的应用。例如逆特征值方法是结构动态设计( 见 3 0 ) 和飞行器设计中的振动设计的有力工具；又比如：设计水坝，要求具有固 有频率与一定的抗震程度；再比如控制论中的黑箱问题等。正是为了这种需要， 促使了矩阵的反问题及特征值反问题的兴起，近年来，由于实际问题的需要，对 矩阵反问题特别是特征值反问题的研究成为当今计算数学中一个非常活跃的课 题。 矩阵的逆特征( 值) 问题研究的内容主要是：对给定的特征值或特征对，能 否构造出所要求的特定类的矩阵。 本文的第二部分工作是对矩阵的一类逆特征值问题进行了研究，提出了矩阵 的逆次特征值概念，讨论了线性流形上次反对称矩阵的逆次特征值问题，给出了 解存在的条件，并给出了解的通式。本章在后面将就逆特征值问题的相关知识以 及国内外同行的研究进展情况作一个简单介绍。 1 2 多项式的最大公因式概念及问题研究进展 1 2 1 多项式的最大公因式概念 浙江大学硕士学位论文 本文总是假定足是某个数域，x 是一个符号 定义1 2 1 设n 是一个非负整数，形式表达式 a n x “+ a ni x ”_ 1 + + o i l 3 , a h ，n1 ，- 一，a o k ( 1 1 ) 称为系数在数域中的一元多项式，或称数域k 上的一元多项式 数域丘上所有一元多项式的集合记为k x 1 用厂g l g g l 等符号表示多项 式 多项式中系数不等于0 的最高次数的项称为多项式的首项，其系数称为首项 系数，首项系数等于l 的多项式称为首一多项式，首项的次数称为多项式的次 数多项式厂g ) 的次数记为d e g w g ) ) 所有系数都等于0 的多项式称为零多项式，记为0 规定零多项式的次数为 一0 0 定义1 2 2 设，b l g g ) 置h 是两个多项式如果存在一个多项式 g ) e 世k 】，使得等式 厂0 ) = g ( x ) h ( x ) ( 1 2 ) 成立，我们就说g g ) 整除厂g ) 或，g ) 被g b ) 整除，记为g ( x ) s ( x ) ，并把g g ) 叫 做，g ) 的因式 定义1 2 3 设厂g l g g ) k h ，如果多项式d g ) k k 】具有以下两个性质： ( 1 ) 4 x l s ( x ) , 4 x g ( 工) ( 此时称d g ) 是厂g l g g ) 的一个公因式) ( 2 ) f ( d - 与g ( x ) 的公因式都是d 0 ) 的因式 则称d g ) 为厂g ) 与g ( x ) 的一个最大公因式 定理1 2 1 对于k 阳中的任意两个多项式，b ) ，g b ) ，在k 嘲中一定存 在最大公因式，且在i ( x ) ，g ( x ) 不全为0 时，最大公因式不唯一，它们相差 个非零常数，此时 记驴g l g g ) ) 表示首项系数是1 的那个最大公因式 最大公因式可以被推广到有限个多项式的情形 浙江人学硕士学位论文 定义1 2 4 设有任意多个多项式五g l ，工g ) e k b b 2 ) ，如果多项式 d o ) k m 具有以下性质，就被称为 g l ，丘g ) 的一个最大公因式： ( 1 ) d 0 】工0 l ，= 1 ，2 ， ( 2 ) 如果 b ) 工b ) ，f - - - 1 ，2 ，s ，那么 b 】d b ) 仍用g l ，丘g ”表示最大公因式中的首一多项式 求解多项式最大公因式的典型方法是辗转相除法 设厂g l g g ) k 1 w i ，显然只须考虑，g l g o ) 不全为0 的情形，不妨设g g ) 0 通过辗转相除得到以下式子： 厂( 为= g 。g k g ) + g ) g g ) = q ：g h g ) + 吃g ) ，l b ) = 吼g k g ) + r 3 ( x ) 一：g ) = q s g k 一，g ) + 0 ) g ) = g 。( x k ( x ) 贝4 ( 厂0 l g b ) ) = c - g l c 0 k 以求两个多项式的最大公因式为基础，给定k 上任意s 个n 次一元多项式 b l f _ l j 2 ，s ，经过s 1 次辗转相除法，即可求得b l ，正0 ) ) 1 2 2 多项式最大公因式的问题研究进展 辗转相除法的缺点是运算繁琐、复杂、易错，从算法实现角度考虑，该方法 存在存储量大，运算时间长，运算速度慢等不足 吴文俊教授建立的吴消元法 1 9 , 2 0 j 是处理多项式方程组求解问题的著名方法， 该法也是我国数学机械化研究领域中的核心算法。目前该法已被得到广泛的应 用。中国科学院系统科学研究所数学机械化研究中心的王定康博士开发了在 m a p l e 环境下运行的w s o l v e 软件包，该软件包对吴消元法进行了计算机编程实 现。吴消元法为多项式的最大公因式求解提供了有效的手段。 近年来，国内不少同行不断在最大公因式求解问题上提出新的处理方法 张三元，汪国昭等在文献”1 中给出了一种并行算法，比辗转相除法具有存储 浙江大学硕士学位论文 量和运算时间均小等特点 包桐桢，蒋忠樟等在文献b 中提出了用矩阵的初等变换来求多项式晟大公 因式的方法，其实质是利用多项式矩阵的初等行、列变换求多项式矩阵的一阶行 列式因子，相比于辗转楣除法，该法简便了许多，但在求解过程中，仍然是多项 式的运算 刘国琪在文献晤3 中通过引入给定多项式的系数矩阵表示，提出了一种利用 矩阵的初等行变换求解多个多项式最大公因式的方法，该方法摆脱了求解过程中 的多项式运算，而单纯运用数字矩阵的初等行变换，直观明了，简单易行 本文作者郁金祥在文献”，7 3 中，在运用矩阵的初等行变换求解最大公因式的基 础上，通过引入矩阵的移位变换概念，提出了用纯数字式矩阵求解最大公因式的方 法 本文在上述研究的基础上，进行了更进一步的研究，第二章中引入了矩阵的 第一、第二斜消变换概念，并基于此，提出了利用第一、第二斜消变换求解多项 式的新方法，给出了严格的证明和具体的应用实例第四章中给出了上述方法的 算法实现和具体的程序代码 1 3 矩阵的逆特征值问题及其研究进展 1 ，3 1 矩阵的逆特征值问题 用r 表示所有h r l e l 阶实矩阵的集合，o r “。表示所有 阶正交矩阵全体； a + 表示a 的m o o r e - p e r t r o s e 广义逆；j 。表示n 阶单位矩阵；s r ”5 表示n 阶实对 称矩阵的全体；r a n k ( a ) 表示爿的秩： 下面在r 中引入内积 定义1 3 1 设a ，b r ，称护( 爿7 b ) 为a ，b 的内积( 这里“t r ”表示方阵 的迹) ，记为( 爿，曰) ，即0 ，b ) = f ，0 7 占) 。 由矩阵的内积引入范数概念 定义1 3 2 设z 足，称( 万萄= b 0 7 4 萨为a 的f r o b e n i u s 范数，记为 。 显然，r 关于f r o b e n i u s 范数构成一个完备的内积空间。 再介绍m o o r e p e n r o s e 广义逆概念 渐江大学硕上学位论文 定义1 3 3 1 s l 设4 是n m 矩阵如果m h 矩阵g 满足以下条件： ( 1 )爿g a = a ( 2 )g a g = g ( 3 ) 0 g r = a g ( 4 ) ( 础r = 洲 就称g 是4 的一个m o o r e - p e n r o s e 广义逆，简称为m - p 逆。 定理1 3 1 ”1 设a 是h m 矩阵，则其m o o r e p e n r o s e 广义逆是存在而且唯 o 记矩阵爿的m o o r e p e n r o s e 广义逆为“+ 。 我们建立如下数学模型 问题1 已戋口x r ，b r ，scr “。4 ，a + r “。”，令 工= 缸sl l i 删一b l l = m i n 求a b l ，使 l i a l 缸0 = 艇一4 0 这就是矩阵的反问题讨论，显然，不同的集合s ，给出不同的反问题。 问题2 已圭口爿r “。“，b r ，s c r “。“，a + r “。”，令 上= 扛s l i l , 。一丑l = 血n 对给定的z ：r “，a = a i 口g ( 4 ，五，以) r “， 求a ，使 i t a x ：- x ：a i l = r a i n 这就是矩阵的逆特征值问题，同样的，不同的集合s ，给出了不同的矩阵的 逆特征值问题。 1 3 2 矩阵的逆特征值问题的研究进展 关于逆特征值问题的研究已取得了许多有意义的成果，下面列举一些这方面 的成果。 孙继广、张磊分别在文献 3 1 、文献 3 2 】中讨论了一类对称矩阵的逆特征值 问题： 胡锡炎、谢冬秀等在文献【3 3 ，3 4 】中讨论了一类双对称矩阵的逆特征值问题； 浙江大学硕上学位论文 谢冬秀、张磊在文献 3 5 1 中讨论了反对称矩阵的情形； 盛炎平在文献 3 6 忡讨论了双反对称矩阵的情形； 寥安平在文献 2 5 1 0 0 讨论了实对称半正定阵的情形； 何楚宁在文献 3 8 1 中讨论了实对称亚半正定阵的情形； 周富照等在文献 3 9 ，4 0 中讨论了一类对称正交对称矩阵的情形 王福义等在文献 4 5 1 中讨论了次对称矩阵的情形； 戴华在文献 4 3 1 中讨论了线性流形上的逆特征值问题， 浙江大学硕士学位论文 第二章多项式最大公因式求解的矩阵方法研究1 2 1引言 问题：给出数域茁上关于文字石的n 铆2 ) 个多项式，如何求其最大公因式? 对于上述多项式的最大公园式求解问题，是多项式理论中的核心问题之一。 传统的方法是采取分步求解法，即每次针对两个多项式，用辗转相除法求出其最 大公因式，逐步进行下去，最后求出所需结果。例如，欲求 ( 功， ( x ) ，六( x ) 的 最大公因式，可分为二步，先求出五( x ) ，厶( 砖的最大公因式d ( 力，再求矗g 铋b ) 的最大公因式。显然这种处理运算繁琐、易错，尤其在多项式个数h 较大时，更 是如此。 蒋忠樟、包桐桢通过用x 一矩阵方式来表示给出的n 个多项式，采用x 一矩阵 的初等行变换来求解多项式的最大公因式，相比于辗转相除法，该法简便了许多。 该法的结论见下面定理。 定理2 1 1 设x 一矩阵 f g ) 1 4 b ) = f ； i ，经过一些行初等变换后得到曰g ) = l ：o x ) j d g ) 0 o ，那么 d ( x ) 是多项式 g l ， 0 ) 的一个最大公因式。 例2 1 1 设厂g ) = x 4 + 2 x 3 一x 2 4 x - 2 占g ) = 工4 + 工3 一工2 2 x 一2 都是有理数域q 上的多项式，求，g 的最大公因式驴b ) ，g 【呦 解瞄x 4 + 2 ；x ，- - x 2 并 一 2 x 。3 - - x 忆2 - - 虮2 一p + x 2 - - ：4 ，x 以 一( 一姜剖一p ) 故( 厂9 0 ) ) = 工2 2 刘国琪通过引入纯数字形矩阵来表示给出的n 个多项式的方式，改进了上述 本章内容的相关研究成果已发表在数学的实践与认识( 2 0 0 5 年第1 1 期) 上 7 塑垩查兰雯主兰篁笙壅一 利用初等行变换求解多项式最大公因式的方法。还是以上述例越为例，说明该万 法。在说明之前，首先介绍多项式组的纯数字形矩阵表示概念。 定义2 1 1设上( 曲= a l l x “+ 口f 2 x “+ + d 。l x + a h ，( i = l ，2 ，m ) 是 数域上的一元多项式，称矩阵爿= k ) 爪。为与多项式组工( f ) ，i = 1 ，2 ，m 桂l x 寸 应的系数矩阵。 按照定义，给定一组多项式总可写出唯一的与之相对应的矩阵，反之亦是a i 喟f f l ( x ) ，厶o ) ，厶( x ) ) 表示多项式z ( x ) ，厶( x ) ，厂m ( z ) 的最高次项系数为 1 的最大公因式。 下面用纯数字形矩阵表示法来演示例2 1 1 的求解过程。 解m ： ：菊一0 二苫? 爿 型玛f 二，2 4 2 鸟( 。2 0200 - - 10 一1 2 h 4 0 苫 l 一1jiu 屿f 二，1 - - 4 - 。2 马( ! 。1 020 。2 _ 0 2 l 一1 0 jl l 卫玛( 二。：习乌( ：。0 - - 。2 故c 厂g g ) ) - - 7 - - x 2 2 。 注：上述过程中，执行左对齐操作时，若出现最后一列全为零，应及时划去 该列。 本文作者在文献 6 ，7 1 中，利用多项式的相关性质，提出了右移位变换概念， 从最后一列消元入手，得到了求解多项式最大公因式的一种方法。仍以上述例题 为例说明该方法。 解n ：菊一二：i 习 玛f o 。11 1 1 2 二鞠2 一( 0 0 1 1 二2 二27 0 i1 一一一 l 一一 一f ：三二约一 ? j 三1 2 浙江大学硕士学位论文 上马( ：。0 二i ) 一f t , 0 1 0 0 2 0 ) l l2 jj 故( 厂g l g g ) ) = x 2 2 。 注：上述过程中，执行右对齐操作时，若出现首列全为零，应及时划去该列。 详细的过程可以参见文献【6 ，7 】。 本章以下章节中，在上述研究基础上，展开了更进一步深入的探索研究。首 先引入第一、第二斜消变换概念，据此得到了用第一、第二斜消变换求解最大公 因式的方法。 下面先介绍矩阵的初等行变换及矩阵的斜消变换概念。 2 2 矩阵的斜消变换 2 2 i 矩阵的初等行变换 先介绍矩阵的初等行交换概念 定义2 2 1以下三种变换称为矩阵的初等行变换 i )交换矩阵的两行 2 )用一个非零数乘矩阵的某一行 3 ) 将矩阵的某一行乘上一数后加到另一行上 为书写方便起见，引入如下记号： 记交换第i 行，第行的初等行变换为岛； 记第七行乘非零数c 的变换为d 。如) ： 记将第衍f 乘以数c 加到第j 行的变换为l ( c ) 2 2 2 矩阵的第一、第二斜消变换 现引入矩阵的第一、第二斜消变换概念 定义2 2 2 设爿= ( 口f l 。是数域世上的珊 矩阵，若一的第珂f 自左向 右第一个不为零的元素为“。+ 1 ，第行的第一列元素不为零( i ) ，则称将第f 行的h s 个元素：口“。f 。：，口m 乘以数c 斜加到第，行元素：。“，口”一， 上的变换为第f 行到第- ，行的第一斜消变换，记为t l ；i ( c ) 。 规定：用第一斜消变换化简矩阵时，化简所得矩阵的前若干列元素全为零时， 应及时消去这些列再作变换。于是反复用第一斜消变换可达到简化矩阵的目的。 9 浙江大学硕_ 卜：学位论文 注1 ：当s = 0 时，皿0 ( c ) 相当于矩阵的第三种行初等变换咒( c ) 。 定义2 2 3 设爿= k l 。是数域k 上的州h 矩阵，若一的第f 行自右向 左第一个不为o 的元素为d 。，l s 墨”，第j 行的第n 列元素a j n 不为o ( j ) ， 则称将第f 行的s 个元素：口n ，d 。乘以数c 斜加到第行元素：a 。+ 1 ，一，a 向上 的变换为第i 行到第，行的第二斜消变换，记为豫扩( c ) 。 规定：用第二斜消变换化简矩阵时，化简所得矩阵的后若干列元素全为零时， 必须及时消去这些列再作变换。于是反复用第二斜消变换也可达到简化矩阵的目 的。 注2 ：当s = n 时，豫：_ ( c ) 也相当于矩阵的第三种行初等变换( c ) 。 下面兹举一例说明上述这种变换 例2 2 1 用第一或第二斜消变换化简短阵 r 120 0o 、 o l1o oi l o o12 1 j 争 2 3 利用斜消变换求解多项式最大公因式 为得到利用斜消变换求解多项式最大公因式的相关定理，先介绍几个引理 弓i 理2 3 1设，( x ) = 口n 工8 - 1 + 口i 2 x 。一2 + + a f ，。一1 x + a m ，( f ；1 ，2 ，。一，m ) 是 数域k 上的m 个一元多项式，则有 ( 1 ) ( x ) ，z ( 工) ，f j ( x ) ，厶( x ) ) = ( x ) ，f j ( x ) ，z ( 砷，厶( x ) ) ( 2 ) 0 ) ，斫( 工) ，厶( z ) ) = ( x ) ，f a x ) ，l ( x ) ) ( c 0 ( 3 ) ( 工) ，( x ) ，乃( n 厶( x ) ) = ( 工) ，l ( x ) ，甜5 ( x ) + ( x ) ，厶( 工) ) ( 其中c e k ，s 为非负整数) 弓f 理2 3 2 盯1设，( j ) = o i l x ”一1 + 口。2 x ”2 + 一+ d f ，。一1 x + a 。，( i = 1 , 2 ，m ) 是 1 0 一 一 浙江大学硕士学位论立 数域k 上的m 个一元多项式，其中多项式；( x ) = x k g ，( z ) ，这里1 i m ，k 为 非负整数，其余多项式中存在某个多项式f j ( x ) 的常数项不为0 ，这里j i ，则 抚( x ) ，工( 彳) ，f j ( x ) ，厶( x ) ) = 戗( x ) ，g 。( x ) ，f i ( x ) ，厶( x ) ) 。 由引理2 3 1 、引理2 3 2 可以得到如下结论 定理2 3 1 设，( x ) = a i l 工4 _ 1 + a i 2 x “一2 + + a i , n - i x + 口m ，( i = 1 ，2 ，一，m ) 是 数域世上的m 个一元多项式( 至少有一个常数项不为o ) ，a = 也l 。为与多项 式工( 曲，i = 1 , 2 ，m 相对应的矩阵。对4 施行矩阵的行初等变换b ，d i ( c ) 以及第 一或第二斜消变换不改变与其对应的这组多项式的最大公因式。 证明 由引理l 的( 1 ) 、( 2 ) 易知，对a 施行矩阵的行初等变换0 ，q ( c ) 不改变与其对应的这组多项式的最大公因式。 下面证对爿施行矩阵第一斜消变换的情况。 对a 施行一次第一斜消变换z 致( c ) 后，与所得矩阵相对应的多项式组为 _ ( 功，工( x ) ，蕊5 z ( x ) + ，( z ) ，厶( x ) ，由引理1 的( 3 ) 知定理成立。 再证对爿施行矩阵第二斜消变换结论也成立。 设工( z ) = 工5 璺( z ) 其中1 i m ，s 为非负整数， ( 砷的常数项不为0 ，其中 1 i ，m 且，i 。现对彳施行一次第二斜消变换t r i i ( c ) 。 首先考虑j = 0 的情形，施行变换后所得矩阵的相应多项式组为： 一( 工) ，z ( z ) ，啊0 ) + ( 曲，厶( x ) ，由引理l ( 3 ) 显知定理成立。 再考虑s 0 的情形。设施行变换后所得的矩阵是8 ，则有二种情况出现： ( i ) b 的第n 列元素不全为0 ，则占所对应的多项式组是 ( z ) ，x5 9 f ( x ) ，e g f ( x ) + 厶( 砷，厶( x ) ，由引理2 得 c 一( j ) ，x s g ；( x ) ，c g 。o ) + 乃( z ) ，一，：( 工) j = ( x ) ，一，g ，( x ) ，一，e g ；( 工) + ( j ) ，一，f a x ) j u ( x ) ，g i ) ，一( z ) ， ( z ) ) = ( z ) ，f a x ) ， ( z ) ，厶( x ) j 浙江大学硕十学位论文 故定理成立。 ( i i ) b 的第h 列元素全为0 ，此时设b 的自右向左元素全为0 的列共有k 列( 自 然k s ) ，则按照第二斜消变换的定义规定，应消去b 的自右向左元素全为0 的 这是列，所得的矩阵设为否。 下欲证百所对应的多项式组的最大公因式等于a 所对应的多项式组最大公 因式。 设b 所对应的多项式组为：g ，( j ) ，工”g 。( z ) ，g i ( x ) ，g 。( j ) ，这里有关 系：，( x ) = x g 。( j ) ，1 ，蔓m ，f ，c g ，( x ) + f j ( x ) = z “g ，( x ) ，而且毋 ) 的 常数项不为o 。当k o ，1 f _ ，则存在4 a s r 4 。“使 a x l = b l ( 3 2 ) 当且仅当矸b 1 = 一钟x l ，b 。= e 珂x 。且( 3 2 ) 解的一般表达式为 浙江大学硕士学位论空 爿= b 墨一慨z j ) t 0 。一五x i ) + u ：g u j ，v 6 a s r 枷一咿”n ，v g a s r p ”- 引理3 3 3 “设x ，b r “，且x 有奇异值分解为 x = f n 1 x = l 1 l oo 其中，= ( ，) o r 肚”，= ( - ， z ) d r ， 划蛾分j 莓) ，p o 1 姚r 7 令锈2 志1 g 歹织 m = 0 。) r “， 则使得 i i 爿x 一日| | = m i n ，a a s r “ 的通解为 爿：f f 。+ 暇7 璺一掣占7 ) 1 w 口1 e k ， l，2 1 b n l 一a 2 2j 其中a ，a s r ( m ) 3 3 2 理论成果 为解决问题p ，首先我们有如下结论 定理3 3 1 给定b 1 ，x 1 r “，x 。的奇异值分解如( 3 1 ) 所表示，则任 取a s ，a 可表示成 彳= 曰。x ? 一，。d ? ) t j 。i n x ，x i ) + j 。u ：c u ：， ( 3 3 ) 其中g a s r ( 一 k ( 月一1 ) 为任意的反对称矩阵。 证明 v a s ，有，。a a s r “”，又j 。是正交矩阵，利用f r o b e n i u s 范数对正交矩阵的不变性可得： 恢肘。- j 。b 。1 | = i l 埘一b 1 1 1 再由于对于线性流形j ，x 。，b 。满足条件：x j j b 。= 一占j 六。，b ，= b ，x ；x ，依 据引理3 3 2 可得 ja = j b x 1 + 一p 。b ，x ? ) 1 ( ，。一x x 1 ) 十u ：g u j ， 浙江大学硕士学位论文 其中g a s r ( ”一 m 一w ，因此( 3 3 ) 式成立。 现对问题p 有如下结论 定理3 3 2 对给定的工：r “，a = d i a g ( 2 i j 一，a 。：) r 吣5 ：，ue o r “”为 满足x ，的奇异值分解式( 3 1 ) 的矩阵 训耻暇聃。x 驯1 2 ， 曰：( ： = u 7 ( r 2 a - j b a x ? x ：) = l ( u u f j ( e x 2 ：a a 一- j j 。b 8 i 。x x ；x r 2 ：习 设x 。的奇异值分解为 如= 矿r ： q 7 其中= ( ， ) 4 一m “一，q = ( q 1 ，q z ) c 璃3 “2 ， r 2甩一一r zr 2k 2 一r 2 _ ：r a n k ( x 2 2 ) ，2 = d i a g 0 1 ，0 2 ，日，2 ) p ， 0 , 1 茎i ，2 ， 记妒口2 百丽1 1 f ，2甲= 饥) r 啪 4 ，= 蜀鼻以佃。x ? ) t ，。( ，。一x 。x ) 4 ：= t * ( w z t b 2 2 q i z 2 - e 2 q j 曰丢一 t 廿2 t 2 形7 ， 则0 崩：一j x ：人j | = 1 t l i n 在s 上有解，且其解集为i = 4 ：4 + 以巩4 嵋+ 以马r 。t i e ：彳蒯”1 4 。”1 一。) ( 3 ，4 ) 证明由定理3 3 1 ，s 中的矩阵具有形式 爿：层x j i ，。b ，x ) 丁，。0 。一j l x j ) + ，。u ：g u ：，其中g a s r h 一1 弦一1 为任意的反对称矩阵。利用f r o b e n i u s 范数对正交矩阵的不变性可得 l l a x ：一j x ：a ll 2 删：一j 。u 。x ：w 2 9 浙江火学硕士学位论文 帆a x ：一x ：a | | 2 ，b 。x ：x 2 一b n b 。x ：1 心，一x l x ：? i ) c 2 + u 2 g 哦x 2 一x z a 。 2 p 磷j b 篙麓( 浆第u ：x 骠卅以a 斯 u j p 。工? 归：+ g u j 爿：一 ：a 州 2 粉c ，。即? 弦：一【，jc ，。e i 炖_ 州x ：一v ? x ：a + i p j c ，。b 。jk ：+ g u t x ：一u ：x ：a 6 2 = l 盼c ，。目舛弦：一【，j ( ，。b 。x 0 。一。矸皿：一u ? x ：2 + i l c x ：一8 ：l | 2 则i 阻五一以五删= m 抽当且仅当i l g x ：一b 2 2 i = r a i n 由引理3 。3 。3 知，使得i i ( 避2 一| i = r f f m ，g e a s r ( 。“一 的通解为 g = l - f * ( 啊r b 孵z 2 q t z 以2 - z ? z q r t 砭吲戈 一o t ，b r 形b e 卜其忆础忙脚) i时：9 ；1：j 由此可知 i 斯：一，。x 2 删= m i n 在s 上有解，且其解集为j = 扛= 4 + 五心晖+ 五呸最孵谚恒彳5 霄4 一t 。h 刊 定理3 3 3 对给定的z 2 r 础2 ，人= d i a g ( 2 l ，k ) r 协也 允= ，。置a 在s 上有解的充分必要条件是给定的x ，a 满足条件： 曰：t ：盖：= 一z 丢曰：，日：= 占2 2 工刍j ，2 2 ( 3 5 ) w ，。b ，x i k w 蜀矸) r ( ，。一。冒k u r ，x 2 a = o ( 3 6 ) 这时，a x 2 = j 。2 a 在s 上的通解可表为 一：4 + 以址b ：或一k 瓦) t 以r 五：磁妞+ u ：e 时w ，ee 一时一t ) ( 3 7 ) 证明由定理3 3 2 证明可知 1 l a x ：一，。z ：a 旷 = i ，j ( j 。置? 弦：一u j ( ，。马x j ) t o 。一x ，x i 弦。一u ：x ：叫1 2 + l l g x ：z 一曰娩1 1 2 因此，使得且y 2 = j 。：a 的充分必要条件是 浙江人学硕士学位论文 u j p 。b 。x ? k ：一u j 0 。置研) t 也一x 。f 弦，一w 五a = 0 ，g x 2 ：= b 2 ： 又由引理3 3 2 知，使得g 墨：= 呸：，g a s r ( n - 硒一 ) 的充分必要条件是 且这时g b 矗z n = 一z 三口：，b 2 2 = 曰2 2 盏爿2 2 b ：并乏一( b 2 2 z 立) t o 。一。一x 2 2 鼻矗归j + e ：孵，e ：ea s r ( 4 一t t 硒一n t 因此丘墨= 以x 2 a 在s 上有解的充分必要条件是给定的x 2 ，人满足条件( 3 5 ) ( 3 6 ) ，且这时通解可表为( 3 7 ) 。 2 1 浙江大学硕士学位论文 第四章多项式最大公因式求解的算法实现 4 1 引言 本章依据第二