Ньютон предложил следующий вид интерполяционного полинома:
| P n(x)= A 0+ A 1(x - x 0)+ A 2(x - x 0)(x - x 1)+...+ A n(x - x 0)(x - x 1)...(x - x n-1) | (5.6) |
Коэффициенты этого полинома A 0, A 1, A 2,..., A n определяются из условий Лагранжа (5.3).
Полагаем x = x 0. Тогда в (5.6) все слагаемые, кроме A 0, обращаются в нуль, следовательно,
A 0 = f 0.
Затем полагаем x = x 1, тогда из (5.3) имеем:
f 0 + A 1(x 1- x 0)= f 1,
откуда находим коэффициент A 1:
A 1 = 
или A 1 = f 01.
Величина f 01 = 
называется разделенной разностью первого порядка. При малом расстоянии между x 0 и x 1 эта величина близка к первой производной от функции f (x), вычисленной в точке x = x 0.
При x = x 2 полином (5.6) принимает вид:
P n(x)= f 0+ f 01(x - x 0)+ A 2(x - x 0)(x - x 1),
откуда с учетом (5.3) получаем:
f 2 = f 0+ f 01(x 2- x 0)+ A 2(x 2- x 0)(x 2- x 1) или f 2 - f 0- f 01(x 2- x 0) = A 2(x 2- x 0)(x 2- x 1),
следовательно, коэффициент A 2:
A 2= 
= 
= 
= 
,
где 
. Обозначая = f 012 (разделенная разность второго порядка),
окончательно получаем выражение для A 2:
A 2 = f 012 .
Аналогично, при x = x 3, находим коэффициент A 3:
,
где 
; 
.
Методом математической индукции можно получить для любого A k (k=0,...,n) следующее выражение:
.
Полученные результаты сведены в представленной ниже таблице.
Следует отметить, что добавление новых узлов в исходных данных не изменяет уже вычисленные коэффициенты; таблица будет лишь дополняться новыми строками и столбцами.
В интерполяционный полином Ньютона входят только диагональные элементы данной таблицы, а остальные являются промежуточными данными. Для вычисления любого элемента этой таблицы необходимы: диагональный элемент предыдущего столбца и предыдущий элемент данной строки.
Поэтому в программе, реализующей данный алгоритм, не нужно организовывать двумерный массив. Более того, все разделенные разности, в том числе и диагональные элементы (коэффициенты полинома) можно помещать по мере вычисления на место исходных значений f k. Следовательно, в программе можно ограничиться только двумя массивами: Х -для узлов и F -для значений аппроксимируемой функции. Массив F по мере выполнения программы будет заполняться разделенными разностями, и в конце концов в нем будут получены коэффициенты полинома A 0, A 1, A 2,..., A n.
Таким образом, данный метод аппроксимации, так же как и в случае канонического полинома, дает в качестве результата коэффициенты интерполяционного полинома.
После определения коэффициентов A 0, A 1, A 2,..., A n вычисление значений полинома Ньютона при конкретных аргументах x рекомендуется выполнять также по схеме Горнера, для чего полином (5.8) надо преобразовать к виду:
P n(x)= A 0+(x-x 0)(A 1+(x-x 1)(A 2+...+(x-x n-1) A n)...)).
На рис.5.4 представлена блок-схема вычисления коэффициентов полинома Ньютона и его значений в точках интерполяции по схеме Горнера.
| Разделенные разности | ||||||||||
| x | f | |||||||||
| x 0 | f 0 | = A 0 | ||||||||
| x 1 | f 1 | f 01=
| = A 1 | |||||||
| x 2 | f 2 | f 02= 
| f 012=
| = A 2 | ||||||
| x 3 | f 3 | f 03= 
| f 013= 
| f 0123= 
| = A 3 | |||||
| x 4 | f 4 | f 04= 
| f 014= 
| f 0124= 
| f 01234= 
| = A 4 | ||||
