Лекция 5 (часть 2). ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИИ
1. Разделенные разности и их свойства
2. Интерполяционная формула Ньютона
3. Интерполяционные сплайны
1. Разделенные разности и их свойства
Обобщением понятия производной является понятие разделенной разности. Разделенные разности нулевого порядка просто совпадают со значениями функции ; разности первого порядка определяются равенством:
. (230)
Если вспомнить определение производной функции в точке :
,
и сравнить с (230), то становится очевидной аналогия разделенной разности с производной.
Разделенные разности второго порядка определяются равенством:
,
и вообще, разности -го порядка определяются через разности -го порядка в соответствии с формулой:
. (240)
Лемма. Справедливо равенство:
. (250)
Доказательство. Для доказательства воспользуемся методом математической индукции. Проверим выполнение (250) для :
;
для :
,
а ,
что говорит о выполнении (250) для .
Предположим, что для для формула (250) доказана. Покажем, что тогда она верна и для , т.е. , а коэффициент при действительно равен
. (255)
Для этого преобразуем выражение для , которое получается по определению разделенной разности -го порядка:
(260)
Если , то присутствует в обеих суммах, стоящих в скобках в правой части формулы (260). Коэффициенты при в первой и второй суммах соответственно равны:
, .
Тогда полный коэффициент при в правой части формулы (260) равен:
что в точности отвечает (255).
Для или значение входит только в одну сумму в скобках в правой части формулы (260) и коэффициент при нем, как легко убедиться, также имеет требуемый вид (255).
Из предыдущей леммы вытекает, что разделенная разность является симметрической функцией своих аргументов , т.е. не меняется при любой их перестановке.
Если функция задана в точках , то таблицу
называют таблицей разделенных разностей. Таблица разделенных разностей часто используется для удобства при вычислении значения , а также всех разделенных разностей меньшего порядка.
2. Интерполяционная формула Ньютона
Получим еще одну форму записи интерполяционного многочлена, строящегося по набору узлов интерполяции и значений функции , в этих узлах. Пусть - отвечающий имеющемуся набору данных интерполяционный многочлен Лагранжа (180). Тогда справедливо равенство:
.
Учитывая, что , стоящее в знаменателе последней дроби выражения в скобках, отличается от , стоящего в числителе, только наличием множителя , то после сокращения дроби получим:
.
Выражение в скобках – это , а с учетом обозначения (185) последняя формула примет вид:
. (270)
Пусть - интерполяционный многочлен Лагранжа с узлами интерполяции . Интерполяционный многочлен Лагранжа можно представить в виде:
. (280)
Поскольку для любого - это многочлен степени , то разность для любого - это также многочлен степени , причем его корнями являются узлы . Действительно:
.
Тогда, зная все корни многочлена , его можно представить в виде:
, (290)
где .
Пусть , тогда из (290) получается:
. (300)
При и из (270):
(310)
Из равенства левых частей формул (300) и (310) получаем равенство правых частей:
,
Откуда .
Тогда формула (290) приобретает вид:
. (320)
Подставим (320) в (280):
(330)
Интерполяционный многочлен, представленный в виде (330), называется интерполяционным многочленом Ньютона с разделенными разностями.
Задача. Даны значения некоторой функции в узлах . Требуется для вычислить значение с заданной точностью или с наилучшей возможной точностью при имеющейся информации.
Предлагаемый ниже алгоритм решения задачи является довольно типичным для ситуации, возникающей в реальной практике. Невозможно предложить обоснованный алгоритм решения поставленной задачи для всех функций, поскольку про функцию ничего не известно, кроме ее значений в заданных точках. Однако, предполагая функцию гладкой, мы выводим практический критерий оценки погрешности и, основываясь на нем, строим алгоритм решения задачи.
Пусть фиксировано. Предположим, что узлы интерполяции перенумерованы в порядке возрастания (это всегда можно сделать). Выше было получено представление погрешности интерполирования в виде (270):
, (340)
кроме того, из (320):
. (350)
Сравнивая (210) и (270), из равенства левых частей этих формул получаем равенство правых частей:
,
откуда , (360)
где , . При малых из (360) получаем:
. (370)
Тогда из (340) и (350) с учетом (370) получаем:
.
Величину можно рассматривать как приближенную оценку погрешности интерполяционной формулы . Таким образом, для решения поставленной задачи последовательно вычисляются значения , , , ...; если при некотором будет выполняться
, (380)
то вычисления прекращаются и полагают
.
Если (380) не выполняется ни для какого (а уже достигло достаточно большого значения), то находят
и полагают
.
Если этот минимум достигается при нескольких , то среди них выбирают наименьшее. Если величины , начиная с некоторого , имеют устойчивую тенденцию к увеличению, то с этого момента вычисление значений прекращают.
Замечание. Пусть даны значения некоторой функции в узлах . Требуется построить интерполяционный многочлен степени . Независимо от выбранного способа построения (при помощи решения соответствующей системы линейных уравнений, многочлен Лагранжа, Ньютона и т.д.) по имеющимся данным многочлен определяется однозначно. Лишь соображения, связанные с памятью и временем реализации могут повлиять на выбор метода построения интерполяционного многочлена.