牛顿多项式的规范系数

不久前，我为我编写的游戏实现了多项式逼近。

我正在使用牛顿金字塔法。 我花了很长时间才弄清楚，但我的解决方案需要计算二项式系数，并且我还必须将所有系数相加以获得每个幂的最终系数（因为解决这个问题类似于平方，立方..项并计算二项式系数）

例如： 从 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 https://github.com/superphil0/Polynominterpolation/blob/master/PolynomInterpolation.java

效果很好，虽然如果给太多分的话会很慢 因为所选择的术语都已被总结

（我真的不擅长用英语解释这一点，但我希望有人能理解我想知道的东西）

cheers

Judging from this description http://homepages.gac.edu/~hvidsten/courses/MC355/Textbooks/numerical%20analysis%20course%20notes.pdf, I take it that your “pyramid scheme” generates coefficients c_i such that the polynomial p(x) can be written as
p(x) = c₀ + (x ‒ x₀)( c₁ + (x ‒ x₁)( c₂ + (x ‒ x₂)( c₃ + (x ‒ x₃)( … ( c_n-1 + (x ‒ x_n‒1) c_n ) … ))))

Now you can compute canonical coefficients recursively from the back. Start with
p_n = c_n

In every step, the current polynomial can be written as
p_k = c_k + (x ‒ x_k)p_k+1 = c_k + (x ‒ x_k)(b₀ + b₁x + b₂x² + …)
assuming that the next smaller polynomial has already been turned into canonical coefficients.

Now you can compute the coefficients a_i of p_k using those coefficients b_i of p_k+1. In a strict formal way, I'd have to use indices instead of a and b, but I believe that it's clearer this way. So what are the canonical coefficients of the next polynomial?

• 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];
}