解多项式方程组和计算多项式矩阵最小多项式的几个快速算法

《解多项式方程组和计算多项式矩阵最小多项式的几个快速算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、博士学位论文解多项式方程组和计算多项式矩阵最小多项式的几个快速算法SomeFastAlgorithmsforSolvingPolynomialSystemsandComputingMinimalPolynomialsofPolynomialMatrices作者姓名：学科、专业：学号：指导教师：张金涛计算数学10501037于波教授完成日期o．2013年4月大连理工大学DalianUniversityofTechnology大连理工大学学位论文独创性声明一～_J㈣炒作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果．尽我所知，除文中已经注明引用内

2、容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果．与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意．若有不实之处，本人愿意承担相关法律责任．学位论文题目：盈重!至煎圣鍪塑童：监查!至盎望壁垒兰丝墼坠堕!坚≥磕作者签名：卓岔吐魄垃年上月旦日大连理工大学博士学位论文摘要解多项式方程组是一个经典的数学问题，而求多项式方程组全部解是计算机数学和计算数学领域中一个重要而困难的问题。同伦方法是求多项式方程组全部孤立解的主要数值方法。在自动控制等领域中，经常需要求一个方阵的特征多项式或最小多项式。这

3、个方阵有的时候是多项式矩阵。计算多项式矩阵的特征多项式或最小多项式是计算机数学领域中一个基本问题，尚缺乏有效的算法。本文对求多项式方程组全部解的同伦方法、多项式方程组的最小m—Bezout数及相应的变元分组的算法以及计算多项式矩阵的最小多项式的方法进行了研究，取得了如下主要结果：1．提出了解亏欠多项式方程组的同伦分治方法，该同伦由两种形式的同伦组成：一部分是随机乘积同伦，另一部分是系数参数同伦，由程序根据一些准则自动构造。该同伦的初始多项式方程组可以分解为一些多项式方程组子问题。这些子问题可以分成若干组，每组的多项式组具有相同的支集，可以通过相同的消元和约化过程，降低其

4、维数和次数或BKK界，然后利用同一个多胞体同伦和一些系数参数同伦以较小的代价得到它们的全部零点。从由所有子问题的解得到的初始方程组的全部解出发，通过跟踪混合同伦路径即可得到目标方程组的全部孤立解。这个方法是一个基于同伦方法的分而治之方法，也是一个符号数值混合方法。数值算例说明了算法的有效性。2．解多项式方程组的基于m—Bezout定理的同伦方法，需要跟踪解路径的条数是m—Bezout数。不同的变元分组对应不同的m-Bezout数，寻找最小m—Bezout数及其对应的变元分组就意味着跟踪最少的路径。寻找具有最小m—Bezout数的变元分组是一个NP困难的问题。我们提出了两

5、种遗传算法和两种启发式算法以期能快速找到最佳变元分组。测试算例说明了这几个算法是有效的。3．通过引进一个随机向量和随机平移，我们将需要很强条件的基于Cayley—Hamilton定理计算特征多项式的算法改造成了一个不需要任何条件计算多项式矩阵最小多项式的算法，并证明它是以概率1成功的。对整系数多项式矩阵，我们提出了基于模技巧的并行化方法，对整个计算过程加速。计算复杂度分析说明了该方法的有效性，数值实验结果也与结论一致。关键词：多项式方程组；多项式矩阵；同伦方法；最小m—Bezout数；最小多项式解多项式方程组和计算多项式矩阵最小多项式的几个快速算法大连理工大学博士学位论

6、文SomeFastAlgorithmsforSolvingPolynomialSystemsandComputingMinimalPolynomialsofPolynomialMatricesAbstractSolvingpolynomialsystemsisaclassicalproblem，whilefindingallthesolutionsofpolynomialssystemsishardandimportantproblemincomputeralgebraandcomputa-tionalmathematics．Homotopycontinuationme

7、thodistheprimarynumericalalgorithmtosolvepolynomialsystems．Inthestabilityproblem，weoftenneedtocomputethecharac—teristicpolynomialortheminimalpolynomialofamatrixwhichsometimesisapolynomialmatrix．Computingthecharacteristicpolynomialortheminimalpolynomialofapolyno-mialmatrix