python – 用于计算“多项式系数”的numpy / scipy函数

发布时间：2020-12-20 13:42:41 所属栏目：Python 来源：网络整理

导读：是否有任何 python函数(可能来自numpy或scipy)计算扩展中x ** r的系数(1 xx ** 2 x ** 3 … x **(k-1))** n,其中k = 1,n = 0且0 = r = n(k-1)？这有时被称为多项式系数(PC)(参见,例如,here). 如果没有,你能想到一种有效的计算方法吗？ (我对天真/贪婪的方式

是否有任何 python函数(可能来自numpy或scipy)计算扩展中x ** r的系数(1 xx ** 2 x ** 3 … x **(k-1))** n,其中k> = 1,n> = 0且0 <= r <= n(k-1)？这有时被称为多项式系数(PC)(参见,例如,here).

如果没有,你能想到一种有效的计算方法吗？ (我对天真/贪婪的方式不感兴趣).

解决方法

你实际上正在进行[1,1,…,1]的n次卷积.
因此,您是否考虑在足够零填充的阵列上使用FFT,将其元素提升到幂n并使用逆FFT来恢复所有系数

(1+x+x**2+x**3+...+x**(k-1))**n

然后只是阅读你感兴趣的那些？

更新：

由于FFT是循环的,因此您需要一个不小于其中的项数的数组

(1+x+x**2+x**3+...+x**(k-1))**n

或者换句话说,(k-1)* n 1使结果不会在末端环绕(或者至少在它们这样做时它们只向受影响的元素添加零).通常它的长度也应该是2的幂,因为这是FFT算法所要求的(实现不需要它将用零填充输入直到它).

在类似C的伪代码中：

unsigned int m = 1;
while(m<(k-1)*n+1) m *= 2;

complex c[m];
for(unsigned int i=0;i!=k;++i) c[i] = complex(1.0,0.0);
for(unsigned int i=k;i!=m;++i) c[i] = complex(0.0,0.0);

c = fft(c);
for(unsigned int i=0;i!=m;++i) c[i] = pow(c[i],double(n));
c = inv_fft(c);

在此结束时,复数组c的第r个元素的实部等于x ** r的系数和零的虚部.
现在,由于这都是以浮点形式完成的,因此您应该知道这些元素将累积舍入错误.您可以通过将它们四舍五入到最接近的整数来部分纠正这一点,但要注意,对于足够大的k和n,这些误差将超过0.5,因此这会产生因某些小的相对误差而关闭的结果.

在网上快速搜索显示,numpy分别具有FFT及其逆,numpy.fft.rfft和numpy.fft.irfft的实现,您可以在输入数据为真时使用.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!