论文部分内容阅读
科学计算中的诸多问题都可以转化为多项式系统求解问题。符号计算和数值计算是两种不同的计算方法。与传统的数值方法相比,利用符号方法得到的解是完备精确解,不存在计算误差等问题。但符号方法由于中间系数膨胀的原因导致了存储空间的增加,降低了计算的速度,因而不能满足实际应用的需求。数值方法采用插值、拟合、迭代法等求解问题的数值近似解,计算效率较高,被广泛应用于解决工程实际问题。但受病态问题与近似计算的约束,数值方法存在迭代不收敛等问题。同时,计算结果需要进行可信性与正确性验证。本文针对上述问题,采用符号数值混合计算方法进行深入研究,讨论了若干机器证明和科学计算中的典型问题,设计和实现了一些解决这些问题的高效的、可信的算法,并进一步探讨了它们在一些工程问题中的应用。主要工作包括以下几个方面:1.针对一类代数系统重零点的计算问题,提出了一个显式表示对偶空间元素的公式。在此基础上,利用对偶空间对原代数系统做微分运算构造新系统,得到一个在初始点雅克比矩阵满秩的代数系统,从而恢复了牛顿迭代算法的二阶收敛性。同时,得到了重零点的重数。最后应用此算法解决了电力系统潮流计算的病态问题。2.半代数系统实根隔离方面,提出了基于连续同伦算法和区间牛顿算法的高效、可信的方法。该方法首先通过连续同伦算法和区间牛顿算法得到代数系统的实根区间。然后利用区间扩展对半代数系统中的限制条件进行验证。该方法克服了符号算法只能解决中小规模以及有理系统的缺点。此外,该算法具有明显的可并行性。3.研究了一个含超越函数的半代数系统的实根计算问题。首先,通过超越函数在区间上的泰勒展开,将此系统转化为多项式系统。然后采用连续同伦方法和区间算法得到此多项式系统在区间上的近似实数解。最后,将此实数解视为原系统的近似零点,利用牛顿迭代算法,得到系统的实数解。实验结果表明,该方法的效率比二分法的效率更高。4.针对具有不同维数的不可约分支的正维数系统的实根计算问题。利用随机行满秩矩阵构造新系统,使得原系统中维数不等于变量个数与方程个数之差的不可约分支满足新系统,且维数等于新系统的变量个数与方程个数之差。以此为基础,构造特殊的同伦方程以保证在此不可约分支上找到至少一个实数解。该方法克服了已有方法不能得到所有不可约分支上实数点的问题,且算法可以并行计算所有不同维数的分支。同时,基于李雅普诺夫函数的性质,通过增加变量,将微分系统李雅普诺夫函数的计算问题转化为正维数系统的实根计算问题。实验结果表明,该方法效率更高。5.基于三种经典结式矩阵之间的转换关系,通过构造中间矩阵方法,在不计算结式的前提下,证明了它们之间相差一个符号或者相差一个因子,且证实了这个因子是以原系统的系数为变量的多项式。同时,基于混合Cayley-Sylvester结式矩阵本身的特性,给出了构造它的递归方法。