Интерполяция и аппроксимация функций: различия между версиями
Содержимое удалено Содержимое добавлено
Ramir (обсуждение | вклад) мНет описания правки |
Ramir (обсуждение | вклад) мНет описания правки |
||
Строка 1:
{{Вычислительная математика}}
==Алгебраическая интерполяция==
===Табличное задание функции===
При алгебраической итерполяции для представления информации о функции <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> по таблице является ступенчатая интерполяция. Один из ее вариантов формулируется так:
<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(g-|\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}|)</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
===Сплайн-интерполяция===
Основная идея [http://ru.wikipedia.org/wiki/Сплайн сплайн]-интерполяции функций - построение кусочно-полиномиальной интерполяции, при которой остается непрерывной функция <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> равны 0.
Если теперь на отрезке <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 \Big( a_k \sin(\frac{2\pi x}{L}) + b_k \cos(\frac{2\pi x}{L}) \Big) </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, m=0,1,...,N-1
</math>
своими значениями
<math>
f_m=f(x_m)
</math>
Оказывается, при правильном выборе <math>N,K,x_0</math>, существует только один полином <math>\tilde f(x)</math>.
==Неклассические методы интерполяции==
В различных приложениях используются различные методы интерполяции, не сводящиеся к классическим. Рассмотрим некоторые из них.
=== Реконструкция функций ===
Для реконструкции разрывных функций часто применяют так называемую minmod-реконструкцию. Суть ее в следующем:
Распределение функции на отрезке <math>[-(x_{m-1}+x_m)/2,(x_m+x_{m+1})/2]</math> полагается линейным, а коэффициент наклона выбирается как
<math>q=\operatorname{minmod}(\frac{f_{m+1}-f_{m}}{x_{m+1}-x_m},\frac{f_{m}-f_{m-1}}{x_{m}-x_{m-1}})</math>,
где <math>\operatorname{minmod}(a,b)=\frac{\operatorname{sign}(a)+\operatorname{sign}(b)}{2}\min(|a|,|b|)</math>
=== (unknown) ===
Есть еще такая всюду гладкая интерполяция:
<math>f(x)=\frac{\sum \frac{f_i}{(x-x_i)^2}}{\sum \frac{1}{(x-x_i)^2}}</math>
[[Категория:Вычислительная математика]]
| |||