真三次多项式的最快数值解？

Question

R问题:寻找最快的方法来数值地解决一堆已知具有真实系数和三个真实根的任意立方体.据报道,R中的多根函数使用Jenkins-Traub的算法419用于复数多项式,但对于实数多项式,作者参考了他们早期的工作.对于真实的多项式,或者更普遍的真实多项式,有哪些更快的选项？

Answer 1

以可靠,稳定的方式多次这样做的数值解包括:(1)形成伴随矩阵,(2)找到伴随矩阵的特征值.

您可能认为这是一个比原始问题更难解决的问题,但这就是大多数生产代码(例如,Matlab)中解决方案的实现方式.

对于多项式:

p(t) = c0 + c1 * t + c2 * t^2 + t^3

伴随矩阵是:

[[0 0 -c0],[1 0 -c1],[0 1 -c2]]

找到这种矩阵的特征值; 它们对应于原始多项式的根.

为了非常快速地执行此操作,请从LAPACK下载奇异值子例程,编译它们,并将它们链接到您的代码.如果您有太多(例如,大约一百万)个系数集,请同时执行此操作.

请注意,系数t^3为1,如果在多项式中不是这种情况,则必须将整个系数除以系数,然后继续.

祝好运.

编辑:Numpy和octave也依赖于这种方法来计算多项式的根.例如,请参阅此链接.