分母为导数的 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 之一，仅保留一个乘积项。

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

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

要以 "naive" 的方式计算多项式 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]

Durand-Kerner with derivative in denominator