Интерполяционный полином Ньютона
Ньютон предложил следующий вид интерполяционного полинома:
| Pn(x)=A0+A1(x-x0)+A2(x-x0)(x-x1)+...+An(x-x0)(x-x1)...(x-xn-1) | (5.6) |
Коэффициенты этого полинома A0, A1, A2,...,An определяются из условий Лагранжа (5.3).
Полагаем x=x0. Тогда в (5.6) все слагаемые, кроме A0, обращаются в нуль, следовательно,
A0 = f0.
Затем полагаем x=x1, тогда из (5.3) имеем:
f0 + A1(x1-x0)= f1,
откуда находим коэффициент A1:
A1 = 
или A1 = f01.
Величина f01 = 
называется разделенной разностью первого порядка. При малом расстоянии между x0 и x1 эта величина близка к первой производной от функции f(x), вычисленной в точке x=x0.
При x=x2 полином (5.6) принимает вид:
Pn(x)= f0+f01(x-x0)+A2(x-x0)(x-x1) ,
откуда с учетом (5.3) получаем:
f2 = f0+f01(x2-x0)+A2(x2-x0)(x2-x1) или f2 -f0-f01(x2-x0) = A2(x2-x0)(x2-x1) ,
следовательно, коэффициент A2:
A2= 
= 
= 
= 
,
где 
. Обозначая = f012 (разделенная разность второго порядка),
окончательно получаем выражение для A2:
A2 = f012 .
Аналогично, при x=x3, находим коэффициент A3:
,
где 
; 
.
Методом математической индукции можно получить для любого Ak (k=0,...,n) следующее выражение:
.
Полученные результаты сведены в представленной ниже таблице.
Следует отметить, что добавление новых узлов в исходных данных не изменяет уже вычисленные коэффициенты; таблица будет лишь дополняться новыми строками и столбцами.
В интерполяционный полином Ньютона входят только диагональные элементы данной таблицы, а остальные являются промежуточными данными. Для вычисления любого элемента этой таблицы необходимы: диагональный элемент предыдущего столбца и предыдущий элемент данной строки.
Поэтому в программе, реализующей данный алгоритм, не нужно организовывать двумерный массив. Более того, все разделенные разности, в том числе и диагональные элементы (коэффициенты полинома) можно помещать по мере вычисления на место исходных значений fk. Следовательно, в программе можно ограничиться только двумя массивами: Х-для узлов и F-для значений аппроксимируемой функции. Массив F по мере выполнения программы будет заполняться разделенными разностями, и в конце концов в нем будут получены коэффициенты полинома A0,A1,A2,... ,An.
Таким образом, данный метод аппроксимации, так же как и в случае канонического полинома, дает в качестве результата коэффициенты интерполяционного полинома.
После определения коэффициентов A0,A1,A2,... ,An вычисление значений полинома Ньютона при конкретных аргументах x рекомендуется выполнять также по схеме Горнера, для чего полином (5.8) надо преобразовать к виду:
Pn(x)=A0+(x-x0)(A1+(x-x1)(A2+...+(x-xn-1)An)...)).
На рис.5.4 представлена блок-схема вычисления коэффициентов полинома Ньютона и его значений в точках интерполяции по схеме Горнера.
| Разделенные разности | ||||||||||
| x | f | |||||||||
| x0 | f0 | =A0 | ||||||||
| x1 | f1 | f01= | =A1 | |||||||
| x2 | f2 | f02=  | f012= | =A2 | ||||||
| x3 | f3 | f03=  | f013=  | f0123=  | =A3 | |||||
| x4 | f4 | f04=  | f014=  | f0124=  | f01234=  | =A4 | ||||