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

Учитывая две красные точки, синяя линия представляет собой линейный интерполянт между точками, а значение $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).

// Imprecise method, which does not guarantee v = v1 when t = 1, due to floating-point arithmetic error.
// This method is monotonic. This form may be used when the hardware has a native fused multiply-add instruction.
float lerp(float v0, float v1, float t) {
  return v0 + t * (v1 - v0);
}

// Precise method, which guarantees v = v1 when t = 1. This method is monotonic only when v0 * v1 < 0.
// Lerping between same values might not produce the same value
float lerp(float v0, float v1, float t) {
  return (1 - t) * v0 + t * 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]