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

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

Табличное задание функции

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

$x_{0}$	$x_{1}$	$x_{2}$	$..$
$f(x_{0})$	$f(x_{1})$	$f(x_{2})$	$..$

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

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

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

${\tilde {f}}(x)=f(x_{i}),i:\forall j\neq i,|x-x_{j}|>|x-x_{i}|$

То есть за значение функции ${\tilde {f}}(x)$ берется значение функции $f(x)$ в точке, ближайшей к рассматриваемой.

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

${\tilde {f}}(x)={\frac {f(x_{i})(x_{i+1}-x)+f(x_{i+1})(x-x_{i})}{x_{i+1}-x_{i}}},i:x_{i}<x<x_{i+1}$

(здесь подразумевается монотонное возрастание последовательности $x_{i}$)

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

Предположим, что производная функции $f$ ограничена величиной $g$. Тогда на отрезке $[x_{i},x_{i+1}]$ функция $f$ не может отклониться от линейной интерполяции более, чем на $h\left(g-\left|{\frac {f(x_{i+1})-f(x_{i})}{x_{i+1}-x_{i}}}\right|\right)$. Если, кроме того, вторая производная функции $f$ ограничена, можно построить более точную оценку:

TODO

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

Алгебраическим интерполяционным многочленом $P_{n}(x,f,x_{0},...,x_{n})$ называется многочлен

$P_{n}(x)=c_{0}+c_{1}x+c_{2}x^{2}+...+c_{n}x^{n}$

степени не выше $n$, принимающий в точках $x_{0},x_{1},...,x_{n}$ значения $f(x_{0}),f(x_{1}),...,f(x_{n})$

Теорема. Если заданы попарно различные узлы $x_{0},x_{1},x_{2},...,x_{n}$ и значения $f(x_{0}),f(x_{1}),...,f(x_{n})$, то алгебраический интерполяционный многочлен cсуществует и единственен.

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

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

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

Введем понятие разностного отношения. Разностным отношением нулевого порядка в точке $x_{i}$ назовем значение $f(x_{i})$. Разностное отношение первого порядка определяется как

$f(x_{i},x_{j})={\frac {f(x_{j})-f(x_{i})}{x_{j}-x_{i}}}$

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

$f(x_{0},x_{1},...,x_{n+1})={\frac {f(x_{1},x_{2},...,x_{n+1})-f(x_{0},x_{1},...,x_{n})}{x_{n+1}-x_{0}}}$

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

$P_{n}(x,f,x_{0},...,x_{n})=f(x_{0})+(x-x_{0})f(x_{0},x_{1})+...+(x-x_{0})(x-x_{1})...(x-x_{n-1})f(x_{0},...,x_{n})$

TODO

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

Основная идея сплайн-интерполяции функций - построение кусочно-полиномиальной интерполяции, при которой остается непрерывной функция ${\tilde {f}}(x)$ и несколько ее первых производных.

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

Тогда для начала построим на заданной таблице кусочно-линейную интерполяцию ${\tilde {f}}_{1}(x)$. Это непрерывная функция, производная которой в каждом узле $x_{i}$ имеет скачок

${\tilde {f}}_{1}'(x_{i}+\delta x)-{\tilde {f}}_{1}'(x_{i}-\delta x)={\frac {f_{i+1}-f_{i}}{x_{i+1}-x_{i}}}-{\frac {f_{i}-f_{i-1}}{x_{i}-x_{i-1}}}$

Теперь построим полином 3-ей степени $f_{2,i}(x)$ такой, что его производная точке $x_{i}$:

${\tilde {f}}_{2,i}'(x_{i})={\tilde {f}}_{1}'(x_{i}+\delta x)-{\tilde {f}}_{1}'(x_{i}-\delta x)$

А значения в точках $x_{i}$ и $x_{i+1}$ равны 1.

Если теперь на отрезке $[x_{i},x_{i+1}]$ к функции $f_{1}(x)$ прибавить $f_{2,i}(x)$, получившаяся функция будет непрерывна в $x_{i}$ вместе со своей первой производной.

Осталось провести аналогичную операцию на всех остальных отрезках $[x_{i},x_{i+1}]$, учитывая на каждом следующем отрезке производную уже построенной функции на предыдущем отрезке.

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

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

${\tilde {f}}(x)=\sum _{k=0}^{K}\left(a_{k}\sin \left({\frac {2\pi x}{L}}\right)+b_{k}\cos \left({\frac {2\pi x}{L}}\right)\right)$

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

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

$f(x+L)=f(x)$

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

$x_{n}={\frac {L}{N}}n+x_{0},n=0,1,...,N-1$

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

$f_{n}=f(x_{n})$

Оказывается, при правильном выборе $N,K,x_{0}$, существует только один полином ${\tilde {f}}(x)$.

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

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

Реконструкция функций

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

Распределение функции на отрезке $\left[-{\frac {x_{m-1}+x_{m}}{2}},{\frac {x_{m}+x_{m+1}}{2}}\right]$ полагается линейным, а коэффициент наклона выбирается как $q=\operatorname {minmod} \left({\frac {f_{m+1}-f_{m}}{x_{m+1}-x_{m}}},{\frac {f_{m}-f_{m-1}}{x_{m}-x_{m-1}}}\right)$, где $\operatorname {minmod} (a,b)={\frac {\operatorname {sign} (a)+\operatorname {sign} (b)}{2}}\min(|a|,|b|)$

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

Есть еще такая всюду гладкая интерполяция: $f(x)={\frac {\sum {\frac {f_{i}}{(x-x_{i})^{2}}}}{\sum {\frac {1}{(x-x_{i})^{2}}}}}$