algorithm - 找到给定根的多项式的系数

Question

我正在尝试编写一个算法，它会找到 a(0),...,a(n-1)，给定 n, x_1, ... , x_n, a(n), 这样:

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) 之后，我想到了使用 Viete 的公式来求系数。

但事实证明，写下代码并不像我预期的那么明显。

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

公式如下:

首先，我想强调的是，我只需要一个伪代码，我并不关心为根和系数定义数组。这就是为什么我只写 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 中来交换数组的两个元素)。

Answer 1

您可以逐步创建多项式。

从 p = 1 开始。 IE。 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