Меню

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

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

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

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

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

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

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

Ставим опыты

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

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

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

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

Традиционно для решения такой задачи используют полиномы третьей степени и добиваются непрерывности первой и второй производной. То, что получается, называют кубическим сплайном дефекта 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 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (Pi), как это делается в классическом варианте кубического сплайна.
Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
Вот что получится на нашем тестовом наборе:

Читайте также:  Структура белка таблица с примерами

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

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

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

В качестве прямых, на которых лежат точки Ci&nbsp–&nbsp1 (2) , Pi и Ci (1) , целесообразно взять касательные к графику интерполируемой функции в точках Pi. Это гарантирует отсутствие ложных экстремумов, так как кривая Безье оказывается ограниченной ломаной, построенной на её контрольных точках (если эта ломаная не имеет самопересечений).

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

image

Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C1 (1) и Cn&nbsp–&nbsp1 (2) совпадают с точками P1 и Pn соответственно).
В этом случае получается вот такая кривая:

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

К текущему варианту мы пришли, уменьшив гладкость на один порядок. Можно сделать это ещё раз: пусть сплайн будет иметь дефект 3. По факту, тем самым формально функция не будет гладкой вообще: даже первая производная может терпеть разрывы. Но если рвать её аккуратно, визуально ничего страшного не произойдёт.
Отказываемся от требования равенства расстояний от точки Pi до точек Ci&nbsp–&nbsp1 (2) и Ci (1) , но при этом сохраняем их все лежащими на одной прямой:

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

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

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

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

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

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

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

MS Excel

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

LibreOffice Calc

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

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

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

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

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

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

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

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

Читайте также:  Оптимальное соотношение роста и веса таблица
aChartEngine, вроде как самая популярная библиотека построения графиков для Android

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

Источник

Вычислительная математика копия 1

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

Задача интерполяции ставится так:

Функция y = f ( x ) задана в виде таблицы

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

Очевидно, что коэффициенты с j можно найти методом наименьших квадратов, положив n = m .

Рассмотрим другие способы решения этой задачи.

3.1 Интерполяция по Лагранжу

Выражение (3.2) – алгебраический полином степени n . Покажем, что он проходит через все точки таблицы при n =2 и n =3.

Выражение (3.2) – интерполяционный полином Лагранжа, проходящий через все точки таблицы. Теперь, чтобы найти значение функции в некоторой точке x * , которой нет в таблице, достаточно подставить эту точку вместо x в формулу (3.2) и считать, что

1

3.2 Интерполяция при постоянном шаге

Конечной разностью функции y= f (x) c шагом D x = h называют функцию D y=f (x+h)-f(x). Это первая конечная разность. Вторая конечная разность D 2 y = D ( D y )=[ f ( x +2 h )- f ( x + h )]-[ f ( x + h )- f ( x )]= f ( x +2 h )-2 f ( x + h )+ f ( x ) и т.д.

Предположим, что функция y = f (x) задана в виде таблицы из четырех точек. Построим для нее таблицу конечных разностей:

Предположим, что шаг в этой таблице – постоянный, то есть

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

После подстановки в ( 3.5) значений ai i=0,1,2,3 и q1 окончательно получаем:

Запишем общий вид полинома n -й степени:

22

I “ означает, что это первый интерполяционный полином Ньютона. Он удобен для вычислений, когда точка х=х * , в которой нужно вычислить функцию, расположена ближе к началу таблицы.

Если точка х * расположена ближе к концу таблицы, то удобнее пользоваться формулой второго интерполяционного полинома Ньютона:

22

Результаты применения формул (3.6) и (3.7) – одни и те же, если используются одни и те же узлы таблицы.

3.3 Обратная интерполяция

Функция y задана в виде таблицы

Требуется найти значение аргумента x * , при котором функция принимает некоторое значение y * .

Задачу можно решить по крайней мере двумя различными способами.

1. а) Строим интерполяционный полином (как правило, ИПЛ) y=Ln( x )

в) Решаем уравнение y * =Ln(x) любым подходящим численным методом (например, методом деления отрезка пополам).

1

Из рисунка видно, что задача может иметь не единственное решение.

2. а) Строим интерполяционный полином x=Ln( y )

в) Подставляем в этот полином значение y * и получаем x * :

2

Как правило, решения задачи, полученные первым и вторым способом, будут различными.

3.4 Численное дифференцирование

Численное дифференцирование – это вычисление производных от функций, заданных в виде таблицы. Задача решается в два этапа. На первом этапе строится интерполяционный полином. На втором этапе находятся производные (первая, вторая и т.д.) от этого полинома.

Если шаг постоянный, то на первом этапе строят ИПН.

Найдем первую производную от этого полинома.

Если производную нужно вычислить в каком-либо узле таблицы (например, в точке х=х), то формулы (3.9) и (3.10) упрощаются, так как q1=0.

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

Пример. Функция задана в виде таблицы из четырех точек. Вычислить значение функции в точке х=-1 и значение первой и второй производной в этой же точке.

3.5 Численное интегрирование

Численное интегрирование – это вычисление определенных интегралов от функций, заданных либо в явном виде (например, Undetermined error: ), либо в виде таблицы. В любом случае функцию приводят к табличному виду, задавая шаг h и вычисляя значения подынтегральной функции в определенных точках. Интегралы вычисляют с помощью так называемых квадратурных формул, то есть

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

Для нахождения коэффициентов Ai в формуле (3.13) функцию y=f(x) заменяют интерполяционным полиномом. Интеграл от полинома легко вычисляется.

Для нахождения двойных определенных интегралов существуют соответствующие кубатурные формулы (с двойными суммами).

Читайте также:  Российская федерация форма правления таблица

Существует множество квадратурных формул. Рассмотрим три из них.

1. Формулы прямоугольников

а) формула левых прямоугольников

1

На отрезке [ a , b ] функцию заменяют прямой и считают, что интеграл (то есть площадь криволинейной трапеции, ограниченной осью Х, прямыми х=а , х=в и графиком функции y=f(x)) приближенно равен площади прямоугольника:

в) формула правых прямоугольников

4

На отрезке [ a , b ] функцию y=f(x) заменяют прямой y=f(b) и считают, что интеграл приближенно равен площади прямоугольника:

с) формула центральных прямоугольников

7

На отрезке [ a , b ] функцию y=f(x) заменяют прямой y=f((a+b)/2) и считают, что интеграл приближенно равен площади прямоугольника:

2(3.16)

2. Формула трапеций

На отрезке [ a , b ] функцию y=f(x) заменяют полиномом первой степени, проходящим через точки ( a , f(a)) и ( b , f ( b )) и считают, что интеграл приближенно равен площади прямоугольной трапеции:

7

3. Формула Симпсона

На отрезке [a , b] функцию заменяют полиномом второй степени, проходящим через точки (a , f(a)) , (((a+b)/2,f((a+b)/2)))и ( b , f ( b )) и считают, что интеграл приближенно равен площади заштрихованной криволинейной трапеции:

6

Из рисунков видно, что чем больше длина отрезка [a , b], тем, как правило, больше погрешность, то есть разность между точным значением интеграла и приближенным, полученным по соответствующей квадратурной формуле. Для уменьшения этой погрешности поступают следующим образом. Отрезок [a , b] разбивается на n частей. Для простоты будем считать, что эти части равные, то есть hi=xi+1-xi=h=const. На каждом из отрезков [xi , xi +1] используется соответствующая формула. Получают так называемые обобщенные формулы.

1а. Обобщенная формула левых прямоугольников

8

1 b . Обобщенная формула правых прямоугольников

5

1с. Обобщенная формула центральных прямоугольников

7

2а. Обобщенная формула трапеций

9

3а. Обобщенная формула Симпсона

0

Число точек в формуле Симпсона должно быть нечетным.

Чем больше n , тем, как правило, меньше погрешность. Формулы дают следующую погрешность. Погрешность обобщенных формул левых и правых прямоугольников – o( h ), погрешность обобщенной формулы центральных прямоугольников и обобщенной формулы трапеций – o( h 2 ). погрешность обобщенной формулы Симпсона – o( h 4 ) .

Каждую из формул нетрудно запрограммировать.

Вычислить Undetermined error: =[x-ln(1+x)]| 4 =4-ln5 » 2.391

Взять шаг равным одной четвертой длины интервала интегрирования.

Источник



Интерполяционный многочлен Лагранжа (полином Лагранжа)

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

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

Калькулятор ниже обладает следующими функциями:

  1. Он находит формулу полинома Лагранжа для заданного набора точек.
  2. Он отображает пошаговый вывод формулы.
  3. Он вычисляет значения интерполяционного многочлена Лагранжа для заданных точек (интерполирует функцию полиномом Лагранжа в заданных точках интерполяции)
  4. Он отображает набор точек, значения в точках интерполяции, полином Лагранжа и все базисные полиномы на графике.

Как пользоваться

Сначала вводите набор точек — одна точка на строку в форме x f(x), значения разделены пробелом. Если вы хотите получить интерполяцию, вводите значения точек интерполяции в следующее поле в виде значений x, разделенных пробелом.

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

Теория и формулы, как обычно, описаны под калькулятором.

Источник

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

Интерполяция – это способ определения промежуточных значений по дискретному набору данных.

Формула линейной интерполяции имеет вид:

линейная интерполяция формула

Ниже представлен график линейной интерполяции для нелинейной функции $y=\sqrt$

Линейная интерполяция график пример

Пример 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(x)=x 2 . Проверим правильность, подставив в функцию значение X=3

f(3)=3 2 =9

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

Насколько публикация полезна?

Нажмите на звезду, чтобы оценить!

Средняя оценка 4.6 / 5. Количество оценок: 10

Оценок пока нет. Поставьте оценку первым.

4458

Источник