Как построить уравнение кривой по точкам

Построение кривой по точкам с помощью интерполяции Лагранжа

Written on 04 Июля 2013 .

Построение кривой по множеству точек P с помощью интерполяционного многочлена Лагранжа.

Как построить уравнение кривой по точкам

Видео:Математика без Ху!ни. Кривые второго порядка. Эллипс.Скачать

Математика без Ху!ни. Кривые второго порядка. Эллипс.

Введение

В данной статье объясняется построение кривой по точкам с помощью интерполяционного многочлена Лагранжа. Построение кривой по точкам используется в широком спектре технических применений, таких как проектирование машин и поверхностей самолетов. Главная проблема, учитывая множество точек в плане, в том, что надо построить по ним гладкую кривую, проходящую через эти точки. Порядок кривой f(x) зависит от количества заданных точек. Например, если задано две точки, функция будет иметь первый порядок, и кривая будет линией, проходящей через эти две точки, тогда как если задано три точки, функция будет иметь второй порядок f(x) = x2 . Сначала разберем многочлен Лагранжа, затем перейдем к алгоритму и реализации. В этой статье код написан на C#.

Видео:Уравнения касательной и нормали к кривой, заданной в неявном видеСкачать

Уравнения касательной и нормали к кривой, заданной в неявном виде

Основы

Многочлен Лагранжа

Интерполяция на двух точках, (x0, y0) и (x1, y1), дает линейное уравнение или прямую линию. Стандартная форма линейного уравнения задается y = mx +c, где m – градиент линии, а c — отрезок, отсекаемый на оси Y.

Линейное уравнение переписано, чтобы две полученные интерполяцией точки, (x0, y0) и (x1, y1), были непосредственно представлены.

Поэтому линейное уравнение переписывается в виде:

где a0 и a1 — константы. Точки x0 и x1 в множителях вышеприведенного уравнения называются центрами. Применив уравнение в (x0, y0), получаем:

В (x1, y1) получаем:

Следовательно, линейное уравнение становится:

Квадратичная форма многочлена Лагранжа интерполирует три точки, (x0, y0), (x1, y1), and (x2, y2). Многочлен имеет вид:

с центрами в x0, x1, и x2. В (x0, y0):

В целом, многочлен Лагранжа степени n является многочленом, полученным путем интерполяции по множеству точек, (xi , yi ) для i = 0, 1, . . ., n, следующим образом:

Видео:Как написать уравнения касательной и нормали | МатематикаСкачать

Как написать уравнения касательной и нормали | Математика

Использование кода

Алгоритм

Заданы интерполяционные точки (xi , yi ) для i =0, 1, . . . ,n;

Скачайте исходники из верха этой страницы, чтобы изучить код.

Видео:Математика Без Ху!ни. Полярные координаты. Построение графика функции.Скачать

Математика Без Ху!ни. Полярные координаты. Построение графика функции.

Интересные моменты

Численные методы – очень интересная область разработки программного обеспечения. Данная статья связана с этой областью . Скоро будут опубликованы новые статьи о вычислительной геометрии,такие как алгоритм выпуклой оболочки и триангуляция.

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

Видео:Составляем уравнение прямой по точкамСкачать

Составляем уравнение прямой по точкам

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

Как построить график по 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. Это гарантирует отсутствие ложных экстремумов, так как кривая Безье оказывается ограниченной ломаной, построенной на её контрольных точках (если эта ломаная не имеет самопересечений).

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

Как построить уравнение кривой по точкам

Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки 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». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.

Видео:§31.1 Приведение уравнения кривой к каноническому видуСкачать

§31.1 Приведение уравнения кривой к каноническому виду

Кривые второго порядка

Видео:Построение кривой в полярной системе координатСкачать

Построение кривой в полярной системе координат

Как построить уравнение кривой по точкам

Видео:Как составить уравнение прямой, проходящей через две точки на плоскости | МатематикаСкачать

Как составить уравнение прямой, проходящей через две точки на плоскости | Математика

Кривая второго порядка — это некоторая линия на плоскости, которая в декартовой системе координат задается общим уравнением:

Видео:Математика без Ху!ни. Уравнения прямой. Часть 2. Каноническое, общее и в отрезках.Скачать

Математика без Ху!ни. Уравнения прямой. Часть 2. Каноническое, общее и в отрезках.

Как построить уравнение кривой по точкам

Видео:Математика без Ху!ни. Уравнение плоскости.Скачать

Математика без Ху!ни. Уравнение плоскости.

Имеем дело с уравнением второй степени, в котором коэффициенты при старших членах — при вторых степенях одновременно не нули.

Видео:Математика без Ху!ни. Уравнения прямой. Часть 1. Уравнение с угловым коэффициентом.Скачать

Математика без Ху!ни. Уравнения прямой. Часть 1. Уравнение с угловым коэффициентом.

Как построить уравнение кривой по точкам

или можно встретить следующую форму записи:

Видео:Математика без Ху!ни. Уравнение касательной.Скачать

Математика без Ху!ни. Уравнение касательной.

Как построить уравнение кривой по точкам

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

Покажем на примере определение значений коэффициентов.

Как построить уравнение кривой по точкам

Рассмотрим кривую второго порядка:

Видео:Математика без Ху!ни. Нахождение асимптот, построение графика функции.Скачать

Математика без Ху!ни. Нахождение асимптот, построение графика функции.

Как построить уравнение кривой по точкам

Вычислим определитель из коэффициентов:

Как построить уравнение кривой по точкам

Если Δ = 0, кривая второго порядка параболического типа,

если Δ > 0, кривая второго порядка эллиптического типа,

если Δ F1 и F2 — фокусы.

Как построить уравнение кривой по точкам

с — фокальное расстояние,

Как построить уравнение кривой по точкам

Каноническое уравнение эллипса с центром симметрии в начале координат:

Как построить уравнение кривой по точкам

2а — большая ось эллипса, 2b — малая ось эллипса.

а — большая полуось эллипса, b — малая полуось эллипса.

Если a = b, то имеем окружность с радиусов R = a = b:

Как построить уравнение кривой по точкам

Если центр эллипса находится не в начале координат, а в некоторой точке C(x0;y0), оси эллипса параллельны осям координат, то каноническое уравнение эллипса имеет вид:

Как построить уравнение кривой по точкам

Эксцентриситет — число, равное отношению фокального расстояния к большей полуоси:

Как построить уравнение кривой по точкам

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

Гипербола — множество точек на плоскости для каждой из которых абсолютная величина разности расстояний до двух данных точек F1 и F2 есть величина постоянная, меньшая расстояния между этими точками.

Как построить уравнение кривой по точкам

Как построить уравнение кривой по точкам

с — фокальное расстояние,

Как построить уравнение кривой по точкам

Расстояние от центра гиперболы до одного из фокусов называется фокальным расстоянием.

Каноническое уравнение гиперболы с центром симметрии в начале координат:

Как построить уравнение кривой по точкам

x — действительная ось, y — мнимая ось.

а — действительная полуось, b — мнимая полуось.

Если центр гиперболы находится в некоторой точке C(x0;y0), оси симметрии параллельны осям координат, то каноническое уравнение имеет вид:

Как построить уравнение кривой по точкам

Эксцентриситет гиперболы — число, равное отношению фокусного расстояния к действительной полуоси.

Как построить уравнение кривой по точкам

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

Директриса гиперболы — прямые, параллельные мнимой оси гиперболы и отстоящая от нее на расстоянии a/Ε.

f1 — правая директриса, f2 — левая директриса.

Как построить уравнение кривой по точкам

Порядок построения гиперболы :

1. Строим прямоугольник со сторонами 2a и 2b.

Как построить уравнение кривой по точкам

2. Провести асимптоты гиперболы — диагонали построенного прямоугольника.

Как построить уравнение кривой по точкам

3. Строим гиперболу с вершинами в точках А 1 (-а;0), А 2 (а;0).

Как построить уравнение кривой по точкам
Как построить уравнение кривой по точкамКак построить уравнение кривой по точкам

Парабола — множество точек на плоскости для каждой из которых расстояние до данной точки F равно расстоянию до данной прямой f.

F — фокус параболы, f — директриса параболы.

🎥 Видео

Видеоурок "Гипербола"Скачать

Видеоурок "Гипербола"

Аналитическая геометрия, 7 урок, Линии второго порядкаСкачать

Аналитическая геометрия, 7 урок, Линии второго порядка

Аналитическая геометрия, 5 урок, Уравнение плоскостиСкачать

Аналитическая геометрия, 5 урок, Уравнение плоскости

Уравнения стороны треугольника и медианыСкачать

Уравнения стороны треугольника и медианы

9 класс, 7 урок, Уравнение прямойСкачать

9 класс, 7 урок, Уравнение прямой

Точки пересечения графика линейной функции с координатными осями. 7 класс.Скачать

Точки пересечения графика линейной функции с координатными осями. 7 класс.

Уравнение касательной в точке. Практическая часть. 1ч. 10 класс.Скачать

Уравнение касательной в точке. Практическая часть. 1ч. 10 класс.
Поделиться или сохранить к себе: