Matlab中的roots函数的算法原理

xray

最近写论文，需要求解一个高次代数方程，本来很简单的使用matlab中的roots函数就可以了。由于写论文要注明算法的参考文献，我查看了Matlab的roots函数的帮助，发现它是把代数方程转化为矩阵特征根求解来做的。

现在的问题是，在大部分数值分析的书中，讲的都是二分法、不动点法、牛顿法，并没有谈到roots函数中使用的这种方法。我查了文献，有两篇中文论文《D_Q方法求实系数高次代数方程的全部根》和《代数方程求根的一个新的数值解法》都是采用了这种方法。不过，作者没有给出相关的参考文献。请问，roots函数中使用的方法到底是来自哪里，或者哪本英文教材中提到过，如果有高人知道，请不吝赐教，谢谢！

ChaChing

我一直在注意此帖的动态, 因我亦有兴趣知道! 苦等许久, 楼主解决否?
刚google搜了下, 了解不是很透彻, 说说心得, 恳请指教
Matlab的roots函数, 是将多项式表示成伴随矩阵(Companion), 再用解特徵值方法求根
伴随矩阵A, 其特徵多项式为det(A-sI); 其多项式的根即为矩阵A的特徵值
其他数值方法依次仅求出一个根, 使用矩阵特徵值eig一次全解出

xray

呵呵，难得有同道中人啊！在这个问题上，我找到的最早文献是
A composite polynomial zerofinding matrix algorithm
作者是 F. Malek, R. Vaillancourt
发表在 Computers & Mathematics with Applications
Volume 30, Issue 2, July 1995, Pages 37-47

ChaChing

我也挖了几篇文献, 只不过个人搅工程久了, 数学水平又不高, 没怎麽细看! 仅瞄瞄了解个大概! 还希望楼主研究完教教!

xray

ChaChing

谢谢楼主提供的资料, 学习了
个人看法, 若把n次方程视为n次ODE, 将ODE转换成状态方程(state space)的过程, 除Companion矩阵外, 尚有许多种型态的可能性, 其中各型态的特徵矩阵A的特徵值, 都是n次方程的根
利用此种方式除了降为一阶外, 在数值分析上有其方便性, 只不过各类数值分析稳定性的问题, 有时会造成一些round-off误差

xray

这种方法把高次代数方程求根转换为矩阵求特征值，从而把代数方程求根与一般意义上的任意方程求根区别开来，从思路上来说，体现了代数方程的特殊性。此外，矩阵求特征值是数值分析中的经典问题，已经有很多成熟的方法，最常用的就是QR分解方法。

正如楼上提到的，把代数方程系数转换成矩阵有许多方法，在《A composite polynomial zerofinding matrix algorithm》一文中就给出了Frobenius' Companion Matrix (这个也是Matlab中roots所使用的)，Schmeisser's Companion Matrix 和 Fiedler's Companion Matrix 三种矩阵，至于其中哪一种矩阵在求解特征值的过程中具有较高的稳定性，就不是一般工程人员能够探讨的问题了。