根据多项式的根求其系数

Question

我正在尝试编写一个算法，可以找出给定 n, x_1, ..., x_n, a(n) 值时的 a(0),..., a(n-1)。具体要求如下：

a(n)*p^n + a(n-1)*p^(n-1) + ... + a(1)*p + a(0) = a(n)(p-x_1)(p-x_2)...(p-x_n)

对于所有实数p。

在乘以a(n)(p-x_1)(p-x_2)之后，我想使用维达公式来找到系数。

但是写代码并不像我预期的那样显而易见。

我只想在我的代码中使用基础知识 - 即循环、if语句、加法和乘法 - 不使用现成/复杂的函数。

以下是公式：

首先，我想强调一下，我只需要伪代码，我不关心为根和系数定义数组。这就是为什么我只会写a(n)，xn。哦，如果我从i=1开始索引以与数学符号同步，而不是从i=0开始索引，希望这不会让你太困扰。要从i=0开始，我必须重新编号根并引入更多括号。

到目前为止，这就是我想出来的：

a(n-1)=0;
for(i=1; i <= n; i++){
    a(n-1) = a(n-1) + x_i;
}

a(n-1) = -a(n)*a(n-1);
a(n-2)=0;

for(i=1; i <= n; i++){ 
    for(j=i; j <= n; j++){
        a(n-2) = a(n-2)+ x_i * x_j;
    }
}

a(n-2) = -a(n)*a(n-2);
a(n-3)=0;

for(i=1; i <= n; i++){
    for(j=i; j <= n; j++){
        for(k=j; k <= n; k++){
            a(n-3) = a(n-3)+ x_i * x_j * x_k;
        }
    }
}

a(n-3) = a(n)*a(n-3);

...

a(0)=1;
for(i=1; i<=n; i++){
    a(0) = a(0) * x_i;
}
if(n%2 == 0) a(0) = a(n) * a(0);
else a(0) = -a(n) * a(0);

正如您所看到的，这看起来并不好。

我想将所有这些循环链接到一个循环中，因为如果没有它，我无法编写完整的代码，无法填补固定j下 a(0) 和 a(n-j)之间的空缺。

你能帮我吗？

以下是我基于Nico Schertler答案所拥有的：

for(i=1; i<=n; i++)
{a(i)=1; 
for(j=1; j <= n; j++)
{b(i)= clone( a(i) );
a(i) = a(i-1);
b(i) = x_j * b(i);
c(i) = a(i) - b(i);
}
}

如果我们改为写成下面这样，结果会一样吗？

for(i=1; i<=n; i++)
{a(i)=1; b(i)=1;
for(j=1; j <= n; j++)
{t = a(i) ;
a(i) = a(i-1);
b(i) = x_j * t;
c(i) = a(i) - b(i);
}
}

（这是我们如何交换数组中两个元素的示例，通过将a [i]的值保留在某个变量t中。）

- Don

---

你用的是哪种编程语言？当你说“正如你所看到的，它看起来不好”时，你的意思是什么？算法是否按照你写下的方式工作？ - Gijs

@Gijs 我在写C++，所以应该使用方括号[]代替圆括号()。但是当我说它看起来不好时，我的意思是下面一行中我写的内容。确切地说，我从计算a [n-1]开始，然后是a [n-2]，...在某个点上，我需要找到a[2]，a[1]，a[0]，因此我需要从a[n - something]切换到a[something]。 - Don

另一种可能不太实际但有趣的计算系数的方法是使用称为Kronecker替换的技术，前提是根是整数。 - biziclop

可能是重复的问题：如何高效地从多项式的根中找到系数？ - Lutz Lehmann

Answer 1

您可以逐步创建多项式。

从 p = 1 开始，即 a(0) = 1。

要添加一个根，您必须将当前的多项式乘以 x - x_i。这是：

p * (x - x_i) = p * x - p * x_i

所以您需要支持三个操作：

1. 乘以x

这很简单。只需将所有系数向左移动一位。例如：

a(i    ) := a(i - 1)
a(i - 1) := a(i - 2)
...
a(1    ) := a(0)
a(0    ) := 0

2. 数量的数乘

这同样很简单。将每个系数乘以相应的数:

a(i    ) *= s
a(i - 1) *= s
...

3. 减法

只需减去相应的系数：

c(i    ) = a(i    ) - b(i    )
c(i - 1) = a(i - 1) - b(i - 1)
...

总体而言

逐项相加。首先，克隆您当前的多项式。然后，按照上述操作进行：

p := 1
for each root r
    p' = clone(p)
    multiply p with x
    multiply p' with r
    p := p - p'
next

- Nico Schertler

---

谢谢。您能解释一下为什么我们要使用p' = clone(p)而不是p' = p吗？ - Don

@Don 因为你需要将原始值乘以某个数，而克隆值乘以另一个数。 - biziclop

当然，如果乘法不是在原地进行而是返回一个副本，那么您就不需要进行单独的克隆。 - biziclop

如果我们只是这样写会出什么问题呢：p' := p; 用x乘以p; 用r乘以p'; p := p - p'？ - Don

@Don 最终的结果将是常数为 0 的多项式，因为在最后你会执行 p := p - p。 - biziclop

你能看一下我上面的问题编辑吗？ - Don

Answer 2

为此目的在C#中使用静态函数。 x^4-11x^3+44x^2-76x+48的根为{2,2,3,4}，给定参数

 roots = new Complex[4] {2, 2, 3, 4}

这个函数返回 [48，-76，44，-11，1]

public static double[] FromRoots(Complex[] roots)
{
   int N = roots.Length;
   Complex[] coefs = new Complex[N + 1];
   coefs[0] = -roots[0];
   coefs[1] = 1.0;

   for (int k = 2; k <= N; k++)
   {
       coefs[k] = 1.0;
       for (int i = k - 2; i >= 0; i--)
       {
           coefs[i + 1] = coefs[i] - roots[k - 1] * coefs[i + 1];
       }
       coefs[0] *= -roots[k - 1];

       if (Math.IEEERemainder(k, 2) == 1)
           coefs[k] = -coefs[k];
    }

        double[] realCoefs = new double[N + 1];
        for (int i = 0; i < N + 1; i++)
            realCoefs[i] = coefs[i].Real; // Not sure about this part!

        return realCoefs;
    }

- rmojab63