论文摘要
目前利用计算机进行计算的大部分问题,最终都可转化为利用计算机进行多项式实根求解问题,这就使得多项式实根求解这一过程直接影响到各种算法的效率与准确性。因此,寻求一种更快速更准确的多项式实根求解方法,就显得非常必要。目前针对多项式实根求解这一问题的主要方法,大体可分为数值计算和符号计算两类,其中符号计算方法因为其准确性而越来越受到关注。而在实际工程应用中,由于不可避免的测量精度和计算机内部存储精度限制等导致的误差,往往无法得到具有精确系数的多项式而只能得到区间系数形式,这也是一个不可忽视的问题。本文考察了Rouillier和Zimmermann提出的一种实根隔离算法框架,并在该框架的基础上,提出了一种对实根隔离过程中得到的二分区间所构成的二叉树的遍历顺序,可以更好地利用Descartes符号法则的性质,从而减少二叉树上各结点对应多项式的变换次数。实验数据表明,对于随机实系数多项式,该改进方法所需计算时间为Rouillier算法的60%左右,而对于随机实根多项式,该方法所需时间为Rouillier算法的80%左右。本文还对区间系数多项式的区间根求解进行了分析,提出了一种利用区间多项式的上界与下界多项式的实根来确定区间多项式的区间根的方法。该方法通过将区间多项式的区间根求解转化为实系数多项式的实根求解,降低了原问题的复杂性。此外,通过对上界多项式与下界多项式的性质的考察,即上界多项式永远位于下界多项式上方,本文提出了一种用以加速上下界多项式的实根计算的方法,该方法需要首先完成对一侧边界多项式的实根隔离,并利用其计算结果来提高另一侧边界多项式的实根隔离计算速度。实验数据表明,如果首先计算下界多项式的实根,则在计算上界多项式的实根时,使用该加速方法可以将计算时间缩短为70%-80%。由于上下界多项式的实根隔离计算时间可以视为相同,即上下界多项式的实根隔离总计算时间缩短为85%-90%。