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

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

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

При алгебраической интерполяции для представления информации о функции $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:\mathrm{\forall }j\ne 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(g-\left|\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}\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}^{\prime }(x_i+\delta x)-{{\tilde{f}}_1}^{\prime }(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^{\prime },i}(x_i)={{\tilde{f}}_1}^{\prime }(x_i+\delta x)-{{\tilde{f}}_1}^{\prime }(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(a_k\sin \left(\frac{2\pi x}{L}\right)+b_k\cos \left(\frac{2\pi x}{L}\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-реконструкцию. Суть ее в следующем:

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

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

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