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

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

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

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

Пример

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

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

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

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)

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

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

Это предыдущее уравнение утверждает, что наклон новой линии между $(x_{a},y_{a})$ и $(x,y)$ равен наклону линии между $(x_{a},y_{a})$ и $(x_{b},y_{b})$

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

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

|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)|.

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

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

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

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

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 ]. Сплайн-интерполяция использует полиномы низкой степени в каждом из интервалов и выбирает части полинома так, чтобы они плавно сочетались друг с другом. Полученная функция называется сплайном.

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

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]

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

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

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

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

Другие формы

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщение

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

См. также

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

Ссылки

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

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

Онлайн-инструменты для линейного , Архивировано 18 сентября 2016 г. в Wayback Machine , квадратичного , Архивировано 18 сентября 2016 г. в Wayback Machine , кубического сплайна, Архивировано 20 августа 2016 г. в Wayback Machine , и полинома , Архивировано 18 сентября 2016 г. в Интерполяция Wayback Machine с визуализацией и исходным кодом JavaScript .
Учебные пособия по Sol — трюки с интерполяцией, заархивировано 31 января 2021 г. в Wayback Machine.
Барицентрическая рациональная интерполяция в Boost.Math
Интерполяция через преобразование Чебышева в Boost.Math

[1] Шеппард, Уильям Флитвуд (1911). «Интерполяция» . В Чисхолме, Хью (ред.). Британская энциклопедия . Том. 14 (11-е изд.). Издательство Кембриджского университета. стр. 706–710.

[2] Стеффенсен, Дж. Ф. (2006). Интерполяция (Второе изд.). Минеола, ISBN штата Нью-Йорк 978-0-486-15483-1 . OCLC 867770894 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[3] Кресс, Райнер (1998). Численный анализ . ISBN 9781461205999 .

[4] Плетцер, Александр; Хайек, Вольфганг (01 января 2019 г.). «Миметическая интерполяция векторных полей на C/D-сетках Аракавы» . Ежемесячный обзор погоды . 147 (1): 3–16. Бибкод : 2019MWRv..147....3P . дои : 10.1175/MWR-D-18-0146.1 . ISSN 1520-0493 . S2CID 125214770 . Архивировано из оригинала 7 июня 2022 г. Проверено 7 июня 2022 г.

[5] Стерн, Ари; Тонг, Иин; Дебрен, Матье; Марсден, Джеррольд Э. (2015), Чанг, Донг Ый; Холм, Дэррил Д.; Патрик, Джордж; Ратиу, Тюдор (ред.), «Геометрическая вычислительная электродинамика с вариационными интеграторами и дискретными дифференциальными формами» , Геометрия, механика и динамика , Fields Institute Communications, vol. 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 , получено 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). Многоскоростная цифровая обработка сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис – Холл» . Архивировано из оригинала 13 апреля 2016 г. Проверено 1 сентября 2017 г.

[11] Колин Беннетт, Роберт К. Шарпли, Интерполяция операторов , Academic Press, 1988 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]