什么是寻找（立方）多项式的实根的简单方法？

这对我来说似乎是一个明显的问题，但我无法在SO上找到它。我有一个三次多项式，我需要找到函数的真正根。什么是THE这样做？什么是寻找（立方）多项式的实根的简单方法？

我发现了立方函数根的几个封闭形式公式，但它们都使用复数或大量的测角函数，我不喜欢它们（也不知道选择哪一个）。

我需要一些简单的东西;越快越好;而且我知道我最终需要求解更高阶的多项式，所以有一个数值解算器也许也会有帮助。我知道我可以用一些图书馆为我做些辛苦的工作，但可以说我想做这个练习。

我在C编码，所以没有import magic_poly_solver，请。

奖金问题：我如何在给定的时间间隔内找到根？

来源

2011-02-05 cube

对于三次多项式有closed form solutions，但它们并不特别适合数值计算。

我会做以下的立方案：任何三次多项式至少有一个真正的根，你可以很容易地用牛顿的方法找到它。然后，您使用deflation来获得剩余的二次多项式来解决，请参阅我的回答there了解如何正确完成后一步骤。

请注意一句：如果判别式接近零，将会有一个数值上的多重实根，而牛顿的方法将失败。此外，由于到根的附近，多项式就像（x-x0）^ 2，你将失去一半的有效位数（因为P（x）将是<ε一旦x - x0 < sqrt（epsilon ））。因此，您可能想要排除这种情况，并在此特定情况下使用封闭形式解或者求解导数多项式。

如果要在给定的时间间隔内找到根，请检查Sturm's theorem。

用于通用多项式求解的更一般（复杂）算法是Jenkins-Traub algorithm。这在这里显然是过分的，但它在立方体上运行良好。通常，您使用第三方实施。

既然你做C，使用GSL肯定是你最好的选择。

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

来源

2011-02-05 12:11:23

感谢您的回答，但我还有一个问题：我应该在哪里获得牛顿方法的第一个估计值，我应该把0放入？ – cube 2011-02-05 18:04:05

@cube：好点。如果它不起作用，则将0置为1.您也可以求解导数多项式以获得立方的变化。如果只有一个根，那么0将会执行，如果有3个，则以衍生多项式的根之间的任何数字开始。 – 2011-02-06 08:51:08

如果不想使用封闭解（或期望更大阶的多项式），最明显的方法是使用Newton's method来计算近似根。

不幸的是，当迭代时不能决定你将得到哪个根，尽管它取决于起始值。

另见here。

来源

2011-02-05 11:59:15 ebo

一字虽然：牛顿法悲惨地具有多个（或数值倍数）根失败。而且，一旦你有一个根，你必须从多项式中移除它，这可能是不稳定的。 – 2011-02-05 12:36:25

查看Solving quartics and cubics for graphics作者：D Herbison-Evans，发表在图形宝石V。

来源

2011-02-05 13:22:08 lhf

/******************************************************************************* 
* FindCubicRoots solves: 
*  coeff[3] * x^3 + coeff[2] * x^2 + coeff[1] * x + coeff[0] = 0 
* returns: 
*  3 - 3 real roots 
*  1 - 1 real root (2 complex conjugate) 
*******************************************************************************/ 

int FindCubicRoots(const FLOAT coeff[4], FLOAT x[3]);

谨慎

http://www.realitypixels.com/turk/opensource/index.html#CubicRoots

来源

2016-05-08 03:01:24

什么是寻找（立方）多项式的实根的简单方法？

回答

相关问题