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

(перенаправлено с «Алгебраическая интерполяция»)

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

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

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

    
    

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

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

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

 

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

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

 

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

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

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

TODO

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

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

 

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

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


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

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

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

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

 

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

 

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

 

TODO

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

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

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

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

 

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

 

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

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

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

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

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

 

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

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

 

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

 

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

 

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

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

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

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

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

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

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

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