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

Метод оценки новых данных в пределах известных точек данных

В математической области численного анализа интерполяция — это тип оценки , метод построения (поиска) новых точек данных на основе диапазона дискретного набора известных точек данных. ^{[1] [2]}

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

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

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

Пример

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

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

Интерполяция предоставляет средства оценки функции в промежуточных точках, например: ${\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}}}{\text{ at the point }}\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})}$

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

Следующая оценка ошибки показывает, что линейная интерполяция не очень точна. Обозначим функцию, которую мы хотим интерполировать, через 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. ^[3]

Миметическая интерполяция

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

Ключевой особенностью миметической интерполяции является то, что выполняются тождества векторного исчисления , включая теорему Стокса и теорему о дивергенции . В результате миметическая интерполяция сохраняет интегралы линий, площадей и объёмов. ^[4] Сохранение линейных интегралов может быть желательным, например, при интерполяции электрического поля , поскольку линейный интеграл дает разность электрических потенциалов в конечных точках пути интегрирования. ^[5] Миметическая интерполяция гарантирует, что ошибка оценки линейного интеграла электрического поля такая же, как ошибка, полученная при интерполяции потенциала в конечных точках пути интегрирования, независимо от длины пути интегрирования.

Линейная , билинейная и трилинейная интерполяция также считается миметической, даже если сохраняются значения поля (а не интеграл поля). Помимо линейной интерполяции, интерполяцию, взвешенную по площади, можно считать одним из первых разработанных методов миметической интерполяции. ^[6]

Аппроксимация функции

Интерполяция — распространенный способ аппроксимации функций. Учитывая функцию с набором точек, можно сформировать функцию такую, что for (то есть которая интерполирует в этих точках). В общем, интерполянт не обязательно должен быть хорошим приближением, но существуют хорошо известные и часто разумные условия, при которых он будет. Например, если (четыре раза непрерывно дифференцируемо), то интерполяция кубическим сплайном имеет границу ошибки, определяемую где и является константой. ^[7] ${\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}$

Через гауссовы процессы

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

Другие формы

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

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

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

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

В высших измерениях

Сравнение некоторых 1- и 2-мерных интерполяций.
Черные и красные / желтые / зеленые / синие точки соответствуют интерполируемой точке и соседним выборкам соответственно.
Их высота над землей соответствует их значениям.

Многомерная интерполяция — это интерполяция функций более чем одной переменной. Методы включают билинейную интерполяцию и бикубическую интерполяцию в двух измерениях и трилинейную интерполяцию в трех измерениях. Их можно применять к данным с координатной сеткой или к разбросанным данным. Миметическая интерполяция обобщается на размерные пространства, где . ^{[8] [9]} ${\displaystyle n}$ ${\displaystyle n>3}$

• 
  Ближайший сосед
• 
  Билинейный
• 
  Бикубический

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

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

Связанные понятия

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

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

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

Обобщение

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

Смотрите также

• Барицентрические координаты - для интерполяции внутри треугольника или тетраэдра.
• Интерполяционная формула Брахмагупты
• Фрактальная интерполяция
• Вменение (статистика)
• Интерполяция Лагранжа
• Недостающие данные
• Формулы Ньютона–Котеса
• Интерполяция радиальной базисной функции
• Простое рациональное приближение

Рекомендации

1. Шеппард, Уильям Флитвуд (1911). «Интерполяция»  . В Чисхолме, Хью (ред.). Британская энциклопедия . Том. 14 (11-е изд.). Издательство Кембриджского университета. стр. 706–710.
2. Стеффенсен, Дж. Ф. (2006). Интерполяция (Второе изд.). Минеола, ISBN штата Нью-Йорк 978-0-486-15483-1. ОСЛК  867770894.{{cite book}}: CS1 maint: location missing publisher (link)
3. Кресс, Райнер (1998). Численный анализ. ISBN 9781461205999.
4. Плетцер, Александр; Хайек, Вольфганг (01 января 2019 г.). «Миметическая интерполяция векторных полей на C/D-сетках Аракавы». Ежемесячный обзор погоды . 147 (1): 3–16. Бибкод : 2019MWRv..147....3P. doi : 10.1175/MWR-D-18-0146.1. ISSN  1520-0493. S2CID  125214770.
5. Стерн, Ари; Тонг, Иин; Дебрен, Матье; Марсден, Джеррольд Э. (2015), Чанг, Донг Ый; Холм, Дэррил Д.; Патрик, Джордж; Ратиу, Тюдор (ред.), «Геометрическая вычислительная электродинамика с вариационными интеграторами и дискретными дифференциальными формами», Геометрия, механика и динамика , Связь Института Поля, Нью-Йорк, Нью-Йорк: Springer New York, vol. 73, стр. 437–475, arXiv : 0707.4470 , doi : 10.1007/978-1-4939-2441-7_19, ISBN 978-1-4939-2440-0, S2CID  15194760 , получено 15 июня 2022 г.
6. Джонс, Филип (1999). «Схемы консервативного переотображения первого и второго порядка для сеток в сферических координатах». Ежемесячный обзор погоды . 127 (9): 2204–2210. Бибкод : 1999MWRv..127.2204J. doi : 10.1175/1520-0493(1999)127<2204:FASOCR>2.0.CO;2 . S2CID  122744293.
7. Холл, Чарльз А.; Мейер, Уэстон В. (1976). «Оптимальные границы ошибок для интерполяции кубическими сплайнами». Журнал теории приближения . 16 (2): 105–122. дои : 10.1016/0021-9045(76)90040-X .
8. Уитни, Хасслер (1957). Геометрическая теория интегрирования . Дуврские книги по математике. ISBN 978-0486445830.
9. Плетцер, Александр; Филлмор, Дэвид (2015). «Консервативная интерполяция данных о краях и гранях на n-мерных структурированных сетках с использованием дифференциальных форм». Журнал вычислительной физики . 302 : 21–40. Бибкод : 2015JCoPh.302...21P. дои : 10.1016/j.jcp.2015.08.029 .
10. RE Crochiere и LR Rabiner. (1983). Многоскоростная цифровая обработка сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл.
11. Колин Беннетт, Роберт К. Шарпли, Интерполяция операторов , Academic Press, 1988 г.

Внешние ссылки

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