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

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

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

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

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

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

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

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

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

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

что является формулой линейной интерполяции в интервале . За пределами этого интервала формула идентична линейной экстраполяции .${\ displaystyle (x_ {0}, x_ {1})}$

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

${\displaystyle 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),}$

что дает формулу линейной интерполяции, приведенную выше.

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

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

Линейная интерполяция на наборе точек данных ( 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}}|f''(x)|.}$

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

История и приложения [ править ]

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

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

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

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

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

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

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

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

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

Во многих библиотеках и языках затенения есть вспомогательная функция «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. Перемещение между одинаковыми значениями может не давать одно и то же значение float  lerp ( float  v0 ,  float  v1 ,  float  t )  {  return  ( 1  -  t )  *  v0  +  t  *  v1 ; }

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

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

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

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

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

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

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