Dixon结式的理论研究与新算法

论文摘要

非线性代数方程组的求解是构造性代数几何的一个基本且重要的问题.其消元法主要包括吴方法、Gr¨obner基方法和几种结式方法.值得注意的是,近几年来,基于Dixon结式的消元法被广泛地用来求解非线性代数方程组.特别是在自动控制、机器人等高新技术领域中有着广泛的应用.因此国际上有许多学者研究基于Dixon结式的消元法.Dixon结式方面的理论研究主要集中在如何提高计算Dixon结式的效率以及如何去除多余因子和Dixon矩阵在退化条件下如何取得非平凡的结果.这三个方向是目前国际上Dixon结式方面研究的前沿热点.本文就这三个问题进行了全面深入的研究,取得了一些原始创新和重大进展,其主要创新点如下:一、在提高计算Dixon结式的效率方面,目前国际上出现了变元轮换法[8]、插值法[6]、矩阵快速构造法[18, 31, 49, 57]、切角法[29]等诸多方法.在这其中,Chionh等提出的矩阵快速构造法[31]的复杂度最低,效率最高.但它们的方法最多只能解决3个方程的多项式系统.本文利用一般Sylvester结式理论,将之推广到了一般情形,即n个变元n + 1个方程的多项式系统.在此基础上,并提出了Dixon矩阵的递归算法,应用此算法首次构造出了9循环方程的Dixon矩阵.二、对于国际上公认的非常困难的多余因子问题,虽然有切角法[29]、支撑点法[32]、露点法[80]等方法,但它们只能处理某一特殊类型的系统.本文利用Dixon导出多项式,提出了一种新的一般的构造Dixon结式的算法,用此算法构造出的Dixon结式中没有多余因子.三、对于Dixon结式的退化问题,国际上存在两种方法: KSY方法[55]与雅可比方法[24]. KSY方法是杨路等人于1994年提出,在国际上被广泛采用,且被美国海军研究院的Nakos等编程实现,其程序被收入Mathematica软件.但是自从KSY方法提出后,十余年来几乎没有更新的进展.针对杨氏的方法,本文提出了一种新的、更易理解、更易验证的矩阵方法.这种方法表明,本质上, KSY条件等价于在Dixon退化矩阵中,能否导出只含一个单项式的导出多项式.总之,本文建立了一般Sylvester结式理论,解决了结式的多余因子与部分退化问题,扩展并提出了构造Dixon结式矩阵的系列快速算法,并且利用这些算法解决了一些标高和有实际意义的问题.这些方法与理论对于基于Dixon结式的非线性代数方程组的求解具有重要意义.

论文目录

• 摘要
• Abstract
• 目录
• 第一章 引言
• 1.1 消元法
• 1.1.1 吴方法
• 1.1.2 Gro¨bner基方法
• 1.1.3 结式方法
• 1.2 结式
• 1.2.1 预备知识
• 1.2.2 结式的定义
• 第二章 Sylvester结式
• 2.1 定义
• 2.2 Sylvester矩阵的分块表示法
• 2.3 Sylvester结式的多余因子
• 第三章 Dixon结式的快速递归算法
• 3.1 Dixon结式的定义
• 3.2 Dixon矩阵的分块表示法
• 3.3 Dixon多项式的递归算法
• 3.4 Dixon导出多项式的快速递归算法
• 3.5 Dixon矩阵的快速算法
• 第四章 Dixon结式的多余因子与退化问题
• 4.1 Dixon结式的多余因子问题
• 4.2 Dixon结式的退化问题
• 第五章 Sylvester结式与Dixon结式的关系
• 5.1 Sylvester矩阵与Dixon矩阵的关系
• 5.2 混合Dixon-Sylvester结式
• 5.3 三种结式的关系
• 第六章 结论与展望
• 6.1 本文总结
• 6.2 今后的主要工作
• 6.2.1 Dixon结式与吴方法的内在联系
• 6.2.2 Dixon结式与Gro¨bner基的内在联系
• 6.2.3 一般通用的组合结式算法
• 6.2.4 组合结式的并行算法
• 参考文献
• 发表文章目录
• 致 谢