2014-02-09
968
Разделенные разности и их свойства
Обобщением понятия производной является понятие разделенной разности. Разделенные разности нулевого порядка 
просто совпадают со значениями функции ; разности первого порядка определяются равенством:
. (230)
Если вспомнить определение производной функции в точке 
:
,
и сравнить с (230), то становится очевидной аналогия разделенной разности с производной.
Разделенные разности второго порядка определяются равенством:
,
и вообще, разности 
-го порядка 
определяются через разности 
-го порядка в соответствии с формулой:
. (240)
Лемма. Справедливо равенство:
. (250)
Доказательство. Для доказательства воспользуемся методом математической индукции. Проверим выполнение (250) для 
:
;
для 
:
,
а 
,
что говорит о выполнении (250) для .
Предположим, что для для 
формула (250) доказана. Покажем, что тогда она верна и для 
, т.е. 
, а коэффициент при 
действительно равен
. (255)
Для этого преобразуем выражение для 
, которое получается по определению разделенной разности 
-го порядка:
(260)
Если 
, то присутствует в обеих суммах, стоящих в скобках в правой части формулы (260). Коэффициенты при в первой и второй суммах соответственно равны:
, 
.
Тогда полный коэффициент при в правой части формулы (260) равен:
что в точности отвечает (255).
Для 
или 
значение входит только в одну сумму в скобках в правой части формулы (260) и коэффициент при нем, как легко убедиться, также имеет требуемый вид (255).
Из предыдущей леммы вытекает, что разделенная разность 
является симметрической функцией своих аргументов 
, т.е. не меняется при любой их перестановке.
Если функция 
задана в точках , то таблицу
называют таблицей разделенных разностей. Таблица разделенных разностей часто используется для удобства при вычислении значения , а также всех разделенных разностей меньшего порядка.
Получим еще одну форму записи интерполяционного многочлена, строящегося по набору узлов интерполяции 
и значений функции 
, в этих узлах. Пусть 
- отвечающий имеющемуся набору данных интерполяционный многочлен Лагранжа (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) не выполняется ни для какого (а уже достигло достаточно большого значения), то находят
и полагают
.
Если этот минимум достигается при нескольких , то среди них выбирают наименьшее. Если величины 
, начиная с некоторого , имеют устойчивую тенденцию к увеличению, то с этого момента вычисление значений 
прекращают.
Замечание. Пусть даны значения некоторой функции в узлах 
. Требуется построить интерполяционный многочлен степени 
. Независимо от выбранного способа построения (при помощи решения соответствующей системы линейных уравнений, многочлен Лагранжа, Ньютона и т.д.) по имеющимся данным многочлен определяется однозначно. Лишь соображения, связанные с памятью и временем реализации могут повлиять на выбор метода построения интерполяционного многочлена.
