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

Материал из Викиучебника

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

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

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

Содержание

1 Алгебраическая интерполяция
2 Тригонометрическая интерполяция
3 Неклассические методы интерполяции
- 3.1 Реконструкция функций
- 3.2 (unknown)

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

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

При алгебраической интерполяции для представления информации о функции $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 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$ равны 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, m=0,1,...,N-1$

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

$f m = f (x m)$

Оказывается, при правильном выборе $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|)$