Канонические коэффициенты из полинома Ньютона

Question

Некоторое время назад я реализовал приближение Полинома для игры, которую я запрограммировал.

Я использую метод пирамиды Ньютона. Мне потребовалось много времени, чтобы понять это, но мое решение требует вычисления биномиальных коэффициентов, и я также должен суммировать все коэффициенты для конечного коэффициента каждой степени (так как решение этой проблемы похоже на возведение в квадрат, кубирование.. условия и вычисление биномиальных коэффициентов)

Например: выберите k из n биономных терминов и добавьте их
один выбор умножается
a * (x + b)(x + c)(x + d) ==> a * x ^ 3 + a * x ^ 2 * (b + c + d) + a * x (bc + bd + cd) + а * Ь * с * д
поэтому b * c * d будет одним выбором b * c и b * d тоже

Мой вопрос сейчас таков: есть ли способ вычисления полиноминтерполяции по схеме Ньютона без необходимости вычисления всех биономных коэффициентов?

Мой код: https://github.com/superphil0/Polynominterpolation/blob/master/PolynomInterpolation.java

Это работает довольно хорошо, хотя, если кто-то даст слишком много очков, он будет довольно медленным из-за выбора терминов, которые все должны быть суммированы

(Я действительно плохо объясняю это по-английски, я надеюсь, что кто-то может понять то, что я хочу знать, хотя)

ура

Answer 1

Исходя из этого описания, я понимаю, что ваша "схема пирамиды" генерирует коэффициенты 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² +…)
предполагая, что следующий меньший многочлен уже превращен в канонические коэффициенты.

Теперь вы можете вычислить коэффициенты a_i of p_k, используя эти коэффициенты b_i of p_k+1. Строго формально я должен был бы использовать индексы вместо a и b, но я считаю, что так понятнее. Так каковы канонические коэффициенты следующего многочлена?

• a₀ = c_k - x_k b₀
• a₁ = b₀ - x_k b₁
• a₂ = b₁ - x_k b₂
• ...

Вы можете написать это в цикле, используя и повторно используя один массив 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];
}