论文部分内容阅读
具有有限精度的一元多项式的近似最大公因子的计算在控制理论,网络理论和计算机辅助设计中都有着重要应用。作为符号数值混合计算领域的一个分支,求解近似最大公因子问题的一个主要方法是把这一数值多项式代数问题转化成矩阵代数问题,而矩阵在数值计算中是可以用数值稳定的技巧来处理的。位移结构矩阵是把数值计算和多项式代数计算联系起来的一个有效的桥梁.
位移结构矩阵的概念最早是由Kailath,Kung和Morf在1979年提出的.数值计算中,对于位移结构矩阵,人们可以发展出相比于经典算法复杂度更低的快速算法;因而,基于位移结构矩阵可以更加高效地处理数值多项式代数中的问题.
本文研究与求解一元近似最大公因子相关的快速算法,并做了如下两方面工作:
1.提出了一个求解Sylvester矩阵数值秩的快速算法,并讨论其在计算sylvester矩阵的奇异值方面的应用。Sylvester矩阵的数值秩与一元近似最大公因子的次数上界密切相关。计算Sylvester矩阵的数值秩最稳定的方法是应用奇异值分解;但这样做的代价是需要关于Sylvester矩阵阶数立方次的运算量。基于Sylrester矩阵S的位移结构,本文提出了用广义Schur算法实现快速Cholesky分解来计算STS的数值秩,进而得到S的数值秩的快速算法。这一算法具有Sylvester矩阵阶数平方次的复杂度,相比于奇异值分解来说其复杂度降了一阶.
2.用快速算法求解了Sylvester矩阵的结构低秩逼近问题。在文献[53]中,本文提出通过求解Sylvester矩阵的结构低秩逼近矩阵,来计算所给多项式的极小扰动的多项式,其具有次数不低于给定正整数的最大公因子。这一算法可以直接应用于求解近似最大公因子。这一算法的复杂度取决于算法中求解一系列最小二乘问题的运算量,利用经典的算法,其复杂度为O(st2),这里s和t分别代表最小二乘问题系数阵的行数和列数。本文中基于最小二乘问题系数阵的位移结构,应用低秩的生成子矩阵,用平方阶的复杂度O(s2)求解了这一问题.