Вторая интерполяционная формула Ньютона.

Для интерполирования функции в конце таблицы применяется вторая интерполяционная формула Ньютона.

 (1)

Вывод формулы аналогичен 1-ой интерполяционной формуле, только теперь коэффициент полинома  (коэффициент ) определяется из равенств

                                                                                         (2)

Введем обозначение

Тогда

 

и так далее.

В результате получим:

(3)

Пример: дана таблица значений  семизначных логарифмов:

 

х	У
1000 1010 1020 1030 1040 1050	3,0000000 3,0043214 3,0086002 3,0128372 3,0170333 3,0211893

 

 

Найти lg1044

 

 

Решение: составляем таблицу конечных разностей.

1000 1010 1020 1030 1040 1050	3,0000000 3,0043214 3,0086002 3,0128372 3,0170333 3,0211893	43214 42788 42370 41961 41560	-426 -418 -409 -401	8 9 8

 

Примем  Тогда .

По формуле (3) получаем:

В результате все знаки верные!

Т.о. первая интерполяционная формула Ньютона применяется для интерполирования вперед и экстраполирования назад (за границы интервала); Вторая формула – для интерполирования назад и экстраполирования вперед.

Операция экстраполирования менее точна!

Оценки погрешностей интерполяционных формул Ньютона.

       Если узлы интерполирования  - равноотстоящие причем  то, пологая , получим остаточные члены для 1-ой и 2-ой интерполяционных формул Ньютона:

                        (1)

 ,                      (2)

Где - некоторое промежуточное значение между узлом интерполирования  и точкой .

(Для интерполирования , для экстраполирования возможно, что ).

При расчетах порядок n разностей выбирается таким, что . Учитывая, что h достаточно мало и  и что

можно положить:

                                                                (3)

При этом остаточные члены интерполяционных формул Ньютона будут равны (подставляя (3) в (1) и (2)).

Пример: В пятизначных таблицах логарифмов даются логарифмы целых чисел от х=1000 до х=10000 с предельной абсолютной погрешностью, равной . Возможно ли линейное программирование с той же степенью точности?

Решение: Т.к. , то  где

Отсюда

, а

Из формулы (1) при n=11 и h=1 получаем:

Т.к.  (интерполируем не далее, чем на 1 шаг), то

Окончательно получаем:

Т.о. погрешность интерполирования не превосходит погрешностей исходных данных!

Линейное интерполирование (h=1) возможно!!!

* * *

Интерполяционные формулы Ньютона используют лишь значения функций, лежащие лишь по одну сторону от выбранного начального значения

 

Для интерполирования в середине таблицы удобно применять формулы, содержащие как последующие, так и предшествующие значения функций по отношению к начальному ее значению.  При этом используются центральные разности:

Причем:

  

 

 

Интерполяционные формулы с центральными разностями: формулы Гаусса, Стирлинга, Бесселя.

 

. Интерполяционная формула Лагранжа.

Для произвольно заданных узлов интерполирования (в том числе и для неравноотстоящих узлов) применяется интерполяционная формула Лагранжа.

На отрезке [a, b]  задано  n+1 значений аргумента и известны значения функций y=f(x):

Требуется построить полином  степени не выше n, имеющий в заданных узлах , те же значения, что и функция f(x), т.е. такой, что

Рассмотрим частную задачу: построить полином , такой, что бы  при

Т.е.                               (1)

Такой полином имеет вид:

(2)

При         - условие (1)

Поэтому  

И

В результате получаем:

    (3)

Будем теперь искать интерполяционный полином в виде

Этот полином имеет вид:

                          (4)

Подставляя (3) в (4), получаем:

   (5)

 

----- интерполяционная формула Лагранжа

 

Можно доказать единственность полинома Лагранжа

         

При  n=1 имеем:

 - уравнение прямой, проходящей через две заданные точки: (

При n=2 получаем уравнение параболы, проходящей через три точки:

 

(точки

Пример: Для функции  построить интерполяционный полином Лагранжа, выбрав узлы:

Решение: Вычисляем

По формуле (5) получаем:

Точность не велика, т.к. синусоиду мы интерполируем параболой (квадратичной).

 

`Оценка погрешности интерполяционной формулы Лагранжа.

 

(6)

где

 

Пример1: с какой точностью можно вычислить  с помощью интерполяционной формулы Лагранжа для функции , выбрав узлы интерполирования  Три точки n=2.

Решение:  имеем

Отсюда               (т.к.

Из формулы (6) получаем:

 

Пример2 с какой точностью можно вычислить  по формуле Лагранжа

Точное значение

 

 

 

6 Обратное интерполирование

Задача обратного интерполирования: по заданному значению функции  найти аргумент , при котором . Функция y=f(x) задана таблично.

Предположим, что на отрезке [a, b], содержащем узлы интерполяции, функция f(x) монотонна. Тогда существует однозначная обратная функция x=F(y). Она задана той же таблицей, что и y=f(x), только теперь аргументом будет значение , а -соответствующее значение функции.

В этом случае обратное интерполирование сводится к обычному интерполированию для функции x=F(y). Т.е. строится интерполяционный многочлен (например, по формуле Лагранжа) – многочлен . При подстановке в  значения   - получаем .

Второй способ применим ко всякой функции f(x) (не обязательно к монотонной!). Не меняя ролями функцию и аргумент, записываем по какой – либо формуле интерполяционный многочлен . Неизвестное значение   находим приближенно, решая уравнение . Если число узлов велико, то этот способ нахождения  приводит к решению системы алгебраических уравнений высокого порядка.

  Рассмотрим другой -  интерполяционный метод решения уравнений.

Будем рассматривать только равноотстоящие узлы, т.е.

Пусть для определенности  находится между  и . Строим интерполяционный многочлен по 1-ой формуле Ньютона. Уравнение  принимает вид:

                               (2)

Выберем начальное приближение

Подставляя  в (2) последовательно получаем

Итерационный процесс прекращается, когда два соседних приближения совпадают с заданной системой точности.

Т.о. находится

Т.к.   то

Пример: функция y=f(x) задана таблично

 

х	0,5	0,6	0,7	0,8	0,9
у	1,6487	1,8221	2,0138	2,2255	2,4596

 

Найти значение , для которого =1,7333

Решение: строим таблицу конечных разностей заданной функции.

х	у
0,5 0,6 0,7 0,8 0,9	1,6487 1,8221 2,0138 2,2255 2,4596	1734 1917 2117 2341	183 200 224	17 24	7

 

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

Получаем:

Т.к. решение ищем с точностью до 0,0001, (4-ре значащих цифры после запятой), то

 - шаг по х.

 

ЛЕКЦИЯ 10

Сплайн – интерполяция.

 (spline – рейка, планка) Механические сплайны – гибкие деревянные рейки, закрепленные на концах. В узлах (точках) интерполяции подвешивают грузила. Сплайн принимает форму, минимизирующую его потенциальную энергию. Если сплайн представить функцией S(x), то S и  непрерывны на [ ].

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

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

Пусть отрезок [a, b] разбит на n частей точками

Сплайном k-ой степени называется функция, представляющая собой многочлен не выше к-ой степени на каждом из последовательно примыкающих друг к другу интервалов  причем в точках стыка двух интервалов  функция непрерывна вместе со своими производными до порядка не выше к

Сплайн 1-ой степени – кусочно-линейная функция (непрерывная). Производная терпит разрыв в точках излома.

Задача интерполяции функции на отрезке [ a, b] кубическим сплайном (сплайном 3-ей степени) состоит в нахождении функции S(x), равной многочлену третьей степени на каждом отрезке  т.е.                (1)

  Значения сплайна в узлах интерполяции  равны  и сплайн-функция S(x) непрерывна в узлах интерполяции вместе с производными первого и второго порядков.

 

В сплайне (1) неизвестные    . Интервал [a, b] разбит на n участков. Т. о. имеем 4n неизвестных: (i*p) = 4n.

Уравнения (2) – (5) дают 4n – 2 уравнения. Т.о. для определения величин  необходимо ввести еще каких-либо 2 ограничения. В качестве ограничений выбирается одна из 3-х пар краевых условий:

Построим сплайн, удовлетворяющий краевым условиям I типа.

Введем величины , называемые наклонами сплайна в узлах  (i=0,1,..,n)

Интерполяционный кубический сплайн вида

    (6)

Где       удовлетворяет условиям (2) – (4) для любых

Из условия (5) и краевых условий     (I) можно определить параметры .

Действительно, легко проверить, подставляя в (6) и т.д., что

С учетом выражений: (беря вторые производные от S(x) по х и подставляя  и )

   

 

И краевых условий (I) и условий (S) получим систему из n+1 линейных уравнений относительно неизвестных

(Приравнивая:

               (7)

Решая систему (7) методом Гаусса, получаем в результате прямой прогонки коэффициенты:

                                    (8)

Обратной прогонкой получаем результат:

                                  (9)

Результаты (8) и (9) позволяют построить кубический сплайн (6)

     Построение сплайна с учетом краевых условий (II) производится аналогично!

Точность интерполяционной функции f(x), имеющей на отрезке [a, b] непрерывные производные до 3-его порядка включительно, кубическим сплайном S(x)  по точкам равномерного разбиения отрезка с шагом h  при любых краевых условиях (I – III), оценивается неравенством:

  где                    (10)

! Неравенство (10) дает завышенную оценку точности.

 Пример: На отрезке [0, ] построить кубический сплайн с шагом , интерполирующий функцию , если заданы значения функции в трех узлах интерполяции:

 

 

x
Sin(x)

С помощью интерполяционной формулы вычислить приближенное значение  и сравнить с точным значением 0,5.

 

Решение: Т.к. задано 2 отрезка, , то представим сплайн в виде:

 

Краевые условия (I) имеют вид:

Из системы уравнений (7) имеем:

Находим

Подставляем значения  в (6). Получаем:

(т.к.  и числа, содержащие

Аналогично:

Получаем для : (т.к.

Т. о.

Погрешность меньше !

Мы могли бы получить выражение для  по формуле (8) и (9) – рекуррентные соотношения, получаемые при прямом и обратном прогоне в Методе Гаусса.

Действительно имеем:

               Находим:

7 Блок – схема программ интерполяции

(Ракитин, Первушин «Практическое руководство по методам вычислений. 1998)