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

Question

R问题：寻找最快的方法以数值方式求解一堆任意立方，这些立方具有有效系数和三个真实根。据报道，R中的多重根函数对复杂多项式使用Jenkins-Traub算法419，但是对于实数多项式，作者参考了他们的早期工作。实三次或更普遍的实多项式有哪些更快的选择？

Answer 1

充实上面的Arietta的答案：

> a <- c(1,3,-4)
> m <- matrix(c(0,0,-a[1],1,0,-a[2],0,1,-a[3]), byrow=T, nrow=3)
> roots <- eigen(m, symm=F, only.values=T)$values

[这比在GSL软件包中使用三次求解器快还是慢（如上面的knguyen所建议的那样，都是在系统上进行基准测试的问题。

Answer 2

以可靠，稳定的方式多次执行此操作的数值解涉及：（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。

Answer 3

（我知道）最快的已知方法，可以找到n

Answer 4

您需要全部3个根还是只需要1个？如果只是一个，我认为牛顿法会行得通的。如果全部为3，则在两个彼此靠近的情况下可能会出现问题。

Answer 5

1）求解导数多项式P'，以找到您的三个根。请参阅there了解如何正确执行。称这些根为a和b（以

2）对于中间根，使用a和b之间的两等分步骤，当距离足够近时，使用牛顿法结束。

3）对于最小和最大根，“寻找”解决方案。对于最大根：

Answer 6

可用的常用方法：牛顿法，对分法，割线法，不动点迭代法等。谷歌中的任何一种。

Answer 7