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

Вычислительная математика:

Интерполяция и аппроксимация функций
Решение систем скалярных уравнений
Решение систем дифференциальных уравнений
Решение систем интегро-дифференциальных уравнений

Численные методы математической статистики

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

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

При алгебраической интерполяции для представления информации о функции $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\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\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_1x+c_2x^2+...+c_nx^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}$ равны 0.

Если теперь на отрезке $[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}}$