Интерполяционная формула Ньютона и табулирование значений многочлена

Рассмотрим специальный случай вычисления многочлена. Интерполяционный многочлен Ньютона степени n, определяемый формулой

u ^{[ n ]}(x) = a _n (x – x ₀) (x – x ₁)…(x – x_{n – 1}) +…+ a _n (x – x ₀) (x – x ₁) + a₁ (x – x ₀) + a₀, (5)

является единственным многочленом степени £ n от x, который принимает предписанные значения y ₀, y ₁, …, y_n в заданных n + 1 различных точках x ₀, x ₁, …, x_n соответственно. После того, как значения постоянных a найдены, интерполяционная формула Ньютона становится удобной для вычислений, так как мы можем, обобщив правило Горнера, записать

u ^{[ n ]}(x) = ((…(a _n (x – x_{n – 1}) + a _{n – 1})(x – x_{n – 2}) + …)(x – x ₁) + a₁)*

*(x – x ₀) + a ₀. (6)

Теперь рассмотрим, как находятся постоянные a в формуле Ньютона. Их можно определить, находя «разделённые разности» и сводя вычисления в следующую таблицу (иллюстрирующую случай n = 3):

y ₀

(y ₁ – y ₀)/(x ₁ – x ₀) = y¢ ₁

y ₁                              (y ₂ – y’ ₁)/(x ₂ – x ₀) = y¢¢ ₂

(y ₂ – y ₁)/(x ₂ – x ₁) = y¢ ₂                               (y’’ ₃ – y’’ ₂)/(x ₃ – x ₀) = y¢¢¢ ₃

y ₂                              (y ₃ – y’ ₂)/(x ₃ – x ₁) = y¢¢ ₃

(y ₃ – y ₂)/(x ₃ – x ₂) = y¢ ₃

y ₃                                                                                                         (7)

Можно доказать, что a₀ = y ₀, a₁ = y’ ₁, a₂ = y’ ₂, и т. д. Следовательно, для нахождения величин может быть использована следующая вычислительная процедура (соответствующая таблице (7)):

Начать с того, что установить (a₀, a₁, …, a _n) (y ₀, y ₁, …, y_n); затем для k = 1, 2, …, n (именно в таком порядке) установить y_j (y_j – y_{j – 1})/(x_j – x_{j – k})для j  = n, n – 1, …, k (именно в таком порядке).

Если мы хотим вычислить многочлен u (x) степени n сразу для многих значений x, образующих арифметическую прогрессию (т. е. хотим вычислить u (x ₀), u (x ₀ + h), u (x ₀ + 2 h),…), то весь процесс можно после нескольких первых шагов свести к одному только сложению вследствие того факта, что n -я разность от многочлена есть постоянная.

1 Найти коэффициенты b _n, …, b₁, b₀ представления нашего многочлена в виде интерполяционного многочлена Ньютона

u (x) = b _n / n! hⁿ (x – x ₀ – (n – 1) h)…(x – x ₀ – h)(x – x ₀) +…+ b₂/ 2! h ²* *(x – x ₀ – h)(x – x ₀) + b₁/ h ² (x – x ₀) + b₀.      (8)

(Это можно сделать, беря повторные разности, в точности так же, как мы определяли выше постоянные a в (5) (надо принять x_j = x ₀ + jh), с тем исключением, что все деления на x_j – x_{j – k}  из вычислительной процедуры устраняются.)

2 Установить x x ₀.

3 Теперь значением u (x) является b₀.

4 Установить b _j b _j + b _{j + 1} для j = 0, 1, …, n – 1 (именно в таком порядке). Увеличить x на h и вернуться в шаг 3.