algorithm - 多项式逆

Question

我有一个五阶多项式：

y = ax ⁵ + bx ⁴ + cx ³ + dx ² + ex + f

系数 af 是已知的，我需要计算给定 y 的 x。我可能会使用 Newton-Raphson 算法或类似的算法，但如果可能的话，我更喜欢非迭代解决方案。

编辑：我想在发布我的问题之前我没有充分考虑这一点。我的多项式系数是从采样数据中计算出来的，在这种特殊情况下，只有一个根。我没有想到，当然，在一般情况下可能有五个不同的词根。我想我也会将采样数据拟合到一个逆多项式，并使用它从 y 计算 x。

Answer 1

找到多项式的根既困难又棘手。获得一个稳定的鲁棒算法会让你头疼。Newton + 根删除似乎是一个好主意，但正确地完成这项工作真的很痛苦。

一个明显的问题是根去除的稳定性。另一个问题是复杂的根源。一个更困难的问题是（数字上）多个根，您会失去很多精度。

最先进的黑盒算法是Jenkins-Traub。但是，它很难实现，因此您必须在某个地方找到（或支付）实现。

不过，如果您可以访问线性 alebra 包，那么一种简单、稳健、稳定且有效的方法是计算伴随矩阵的特征值。这就是例如。GSL 可以。

Answer 2

J Trana 已经回答了这个问题，但答案是您通常无法找到解决此问题的算法（这是使伽罗瓦闻名的数学结果）。

此外，如果这不是家庭作业问题，那么您可能无论如何都不希望算法以部首形式解决问题，因为这在数值上会表现得很糟糕。

Answer 3

Newton-Raphson 只会为您提供一种解决方案。一个五次元可能最多有 5 个。

如果您想要所有解决方案，您要么需要将 Newton-Raphson 与根去除配对，要么使用更强大的东西。

一种常见的方法是使用Sturm 多项式