从多项式的根有效地计算其系数

Question

从多项式的根有效地计算其系数

5

我有一个首项系数为1的多项式的根，即

p(x) = (x-x_1)*...*(x-x_n)

我需要从中获取系数a_n, ..., a_0。

p(x) = x^n + a_{n-1}x^{n-1} + ... + a_0.

请问有没有一种计算效率高的方法来做到这一点？如果有人知道C/C++实现，那么这将是最好的选择。（我已经查看了GSL但它没有提供函数。）

当然，我知道如何在数学上解决它。我知道系数 a_i 是所有具有 n-i 元素的子集的积的总和。但是，如果我采用愚蠢的方式进行迭代，这意味着要遍历所有子集，则需要：

sum^{n-1}_{k=1} ( k choose n) * (k-1)

乘法和

sum^n_{k=0} ( k choose n) - n

添加。因此，这两个术语都随着O(n!)的增长，这太多了，无法将n个根的列表转换为n个系数的列表。我相信必须有一种聪明的方法可以重复使用大部分中间结果，但我找不到。

- user2690527

你可以通过卷积递归地构建多项式。如果这是一个非常大的多项式，在某个时候FFT将会击败O(n^2)方法。 - Aki Suihkonen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shahbaz · Accepted Answer

如果您逐步构建多项式，可以非常容易地在 O(n^2) 中完成此操作。让我们定义：

p_k(x) = (x-x_1)*...*(x-x_k)

这里的p_k(x)是p(x)的前k个(x-x_i)的乘积。我们有：

p_1(x) = x-x_1

换句话说，系数数组（a）的索引从左边开始为0：

-x_1 1

现在假设我们有关于p_k(x)系数的数组：

a_0 a_1 a_2 ... a_k

(顺带一提：a_k 等于 1）。现在我们想要计算 p_k+1(x)，它是（注意 k+1 是索引，没有 1 的求和）：

p_k+1(x) = p_k(x)*(x-x_k+1)
=> p_k+1(x) = x*p_k(x) - x_k+1*p_k(x)

将它转化为系数数组后，这意味着新的系数是前一个系数向右移动(x*p_k(x))减去k+1个根乘以相同的系数(x_k+1*p_k(x)):

           0   a_0 a_1 a_2 ... a_k-1 a_k
- x_k+1 * (a_0 a_1 a_2 a_3 ... a_k)
-----------------------------------------
-x_k+1*a_0 (a_0-x_k+1*a_1) (a_1-x_k+1*a_2) (a_2-x_k+1*a_3) ... (a_k-x_k+1*a_k-1) a_k

（顺带一提：这就是a_k保持为1的方法）这是你的算法。从p_1(x)（甚至是p_0(x) = 1）开始，通过上述公式逐步构建多项式系数数组，以每个根为基础。