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

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

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

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

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

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

которое можно вывести геометрически из рисунка справа. Это частный случай полиномиальной интерполяции с

n=1

.

Решая это уравнение для $y$ , что является неизвестным значением в $x$ , дает

{\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}}

что представляет собой формулу линейной интерполяции в интервале

(x_{0},x_{1})

. За пределами этого интервала формула идентична линейной экстраполяции .

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

{\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 0, y 0), (x 1, y 1), ..., (x n, y n)$ определяется как кусочно-линейная , возникающая в результате объединения интерполянтов линейных сегментов между каждую пару точек данных. В результате получается непрерывная кривая с разрывной производной (вообще), то есть класса дифференцируемости. $C^{0}$ .

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

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

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

где

p

линейной интерполяции обозначает полином , определенный выше:

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

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

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

Расширения [ править ]

Точность [ править ]

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

Многомерный [ править ]

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

Пример билинейной интерполяции на единичном квадрате со $значениями 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   т  )   { 
   возврат   (  1   -   т  )   *   v0   +   т   *   v1  ; 
  }

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

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

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

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

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

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

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

[1]