Интерполяция и аппроксимация функций
Алгебраическая интерполяция
правитьТабличное задание функции
правитьПри алгебраической интерполяции для представления информации о функции используется таблица значений этой функции:
Собственно, задачей вычислительной математики здесь является задача построения по таблице такой функции , которая бы не сильно отличалась от и выработка ограничений, и разработка критериев, при которых задача имеет решение.
Простейшие способы интерполяции
правитьПростейшим способом интерполяции функции по таблице является интерполяция методом ближайшего соседа. Один из ее вариантов формулируется так:
То есть за значение функции берется значение функции в точке, ближайшей к рассматриваемой.
Более точным способом интерполяции является кусочно-линейная интерполяция. При таком подходе значение интерполируется по двум соседним с точкой точкам.
(здесь подразумевается монотонное возрастание последовательности )
Интересно понять, с какой точностью интерполяционные формулы аппроксимируют функцию .
Предположим, что производная функции ограничена величиной . Тогда на отрезке функция не может отклониться от линейной интерполяции более, чем на . Если, кроме того, вторая производная функции ограничена, можно построить более точную оценку:
TODO
Интерполяционные полиномы
правитьАлгебраическим интерполяционным многочленом называется многочлен
степени не выше , принимающий в точках значения
Теорема. Если заданы попарно различные узлы и значения , то алгебраический интерполяционный многочлен cсуществует и единственен.
Доказательство
Сначала докажем, что существует не более чем один интерполяционный многочлен, а затем построим его.
Если бы их было два, то их разность - многочлен степени не больше , обращалась бы в 0 в точке - , что невозможно для ненулевого многочлена.
В качестве примера интерполяционного многочлена можно привести Интерполяционный многочлен Лагранжа (доказательство существования очевидно из построения, приведенного по ссылке).
Интерполяционный многочлен в форме Ньютона
Введем понятие разностного отношения. Разностным отношением нулевого порядка в точке назовем значение . Разностное отношение первого порядка определяется как
А n+1-го порядка - рекурсивно через разностное отношение n-го порядка:
Тогда можно показать, что интерполяционный многочлен может быть записан в следующей форме:
TODO
Сплайн-интерполяция
правитьОсновная идея сплайн-интерполяции функций - построение кусочно-полиномиальной интерполяции, при которой остается непрерывной функция и несколько ее первых производных.
Предположим, мы хотим получить функцию, непрерывную вместе со своей первой производной.
Тогда для начала построим на заданной таблице кусочно-линейную интерполяцию . Это непрерывная функция, производная которой в каждом узле имеет скачок
Теперь построим полином 3-ей степени такой, что его производная точке :
А значения в точках и равны 1.
Если теперь на отрезке к функции прибавить , получившаяся функция будет непрерывна в вместе со своей первой производной.
Осталось провести аналогичную операцию на всех остальных отрезках , учитывая на каждом следующем отрезке производную уже построенной функции на предыдущем отрезке.
Тригонометрическая интерполяция
правитьДругим важным видом интерполяции является интерполяция функции f тригонометрическим полиномом, называемой еще интерполяцией полиномом Фурье:
Интерполирующая функция представляет собой сумму конечного числа гармоник ряда Фурье.
Этот вид интерполяции особенно осмысленен для периодических функций. Пусть есть функция с периодом , т.е. для любого :
Пусть эта функция задана таблицей на периодической сетке:
своими значениями
Оказывается, при правильном выборе , существует только один полином .
Неклассические методы интерполяции
правитьВ различных приложениях используются различные методы интерполяции, не сводящиеся к классическим. Рассмотрим некоторые из них.
Реконструкция функций
правитьДля реконструкции разрывных функций часто применяют так называемую minmod-реконструкцию. Суть ее в следующем:
Распределение функции на отрезке полагается линейным, а коэффициент наклона выбирается как , где
Всюду гладкая интерполяция
правитьЕсть еще такая всюду гладкая интерполяция: