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

Материал из Викиучебника — открытых книг для открытого мира
(перенаправлено с «Алгебраическая интерполяция»)

Алгебраическая интерполяция[править]

Табличное задание функции[править]

При алгебраической интерполяции для представления информации о функции используется таблица значений этой функции:

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

Простейшие способы интерполяции[править]

Простейшим способом интерполяции функции по таблице является интерполяция методом ближайшего соседа. Один из ее вариантов формулируется так:

То есть за значение функции берется значение функции в точке, ближайшей к рассматриваемой.

Более точным способом интерполяции является кусочно-линейная интерполяция. При таком подходе значение интерполируется по двум соседним с точкой точкам.

(здесь подразумевается монотонное возрастание последовательности )

Интересно понять, с какой точностью интерполяционные формулы аппроксимируют функцию .

Предположим, что производная функции ограничена величиной . Тогда на отрезке функция не может отклониться от линейной интерполяции более, чем на . Если, кроме того, вторая производная функции ограничена, можно построить более точную оценку:

TODO

Интерполяционные полиномы[править]

Алгебраическим интерполяционным многочленом называется многочлен

степени не выше , принимающий в точках значения

Теорема. Если заданы попарно различные узлы и значения , то алгебраический интерполяционный многочлен cсуществует и единственен.


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

В качестве примера интерполяционного многочлена можно привести Интерполяционный многочлен Лагранжа (доказательство существования очевидно из построения, приведенного по ссылке).

Интерполяционный многочлен в форме Ньютона

Введем понятие разностного отношения. Разностным отношением нулевого порядка в точке назовем значение . Разностное отношение первого порядка определяется как

А n+1-го порядка - рекурсивно через разностное отношение n-го порядка:

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

TODO

Сплайн-интерполяция[править]

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

Предположим, мы хотим получить функцию, непрерывную вместе со своей первой производной.

Тогда для начала построим на заданной таблице кусочно-линейную интерполяцию . Это непрерывная функция, производная которой в каждом узле имеет скачок

Теперь построим полином 3-ей степени такой, что его производная точке :

А значения в точках и равны 1.

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

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

Тригонометрическая интерполяция[править]

Другим важным видом интерполяции является интерполяция функции f тригонометрическим полиномом, называемой еще интерполяцией полиномом Фурье:

Интерполирующая функция представляет собой сумму конечного числа гармоник ряда Фурье.

Этот вид интерполяции особенно осмысленен для периодических функций. Пусть есть функция с периодом , т.е. для любого :

Пусть эта функция задана таблицей на периодической сетке:

своими значениями

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

Неклассические методы интерполяции[править]

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

Реконструкция функций[править]

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

Распределение функции на отрезке полагается линейным, а коэффициент наклона выбирается как , где

Всюду гладкая интерполяция[править]

Есть еще такая всюду гладкая интерполяция: