Линейная интерполяция

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

Учитывая две красные точки, синяя линия представляет собой линейный интерполянт между точками, а значение y в точке x можно найти путем линейной интерполяции.

В математике линейная интерполяция — это метод аппроксимации кривой с использованием линейных полиномов для построения новых точек данных в пределах диапазона дискретного набора известных точек данных.

Линейная интерполяция между двумя известными точками

В этой геометрической визуализации значение в зеленом круге, умноженное на горизонтальное расстояние между красным и синим кругами, равно сумме значения в красном круге, умноженного на горизонтальное расстояние между зеленым и синим кругами, и значения в синий круг, умноженный на горизонтальное расстояние между зеленым и красным кругами.

Если две известные точки заданы координатами и , линейный интерполянт представляет собой прямую линию между этими точками. Для значения в интервале значение вдоль прямой определяется из уравнения наклонов ${\displaystyle (x_{0},y_{0})}$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle x}$ ${\displaystyle (x_{0},x_{1})}$ ${\displaystyle y}$

$${\displaystyle {\frac {y-y_{0}}{x-x_{0}}}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},}$$

полиномиальной интерполяции. ${\displaystyle n=1}$

Решение этого уравнения для , которое является неизвестным значением при , дает ${\displaystyle y}$ ${\displaystyle x}$

$${\displaystyle {\begin{aligned}y&=y_{0}+(x-x_{0}){\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\&={\frac {y_{0}(x_{1}-x_{0})}{x_{1}-x_{0}}}+{\frac {y_{1}(x-x_{0})-y_{0}(x-x_{0})}{x_{1}-x_{0}}}\\&={\frac {y_{1}x-y_{1}x_{0}-y_{0}x+y_{0}x_{0}+y_{0}x_{1}-y_{0}x_{0}}{x_{1}-x_{0}}}\\&={\frac {y_{0}(x_{1}-x)+y_{1}(x-x_{0})}{x_{1}-x_{0}}},\end{aligned}}}$$

.линейной экстраполяции ${\displaystyle (x_{0},x_{1})}$

Эту формулу также можно понимать как средневзвешенное значение. Веса обратно пропорциональны расстоянию от конечных точек до неизвестной точки; более близкая точка имеет большее влияние, чем более дальняя. Таким образом, веса и , которые являются нормализованными расстояниями между неизвестной точкой и каждой из конечных точек. Поскольку их сумма равна 1, ${\textstyle 1-(x-x_{0})/(x_{1}-x_{0})}$ ${\textstyle 1-(x_{1}-x)/(x_{1}-x_{0})}$

$${\displaystyle {\begin{aligned}y&=y_{0}\left(1-{\frac {x-x_{0}}{x_{1}-x_{0}}}\right)+y_{1}\left(1-{\frac {x_{1}-x}{x_{1}-x_{0}}}\right)\\&=y_{0}\left(1-{\frac {x-x_{0}}{x_{1}-x_{0}}}\right)+y_{1}\left({\frac {x-x_{0}}{x_{1}-x_{0}}}\right)\\&=y_{0}\left({\frac {x_{1}-x}{x_{1}-x_{0}}}\right)+y_{1}\left({\frac {x-x_{0}}{x_{1}-x_{0}}}\right)\end{aligned}}}$$

Интерполяция набора данных

Линейная интерполяция набора данных (красные точки) состоит из фрагментов линейных интерполянтов (синие линии).

Линейная интерполяция набора точек данных ( x ₀ , y ₀ ), ( x ₁ , y ₁ ), ..., ( x _n , y _n ) определяется как конкатенация линейных интерполянтов между каждой парой точек данных. В результате получается непрерывная кривая с разрывной производной (вообще), то есть класса дифференцируемости . ${\displaystyle C^{0}}$

Линейная интерполяция как приближение

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

$${\displaystyle R_{T}=f(x)-p(x),}$$

p обозначает полином

$${\displaystyle p(x)=f(x_{0})+{\frac {f(x_{1})-f(x_{0})}{x_{1}-x_{0}}}(x-x_{0}).}$$

Используя теорему Ролля, можно доказать , что если f имеет непрерывную вторую производную, то ошибка ограничена величиной

$${\displaystyle |R_{T}|\leq {\frac {(x_{1}-x_{0})^{2}}{8}}\max _{x_{0}\leq x\leq x_{1}}\left|f''(x)\right|.}$$

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

История и приложения

Линейная интерполяция использовалась с древности для заполнения пробелов в таблицах. Предположим, что у вас есть таблица, в которой указано население некоторой страны в 1970, 1980, 1990 и 2000 годах, и вы хотите оценить численность населения в 1994 году. Линейная интерполяция — простой способ сделать это. Считается, что он использовался в Империи Селевкидов (последние три века до нашей эры) и греческим астрономом и математиком Гиппархом (второй век до нашей эры). Описание линейной интерполяции можно найти в древнем китайском математическом тексте под названием « Девять глав математического искусства» (九章算術), ^[1] датированном от 200 г. до н. э. до 100 г. н. э., и в «Альмагесте » (2 век н. э.) Птолемея .

Основная операция линейной интерполяции между двумя значениями обычно используется в компьютерной графике . На жаргоне этой области его иногда называют лерпом ( от линейной интерполяции ). Этот термин может использоваться как глагол или существительное для операции. например: « Алгоритм Брезенхэма постепенно перемещается между двумя конечными точками линии».

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

Расширения

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

Точность

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

Многомерный

Линейная интерполяция, описанная здесь, предназначена для точек данных в одном пространственном измерении. Для двух пространственных измерений расширение линейной интерполяции называется билинейной интерполяцией , а в трех измерениях — трилинейной интерполяцией . Обратите внимание, однако, что эти интерполянты больше не являются линейными функциями пространственных координат, а являются продуктами линейных функций; это иллюстрируется явно нелинейным примером билинейной интерполяции на рисунке ниже. Другие расширения линейной интерполяции могут применяться к другим типам сеток , таким как треугольные и тетраэдральные сетки, включая поверхности Безье . Их можно определить как действительно многомерные кусочно-линейные функции (см. второй рисунок ниже).

Пример билинейной интерполяции на единичном квадрате со значениями z 0, 1, 1 и 0,5, как указано. Интерполированные значения между ними представлены цветом.

Кусочно-линейная функция в двух измерениях (вверху) и выпуклые многогранники, на которых она линейна (внизу)

Поддержка языков программирования

Многие библиотеки и языки шейдеринга имеют вспомогательную функцию «lerp» (в GLSL известную как mix ), возвращающую интерполяцию между двумя входными параметрами (v0, v1)для параметра tв замкнутом единичном интервале [0, 1]. Сигнатуры между функциями lerp по-разному реализованы как в формах, (v0, v1, t)так и в (t, v0, v1).

// Неточный метод, который не гарантирует v = v1 при t = 1 из-за арифметической ошибки с плавающей запятой. // Этот метод монотонный. Эту форму можно использовать, когда аппаратное обеспечение имеет встроенную инструкцию плавного умножения-сложения. float lerp ( float v0 , float v1 , float t ) { return v0 + t * ( v1 - v0 ); }               // Точный метод, который гарантирует v = v1 при t = 1. Этот метод является монотонным только тогда, когда v0 * v1 < 0. // Lerping между одинаковыми значениями может не дать одинакового значения float lerp ( float v0 , float v1 , float t ) { return ( 1 - t ) * v0 + t * v1 ; }                 

Эта функция lerp обычно используется для альфа-смешивания (параметр «t» является «значением альфа»), и формула может быть расширена для смешивания нескольких компонентов вектора (например, пространственных осей x , y , z или r , g) . , b цветовые компоненты) параллельно.

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

• Билинейная интерполяция
• Сплайн-интерполяция
• Полиномиальная интерполяция
• алгоритм де Кастельжо
• Удержание первого порядка
• Кривая Безье

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

1. Джозеф Нидхэм (1 января 1959 г.). Наука и цивилизация в Китае: Том 3, Математика и науки о небе и Земле. Издательство Кембриджского университета. стр. 147–. ISBN 978-0-521-05801-8.

• Мейеринг, Эрик (2002), «Хронология интерполяции: от древней астрономии до современной обработки сигналов и изображений», Proceedings of the IEEE , 90 (3): 319–342, doi : 10.1109/5.993400.

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

• Уравнения прямой при разрезании узла
• Хорошая интерполяция для чисел и указателей
• «Линейная интерполяция», Математическая энциклопедия , EMS Press , 2001 [1994]
• «Формула конечных приращений», Математическая энциклопедия , EMS Press , 2001 [1994]