algorithm - 分母为导数的 Durand-Kerner

Question

Durand-Kerner 求根法的校正项为

$w_k = -\frac{f(z_k)}{\prod_{j\not=k}(z_k - z_j)}$

维基百科 Talk page提到也可以用分母中的导数来代替上面的乘积。

如何形成这样的导数？我所拥有的只是多项式的系数和根的近似值。如何得出导数的系数，以便我可以使用 Horner 方案对其进行评估，就像我对多项式($f(z_k)$)进行评估一样？

我是否正确地假设导数看起来可能像 $g'(x)$ 其中 $g(x) =\prod(z_k - z_j)$？

PS:我试图从讨论页面实现 Bo Jacoby 的表达式，但我无法让它工作:我试图对除一个以外的所有近似值的所有乘积求和并将结果放入分母，但它没有似乎是这样工作的……

Answer 1

如果在分母中使用导数，则得到牛顿法。您可以通过耦合 Horner 方案获得导数值，或者您可以形成导数多项式并对其进行评估。您需要记录如何计算多项式值。

使用导数的组合。牛顿步和电流根近似是Aberth-Ehrlich方法。

---

链接的讨论是关于分母中的乘积可以解释为辅助多项式的导数这一事实。讨论的公式

(d/dx)((x-p)(x-q)(x-r)(x-s)) = (x-q)(x-r)(x-s)+(x-p)(x-r)(x-s)+(x-p)(x-q)(x-s)+(x-p)(x-q)(x-r)

在更高的程度上仍然是正确的。请注意，当以近似根(即 p,q,r,s 之一)求值时，仅保留一个乘积项。

这可用于高阶的快速评估，其中基于快速多项式乘法的快速插值/多点评估算法比复杂度为二次的朴素实现更快。

---

对于中等程度，评估给定产品的速度更快 (n*(n-2) mults)。将线性因子组装成近似多项式，然后在近似值处评估导数多项式需要更高的努力(大约 n²/2 倍数)。

---

要以“朴素”的方式计算多项式g(z)，您必须反复将多项式与线性因子相乘

[ a[m], ..., a[0] ] * [ 1, -zz ] 
    = [ a[m], a[m-1] - zz*a[m],..., a[0] - zz*a[1], -zz*a[0] ]

这可以通过从顶部开始就地完成，即最高级别

a[m+1] = a[m]
for k=m downto 1
    a[k] = a[k-1]-zz*a[k]
end for
a[0] = -zz*a[0]