从其根有效地计算多项式系数 [英] Efficient calculation of polynomial coefficients from its roots

问题描述

我有单项多项式的根，即

I have the roots of a monic polynomial, i.e.

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

我需要系数a_n，...，a_0 from / p>

and I need the coefficients a_n, ..., a_0 from

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

有人知道这样做的高效计算方法吗？如果有人知道C / C ++实现，那实际上是最好的。 （我已经看过GSL，但它没有提供功能。）

Does anybody know a computationally efficient way of doing this? If anybody knows a C/C++ implementation, this would actually be the best. (I already had a look at GSL but it did not provide a function.)

当然，我知道如何数学上。我知道，系数 a_i 是元素 n-i 的子集的所有乘积之和。但是，如果我以愚蠢的方式这样做，则意味着要遍历所有子集，我将需要

Of course, I know how to to it mathematically. I know, that the coefficient a_i is the sum of all products of the subsets with n-i elements. But if I would do it the dumb way, this means to iterate across all subsets, I would need

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

乘法和

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

添加。因此，两个术语都以 O（n！）增长，这是大量的计算，无法将 n 根列表转换为 n 个系数的列表。我相信必须有某种聪明的方法可以重用大多数中间结果，但是我找不到。

additions. Hence both terms grow with O(n!), which is too much computation to transform a list of n root into a list of n coefficients. I believe there must be some intelligent way to reuse most of the intermediate results, but I do not find one.

推荐答案

您可以如果您逐步构建多项式，则可以在 O（n ^ 2）中轻松完成此操作。让我们定义：

You can do this in O(n^2) very easily if you incrementally build your polynomial. Let's define:

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

即 p_k（x）是 p（x） k （x-x_i） >。我们有：

That is p_k(x) is the multiplication of the first k (x-x_i) of p(x). We have:

p_1(x) = x-x_1

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

In other words the array of coefficients (a) would be (indices start from 0 and from left):

-x_1 1

现在假设我们有 p_k（x）的系数数组：

Now assume we have the array of coefficients for p_k(x):

a_0 a_1 a_2 ... a_k

（旁注： a_k 为1）。现在我们要计算 p_k + 1（x），即（请注意， k + 1 是索引，并且没有1之和）：

(side note: a_k is 1). Now we want to calculate p_k+1(x), which is (note that k+1 is the index, and there is no summation by 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））：

Translating this to the array of coefficients, it means that the new coefficients are the previous ones shifted to the right (x*p_k(x)) minus the k+1th root multiplied by the same coefficients (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 ）开始，并逐步建立系数数组多项式的每个根的上述公式。

(side note: and that is how a_k stays 1) There is your algorithm. Start from p_1(x) (or even p_0(x) = 1) and incrementally build the array of coefficients by the above formula for each root of the polynomial.

这篇关于从其根有效地计算多项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！