§ 5. Интерполяционная формула Ньютона с разделенными разностями
При помощи разделенных разностей можно получить другую форму записи интерполяционного многочлена (2.4). Справедливо равенство
Сравнивая с (4.3), убеждаемся, что выражение в скобках есть
. Таким образом,
где многочлен
определен в § 3.
Пусть
- интерполяционный многочлен Лагранжа с узлами интерполяции
. Интерполяционный многочлен Лагранжа
можно представить в виде
Разность
есть многочлен степени
обращающийся в нуль в точках
, поскольку
при
. Следовательно,
где
. Полагая
, получим
С другой стороны, полагая
и
, имеем
Таким образом,
и поэтому
Подставляя эти величины в (2), получим
Интерполяционный многочлен, записанный в такой форме, называется интерполяционным многочленом Ньютона с разделенными разностями. Из сравнения (1) с (3.1) следует важное равенство
В частности, если
— многочлен
степени
, то на основании этой формулы имеем
при любых
.
Предположим, что точки
пронумерованы в порядке возрастания:
. Вследствие (4) имеем
Поэтому величина
может использоваться в качестве приближенной оценки для величины
Задача 1. Доказать неравенство
где
.
Для упрощения вычислений интерполяционного многочлена иногда используется так называемая схема Эйткена.
Пусть
- интерполяционный многочлен с узлами интерполяции
, в частности
. Справедливо равенство
действительно, правая часть является многочленом степени
и совпадает с
в точках
. Схема Эйткена вычисления значения
заключается в последовательном вычислении с помощью формулы (5) элементов таблицы значений интерполяционных многочленов
Эта схема положена в основу стандартной программы решения следующей задачи.
Дана таблица значений некоторой функции
; требуется при каждом значении
вычислить значение
с заданной точностью
или с наилучшей возможной точностью при имеющейся информации.
Трудно дать четкое определение термина стандартная программа. По установившейся традиции стандартной программой решения задач некоторого класса называют квалифицированно написанную программу, содержащую описание алгоритма решения задач данного класса. Решение конкретной задачи осуществляется подсоединением к стандартной программе информации об этой конкретной задаче. От стандартной программы также требуется, чтобы допускалось ее использование как элемента программы, предназначенной для решения более сложных задач.
Рассматриваемое ниже построение алгоритма решения задачи является довольно типичным для ситуации, возникающей в реальной практике.
Невозможно предложить обоснованный алгоритм решения поставленной задачи для всех функций, поскольку про функцию ничего не известно, кроме ее значений в заданных точках. Однако, предполагая функцию гладкой, мы выводим практический критерий оценки погрешности и, основываясь на нем, строим алгоритм решения задачи.
Пусть
фиксировано; перенумеруем узлы интерполяции в порядке возрастания
. Интерполяционные многочлены
будем обозначать, как обычно,
.
Выше получено представление погрешности (1)
а также равенство
Так как при малых
то отсюда следует
Поэтому величину
можно рассматривать как приближенную оценку погрешности интерполяционной формулы
. Последовательно вычисляют значения
если при некотором
будет
, то вычисления прекращают и полагают
Если это неравенство не выполняется ни при каком
, то находят
и полагают
. Если этот минимум достигается при нескольких
, то среди них выбирают наименьшее. Если величины
, начиная с некоторого
, имеют устойчивую тенденцию к увеличению, то с этого момента вычисление значений
прекращают.