Интерполяция

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Октябрь 2016 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математической области численного анализа , интерполяция представляет собой тип оценки , метод построения новых точек данных в пределах диапазона с дискретным множеством известных точек данных. ^[1]

В инженерии и науке часто бывает несколько точек данных, полученных путем выборки или экспериментирования , которые представляют значения функции для ограниченного числа значений независимой переменной . Часто требуется интерполировать , т. Е. Оценить значение этой функции для промежуточного значения независимой переменной.

Тесно связанная проблема - приближение сложной функции простой функцией. Предположим, что формула для некоторой заданной функции известна, но слишком сложна для ее эффективного вычисления. Несколько точек данных из исходной функции можно интерполировать для получения более простой функции, которая все еще довольно близка к исходной. В результате выигрыш в простоте может перевесить потери из-за ошибки интерполяции.

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

Пример [ править ]

В этой таблице приведены некоторые значения неизвестной функции .${\ displaystyle f (x)}$

График точек данных, как указано в таблице.

	${\ displaystyle x}$		${\ displaystyle f (x)}$
	0		0
	1		0	.	8415
	2		0	.	9093
	3		0	.	1411
	4		−0	.	7568
	5		−0	.	9589
	6		−0	.	2794

Интерполяция позволяет оценить функцию в промежуточных точках, например .${\ displaystyle x = 2,5}$

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

Кусочная постоянная интерполяция [ править ]

Кусочная постоянная интерполяция или интерполяция ближайшего соседа .

Самый простой метод интерполяции - найти ближайшее значение данных и присвоить то же значение. В простых задачах этот метод вряд ли будет использоваться, поскольку линейная интерполяция (см. Ниже) почти так же проста, но в многомерной многомерной интерполяции это может быть благоприятным выбором из-за ее скорости и простоты.

Линейная интерполяция [ править ]

Один из простейших методов - линейная интерполяция (иногда известная как lerp). Рассмотрим приведенный выше пример оценки f (2.5). Поскольку 2,5 находится посередине между 2 и 3, разумно взять f (2,5) посередине между f (2) = 0,9093 и f (3) = 0,1411, что дает 0,5252.

Как правило, линейная интерполяция принимает две точки данных, скажем ( x _a , y _a ) и ( x _b , y _b ), а интерполянт задается следующим образом:

${\ displaystyle y = y_ {a} + \ left (y_ {b} -y_ {a} \ right) {\ frac {x-x_ {a}} {x_ {b} -x_ {a}}} {\ текст {в точке}} \ left (x, y \ right)}$

${\ displaystyle {\ frac {y-y_ {a}} {y_ {b} -y_ {a}}} = {\ frac {x-x_ {a}} {x_ {b} -x_ {a}}} }$

${\ displaystyle {\ frac {y-y_ {a}} {x-x_ {a}}} = {\ frac {y_ {b} -y_ {a}} {x_ {b} -x_ {a}}} }$

В этом предыдущем уравнении говорится, что наклон новой линии между и такой же, как наклон линии между и${\displaystyle (x_{a},y_{a})}$${\displaystyle (x,y)}$${\displaystyle (x_{a},y_{a})}$${\displaystyle (x_{b},y_{b})}$

Линейная интерполяция выполняется быстро и легко, но не очень точно. Другой недостаток состоит в том, что интерполянт не дифференцируем в точке x _k .

Следующая оценка ошибки показывает, что линейная интерполяция не очень точна. Обозначим функцию, которую мы хотим интерполировать, через g и предположим, что x лежит между x _a и x _b и что g дважды непрерывно дифференцируема. Тогда погрешность линейной интерполяции равна

${\displaystyle |f(x)-g(x)|\leq C(x_{b}-x_{a})^{2}\quad {\text{where}}\quad C={\frac {1}{8}}\max _{r\in [x_{a},x_{b}]}|g''(r)|.}$

На словах ошибка пропорциональна квадрату расстояния между точками данных. Ошибка в некоторых других методах, включая полиномиальную интерполяцию и сплайн-интерполяцию (описанных ниже), пропорциональна более высоким степеням расстояния между точками данных. Эти методы также позволяют получить более гладкие интерполянты.

Полиномиальная интерполяция [ править ]

Полиномиальная интерполяция - это обобщение линейной интерполяции. Обратите внимание, что линейный интерполянт является линейной функцией . Теперь заменим этот интерполянт на многочлен более высокой степени .

Снова рассмотрим проблему, указанную выше. Следующий многочлен шестой степени проходит через все семь точек:

${\displaystyle f(x)=-0.0001521x^{6}-0.003130x^{5}+0.07321x^{4}-0.3577x^{3}+0.2255x^{2}+0.9038x.}$

Подставляя x = 2,5, находим f (2,5) = ~ 0,59678.

Обычно, если у нас есть n точек данных, существует ровно один полином степени не выше n −1, проходящий через все точки данных. Ошибка интерполяции пропорциональна расстоянию между точками данных в степени n . Кроме того, интерполянт является многочленом и, следовательно, бесконечно дифференцируемым. Итак, мы видим, что полиномиальная интерполяция преодолевает большинство проблем линейной интерполяции.

Однако полиномиальная интерполяция также имеет некоторые недостатки. Вычисление интерполяционного полинома требует больших вычислительных ресурсов (см. Вычислительную сложность ) по сравнению с линейной интерполяцией. Кроме того, полиномиальная интерполяция может демонстрировать колебательные артефакты, особенно в конечных точках (см . Феномен Рунге ).

Полиномиальная интерполяция может оценивать локальные максимумы и минимумы, которые находятся за пределами диапазона выборок, в отличие от линейной интерполяции. Например, приведенный выше интерполянт имеет локальный максимум при x ≈ 1,566, f ( x ) ≈ 1,003 и локальный минимум при x ≈ 4,708, f ( x ) ≈ −1,003. Однако эти максимумы и минимумы могут выходить за пределы теоретического диапазона функции - например, функция, которая всегда положительна, может иметь интерполянт с отрицательными значениями, и, следовательно, обратная функция которой содержит ложные вертикальные асимптоты .

В более общем плане форма результирующей кривой, особенно для очень высоких или низких значений независимой переменной, может противоречить здравому смыслу, то есть тому, что известно об экспериментальной системе, которая генерировала точки данных. Эти недостатки можно уменьшить, используя сплайн-интерполяцию или ограничивая внимание полиномами Чебышева .

Сплайн-интерполяция [ править ]

Помните, что линейная интерполяция использует линейную функцию для каждого из интервалов [ x _k , x _{k + 1} ]. Сплайн-интерполяция использует полиномы низкой степени в каждом из интервалов и выбирает части полинома так, чтобы они плавно совпадали. Полученная функция называется сплайном .

Например, естественный кубический сплайн является кусочно - кубической и дважды непрерывно дифференцируема. Кроме того, его вторая производная равна нулю в конечных точках. Естественный кубический сплайн, интерполирующий точки в таблице выше, имеет вид

${\displaystyle f(x)={\begin{cases}-0.1522x^{3}+0.9937x,&{\text{if }}x\in [0,1],\\-0.01258x^{3}-0.4189x^{2}+1.4126x-0.1396,&{\text{if }}x\in [1,2],\\0.1403x^{3}-1.3359x^{2}+3.2467x-1.3623,&{\text{if }}x\in [2,3],\\0.1579x^{3}-1.4945x^{2}+3.7225x-1.8381,&{\text{if }}x\in [3,4],\\0.05375x^{3}-0.2450x^{2}-1.2756x+4.8259,&{\text{if }}x\in [4,5],\\-0.1871x^{3}+3.3673x^{2}-19.3370x+34.9282,&{\text{if }}x\in [5,6].\end{cases}}}$

В этом случае мы получаем f (2,5) = 0,5972.

Подобно полиномиальной интерполяции, сплайн-интерполяция вызывает меньшую ошибку, чем линейная интерполяция, в то время как интерполянт более гладкий и более простой для оценки, чем полиномы высокой степени, используемые в полиномиальной интерполяции. Однако глобальный характер базисных функций ведет к плохой обусловленности. Это полностью смягчается использованием шлицев компактной опоры, таких как реализованные в Boost.Math и обсуждаемые в Kress. ^[2]

Аппроксимация функции [ править ]

Интерполяция - это распространенный способ аппроксимации функций. Для данной функции с набором точек можно сформировать такую ​​функцию , что для (то есть интерполирует в этих точках). В общем, интерполянт не обязательно должен быть хорошим приближением, но есть хорошо известные и часто разумные условия, в которых он будет. Например, если (четырехкратно непрерывно дифференцируемый), то кубическая сплайн-интерполяция имеет границу ошибки, задаваемую где и - константа. ^[3]${\displaystyle f:[a,b]\to \mathbb {R} }$${\displaystyle x_{1},x_{2},\dots ,x_{n}\in [a,b]}$${\displaystyle s:[a,b]\to \mathbb {R} }$${\displaystyle f(x_{i})=s(x_{i})}$${\displaystyle i=1,2,\dots ,n}$${\displaystyle s}$${\displaystyle f}$${\displaystyle f\in C^{4}([a,b])}$${\displaystyle \|f-s\|_{\infty }\leq C\|f^{(4)}\|_{\infty }h^{4}}$${\displaystyle h\max _{i=1,2,\dots ,n-1}|x_{i+1}-x_{i}|}$${\displaystyle C}$

Через гауссовские процессы [ править ]

Гауссовский процесс - мощный инструмент нелинейной интерполяции. Многие популярные инструменты интерполяции фактически эквивалентны конкретным гауссовским процессам. Гауссовские процессы могут использоваться не только для подбора интерполянта, который проходит точно через заданные точки данных, но также и для регрессии, то есть подгонки кривой через зашумленные данные. В геостатистическом сообществе регрессия гауссовского процесса также известна как кригинг .

Другие формы [ править ]

Другие формы интерполяции можно построить, выбрав другой класс интерполянтов. Например, рациональная интерполяция интерполяции по рациональным функциям с помощью Пада и тригонометрическая интерполяцией является интерполяцией тригонометрических полиномов с использованием рядов Фурье . Другая возможность - использовать вейвлеты .

Интерполяционной формуле Уиттакер-Шеннона может быть использовано , если число точек данных является бесконечным , или если функция для интерполяции имеет компактный носитель.

Иногда мы знаем не только значение функции, которую мы хотим интерполировать, в некоторых точках, но и ее производную. Это приводит к проблемам интерполяции Эрмита .

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

В высших измерениях [ править ]

Многомерная интерполяция - это интерполяция функций более чем одной переменной. Методы включают билинейную интерполяцию и бикубическую интерполяцию в двух измерениях, а также трилинейную интерполяцию в трех измерениях. Их можно применять к данным с координатной сеткой или разбросом.

• Ближайший сосед

• Билинейный

• Бикубический

В цифровой обработке сигналов [ править ]

В области обработки цифрового сигнала термин интерполяция относится к процессу преобразования дискретизированного цифрового сигнала (такого как дискретизированный аудиосигнал) в сигнал с более высокой частотой дискретизации ( повышающая дискретизация ) с использованием различных методов цифровой фильтрации (например, свертка с частотно-ограниченный импульсный сигнал). В этом приложении есть особое требование, чтобы гармоническое содержание исходного сигнала сохранялось без создания наложенного гармонического содержания исходного сигнала выше исходного предела Найквиста сигнала (то есть выше fs / 2 частоты дискретизации исходного сигнала). Раннее и довольно элементарное обсуждение этого вопроса можно найти в книге Рабинера и Крошьера « Многоскоростная цифровая обработка сигналов» . ^[4]

Понятия, связанные с данным [ править ]

Термин экстраполяция используется для поиска точек данных за пределами диапазона известных точек данных.

В задачах аппроксимации кривой ограничение, согласно которому интерполянт должен проходить точно через точки данных, ослабляется. Требуется только подойти к точкам данных как можно ближе (с некоторыми другими ограничениями). Это требует параметризации потенциальных интерполянтов и наличия некоторого способа измерения ошибки. В простейшем случае это приводит к приближению наименьших квадратов .

Теория приближений изучает, как найти наилучшее приближение к заданной функции другой функцией из некоторого предопределенного класса и насколько хорошо это приближение. Это явно дает оценку того, насколько хорошо интерполянт может аппроксимировать неизвестную функцию.

Обобщение [ править ]

Если мы рассматриваем как переменную в топологическом пространстве , так и функцию, отображающуюся в банахово пространство , то проблема трактуется как «интерполяция операторов». ^[5] Классические результаты об интерполяции операторов являются теорема Рисса-Торина и теорема Марцинкевича . Есть и много других последующих результатов.${\displaystyle x}$${\displaystyle f(x)}$

См. Также [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы по теме интерполяции .

• Онлайн-инструменты для линейной , квадратичной , кубической сплайновой и полиномиальной интерполяции с визуализацией и исходным кодом JavaScript .
• Учебники Sol - Уловки интерполяции
• Компактно поддерживаемая интерполяция кубического B-сплайна в Boost.Math
• Барицентрическая рациональная интерполяция в Boost.Math
• Интерполяция с помощью преобразования Чебышева в Boost.Math