java - 牛顿多项式的规范系数

Question

不久前，我为我编写的游戏实现了 Polynom 近似。

我正在使用牛顿金字塔方法。 我花了很长时间才弄明白，但我的解决方案需要计算二项式系数，而且我还必须对每个幂的最终系数的所有系数求和(因为解决这个问题类似于平方、立方……项和计算二项式系数)

例如: 从 n 个生物计量项中选出 k 个并添加它们
一挑成倍增加
a*(x+b)(x+c)(x+d) ==> a*x^3 + a*x^2*(b+c+d) + a*x (bc+bd+cd) +a*b*c*d
所以 b*c*d 也是 b*c 和 b*d 之一

我现在的问题是: 有没有办法用牛顿方案计算多项式插值而不用计算所有的双项式系数？

我的代码: https://github.com/superphil0/Polynominterpolation/blob/master/PolynomInterpolation.java

效果还不错，就是给分太多会很慢 因为选择了所有总结的术语

(我真的不擅长用英语解释这个，但我希望有人能理解我想知道的)

干杯

Answer 1

从this description来看，我认为您的“金字塔方案”生成系数 c_i 使得多项式 p(x)可以写成
p(x) = c₀ + (x ‒ x₀)( c₁ + (x ‒ x₁)( c₂ + (x ‒ x₂)( c₃ + (x ‒ x₃)( ……( c_n-1 + (x ‒ x _n‒1) c_n ) ... ))))

现在您可以从后面递归地计算规范系数。从
开始 p_n = c_n

在每一步中，当前多项式可以写成
p_k = c_k + (x ‒ x_k)p_k+1 = c_k + (x ‒ x_k)(b₀ + b₁x + b₂x< sup>2 + …)
假设下一个更小的多项式已经转化为规范系数。

现在您可以使用这些系数 b< 计算 p_k 的系数 a_i p_k+1 的 sub>i。以严格正式的方式，我必须使用索引而不是 a 和 b，但我相信这样更清楚。那么下一个多项式的规范系数是多少？

• a₀ = c_k − x_kb ₀
• a₁ = b₀ − x_kb ₁
• a₂ = b₁ − x_kb ₂
• …

您可以在循环中编写它，使用并重复使用单个数组 a 来保存系数:

double[] a = new double[n + 1]; // initialized to zeros
for (int k = n; k >= 0; --k) {
    for (int i = n - k; i > 0; --i)
        a[i] = a[i - 1] - x[k]*a[i];
    a[0] = c[k] - x[k]*a[0];
}