r - 实三次多项式的最快数值解？

Question

R 问题:寻找最快的方法以数值方式求解一堆已知具有实系数和三个实根的任意立方体。据报道，R 中的 polyroot 函数对复数多项式使用 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 也依赖于这种计算多项式根的方法。参见，例如，this link .