论文部分内容阅读
多项式系统求解问题是数学中一个既古老又经典的问题,并在科学与工程计算中有着广泛的应用,例如机器人技术,编码理论,最优化理论,数学生物学,计算机视觉,博弈论,统计学,机器学习,控制理论,密码学等.而孤立奇异根的识别和处理,则是代数和几何计算中具有挑战性的课题之一,并在几何建模问题中经常出现,例如计算隐式曲线曲面的拓扑和参数曲面的交点等.
实际计算中,我们经常需要将多项式系统的近似根精化到一个更高的精度,但数值方法例如Newton法,在孤立奇异根附近收敛速度很慢(有时甚至不收敛).而验证多项式系统是否有孤立奇异根是一个病态问题,因为多项式系数任意微小的扰动都可能导致一个孤立奇异根变成一族正则根(有时甚至消失).因此,研究多项式系统孤立奇异根的数值精化和可信验证问题,具有重要的理论意义和很高的应用价值.
本文首先讨论了多项式系统孤立奇异根代数结构的一种恰当表示—局部对偶空间.利用一些正则化和约化技巧,我们提出了一种计算宽度为1的特殊情形下,局部对偶空间一组既约基的新算法.其对于带有近似系数的多项式系统,或近似奇异根同样适用.而且数值实验表明,无论从计算时间还是存储空间上,算法的效率都是较高的.更为重要的是,我们给出了宽度为1的特殊情形下,局部对偶空间一组既约基(重结构)的参数化表示.
其次,我们研究了多项式系统孤立奇异根的数值精化问题.基于宽度为1的特殊情形下重结构的参数化表示,我们提出了一种正则化的Newton法:解一个正则化的最小二乘问题作为初始近似根的预处理,从而得到一个更好的近似根和一个能够达到二次收敛的迭代方向;通过计算近似局部对偶空间的一组既约基和解一个线性方程组,从而确定合适的迭代步长.我们证明了算法在宽度为1的孤立奇异根附近是二次收敛的.
最后,我们研究了多项式系统孤立奇异根的可信验证问题.利用区间验证方法和宽度为1的特殊情形下重结构的参数化表示,我们提出了一种计算近似奇异根可信误差界的新算法,其可以验证一个带有微小扰动的多项式系统,在误差界内有一个宽度为1的孤立奇异根.对于一般的孤立奇异根,我们提出一种带光滑参数的deflation技术,并且基于这种技术,我们将验证宽度为1的孤立奇异根的算法推广到了一般情形.数值实验表明,算法对于带有近似系数的多项式系统和复的孤立奇异根同样适用.