3. Интерполяционный многочлен Ньютона.

Рассмотрим систему ; для удобства узлы интерполяции также перенумеруем с нулевого по Легко заметить, что определитель (4) в этом случае есть определитель Вандермонда

Следовательно, алгебраический интерполяционный многочлен всегда существует и единствен (с точностью до формы записи). Применим для его вывода следующий прием.

Определим, разделенные разности табулированной функции при помощи соотношений

и т. д. Разделенные разности первого, второго и более высоких порядков имеют размерности производных соответствующих порядков; в главе III показано, что они дают приближенные значения производных. Разделенные разности любого порядка можно выразить непосредственно через узловые значения функции, но вычислять их удобнее по рекуррентному соотношению (6).

Пусть есть многочлен степени . Рассмотрим, что представляют собой его разделенные разности. Вычитая из него константу получим многочлен который обращается в нуль при и поэтому делится нацело на Следовательно, первая разделенная разность многочлена степени есть многочлен степени относительно и в силу симметрии выражения — относительно Аналогично, вторая разность есть многочлен степени в самом деле, из (6) видно, что числитель этой разности обращается в нуль при и значит, нацело делится на а степень при этом понижается на единицу. Продолжая эти рассуждения, можно показать, что разность есть многочлен нулевой степени, т. е. константа, а более высокие разделенные разности тождественно равны нулю.

Перепишем соотношения (6) для случая, когда функция есть многочлен и первый аргумент равен

и т. д. Эта цепочка соотношений конечна, ибо разделенная разность многочлена тождественно равна нулю.

Последовательно подставляя эти соотношения друг в друга, получим формулу

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

Формула Ньютона удобна для вычислений и на ЭВМ, и на клавишной машине. Легко составить следующую таблицу 1 разделенных разностей для табулированной функции и произвести вычисления по формуле (8).

Таблица 1

Замечание 1. За точностью расчета удобно следить, визуально оценивая скорость убывания членов суммы (8). Если они убывают медленно, то на хорошую точность рассчитывать, вообще говоря, нельзя (подробнее см. пп. 6, 7). Если убывание быстрое, то оставляют только те члены, которые больше допустимой погрешности; тем самым определяют, сколько узлов требуется подключить в расчет.

Пример. Покажем, как вычислять синус в первом квадранте, используя четыре известных значения. Составим таблицу 2 с четырьмя узлами, причем для удобства вычисления положим у . Для проверки точности, используя разности верхней косой строки, вычислим

Таблица 2

Это приближенное значение мало отличается от точного значения . Таким образом, достаточно помнить только верхнюю косую строку таблицы 2, чтобы вычислять синус с точностью около 0,001.

Замечание 2. При заданном числе узлов многочлен Ньютона удобнее вычислять по схеме Горнера, записывая его в виде

Но если надо контролировать точность расчета и определять нужное число узлов, то удобнее форма (8).

Замечание 3. Для расчетов по формуле Ньютона безразличен порядок, в котором перенумерованы узлы интерполяции; это полезно помнить при подключении новых узлов в расчет.

Мы ограничились здесь общими формулами, пригодными для таблиц с переменным шагом. Во многих учебниках для таблиц с постоянным шагом вводят конечные разности связанные с разделенными разностями соотношением

Но это дань историческим традициям, ибо разделенные разности не менее удобны в расчетах, чем конечные.

Есть много разных форм записи интерполяционного многочлена общего вида: Ньютона, Лагранжа, Гаусса, Грегори-Ньютона, Лапласа — Эверетта и другие. Наиболее удобной для вычислений с контролем точности и на ЭВМ и вручную является. форма Ньютона (8). Большинство остальных форм рассчитано на определенные частные случаи расположения узлов интерполяции, но те выгоды, которые при этом получаются, обычно несущественны при расчетах на ЭВМ.