Линейная интерполяция что это
Линейная интерполяция
Интерполяция – это способ определения промежуточных значений по дискретному набору данных.
Формула линейной интерполяции имеет вид:
Пример 1
Воспользовавшись таблицей ниже, найдите неизвестное значение функции f(x) при x=3
x | f(x) |
2 | 5 |
3 | ? |
5 | 11 |
Решение
Воспользуемся формулой линейной интерполяции, получим
Так как данные в таблице представлены для линейной функция f(x)=2x+1. Для проверки полученного значения подставим в функцию значение X=3
Пример 2
В соответствии с представленными данными в таблице, найдите неизвестное значение функции f(x) при x=3
x | f(x) |
2 | 4 |
3 | ? |
5 | 25 |
Решение
Применим формулу линейной интерполяции, имеем
f(3)=3 2 =9
Значение получилось не совсем точное, так как метод линейной интерполяции применим в основном для линейных функций, а для нелинейных функций дает результаты с определенной погрешностью в зависимости от типа функции.
Насколько публикация полезна?
Нажмите на звезду, чтобы оценить!
Средняя оценка 4.7 / 5. Количество оценок: 18
Оценок пока нет. Поставьте оценку первым.
2 комментария
Было бы хорошо, если приведёте примеры с количеством чисел больше трёх.
По сути, далее не имеет значения, сколько чисел три, четыре и т.д. алгоритм тот же самый. Просто вы разбиваете функцию на несколько точек и последовательно их вычисляете с помощью данного метода.
Линейная интерполяция
Содержание
Линейная интерполяция между двумя известными точками [ править ]
которое геометрически выводится из рисунка справа. Это частный случай полиномиальной интерполяции с n = 1.
что дает формулу линейной интерполяции, приведенную выше.
Интерполяция набора данных [ править ]
Линейная интерполяция как приближение [ править ]
Линейная интерполяция часто используется для аппроксимации значения некоторой функции f с использованием двух известных значений этой функции в других точках. Погрешность этого приближения определяется как
где p обозначает полином линейной интерполяции, определенный выше:
То есть приближение между двумя точками данной функции ухудшается со второй производной аппроксимируемой функции. Это также интуитивно верно: чем «изогнутее» функция, тем хуже становятся аппроксимации, сделанные с помощью простой линейной интерполяции.
История и приложения [ править ]
Операции Lerp встроены в аппаратное обеспечение всех современных процессоров компьютерной графики. Их часто используют как строительные блоки для более сложных операций: например, билинейную интерполяцию можно выполнить за три лерпа. Поскольку эта операция стоит недорого, это также хороший способ реализовать точные таблицы поиска с быстрым поиском гладких функций без слишком большого количества записей в таблице.
Расширения [ править ]
Точность [ править ]
Многовариантный [ править ]
Поддержка языков программирования [ править ]
Во многих библиотеках и языках затенения есть вспомогательная функция «lerp» (в GLSL известная как mix ), возвращающая интерполяцию между двумя входами (v0, v1) для параметра (t) в закрытом единичном интервале [0, 1]. Сигнатуры между функциями lerp по-разному реализуются в обеих формах (v0, v1, t) и (t, v0, v1).
Интерполяция данных: соединяем точки так, чтобы было красиво
Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:
Немного матчасти
Восстановление промежуточных значений функции, которая в данном случае задана таблично в виде точек P1 .  Pn, называется интерполяцией. Есть множество способов интерполяции, но все они могут быть сведены к тому, что надо найти n – 1 функцию для расчёта промежуточных точек на соответствующих сегментах. При этом заданные точки обязательно должны быть вычислимы через соответствующие функции. На основе этого и может быть построен график:
Функции fi могут быть самыми разными, но чаще всего используют полиномы некоторой степени. В этом случае итоговая интерполирующая функция (кусочно заданная на промежутках, ограниченных точками Pi) называется сплайном.
В разных инструментах для построения графиков — редакторах и библиотеках — задача «красивой интерполяции» решена по-разному. В конце статьи будет небольшой обзор существующих вариантов. Почему в конце? Чтобы после ряда приведённых выкладок и размышлений можно было поугадывать, кто из «серьёзных ребят» какие методы использует.
Ставим опыты
Самый простой пример — линейная интерполяция, в которой используются полиномы первой степени, а в итоге получается ломаная, соединяющая заданные точки.
Давайте добавим немного конкретики. Вот набор точек (взяты почти с потолка):
Результат линейной интерполяции этих точек выглядит так:
Однако, как отмечалось выше, иногда хочется получить в итоге гладкую кривую.
Что есть гладкость? Бытовой ответ: отсутствие острых углов. Математический: непрерывность производных. При этом в математике гладкость имеет порядок, равный номеру последней непрерывной производной, и область, на которой эта непрерывность сохраняется. То есть, если функция имеет гладкость порядка 1 на отрезке [a; b], это означает, что на [a; b] она имеет непрерывную первую производную, а вот вторая производная уже терпит разрыв в каких-то точках.
У сплайна в контексте гладкости есть понятие дефекта. Дефект сплайна — это разность между его степенью и его гладкостью. Степень сплайна — это максимальная степень использованных в нём полиномов.
Важно отметить, что «опасными» точками у сплайна (в которых может нарушиться гладкость) являются как раз Pi, то есть точки сочленения сегментов, в которых происходит переход от одного полинома к другому. Все остальные точки «безопасны», ведь у полинома на области его определения нет проблем с непрерывностью производных.
Чтобы добиться гладкой интерполяции, нужно повысить степень полиномов и подобрать их коэффициенты так, чтобы в граничных точках сохранялась непрерывность производных.
Традиционно для решения такой задачи используют полиномы третьей степени и добиваются непрерывности первой и второй производной. То, что получается, называют кубическим сплайном дефекта 1. Вот как он выглядит для наших данных:
Кривая, действительно, гладкая. Но если предположить, что это график некоторого процесса или явления, который нужно показать заинтересованному лицу, то такой метод, скорее всего, не подходит. Проблема в ложных экстремумах. Появились они из-за слишком сильного искривления, которое было призвано обеспечить гладкость интерполяционной функции. Но зрителю такое поведение совсем не кстати, ведь он оказывается обманут относительно пиковых значений функции. А ради наглядной визуализации этих значений, собственно, всё и затевалось.
Так что надо искать другие решения.
Другое традиционное решение, кроме кубических сплайнов дефекта 1 — полиномы Лагранжа. Это полиномы степени n – 1, принимающие заданные значения в заданных точках. То есть членения на сегменты здесь не происходит, вся последовательность описывается одним полиномом.
Но вот что получается:
Гладкость, конечно, присутствует, но наглядность пострадала так сильно, что… пожалуй, стоит поискать другие методы. На некоторых наборах данных результат выходит нормальный, но в общем случае ошибка относительно линейной интерполяции (и, соответственно, ложные экстремумы) может получаться слишком большой — из-за того, что тут всего один полином на все сегменты.
В компьютерной графике очень широко применяются кривые Безье, представленные полиномами k-й степени.
Они не являются интерполирующими, так как из k + 1 точек, участвующих в построении, итоговая кривая проходит лишь через первую и последнюю. Остальные k – 1 точек играют роль своего рода «гравитационных центров», притягивающих к себе кривую.
Вот пример кубической кривой Безье:
Как это можно использовать для интерполяции? На основе этих кривых тоже можно построить сплайн. То есть на каждом сегменте сплайна будет своя кривая Безье k-й степени (кстати, k = 1 даёт линейную интерполяцию). И вопрос только в том, какое k взять и как найти k – 1 промежуточную точку.
Здесь бесконечно много вариантов (поскольку k ничем не ограничено), однако мы рассмотрим классический: k = 3.
Чтобы итоговая кривая была гладкой, нужно добиться дефекта 1 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (Pi), как это делается в классическом варианте кубического сплайна.
Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
Вот что получится на нашем тестовом наборе:
Стало лучше: ложные экстремумы всё ещё есть, но хотя бы не так сильно отличаются от реальных.
Думаем и экспериментируем
Можно попробовать ослабить условие гладкости: потребовать дефект 2, а не 1, то есть сохранить непрерывность одной только первой производной.
Достаточное условие достижения дефекта 2 в том, что промежуточные контрольные точки кубической кривой Безье, смежные с заданной точкой интерполируемой последовательности, лежат с этой точкой на одной прямой и на одинаковом расстоянии:
Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:
Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C1 (1) и Cn – 1 (2) совпадают с точками P1 и Pn соответственно).
В этом случае получается вот такая кривая:
Как видно, ложных экстремумов уже нет. Однако если сравнивать с линейной интерполяцией, местами ошибка очень большая. Можно сделать её ещё меньше, но тут в ход пойдут ещё более хитрые эвристики.
Эвристика для вычисления расстояний будет такой:
Результат получается такой:
В результате на шестом сегменте ошибка уменьшилась, а на седьмом — увеличилась: кривизна у Безье на нём оказалась больше, чем хотелось бы. Исправить ситуацию можно, принудительно уменьшив кривизну и тем самым «прижав» Безье ближе к отрезку прямой, которая соединяет граничные точки сегмента. Для этого используется следующая эвристика:
Результат следующий:
На этом было принято решение признать цель достигнутой.
Может быть, кому-то пригодится код.
А как люди-то делают?
Обещанный обзор. Конечно, перед решением задачи мы посмотрели, кто чем может похвастаться, а уже потом начали разбираться, как сделать самим и по возможности лучше. Но вот как только сделали, не без удовольствия ещё раз прошлись по доступным инструментам и сравнили их результаты с плодами наших экспериментов. Итак, поехали.
MS Excel
Это очень похоже на рассмотренный выше сплайн дефекта 1, основанный на кривых Безье. Правда, в отличие от него в чистом виде, тут всего два ложных экстремума — первый и второй сегменты (у нас было четыре). Видимо, к классическому поиску промежуточных контрольных точек тут добавляются ещё какие-то эвристики. Но ото всех ложных экстремумов они не спасли.
LibreOffice Calc
В настройках это названо кубическим сплайном. Очевидно, он тоже основан на Безье, и вот тут уже точная копия нашего результата: все четыре ложных экстремума на месте.
Есть там ещё один тип интерполяции, который мы тут не рассматривали: B-сплайн. Но для нашей задачи он явно не подходит, так как даёт вот такой результат 🙂
Highcharts, одна из самых популярных JS-библиотек для построения диаграмм
Тут налицо «метод касательных» в варианте равенства расстояний от точки интерполируемой последовательности до промежуточных контрольных. Ложных экстремумов нет, зато есть сравнительно большая ошибка относительно линейной интерполяции (седьмой сегмент).
amCharts, ещё одна популярная JS-библиотека
Картина очень похожа на экселевскую, те же два ложных экстремума в тех же местах.
Coreplot, самая популярная библиотека построения графиков для iOS и OS X
Есть ложные экстремумы и видно, что используется сплайн дефекта 1 на основе Безье.
Библиотека открытая, так что можно посмотреть в код и убедиться в этом.
aChartEngine, вроде как самая популярная библиотека построения графиков для Android
Больше всего похоже на кривую Безье степени n – 1, хотя в самой библиотеке график называется «cubic line». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.
Интерполяция
Интерполяция использует значения некоторой функции, заданные в ряде точек, чтобы предсказать значения функции между ними. Перечисленные ниже методы предназначены для создания ряда с более высокой частотой наблюдений на основе ряда с низкой частотой. Например, вычислить ряд с квартальной динамикой на основе ряда годовых данных.
Линейная интерполяция
Геометрическая интерполяция
При геометрической интерполяции значения результирующей динамики пропорциональны значению инкремента и обратно пропорциональны фактору, вычисленному на основе инкремента. Инкремент экспоненциально зависит от логарифма относительного прироста исходной динамики, умноженного на длину периода результирующей динамики.
Рассмотрим принцип геометрического метода на примере вычисления квартальных данных на основе годовых.
X [ t ] – исходные данные по годам;
Factor [ t ] = (1 + Inc [ t ] + Inc [ t ]^2 + Inc [ t ]^3) / 4 – значение фактора;
Интерполяция для других динамик осуществляется аналогичным образом.
Интерполяция кубическими сплайнами
Сплайны позволяют эффективно решать задачи обработки экспериментальных зависимостей между параметрами, имеющих достаточно сложную структуру. Наиболее широкое практическое применение, в силу их простоты, нашли кубические сплайны. Основные идеи теории кубических сплайнов сформировались в результате попыток математически описать гибкие рейки из упругого материала (механические сплайны), которыми издавна пользовались чертежники в тех случаях, когда возникала необходимость проведения через заданные точки достаточно гладкой кривой. Известно, что рейка из упругого материала, закрепленная в некоторых точках и находящаяся в положении равновесия, принимает форму, при которой ее энергия является минимальной. Это фундаментальное свойство позволяет эффективно использовать сплайны при решении практических задач обработки экспериментальной информации.
функция S ( x ), а также ее первая и вторая производные непрерывны на отрезке [a, b];
Условие непрерывности всех производных до второго порядка записываются в виде:
Если функция f ( x ) является полиномом третьей или меньше степени, данные воспроизводятся более точно, если граничные условия сплайна c 0 и c n равны точным значениям второй производной кубического полинома.
Интерполяция многочленом Лагранжа
Лагранж предложил методику вычисления подобных многочленов:
Где базисные полиномы определяются по следующей формуле:
l j ( x ) обладают свойствами:
являются многочленами степени n ;
Полиноминальная интерполяция
Полиномиальная интерполяция является наиболее известным из методов одномерной интерполяции. Её достоинствами являются простота реализации и хорошее качество получаемых интерполянтов.
Равномерная интерполяция
Значение исходного ряда делится на число наблюдений, попадающих в один период результирующего ряда. Полученное значение присваивается всем наблюдениям нового ряда, в пределах одного периода.
Повторная интерполяция
Значения исходного ряда повторяются на всех наблюдениях ряда с более высокой частотой динамики.
Интерполяция по шаблону
Рассмотрим три метода интерполяции по шаблону:
среднее по элементам
по первому элементу
по последнему элементу
Первое значение
Значение первой точки результирующей динамики будет совпадать со значением точки на исходной динамике. Значения в остальных точках результирующей динамики остаются пустыми.
Последнее значение
Значение последней точки результирующей динамики будет совпадать со значением точки на исходной динамике. Значения в остальных точках результирующей динамики остаются пустыми.
Линейная интерполяция
Лине́йная интерполя́ция — интерполяция алгебраическим двучленом P1(x) = ax + b функции f, заданной в двух точках x0 и x1 отрезка [a, b]. В случае, если заданы значения в нескольких точках, функция заменяется кусочно-линейной функцией.
Геометрическая интерпретация
Геометрически это означает замену графика функции прямой, проходящей через точки
и
.
Уравнение такой прямой имеет вид:
отсюда для
Это и есть формула линейной интерполяции, при этом
где — погрешность формулы:
Применение
Линейная интерполяция применяется для уплотнения таблиц.
См. также
Полезное
Смотреть что такое «Линейная интерполяция» в других словарях:
линейная интерполяция — — [Я.Н.Лугинский, М.С.Фези Жилинская, Ю.С.Кабиров. Англо русский словарь по электротехнике и электроэнергетике, Москва, 1999 г.] Тематики электротехника, основные понятия EN linear interpolation … Справочник технического переводчика
линейная интерполяция — tiesinė interpoliacija statusas T sritis fizika atitikmenys: angl. linear interpolation vok. lineare Interpolation, f rus. линейная интерполяция, f pranc. interpolation linéaire, f … Fizikos terminų žodynas
ЛИНЕЙНАЯ ИНТЕРПОЛЯЦИЯ — способ приближенного вычисления значения функции f(x), основанный на замене функции f(х).линейной функцией параметры аи b к рой выбираются таким образом, чтобы значения L(х).совпадали со значениями f(x).в заданных точках х 1 и х 2: Этим условиям… … Математическая энциклопедия
интерполяция — Вычисление промежуточных значений между двумя известными точками. Например: linear линейная интерполяция exponential экспоненциальная интерполяция Процесс вывода цветного изображения, когда пикселы, относящиеся к области между двумя цветными… … Справочник технического переводчика
интерполяция — и, ж. interpolation f. < лат. interpolatio изменение; переделка, искажение. 1. Вставка позднейшего происхождения в каком л. тексте, не принадлежащая оригиналу. БАС 1. В древних рукописях много интерполяций, внесенных переписчиками. Уш. 1934. 2 … Исторический словарь галлицизмов русского языка
Интерполяция — О функции, см.: Интерполянт. Интерполяция, интерполирование в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и… … Википедия
Интерполяция (матем.) — О функции, см.: Интерполянт. Интерполяция в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчётами часто … Википедия
Билинейная интерполяция — Билинейная интерполяция в вычислительной математике расширение линейной интерполяции для функций двух переменных. Ключевая идея заключается в том, чтобы провести обычную линейную интерполяцию сначала в одном направлении, затем в другом … Википедия
Интерполирование — О функции, см.: Интерполянт. Интерполяция в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Многим из тех, кто сталкивается с научными и инженерными расчётами часто … Википедия
Таблица поиска — (англ. lookup table) это структура данных, обычно массив или ассоциативный массив, используемая с целью заменить вычисления на операцию простого поиска. Увеличение скорости может быть значительным, так как получить данные из памяти… … Википедия