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

==Алгебраическая интерполяция==
===Табличное задание функции===

При алгебраической интерполяции для представления информации о функции <math>f(x)</math> используется таблица значений этой функции:
<table>
<tr><TD><math>x_0</math></td><TD><math>x_1</math></td><TD><math>x_2</math></td><TD><math>..</math></td>
</tr>
<tr><TD><math>f(x_0)</math></td><TD><math>f(x_1)</math></td><TD><math>f(x_2)</math></td><TD><math>..</math></td>
</tr>
</table>

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

===Простейшие способы интерполяции===
Простейшим способом интерполяции функции <math>f</math> по таблице является [[w:Интерполяция методом ближайшего соседа|интерполяция методом ближайшего соседа]]. Один из ее вариантов формулируется так:

<math>\tilde f(x) = f(x_i),i:\forall j\ne i, |x-x_j|>|x-x_i|</math>

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

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

<math>\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}
</math>

(здесь подразумевается монотонное возрастание последовательности <math>x_i</math>)

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

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

TODO

===Интерполяционные полиномы===
<i>Алгебраическим интерполяционным многочленом</i> <math>P_n(x,f,x_0,...,x_n)</math> называется многочлен 

<math>P_n(x)=c_0+c_1x+c_2x^2+...+c_nx^n</math>

степени не выше <math>n</math>, принимающий в точках <math>x_0,x_1,...,x_n</math> значения <math>f(x_0),f(x_1),...,f(x_n)</math>

<b>Теорема.</b> Если заданы попарно различные узлы <math>x_0,x_1,x_2,...,x_n</math> и значения <math>f(x_0), f(x_1), ...,f(x_n)</math>, то алгебраический интерполяционный многочлен cсуществует и единственен.


<b>Доказательство</b>
Сначала докажем, что существует не более чем один интерполяционный многочлен, а затем построим его.
Если бы их было два, то их разность - многочлен степени не больше <math>n</math>, обращалась бы в 0 в <math>n+1</math> точке - <math>x_0,x_1,...,x_n</math>, что невозможно для ненулевого многочлена.

В качестве примера интерполяционного многочлена можно привести [http://ru.wikipedia.org/wiki/Интерполяционный_многочлен_Лагранжа Интерполяционный многочлен Лагранжа] (доказательство существования очевидно из построения, приведенного по ссылке).

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

Введем понятие <i>разностного отношения</i>. Разностным отношением нулевого порядка в точке <math>x_i</math> назовем значение <math>f(x_i)</math>. Разностное отношение первого порядка определяется как

<math>f(x_i,x_j)=\frac{f(x_j)-f(x_i)}{x_j-x_i}</math>

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

<math>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}</math>

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

<math>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)</math>

TODO

===Сплайн-интерполяция===
Основная идея [[w:Сплайн|сплайн]]-интерполяции функций - построение кусочно-полиномиальной интерполяции, при которой остается непрерывной функция <math>\tilde f(x)</math> и несколько ее первых производных.

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

Тогда для начала построим на заданной таблице кусочно-линейную интерполяцию <math>\tilde f_1(x)</math>. Это непрерывная функция, производная которой в
каждом узле <math>x_i</math> имеет скачок 

<math>\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}}</math>

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

<math>\tilde f_{2,i}'(x_i)=\tilde f_1'(x_i+\delta x) - \tilde f_1'(x_i-\delta x)</math>

А значения в точках <math>x_i</math> и <math>x_{i+1}</math> равны 1. 

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

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

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

<math>\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) </math>

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

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

<math>f(x+L)=f(x)</math>

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

<math>
x_n=\frac{L}{N}n+x_0, n=0,1,...,N-1
</math>

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

<math>
f_n=f(x_n)
</math>

Оказывается, при правильном выборе <math>N,K,x_0</math>, существует только один полином <math>\tilde f(x)</math>.

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

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

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

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

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

[[Категория:Вычислительная математика]]