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

Question

我有一个monic多项式的根,即

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系数列表.我相信必须有一些聪明的方法来重用大多数中间结果,但我找不到一个.

Answer 1

O(n^2)如果逐步构建多项式,则可以非常轻松地完成此操作.我们来定义:

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

也就是说p_k(x)是第一的乘法k (x-x_i)的p(x).我们有:

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+1th根再乘以相同的系数(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)并递增地构建系数数组.