3

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

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

例如：从 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

它工作得很好，虽然如果一个人给出的分数太多，它会相当慢，因为选择的术语都已经总结出来了

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

干杯

4

1 回答 1

1

从这个描述来看，我认为你的“金字塔方案”生成系数c i使得多项式p ( x ) 可以写为
p ( x ) = c 0 + ( x ‒ x 0 )( c 1 + ( x ‒ x 1 )( c 2 + ( x ‒ x 2 )( c 3 + ( x ‒ x 3 )( ... ( 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 0 + b 1 x + b 2 x 2 + ...)
假设下一个较小的多项式已经转换为规范系数。

现在您可以使用p k +1的系数b i计算p k的系数a i。以严格的正式方式，我必须使用索引而不是a和b，但我相信这种方式更清楚。那么下一个多项式的典型系数是多少？

  • 一个0 = c k - x k b 0
  • 一1 = b 0 - x k b 1
  • a 2 = b 1 - x k b 2
  • …</li>

您可以在循环中编写它，使用和重用单个数组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];
}
于 2012-11-17T23:47:41.263 回答