多项式最大公因式最优求法的探讨.doc

唐山师范学院本科毕业论文题 目 多项式最大公因式最优求法的探讨学 生 陈 静 莎指导教师 孙 秀 娟 讲 师 年 级 2009级专 业 数学与应用数学系 别 数学与信息科学系 唐山师范学院数学与信息科学系2013年4月16郑重声明 本人的毕业论文（设计）是在指导教师孙秀娟的指导下独立撰写完成的如有剽窃、抄袭、造假等违反学术道德、学术规范和侵权的行为，本人愿意承担由此产生的各种后果，直至法律责任，并愿意通过网络接受公众的监督特此郑重声明毕业论文（设计）作者（签名）： 年 月 日 目 录标题 多项式最大公因式最优求法的探讨1中文摘要1引言11 基本概念12 最大公因式的求法521 辗转相除法522 因式分解法723 多项式组合法824 等效变换法1025 矩阵初等变换法133 优劣性比较194 结束语22参考文献23致谢24外文页25多项式最大公因式最优求法的探讨陈静莎摘 要 本文介绍了多项式最大公因式的几种常规求法，如辗转相除法、因式分解法、多项式组合法、矩阵初等变换法、等效变换法等，对这些方法进行了详细的证明，由这些方法得出了求最大公因式的一些性质，通过讨论，文章浅析了某些具体多项式应采取的简便的求最大公因式的求法此外，本文通过具体实例对最大公因式的各种求法的优劣性进行了比较，进而探讨出某些具体多项式最大公因式最优的求法关键词 最大公因式 辗转相除法 因式分解法 组合法 初等变换前言多项式理论不仅是中学代数的主要内容之一，也是高等代数的的重要组成部分，它在数学的理论与应用中都有十分重要的意义，而求最大公因式在多项式理论研究中又占有显著地位一元多项式最大公因式的解法，在各种高等教材中已经做了许多基本方法的介绍，但在我们的实际应用中，这些基本方法存在运算过程复杂，计算量大等缺点所以，探讨求最大公因式快速、准确、简便的方法就尤为重要多项式的最大公因式作为多项式理论中的核心部分，是一个一直受到人们关注的古老而又始终充满活力的研究内容多项式的最大公因式的常规求法有辗转相除法、因式分解法和组合法，前人对这些求法及其简单应用都做了较深入的研究而初等变换求法作为计算最大公因式的一种简便方法，克服了传统的辗转相除法及因式分解法带来的繁冗性和复杂性初等变换在几何和矩阵理论的研究中有广泛的应用，因此讨论其性质及其应用具有重要意义1、基本概念设是一个数域，为数域上的一元多项式环，有如下定义和定理：定义 1 设、是中的两个多项式，如果满足是、的公因式，且、的公因式都是的因式，则称多项式是、的一个最大公因式 定理 1 对于中的任意两个多项式、，在中存在最大公因式，且可表成、的一个组合，即存在多项式、满足 证明：（1） 假设、有一个为零，不妨设，则可知是一个最大公因式，显然存在多项式，满足（2） 假设、全不为零，利用带余除法用除，得到商，余式，此时：若，可得，即是一个最大公因式，可求得多项式，满足式；若，就用除，余式，若，可得，即是一个最大公因式，可求得多项式，满足式；若，就用除，得到商，余式，以此类推，所得余式的次数不断降低，即 但的次数有限，因此在辗转相除有限次后，必有一余式为零，于是可得： 由（1）可知是、的一个最大公因式下证存在多项式、满足式，事实上，变形上面倒数第二式有，同理可解得、将解得余式代入上面的运算式，并逐个消去，即可得定理1的式证毕2、主要方法及证明由定义1可知，若、是、的两个最大公因式，则必有，而又由整除的性质可得：，其中是非零常数由此有：两个不全为零的多项式的所有最大公因式均只相差一个非零常数倍，那么，根据此性质，首项系数为1的那个最大公因式是唯一确定的，且记为现约定下文所提及的最大公因式均指首项系数为1的那个最大公因式21辗转相除法由定理1的证明可以很容易得到求最大公因式的一种有效方法辗转相除法例1 在有理数域上，求多项式、的最大公因式，其中表达式分别为， 事实上，多项式的最大公因式只相差一个非零常数倍，因此在计算过程中可以适当的用某一常数乘以多项式的各项系数，从而化简计算量且不改变最大公因式的值，因此利用辗转相除法：解：用除得：商，余式，再用除得：商，余式，再用除得：商，余式，由此可得：是、的一个最大公因式，即：例2 多项式、同上面的例1，求多项式、使其满足定理1的式解：利用例1的计算过程扩大某一多项式的倍数，此时可计算出多项式、使其满足定理1的式，且可得如下等式： 其中 ，同例1，由有： 且代入得 即 又知 ，将上式化简可知满足的项式、分别为，但是，将、代入进行检验得：所以，此时计算的多项式、并不满足定理1的式事实上，在计算过程中若不扩大某一多项式的倍数，经过计算有： 由，可得： 化简可知：满足的多项式、为： ，分析：若用例1计算过程所得商和余式求多项式、，那么所得结果将错误，这是因为在例1的求解过程中，为了简便运算而将多项式扩大了某一常数倍，因此应按照辗转相除法的一般步骤进行求解现考虑个多项式的最大公因式定理2 中的任意个多项式有 ，其中2分析：容易推出，是多项式的一个最大公因式，那么与多项式的最大公因式也是多项式的最大公因式这样，由于两个多项式的最大公因式总是存在的，所以个多项式的最大公因式也总是存在的，并且可以累次应用辗转相除法来求出证明在此不再赘述注意：与两个多项式的情形一样，个多项式的最大公因式也只有非零常数因子的差别我们约定，个不全为零的多项式的最大公因式指的是最高次项系数是1的那一个那么个多项式的最大公因式就是唯一确定的有计算过程可见，当求三个以上多项式的最大公因式时，运用辗转相除法计算相当繁冗并容易出错；除此之外，若又要求将表示成的形式时，此时，在辗转相除法的过程中不能用一个非零的常数去乘以除式或被除式，这就使得计算更加困难22 因式分解法在高等教材中已明确提出，利用多项式的标准分解式可以很快的得到它们的最大公因式又因为多项式的最大公因式不会随着数域扩大而发生改变，所以尽管多项式在不同的数域上标准分解式不尽相同，但这不影响多项式的求解因此只考虑在中，以两个多项式、为例，设、的标准分解式分别为： ;其中、分别是、的首项系数，是两两不等的首项系数为1的不可约多项式，是非负整数，则 这里 因式分解法可推广到个多项式的情形，其方法与两个多项式的情形相同，这里就不再赘述例3 设，用因式分解法求多项式，的最大公因式解：将，进行因式分解，可得在有理数域上的标准分解式分别为： 故可得： 例4 设，用因式分解法求多项式，的最大公因式解：将，进行因式分解，可得在有理数域上的标准分解式分别为： 故可得： 例5 设，为两个非零多项式，证明：存在自然数，使任意的大于的两个自然数，都有证明：设，若，则结论显然成立若，则令由例3 、例4可知，对于因式分解法的前提是，必须求出多项式的标准分解式事实上，并不是所有的多项式都能进行简单的因式分解，就算可以因式分解其过程也是相当复杂，而一般没有一个切实可行的方法对多项式进行因式分解因此，求最大公因式一般不用此种方法，它提供的方法主要是用于理论证明，不用于求解具体的多项式的最大公因式，更不用说求出满足定理的多项式、23 多项式组合法先给出定理1的三个简单推论：推论1 定理1 的逆命题：对任意的多项式、，不一定是多项式、的最大公因式此命题为假命题例如：多项式，可知、互素，此时对任意的，显然不是、的最大公因式推论2 多项式为、的最大公因式，则推论3 对任意的多项式、的任一个组合是、的最大公因式的倍式由上两个结论知、的最大公因式一定是、的组合式由此可得：定理3 在辗转相除法运算式中，都是、的最大公因式的倍式证明：利用辗转相除法计算最大公因式可得如下运算 即得： 将上式运算变形得： ，它是、的组合则 是的倍式将代入运算式得： 由等式可知 是的倍式以此类推： 都是、的最大公因式的倍式证完例6 在有理数域上，求多项式，的最大公因式解：根据题意计算，可得出由推论3可知：是最大公因式的倍式，而1又在有理数域上的因式只有一种可能，即常数，所以所求的最大公因式为：例7 在有理数域上，求多项式、的最大公因式，其中解：由题意可得：其中余式为 由艾森斯坦判别法知：是有理数域上不可约多项式，则的因式只能是或者是常数，用试着去除可知不整除所以、的最大公因式应该是常数，即为：由以上两个例子可见：在辗转相除计算过程中若发现有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得到最大公因式，并且当、的次数很高时用此方法较为方便若是求个多项式，的最大公因式时，有如下定理：定理4 设中的多项式，在辗转相除法所得运算式中，都是，的最大公因式的倍式此命题直接为定理3的推广，不再赘述证明过程由以上讨论结果可知，当求个多项式的最大公因式时，这种方法相比于辗转相除法两两求最大公因式的运算量已经大大减少，但是这种方法只适用于余式能较快因式分解的情形，故此法具有一定的局限性；而且当=2时，求多项式、满足定理1的式，此方法却不适用24 等效变换法定义2 设，称矩阵为、的矩阵，记作则与等效，从而、的最大公因式，这就是等效法求解最大公因式，该方法虽然克服了辗转相除法的来回计算在求解有了很大的进步，虽然该方法也可以推广到求个一元多项式的最大公因式，但是美中不足的是，它没有求解出满足：成立的任给一个矩阵，则显然存在多项式、，使定义3 设， ，若，则称与等效，记作定理5 若矩阵经过三种初等变换变成，则与等效证明： 若变换的两行得到，则，显然，所以与等效若的第一行乘以加到第二行得，则，由最大公因式的性质，所以与等效若的第一行乘以非零数得，则，又，所以与等效定理6 若， 其中，则与等效证明：由条件，则，所以因为，则与互素，故，即与等效例8 已知，求分析：此题只求和的最大公因式，并没有要求求解出满足：的、解：所以 25 矩阵初等变换法基本概念本文以表示数域上的一元多项式环定义7 以中的一元多项式为元素的矩阵称为多项式矩阵设的个一元多项式，规定符号：表示这个一元多项式的最高系数为1的最大公因式，则有以下性质：性质性质性质多项式矩阵的初等变换：多项式矩阵的初等变换;矩阵的某一行（列）乘以非零常数;矩阵的某一行加另一行的倍，其中是一个多项式多项式矩阵的性质：性质 每个可逆的多项式矩阵都可以表示成一些多项式式初等矩阵的乘积；性质 对一个多项式矩阵施行初等变换，不改变每个列向量的多项式的最大公因式；性质 设为多项式矩阵，则存在可逆的多项式矩阵，使得为阶梯型矩阵综上可得：交换两个多项式的位置，不改变其最大公因式；将某一多项式乘以一个不为零的常数，不改变最大公因式；将某一项的倍，加到另一个多项式上，不改变其最大公因式，对比代数理论的矩阵的初等变换，上述性质恰好都满足主要定理及证明定理7 设，其中，且可逆，若其中是首项系数为1的多项式，则有，且，使成立证明：对于，存在，使得令，其中分别为的首项系数，则有 所以，且，使成立定理8 是任意个多项式，若经过矩阵的适当初等变换，可以变换为 (其中是阶单位矩阵)证明：若时，则，已有的形式不全为零时，则必有一个次数最低的多项式，不妨设为，对分别乘以一个适当的多项式，消去的每个最高项，这时矩阵的第一列变为，其中当时，其中不全为零时，继续重复因为次数都是有限的，所以经过有限次后，必然能够出现矩阵b中第一列只有一个元素，其他元素全为零，此时即有，其中上述过程用矩阵的初等变换表示为：定理9 定理8中满足证明：设，由于对矩阵的初等变换相当于在它左边乘上对应的初等矩阵，所以，存在可逆矩阵，使得且于是，比较对应位置的元素得到：最大公因式的矩阵初等变换法将矩阵，经过初等行变换化为矩阵，则是的最大公因式，且应用举例例9 求和的最大公因式，其中， 分析：此题只求和的最大公因式，并没有要求求解出满足：的、，而是对于两个多项式来说的，因为我们可以用多种方法进行求解，在此，运用矩阵的初等变换法进行求解解：所以例10 设，求解： 所以， 例11 ，求，并求出、使得分析：此题求解的是，并且还要求解满足的、，此时若用辗转相除法、因式分解法、多项式组合法、等效变换法、矩阵斜消变换法就非常的困难了，所以最佳的选择就是矩阵的初等变换法解： ，且有，使得成立对于求解此类多项式我们最佳方法就是矩阵初等变换法，它就是利用矩阵的初等变换，一步一步求解，而且同时求解出满足：的最大公因式系数三、优劣性比较由上文我们已经总结出5种求多项式的最大公因式的有效方法，当多项式个数、次数不同时，各个方法中均有其使用条件限制或者使用范围，现以一下两方面为例进行探讨，如下表所示：方法简便求最大公因式的条件限制或使用范围能否求解出，满足+=辗转相除法多项式次数较低，并且多项式的个数不超过三个能，但是其求解过程不能用一非零数乘以除数或者被除数因式分解法要求题中所给多项式在数域上均能分解，利用因式分解法必须求出多项式的标准分解式否多项式组合法有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得到最大公因式，并且当、的次数很高时用此方法较为方便多项式表达式较为特殊，个数少，最后所得组合简便否矩阵的斜消变换法将多项式的系数写成对应矩阵的形式，且系数较简便计算否矩阵的初等变换法表示成多项式矩阵或者对应系数矩阵的形式均可能，但是要求表示成矩阵的形式进行初等变换通过上述表格两方面的简单比较可以探讨出每一种方法均有其优缺点，现将探讨所得简单结果列表如下：方法优点缺点辗转相除法适合于所有形式的多项式，具体的可操作性比较强，在任何数域上都具有固定的格式求解，求解步骤也固定，并且能直接求得多项式，计算过程比较繁琐，当所求多项式个数较多、次数较高时，计算量相当的大，书写过程繁冗很容易出错，尤其是在，的求解过程中不能用一非零数乘以除数或者被除数因式分解法形象直观，看上去整齐，运用的原理比较简单，且容易看懂要求题中所给多项式在数域上均能分解，利用因式分解法必须求出多项式的标准分解式，所以此方法只适用于能够因式分解的多项式，对其他的多项式时失效，另外，此方法也不能直接求出， 多项式组合法不用将辗转相除法进行到底，若有一个余式能较快的因式分解，就可以用此分解式中的不可约因式除、而得到最大公因式，并且当、的次数很不是很高时用此方法较为方便，运算量大大减少当多项式不是特殊形式，并且次数很高时，或者余式都不能分解时，此方法就不能快速求解出最大公因式，而且此法也不能直接求出， 等效变换法此方法不论多项式次数高与低都适合，计算过程也简便，不容易出错对于多项式的系数特别大的计算式就不简便了，此方法的局限性是一般只适合求解两个多项式的最大公因式，而且此方法也不能直接求出， 矩阵的初等变换法结合多项式最大公因式的定义与矩阵的运算性质，不但可以求多个多项式的最大公因式、计算过程简单，而且可以直接利用初等变换求得， 在多项式矩阵的运算过程中，也容易出现计算错误：若写成对应系数矩阵的形式时，不能直接求得， 通过上述表格所对比的结果我们可知在求解多项式最大公因式时，应根据实例中多项式的具体表达式、多项式个数的多少、多项式次数的高低以及多项式系数的大小来灵活选择不同的方法来求解，用适合多项式本身特点的求解法，以达到简化计算量且提高准确率的目的四、结束语本文通过对多项式最大公因式最优求法的探讨，经过对比，得出简单结果，可知对于不同的多个多项式在求解其最大公因式时有不同的解法，需要我们具体问题具体分析，运用最适合的方法求解简化计算量、提高准确率在平时只有训练掌握各种解法，才能在具体求解时选择最优解法最后需要指明的是，到目前为止多项式最大公因式的求法已有很多，但针对不同多项式时采取何种算法求解却还没有一般的可行的方法，如何求特殊多项式的最大公因式及其理论证明还有待于进一步研究、丰富和完善参考文献1 张禾瑞，郝炳新高等代数（第四版）m高等教育出版社，1999，38802 北京大学数学系几何与代数教研室代数小组高等代数（第三版）m高等教育出版社，2003，12293 邱森，高等代数m武汉大学出版社，2008，4354684 沈文选，矩阵初等应用m湖南科学技术出版社，1996，711065 刘国琪，多项式的最大公因式的一种新求法j工科数学，1997，（02）6 刘国琪 利用矩阵的初等行变换对矩阵的特征值与特征向量的同步求解 数学通报，2(1996)，p40-427 杨刚，最大公因式的矩阵求法j甘肃科学学报，2003，（03）8 郁金祥基于矩阵斜消变换的最大公因式求解j数学的实践与认识，2005(11)9 郁金祥一个求最大公因式的方法j嘉兴学院学报，2001，310 张庆，王朝霞求两个多项式的最大公因式的新方法11 钱吉林高等代数题解精粹m北京：中央民族大学出版社：200212 王恩平， 王朝珠多项式与多项式矩阵北京: 国防工业出版社，199213 北京大学数学系高等代数( 第三版)m北京: 高等教育出版社，2003:12-18 北京大学教学系高等代数(第儿版)北京: 高等教育出版社14 北京大学数学系几何与代数教研室代数小组高等代数m第2版，北京：高等教育出版社，198812-1815 北京大学数学系几何与代数教研室代数小组高等代数m北京：高等教育出版社，200316 熊金淹高等代数高等教育出版社，199317 梁保松，苏本堂线性代数及其应用m北京：中国农业出版社，200618 高吉全斜消法变换与结式计算的简化数学通报，199319 王丹华利用矩阵初等变换求多项式的最大公因式j高等数学研究，2005致 谢我的毕业论文（设计）撰写工作自始至终都是在孙秀娟老师全面、具体的指导下进行的孙秀娟老师渊博的学识、敏锐的思维、民主而严谨的作风，使我受益匪浅，终生难忘孙老师严谨的治学态度和对工作兢兢业业、一丝不苟的精神将永远激励和鞭策我认真学习、努力工作感谢我的指导老师孙秀娟对我的关心、指导和教诲！感谢实验室的 老师和 老师的关心和帮助！感谢我的学友和朋友们对我