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

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

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

• 1 Линейная интерполяция между двумя известными точками
• 2 Интерполяция набора данных
• 3 Линейная интерполяция как приближение
• 4 История и приложения
• 5 Расширения
  • 5.1 Точность
  • 5.2 Многомерный
• 6 Поддержка языка программирования
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

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

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

$y\; -\; y\; 0\; x\; -\; x\; 0\; =\; y\; 1\; -\; y\; 0\; x\; 1\; -\; x\; 0,\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{y-y\_\; \{0\}\}\; \{x-x\_\; \{0\}\}\}\; =\; \{\backslash \; frac\; \{y\_\; \{1\}\; -y\_\; \{0\}\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\},\}$

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

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

$y\; =\; y\; 0\; +\; (x\; -\; Икс\; 0)\; Y\; 1\; -\; Y\; 0\; Икс\; 1\; -\; Икс\; 0\; знак\; равно\; Y\; 0\; (Икс\; 1\; -\; Икс)\; +\; Y\; 1\; (Икс\; -\; Икс\; 0)\; Икс\; 1\; -\; Икс\; 0,\; \{\backslash \; Displaystyle\; Y\; =\; Y\_\; \{0\}\; +\; (х\; -x\_\; \{0\})\; \{\backslash \; frac\; \{y\_\; \{1\}\; -y\_\; \{0\}\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\}\; =\; \{\backslash \; frac\; \{y\_\; \{0\}\; (x\_\; \{1\}\; -x)\; +\; y\_\; \{1\}\; (x-x\_\; \{0\})\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\},\}$

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

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

$y\; =\; y\; 0\; (1\; -\; x\; -\; x\; 0\; x\; 1\; -\; x\; 0)\; +\; y\; 1\; (1\; -\; x\; 1\; -\; xx\; 1\; -\; x\; 0)\; =\; y\; 0\; (1\; -\; x\; -\; x\; 0\; Икс\; 1\; -\; Икс\; 0)\; +\; Y\; 1\; (Икс\; -\; Икс\; 0\; Икс\; 1\; -\; Икс\; 0),\; \{\backslash \; Displaystyle\; Y\; =\; Y\_\; \{0\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{x-x\_\; \{0\}\}\; \{x\_\; \{\; 1\}\; -x\_\; \{0\}\}\}\; \backslash \; right)\; +\; y\_\; \{1\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{x\_\; \{1\}\; -x\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\}\; \backslash \; right)\; =\; y\_\; \{0\}\; \backslash \; left\; (1\; -\; \{\backslash \; frac\; \{x-x\_\; \{0\}\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\}\; \backslash \; right)\; +\; y\_\; \{1\}\; \backslash \; left\; (\{\backslash \; frac\; \{x-x\_\; \{\; 0\}\}\; \{x\_\; \{1\}\; -x\_\; \{0\}\}\}\; \backslash \; right),\}$

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

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

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

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

$RT\; =\; f\; (x)\; -\; p\; (x),\; \{\backslash \; displaystyle\; R\_\; \{T\}\; =\; f\; (x)\; -p\; (x),\}$

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

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

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

$|\; R\; T\; |\; \le \; (x\; 1\; -\; x\; 0)\; 2\; 8\; макс.\; X\; 0\; \le \; x\; \le \; x\; 1\; |\; f\; ″\; (x)\; |.\; \{\backslash \; displaystyle\; |\; R\_\; \{T\}\; |\; \backslash \; leq\; \{\backslash \; frac\; \{(x\_\; \{1\}\; -x\_\; \{0\})\; ^\; \{2\}\}\; \{8\}\}\; \backslash \; max\; \_\; \{x\_\; \{0\}\; \backslash \; leq\; x\; \backslash \; leq\; x\_\; \{\; 1\}\}\; |\; f\; \text{'}\text{'}\; (x)\; |.\}$

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

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

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

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

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

Точность

Если функции C недостаточно, например, если известно, что процесс, создавший точки данных, более плавный, чем 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 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).

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

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

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