gpt4 book ai didi

c++ - 从根高效计算多项式系数

转载 作者:塔克拉玛干 更新时间:2023-11-03 01:29:20 25 4
gpt4 key购买 nike

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

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 系数列表.我相信一定有某种智能方法可以重用大部分中间结果,但我没有找到。

最佳答案

如果您逐步构建多项式,则可以在 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)开始,并通过上述公式为多项式的每个根逐步构建系数数组。

关于c++ - 从根高效计算多项式系数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21236788/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com