32. Численные методы восстановления функций: интерполяция полиномом Лагранжа. Интерполяционные формулы Лагранжа и Ньютона без вывода.

Для каждой функции , определенной на [a,b], и любого набора узлов x₀, x₁,....,x_n( x_i [a,b], x_i x_j при i j ) среди алгебраических многочленов степени не выше n существует единственный интерполяционный многочлен Ф(x), который может быть записан в форме:

, (4.1)

где - многочлен n-ой степени, обладающий следующим свойством:

(4.2)

Для интерполяционного полинома многочлен имеет вид:

(4.3)

Этот многочлен (4.1) и решает задачу интерполирования и называется интерполяционным полиномом Лагранжа.

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

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

33. Численные методы восстановления функций: погрешность интерполирования (остаточный член интерполяционной формулы и оптимальный выбор узлов).

При решении задачи интерполяции величина n называется порядком интерполирующего полинома. При этом, как видно из формул (4.1) и (4.5), число узлов интерполирования всегда будет равно n+1 и значение x, для которого определяется величина , должно лежать внутри области определения узлов интерполяции т.е.

. (4.6)

В некоторых практических случаях общее известное число узлов интерполяции m может быть больше, чем порядок интерполирующего полинома n.

В этом случае, прежде чем реализовывать процедуру интерполяции согласно формуле (4.5), необходимо определить те узлы интерполяции, для которых справедливо условие (4.6). При этом следует помнить, что наименьшая погрешность достигается при нахождении значения x в центре области интерполяции. Для обеспечения этого предлагается следующая процедура:

После ввода в программу значения величины Х необходимо проверить условие x₀  x  x_m, где x₀ и x_m – начальное и конечное значение узловых точек интерполяции.

При выполнения предыдущего условия начинается поиск области интерполяции, для чего находим первое x_i такое, для которого выполняется условие x_i > x, при этом номер i будет соответствовать середине интервала интерполяции. Для определения области интерполяции ее левая граница будет начинаться с номера , а заканчиваться узлом с номером .

После выполнения пунктов 1 и 2 программируется формула (4.5).

Основное назначение интерполяции – это вычисление значений табулированной функции для неузловых (промежуточных) значений аргумента, поэтому интерполяцию часто называют «искусством чтения таблиц между строками».

Остаточный член интерполяционной формулы

Заменяя функцию интерполяционным полиномом , мы допускаем погрешность (3.3.1):

(3.3.1)

которая называется погрешностью интерполирования или остаточным членом интерполяционной формулы.

В узлах интерполирования эта погрешность равна нулю.

Погрешность интерполирования определяется следующим соотношением (3.3.2):

(3.3.2)

где и

Отсюда следует оценка точности восстановления функции (3.3.3):

(3.3.3)

где

(3.3.4)

где .

В частности, если - алгебраический многочлен степени , то интерполирование, проведено по любым точкам , осуществляется точно.

Данная оценка справедлива как для формулы Лагранжа. Так и для формулы Ньютона.

3.3.2 Оптимальный выбор узлов

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

Задача состоит в том, чтобы подобрать узлы , так чтобы минимизировать величину:

Решение данной задачи определяется следующим соотношением:

(3.3.5)

и оценка (3.3.3) примет вид:

(3.3.6)

Но при этом следует помнить, что бесконечное увеличение числа узлов может и не привести к уменьшению ошибки интерполяции.

34. Численные методы восстановления функций: интерполяция кубическим сплайном. Интерполирование многочленами Лагранжа или Ньютона на всем отрезке с использованием большого числа узлов интерполяции часто приводит к плохому приближению, что объясняется сильным накоплением погрешности в процессе вычислений. Для того чтобы избежать больших погрешностей, весь отрезок разбивают на частичные отрезки и на каждом из частичных отрезков приближенно заменяют функцию многочленом невысокой степени (кусочно-полиномиальная интерполяция). Одним из способов интерполирования является интерполирование с помощью сплайн-функций.

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

3.4.1 Интерполяция кубическим сплайном

Пусть на интервале задана непрерывная функция . Введем

и обозначим , .

Сплайном, соответствующим функции и узлам называется функция , удовлетворяющая следующим условиям:

на каждом сегменте , функция является многочленом третьей степени;

функция , а также ее первая и вторая производные непрерывны на (условия непрерывности);

(условия интерполирования).

Построение сплайна (алгоритм интерполирования):

В отличие от интерполяции Лагранжа, когда вся функция аппроксимируется одним полиномом, при сплайновой интерполяции на каждом интервале

На каждом отрезке будем искать функцию в виде многочлена (3.4.1):

(3.4.1)

где - коэффициенты, подлежащие определению.

Коэффициент

Коэффициент , так как .

Коэффициент , так как .

Коэффициент , так как .

Найдем коэффициенты из условий, которым должен удовлетворять сплайн:

Условия интерполирования: при этом и условия непрерывности функции: для каждого приводят к уравнению (3.4.2):

(3.4.2)

Обозначим , перепишем уравнениям (3.4.2) в виде (3.4.3)

(3.4.3)

Условия непрерывности первой производной для каждого приводят к уравнениям (3.4.4)

(3.4.4)

Условия непрерывности второй производной для каждого приводят к уравнениям (3.4.5):

(3.4.5)

Объединяя уравнения (3.4.3), (3.4.4), (3.4.5) получим систему уравнений относительно неизвестных .

Два недостающих уравнения получают, задавая те или иные граничные условия для . Например, что функция удовлетворяет условиям . Тогда из этого условия получаем недостающие уравнения (3.4.6):

и (3.4.6)

Таким образом, получаем замкнутую систему, разрешив которую относительно коэффициентов кубического сплайна получим эти коэффициенты.