Интерполяция для чего нужна

Интерполяция

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

Многим из тех, кто сталкивается с научными и инженерными расчётами часто приходится оперировать наборами значений, полученных опытным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.

Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса-Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ.

Содержание

Определения

Рассмотрим систему несовпадающих точек () из некоторой области . Пусть значения функции известны только в этих точках:

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

Пример

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

0	0
1	0,8415
2	0,9093
3	0,1411
4	−0,7568
5	−0,9589
6	−0,2794

Интерполяция помогает нам узнать какое значение может иметь такая функция в точке, отличной от указанных (например, при x = 2,5).

К настоящему времени существует множество различных способов интерполяции. Выбор наиболее подходящего алгоритма зависит от ответов на вопросы: как точен выбираемый метод, каковы затраты на его использование, насколько гладкой является интерполяционная функция, какого количества точек данных она требует и т. п.

2. Найти промежуточное значение (способом линейной интерполяции).

Способы интерполяции

Интерполяция методом ближайшего соседа

Простейшим способом интерполяции является интерполяция методом ближайшего соседа.

Интерполяция многочленами

На практике чаще всего применяют интерполяцию многочленами. Это связано прежде всего с тем, что многочлены легко вычислять, легко аналитически находить их производные и множество многочленов плотно в пространстве непрерывных функций (теорема Вейерштрасса).

Обратное интерполирование (вычисление x при заданном y)

Интерполяция функции нескольких переменных

Другие способы интерполяции

Смежные концепции

См. также

Полезное

Смотреть что такое «Интерполяция» в других словарях:

ИНТЕРПОЛЯЦИЯ — 1) способ определять по ряду данных величин какого либо математического выражения промежуточные его величины; так напр., по дальности полета ядра при угле возвышения оси пушечного канала в 1°, 2°, 3°, 4° и т. д. можно определить помощью… … Словарь иностранных слов русского языка

интерполяция — вставка, интерполирование, включение, отыскание Словарь русских синонимов. интерполяция см. вставка Словарь синонимов русского языка. Практический справочник. М.: Русский язык. З. Е. Александрова. 2 … Словарь синонимов

интерполяция — Вычисление промежуточных значений между двумя известными точками. Например: linear линейная интерполяция exponential экспоненциальная интерполяция Процесс вывода цветного изображения, когда пикселы, относящиеся к области между двумя цветными… … Справочник технического переводчика

Интерполяция — (interpolation) Оценка значения неизвестной величины, находящейся между двумя точками ряда известных величин. Например, зная показатели населения страны, полученные при проведения переписи населения, проводившейся с интервалом в 10 лет, можно… … Словарь бизнес-терминов

Интерполяция — с латинского собственно «подделка». Так называются ошибочные поправки или позднейшие вставки в рукописях, сделанные переписчиками или читателями. Особенно часто этот термин употребляется в критике рукописей античных писателей. В этих рукописях… … Литературная энциклопедия

Интерполяция — нахождение промежуточных значений некоторой закономерности (функции) по ряду известных ее значений. По английски: Interpolation См. также: Преобразования данных Финансовый словарь Финам … Финансовый словарь

интерполяция — и, ж. interpolation f. < лат. interpolatio изменение; переделка, искажение. 1. Вставка позднейшего происхождения в каком л. тексте, не принадлежащая оригиналу. БАС 1. В древних рукописях много интерполяций, внесенных переписчиками. Уш. 1934. 2 … Исторический словарь галлицизмов русского языка

ИНТЕРПОЛЯЦИЯ — (interpolatio), пополнение эмпйрич. ряда значений какой либо величины недостающими промежуточными значениями ее. Интерполирование может быть произведено тремя способами: математич., графич. и логическим. В основе их лежит общая им гипотеза о том … Большая медицинская энциклопедия

ИНТЕРПОЛЯЦИЯ — (от латинского interpolatio изменение, переделка), отыскание промежуточных значений величины по некоторым известным ее значениям. Например, отыскание значений функции y = f(x) в точках x, лежащих между точками x0 и xn, x0 … Современная энциклопедия

ИНТЕРПОЛЯЦИЯ — в филологии изменение первоначального текста; вставка переписчиком или переводчиком в текст слов или фраз, отсутствовавших в оригинале … Большой Энциклопедический словарь

Источник

Интерполяция данных: соединяем точки так, чтобы было красиво

Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:

Немного матчасти

Восстановление промежуточных значений функции, которая в данном случае задана таблично в виде точек P₁&nbsp. &nbspP_n, называется интерполяцией. Есть множество способов интерполяции, но все они могут быть сведены к тому, что надо найти n&nbsp–&nbsp1 функцию для расчёта промежуточных точек на соответствующих сегментах. При этом заданные точки обязательно должны быть вычислимы через соответствующие функции. На основе этого и может быть построен график:

Функции f_i могут быть самыми разными, но чаще всего используют полиномы некоторой степени. В этом случае итоговая интерполирующая функция (кусочно заданная на промежутках, ограниченных точками P_i) называется сплайном.

В разных инструментах для построения графиков — редакторах и библиотеках — задача «красивой интерполяции» решена по-разному. В конце статьи будет небольшой обзор существующих вариантов. Почему в конце? Чтобы после ряда приведённых выкладок и размышлений можно было поугадывать, кто из «серьёзных ребят» какие методы использует.

Ставим опыты

Самый простой пример — линейная интерполяция, в которой используются полиномы первой степени, а в итоге получается ломаная, соединяющая заданные точки.
Давайте добавим немного конкретики. Вот набор точек (взяты почти с потолка):

Результат линейной интерполяции этих точек выглядит так:

Однако, как отмечалось выше, иногда хочется получить в итоге гладкую кривую.

Что есть гладкость? Бытовой ответ: отсутствие острых углов. Математический: непрерывность производных. При этом в математике гладкость имеет порядок, равный номеру последней непрерывной производной, и область, на которой эта непрерывность сохраняется. То есть, если функция имеет гладкость порядка 1 на отрезке [a;&nbspb], это означает, что на [a;&nbspb] она имеет непрерывную первую производную, а вот вторая производная уже терпит разрыв в каких-то точках.
У сплайна в контексте гладкости есть понятие дефекта. Дефект сплайна — это разность между его степенью и его гладкостью. Степень сплайна — это максимальная степень использованных в нём полиномов.
Важно отметить, что «опасными» точками у сплайна (в которых может нарушиться гладкость) являются как раз P_i, то есть точки сочленения сегментов, в которых происходит переход от одного полинома к другому. Все остальные точки «безопасны», ведь у полинома на области его определения нет проблем с непрерывностью производных.
Чтобы добиться гладкой интерполяции, нужно повысить степень полиномов и подобрать их коэффициенты так, чтобы в граничных точках сохранялась непрерывность производных.

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

Кривая, действительно, гладкая. Но если предположить, что это график некоторого процесса или явления, который нужно показать заинтересованному лицу, то такой метод, скорее всего, не подходит. Проблема в ложных экстремумах. Появились они из-за слишком сильного искривления, которое было призвано обеспечить гладкость интерполяционной функции. Но зрителю такое поведение совсем не кстати, ведь он оказывается обманут относительно пиковых значений функции. А ради наглядной визуализации этих значений, собственно, всё и затевалось.
Так что надо искать другие решения.

Другое традиционное решение, кроме кубических сплайнов дефекта 1 — полиномы Лагранжа. Это полиномы степени n&nbsp–&nbsp1, принимающие заданные значения в заданных точках. То есть членения на сегменты здесь не происходит, вся последовательность описывается одним полиномом.
Но вот что получается:

Гладкость, конечно, присутствует, но наглядность пострадала так сильно, что… пожалуй, стоит поискать другие методы. На некоторых наборах данных результат выходит нормальный, но в общем случае ошибка относительно линейной интерполяции (и, соответственно, ложные экстремумы) может получаться слишком большой — из-за того, что тут всего один полином на все сегменты.

В компьютерной графике очень широко применяются кривые Безье, представленные полиномами k-й степени.
Они не являются интерполирующими, так как из k&nbsp+&nbsp1 точек, участвующих в построении, итоговая кривая проходит лишь через первую и последнюю. Остальные k&nbsp–&nbsp1 точек играют роль своего рода «гравитационных центров», притягивающих к себе кривую.
Вот пример кубической кривой Безье:

Как это можно использовать для интерполяции? На основе этих кривых тоже можно построить сплайн. То есть на каждом сегменте сплайна будет своя кривая Безье k-й степени (кстати, k&nbsp=&nbsp1 даёт линейную интерполяцию). И вопрос только в том, какое k взять и как найти k&nbsp–&nbsp1 промежуточную точку.
Здесь бесконечно много вариантов (поскольку k ничем не ограничено), однако мы рассмотрим классический: k&nbsp=&nbsp3.
Чтобы итоговая кривая была гладкой, нужно добиться дефекта 1 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (P_i), как это делается в классическом варианте кубического сплайна.
Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
Вот что получится на нашем тестовом наборе:

Стало лучше: ложные экстремумы всё ещё есть, но хотя бы не так сильно отличаются от реальных.

Думаем и экспериментируем

Можно попробовать ослабить условие гладкости: потребовать дефект 2, а не 1, то есть сохранить непрерывность одной только первой производной.
Достаточное условие достижения дефекта 2 в том, что промежуточные контрольные точки кубической кривой Безье, смежные с заданной точкой интерполируемой последовательности, лежат с этой точкой на одной прямой и на одинаковом расстоянии:

Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:

Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C₁ (1) и C_{n&nbsp–&nbsp1} (2) совпадают с точками P₁ и P_n соответственно).
В этом случае получается вот такая кривая:

Как видно, ложных экстремумов уже нет. Однако если сравнивать с линейной интерполяцией, местами ошибка очень большая. Можно сделать её ещё меньше, но тут в ход пойдут ещё более хитрые эвристики.

Эвристика для вычисления расстояний будет такой:

Результат получается такой:

В результате на шестом сегменте ошибка уменьшилась, а на седьмом — увеличилась: кривизна у Безье на нём оказалась больше, чем хотелось бы. Исправить ситуацию можно, принудительно уменьшив кривизну и тем самым «прижав» Безье ближе к отрезку прямой, которая соединяет граничные точки сегмента. Для этого используется следующая эвристика:

Результат следующий:

На этом было принято решение признать цель достигнутой.
Может быть, кому-то пригодится код.

А как люди-то делают?

Обещанный обзор. Конечно, перед решением задачи мы посмотрели, кто чем может похвастаться, а уже потом начали разбираться, как сделать самим и по возможности лучше. Но вот как только сделали, не без удовольствия ещё раз прошлись по доступным инструментам и сравнили их результаты с плодами наших экспериментов. Итак, поехали.

MS Excel

Это очень похоже на рассмотренный выше сплайн дефекта 1, основанный на кривых Безье. Правда, в отличие от него в чистом виде, тут всего два ложных экстремума — первый и второй сегменты (у нас было четыре). Видимо, к классическому поиску промежуточных контрольных точек тут добавляются ещё какие-то эвристики. Но ото всех ложных экстремумов они не спасли.

LibreOffice Calc

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

Есть там ещё один тип интерполяции, который мы тут не рассматривали: B-сплайн. Но для нашей задачи он явно не подходит, так как даёт вот такой результат 🙂

Highcharts, одна из самых популярных JS-библиотек для построения диаграмм

Тут налицо «метод касательных» в варианте равенства расстояний от точки интерполируемой последовательности до промежуточных контрольных. Ложных экстремумов нет, зато есть сравнительно большая ошибка относительно линейной интерполяции (седьмой сегмент).

amCharts, ещё одна популярная JS-библиотека

Картина очень похожа на экселевскую, те же два ложных экстремума в тех же местах.

Coreplot, самая популярная библиотека построения графиков для iOS и OS X

Есть ложные экстремумы и видно, что используется сплайн дефекта 1 на основе Безье.
Библиотека открытая, так что можно посмотреть в код и убедиться в этом.

aChartEngine, вроде как самая популярная библиотека построения графиков для Android

Больше всего похоже на кривую Безье степени n&nbsp–&nbsp1, хотя в самой библиотеке график называется «cubic line». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.

Источник

Интерполяция

Из Википедии — свободной энциклопедии

Интерполя́ция, интерполи́рование (от лат. inter–polis — «разглаженный, подновлённый, обновлённый; преобразованный») — в вычислительной математике нахождение неизвестных промежуточных значений некоторой функции, по имеющемуся дискретному набору её известных значений, определенным способом. Термин «интерполяция» впервые употребил Джон Валлис в своём трактате «Арифметика бесконечных» (1656).

Многим из тех, кто сталкивается с научными и инженерными расчётами, часто приходится оперировать наборами значений, полученных опытным путём или методом случайной выборки. Как правило, на основании этих наборов требуется построить функцию, на которую могли бы с высокой точностью попадать другие получаемые значения. Такая задача называется аппроксимацией. Интерполяцией называют такую разновидность аппроксимации, при которой кривая построенной функции проходит точно через имеющиеся точки данных.

Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.

Источник

Многие из нас сталкивались с непонятными терминами в разных науках. Но находится очень мало людей, которых не пугают непонятные слова, а наоборот, приободряют и заставляют всё больше углубиться в изучаемый предмет. Сегодня речь пойдёт о такой вещи, как интерполяция. Это способ построения графиков по известным точкам, позволяющий с минимальным количеством информации о функции предсказать её поведение на конкретных участках кривой.

Перед тем как перейти к сути самого определения и рассказать о нём подробнее, немного углубимся в историю.

История

Интерполяция была известна ещё с древнейших времён. Однако своим развитием это явление обязано нескольким самым выдающимся математикам прошлого: Ньютону, Лейбницу и Грегори. Именно они развили это понятие с помощью более продвинутых математических способов, доступных в то время. До этого интерполяцию, конечно, применяли и использовали в вычислениях, но делали это совершенно неточными способами, требующими большого количества данных для построения модели, более-менее близкой к реальности.

Сегодня мы можем даже выбирать, какой из способов интерполяции подходит больше. Всё переведено на компьютерный язык, который с огромной точностью может предсказывать поведение функции на определённом участке, ограниченном известными точками.

Что такое интерполяция?

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

Но мы отошли от основной темы. В следующем разделе разберёмся, какая бывает интерполяция и с помощью каких формул можно произвести эту операцию.

Виды интерполяции

Самым простым видом является интерполяция методом ближайшего соседа. С помощью этого способа мы получаем очень приблизительный график, состоящий из прямоугольников. Если вы видели хоть раз объяснение геометрического смысла интеграла на графике, то поймёте, о каком графическом виде идёт речь.

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

Усложнённые виды интерполяции

Есть более интересный, но при этом более сложный способ интерполяции. Его придумал французский математик Жозеф Луи Лагранж. Именно поэтому расчет интерполяции по этому методу назван его именем: интерполяция по методу Лагранжа. Фокус тут вот в чём: если способ, изложенный в предыдущем абзаце, использует для расчета только линейную функцию, то разложение методом Лагранжа предполагает также использование многочленов более высоких степеней. Но не так просто найти сами формулы интерполяции для разных функций. И чем больше точек известно, тем точнее получается формула интерполяции. Но есть и масса других методов.

Перейдём к, пожалуй, одному из важнейших разделов. Из него мы узнаем, как и где обсуждаемая нами совокупность методов применяется в жизни.

Применение

А как это пригодится в жизни?

Смежные понятия

Заключение

Источник