最快的数值解的一个真正的多项立方?

StackOverflow https://stackoverflow.com/questions/2003465

  •  18-09-2019
  •  | 
  •  

题

R问题：寻找最快的方式解决数一堆任意生成立方体已知有真正的和客观指标上的三个真正根源。该polyroot功能R报告使用詹金斯-特劳布的算法419为复杂的多项式，但真正式提交人提到其以前的工作。什么是更快的选择为一个真正的立方，或更通常的是一个真正的多项式?

有帮助吗？

解决方案

充实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）为基准它在系统上的问题更快或更慢。

其他提示

在一个可靠的，稳定的方式执行此操作多次，数值解涉及：（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的系数是一，如果这不是你的多项式的情况下，你将不得不系数来划分整个事情，然后继续。

好运。

编辑：numpy的和八度也依赖于这种方法用于计算多项式的根。见，例如，此链接。

目前最快的方式（即我所知道的），找到真正的解决方案任意多项式中的名词的变量是多面体同伦的系统。详细的解释可能是超出了StackOverflow的答案，但本质上它是利用利用环面几何形状每个方程的结构的路径算法。谷歌会给你 <强>若干文件 。

也许这问题更适合于的 mathoverflow ？

您需要的所有3根或只是一个？如果只有一个，我认为牛顿的方法将工作正常。如果所有3，那么它可能在两个靠近在一起是有问题的情况。

1)解决的衍生物多项式P'找到你的三个根源。看看 还有 要知道如何做它正确。呼吁那些根a和b(一个 < b)

2)中根，使用几个步骤的二分a和b之间，当你们足够接近，完成与牛顿的方法。

3)为最小和最大的根源，"追捕"的解决方案。为最大根：

  • 开始与x0=b,x1=b+(b-a)*拉姆达，在那里lambda是一个中等数量(说1.6)
  • 做x_n=b+(x_{n-1}-a)*拉姆达到P(x_n)和P(b)具有不同的迹象
  • 执行平分+牛顿之间x_{n-1}和x_n

共同方法可用：牛顿的方法，对分方法、割线，定点迭代，等等。谷歌它们中的任何一个。

如果你有一个非线性 系统 另一方面(例如一个系统上N多项式eqn在N未知数)，一个方法比如 高了牛顿 可以使用。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top