c - 找到(三次)多项式的实根的简单方法是什么？

Question

这对我来说似乎是一个显而易见的问题，但我无法在 SO 上的任何地方找到它。我有一个三次多项式，我需要找到函数的实根。这样做的方法是什么？

我找到了几个求三次函数根的封闭式公式，但它们要么使用复数，要么使用大量测角函数，我不喜欢它们(也不知道该选择哪一个)。

我需要一些简单的东西；越快越好；而且我知道我最终将需要求解高阶多项式，因此使用数值求解器可能也会有所帮助。我知道我可以使用一些库来为我完成艰苦的工作，但假设我想将其作为练习来完成。

我正在用 C 编写代码，所以请不要import magic_poly_solver。

奖励问题:如何只找到给定区间内的根？

Answer 1

对于三次多项式，有 closed form solutions , 但它们并不是特别适合数值微积分。

对于三次情况，我会执行以下操作:任何三次多项式至少有一个实根，您可以使用牛顿法轻松找到它。然后，您使用 deflation要求解剩余的二次多项式，请参阅我的回答 there了解如何正确执行后一步。

提醒一句:如果判别式接近于零，就会有一个数值倍数的实根，牛顿法就会失败。此外，由于在根附近，多项式类似于 (x - x0)^2，你将丢失一半有效数字(因为 P(x) 将 < epsilon，只要 x - x0 < sqrt(epsilon )).因此，您可能想要排除这种情况并在这种特殊情况下使用封闭形式的解决方案，或者求解导数多项式。

如果你想在给定区间内找到根，检查Sturm's theorem .

通用多项式求解的更通用(复杂)算法是 Jenkins-Traub algorithm .这在这里显然有点矫枉过正，但它在立方体上效果很好。通常，您使用第三方实现。

因为你做 C，使用 GSL肯定是您最好的选择。

另一种通用方法是找到 companion matrix 的特征值与例如。平衡 QR 分解，或还原为 Householder 形式。这是 GSL 采取的方法。