牛顿多项式的典范系数 [英] Canonical coefficients from Newton polynomial

问题描述

前一段时间，我为自己编写的游戏实现了多项式逼近.

A while ago I implemented a Polynom approximation for a game I programmed.

我正在使用牛顿的金字塔方法. 我花了相当长的时间才弄清楚，但是我的解决方案需要计算二项式系数，而且我还必须对每个幂的最终系数的所有系数求和(因为解决此问题类似于平方，求和.).项并计算二项式系数)

I am using Newton's pyramide method. It took me quite a while to figure it out, but my solution requires to calculate the binomial coefficients and I also have to sum up all the coefficients for the final coefficient of each power (since solving this problem is similar to squaring, cubing.. terms and calculating the binomial coefficients)

例如: 从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的一个选择

For example: pick k out of n of the bionomeal terms and add them
one pick is multiplied
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
so b*c*d would be one pick b*c and b*d too

我现在的问题是: 有没有一种方法可以用牛顿法来计算多项式插值，而不必计算所有的生物系数?

My question now is: Is there a way calculating the Polynominterpolation with the newton scheme without having to calculate all the bionomial coefficients?

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

它工作得很好，尽管如果给出的分数太多，那将相当慢 因为选择了所有要总结的术语

It works pretty good, although if one gives too many points it will be rather slow because of the selection of terms which have all be summed up

(我真的很难用英语解释这一点，但我希望有人能理解我想知道的内容)

(I am really bad at explaining this in english, I hope someone can understand what I want to know though)

欢呼

推荐答案

从 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 ))))))

Judging from this description, 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 ) … ))))

现在，您可以从背面递归计算规范系数.从
开始 p _n = c _n

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

在每一步中，当前多项式都可以写为
p _k = c _k +( x ‒ x _k ) p _{k +1} = c _k +( x ‒ x _k )( b ₀ + b ₁ x + b ₂ x ² +…)
假设下一个较小的多项式已被转换为规范系数.

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.

现在您可以使用这些系数 b < p _{k +1} 的sub> i .以严格的正式方式，我必须使用索引而不是 a 和 b ，但是我认为这样更清楚.那么下一个多项式的典范系数是多少?

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 _k b ₀
• a ₁ = b ₀ - x _k b ₁
• a ₂ = b ₁ - x _k b ₂
• …

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

您可以将其循环编写，使用并重用单个数组a来保存系数:

You can write this in a loop, using and reusing a single array a to hold the coefficients:

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

这篇关于牛顿多项式的典范系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！