Алгебраическая интерполяция
[править]
При алгебраической интерполяции для представления информации о функции
используется таблица значений этой функции:
![{\displaystyle x_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf) | ![{\displaystyle x_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a8788bf85d532fa88d1fb25eff6ae382a601c308) | ![{\displaystyle x_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7af1b928f06e4c7e3e8ebfd60704656719bd766) | ![{\displaystyle ..}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1424ae53b58e2605b332b6cb27ebd8f0756ae52) |
![{\displaystyle f(x_{0})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27cf1dbaefc6038a22779fb2943aff758a592a3a) | ![{\displaystyle f(x_{1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/af71fd012905bda20f1c736716748676d67c93f3) | ![{\displaystyle f(x_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c20b8a11295ef90324bb4ece6fe2a3dbb6ac996) | ![{\displaystyle ..}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1424ae53b58e2605b332b6cb27ebd8f0756ae52) |
Собственно, задачей вычислительной математики здесь является задача построения по таблице такой функции
, которая бы не сильно отличалась от
и выработка ограничений, и разработка критериев, при которых задача имеет решение.
Простейшие способы интерполяции
[править]
Простейшим способом интерполяции функции
по таблице является интерполяция методом ближайшего соседа. Один из ее вариантов формулируется так:
То есть за значение функции
берется значение функции
в точке, ближайшей к рассматриваемой.
Более точным способом интерполяции является кусочно-линейная интерполяция. При таком подходе значение
интерполируется по двум соседним с точкой
точкам.
(здесь подразумевается монотонное возрастание последовательности
)
Интересно понять, с какой точностью интерполяционные формулы аппроксимируют функцию
.
Предположим, что производная функции
ограничена величиной
. Тогда на отрезке
функция
не может отклониться от линейной интерполяции более, чем на
.
Если, кроме того, вторая производная функции
ограничена, можно построить более точную оценку:
TODO
Алгебраическим интерполяционным многочленом
называется многочлен
степени не выше
, принимающий в точках
значения
Теорема. Если заданы попарно различные узлы
и значения
, то алгебраический интерполяционный многочлен cсуществует и единственен.
Доказательство
Сначала докажем, что существует не более чем один интерполяционный многочлен, а затем построим его.
Если бы их было два, то их разность - многочлен степени не больше
, обращалась бы в 0 в
точке -
, что невозможно для ненулевого многочлена.
В качестве примера интерполяционного многочлена можно привести Интерполяционный многочлен Лагранжа (доказательство существования очевидно из построения, приведенного по ссылке).
Интерполяционный многочлен в форме Ньютона
Введем понятие разностного отношения. Разностным отношением нулевого порядка в точке
назовем значение
. Разностное отношение первого порядка определяется как
А n+1-го порядка - рекурсивно через разностное отношение n-го порядка:
Тогда можно показать, что интерполяционный многочлен может быть записан в следующей форме:
TODO
Основная идея сплайн-интерполяции функций - построение кусочно-полиномиальной интерполяции, при которой остается непрерывной функция
и несколько ее первых производных.
Предположим, мы хотим получить функцию, непрерывную вместе со своей первой производной.
Тогда для начала построим на заданной таблице кусочно-линейную интерполяцию
. Это непрерывная функция, производная которой в
каждом узле
имеет скачок
Теперь построим полином 3-ей степени
такой, что его производная точке
:
А значения в точках
и
равны 1.
Если теперь на отрезке
к функции
прибавить
, получившаяся функция будет непрерывна в
вместе со своей первой производной.
Осталось провести аналогичную операцию на всех остальных отрезках
, учитывая на каждом следующем отрезке производную уже построенной функции на предыдущем отрезке.
Тригонометрическая интерполяция
[править]
Другим важным видом интерполяции является интерполяция функции f тригонометрическим полиномом, называемой еще интерполяцией полиномом Фурье:
Интерполирующая функция представляет собой сумму конечного числа гармоник ряда Фурье.
Этот вид интерполяции особенно осмысленен для периодических функций. Пусть есть функция
с периодом
, т.е. для любого
:
Пусть эта функция задана таблицей на периодической сетке:
своими значениями
Оказывается, при правильном выборе
, существует только один полином
.
Неклассические методы интерполяции
[править]
В различных приложениях используются различные методы интерполяции, не сводящиеся к классическим. Рассмотрим некоторые из них.
Для реконструкции разрывных функций часто применяют так называемую minmod-реконструкцию. Суть ее в следующем:
Распределение функции на отрезке
полагается линейным, а коэффициент наклона выбирается как
,
где
Всюду гладкая интерполяция
[править]
Есть еще такая всюду гладкая интерполяция: