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

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

В математической области численного анализа интерполяция — это тип оценки , метод построения (поиска) новых точек данных на основе диапазона дискретного набора известных точек данных. ^{[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})}$

Линейная интерполяция быстрая и простая, но не очень точная. Другим недостатком является то, что интерполянт не дифференцируем в точке 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. ^[3]

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

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

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

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

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

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

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

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

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

Связанные концепции

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

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

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

Обобщение

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

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

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

Ссылки

1. Шеппард, Уильям Флитвуд (1911). «Интерполяция»  . В Чисхолм, Хью (ред.). Encyclopaedia Britannica . Т. 14 (11-е изд.). Cambridge University Press. С. 706–710.
2. Стеффенсен, Дж. Ф. (2006). Интерполяция (Второе изд.). Минеола, ISBN штата Нью-Йорк 978-0-486-15483-1. OCLC  867770894.{{cite book}}: CS1 maint: location missing publisher (link)
3. Кресс, Райнер (1998). Численный анализ. Springer. ISBN 9781461205999.
4. Плетцер, Александр; Хайек, Вольфганг (2019-01-01). "Миметическая интерполяция векторных полей на сетках Аракавы C/D". Monthly Weather Review . 147 (1): 3–16. Bibcode : 2019MWRv..147....3P. doi : 10.1175/MWR-D-18-0146.1. ISSN  1520-0493. S2CID  125214770. Архивировано из оригинала 2022-06-07 . Получено 2022-06-07 .
5. Stern, Ari; Tong, Yiying; Desbrun, Mathieu; Marsden, Jerrold E. (2015), Chang, Dong Eui; Holm, Darryl D.; Patrick, George; Ratiu, Tudor (ред.), "Геометрическая вычислительная электродинамика с вариационными интеграторами и дискретными дифференциальными формами", Geometry, Mechanics, and Dynamics , Fields Institute Communications, т. 73, Нью-Йорк, Нью-Йорк: Springer New York, стр. 437–475, arXiv : 0707.4470 , doi :10.1007/978-1-4939-2441-7_19, ISBN 978-1-4939-2440-0, S2CID  15194760 , получено 2022-06-15
6. Джонс, Филип (1999). «Консервативные схемы переотображения первого и второго порядка для сеток в сферических координатах». Monthly Weather Review . 127 (9): 2204–2210. Bibcode : 1999MWRv..127.2204J. doi : 10.1175/1520-0493(1999)127<2204:FASOCR>2.0.CO;2 . S2CID  122744293.
7. Холл, Чарльз А.; Мейер, Уэстон В. (1976). «Оптимальные границы погрешности для интерполяции кубическим сплайном». Журнал теории приближений . 16 (2): 105–122. doi : 10.1016/0021-9045(76)90040-X .
8. Уитни, Хасслер (1957). Геометрическая теория интегрирования . Dover Books on Mathematics. ISBN 978-0486445830.
9. Плетцер, Александр; Филлмор, Дэвид (2015). «Консервативная интерполяция данных ребер и граней на n-мерных структурированных сетках с использованием дифференциальных форм». Журнал вычислительной физики . 302 : 21–40. Bibcode : 2015JCoPh.302...21P. doi : 10.1016/j.jcp.2015.08.029 .
10. Crochiere, Ronald E.; Rabiner, Lawrence R. (1983). RE Crochiere и LR Rabiner. (1983). Многоскоростная цифровая обработка сигналов. Englewood Cliffs, NJ: Prentice–Hall . Prentice-Hall. ISBN 0136051626.
11. Колин Беннетт, Роберт С. Шарпли, Интерполяция операторов , Academic Press 1988

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

• Онлайн-инструменты для линейной интерполяции с визуализацией и исходным кодом JavaScript. Архивировано 18.09.2016 на Wayback Machine , квадратичной интерполяции с визуализацией 18.09.2016 на Wayback Machine , кубической интерполяции с визуализацией 2016-08-2016 на Wayback Machine и полиномиальной интерполяции с визуализацией и исходным кодом JavaScript .
• Учебники Sol - Интерполяционные трюки Архивировано 31.01.2021 на Wayback Machine
• Барицентрическая рациональная интерполяция в Boost.Math
• Интерполяция с помощью преобразования Чебышева в Boost.Math