Разделенные разности и интерполяционная формула Ньютона с разделенными разностями.

Ф-ия на задана табл. , . Разд.раз-ти порядка k опр. рекуррентно ч-з разд.раз-ти порядка р-вом

(1)

Здесь разд.раз-ти 0-го порядка совпадают со значениями функции в узлах.

Лемма. Для разд.раз-й справедливо равенство

(2)

Док-во. По методу мат. индукции. При получаем

Далее предположим, что (2) верна для всех разд. разн-й порядка включительно. Докажем, что (2) имеет место для разностей порядка

Лемма док-на. Из нее =>, что разд. разн-ти явл. симметричными функциями своих арг-тов.

Интерполяц. многочлен Ньютона с разд. разн-ми.

Через будем обозначать интерпол. многочлен Лагранжа для ф-и , , построен. по узлам , Рассмотрим очевидное тож-во (1). Разность есть мн-н степени с корнями ,т.к. в силу инт. условий при имеем . Поэтому (2) Положим в (2) и найдем константу : . Итак, получили . Теперь (1) можно записать в виде

(3) Ф-лу (3) наз. инт. ф-лой Ньютона с разд. разностями.

 

Конечные разности и интерполяционные формулы Ньютона с конечными разностями.

Пусть ф-ия на отрезке задана табл. с равноотстоящими узлами . Конечные раз-ти порядка k опр. рекуррентно через конечные раз-ти порядка k-1рав-ом (1). Здесь конечные раз-ти нулевого порядка берутся равными значениям функции в узлах. Лемма. Разд. раз-ти в случае равноотстоящих узлов выр-ся ч-з конечные раз-ти по формуле (2). Доказательство. Для случая k=1проверяем формулу непосредственно

.

Пусть ф-ла (2) справедлива для раз-ей порядка k-1. Т.имеем .Лемма доказана. В случае выбора в качестве узлов инт. табл. узлов ф-ла Ньютона с разд-ми разн-ми принимает вид (3)Заменим в ней разд. раз-ти конечными в соответствии с (2). Получим

(4). В формуле (4) сделаем замену переменной по правилу (4′). Формулу (4′) наз инт. ф-й Ньютона для инт-ия в начале таблицы или для инт. вперед. Здесь имеется в виду, что при p = 0 первый узел инт-ии совп. с начальным узлом т-цы и ост. инт. узлы расп-ся от него вниз (вперед) по таблице. В качестве узлов инт-ии возьмем теперь табличные узлы . Т. инт. формула Ньютона с разд. раз-ми при-ет вид . (5)Так как разд. разности явл-ся сим-ми f-ми своих аргументов, то по формуле (2) имеем . (6)

Заменим в формуле (5) разд. р-ти конечными в соответствии с формулой (6). Получим .(7)

В формуле (7) сделаем замену переменной по пр-лу : (7′)

Ф-лу (7′) наз-ют инт. формулой Ньютона для инт-ия в конце табл. или для инт-ия назад. Здесь имеется в виду, что при первый узел инт-ии совпадает с последним узлом таблицы и остальные инт-ые узлы расп-ся от него вверх (назад) по таблице. Зам. В кач. нач. узла инт-ии обычно выб-ся табл. узел , ближайший к зад. значению аргумента x. Далее выч. . Если , в качестве инт-ых берутся табл. узлы вниз от и выч. пров-ся по инт. Ф-е Ньютона (4′) для инт. в начале таблицы. В случае когда , в кач-е инт. берутся табл. узлы вверх от и вычисления проводятся по инт. формуле Ньютона (7′) для инт-ия в конце табл.

 

Составление таблиц.

Для зад-ой ф-ии требуется постр. на отрезке т-цу . При этом постоянный шаг таблицы h должен быть выбран так, чтобы таблица допускала инт-ию многочленом степени k с заданной точностью . При решении поставленной задачи воспользуемся полученной оценкой остаточного члена инт. многочлена Лагранжа степени k по узлам : ,(1) где , . Т. о., шаг т-цы h следует выбрать так, чтобы уд-лось не-во .(2)Проведем замену переменного по пр-лу . Т. не-во (2) принимает вид . Сл-но, искомое значение шага т-цы h должно уд. Не-ву (3)Здесь предп-ся, что зн-е ар-та x отрезку инт-ии . Итак, задача нах-ия искомого значения шага таблицы h сводится к задаче нахождения max ф-ии на отрезке .В случае линейной инт-ии k=1имеем . Решение уравнения дает . Т.о., т-ца допускает линейную инт-ию с заданной точностью, если ее шаг уд-ет неравенству .(4) Для ф-ии имеем и при можно взять h=0.002. В случае квадратичной интерполяции k= 2имеем . Решение Ур-ия дает .Получаем

. Т.о., т-ца допускает квадратичную инт-ю с заданной точностью, если ее шаг уд-ет не-ву (5) Если при квадр-ой инт-ии выбирать узлы инт-ии так, чтобы таб-ый узел был ближайшим к x,то.б вып. не-во или и при выборе шага нужно находить только . Поскольку , то ф-ия на отрезке монотонно убывает. Сл-но, . В рез-те приходим к оценке шага т-цы .(6)Для ф-ии имеем и при м.взять h= 0.02.Т-ца ф-ии y=sin x, доп-щая кв-ую инт-ию, требует для своего хр-ия в 10 раз < объема памяти, чем т-ца этой же ф-ии, доп-ая только лин-ую инт-ию.