Есть ли простой способ вычислить гладкую функцию со следующими характеристиками в C/C++?

Чтобы сначала указать некоторые вещи: пользователь должен иметь возможность создать график, указав от 3 до 5 точек на 2D-поле. Первая и последняя точки всегда находятся на границах этого поля (их положение можно изменить только в направлении y, а не x). Вывод графика в этих позициях должен быть равен 0. Положение 3-й и последующих точек можно указать произвольно. График должен быть интерполирован, который проходит по всем точкам. Однако этот график должен быть максимально гладким и плоским. (пожалуйста, извините за математически неверную формулировку)

Важная вещь: впоследствии мне нужно взять значения этого графика и применить их к дискретному сигналу. Второе: в диапазоне оси x значения функции не должны превышать границы по оси y. На моих рисунках это будут 0 и 1 по оси y. Я создал несколько фотографий, чтобы проиллюстрировать то, о чем я говорю, используя 3 точки.

Некоторые мысли, которые у меня были:

  1. Используйте (кубические?) сплайны: их характеристики могут быть применены для построения таких кривых без особых проблем. Однако, насколько мне известно, они не относятся к глобальной оси x. Они указываются относительно следующей точки через параметр, обычно называемый (s). Поэтому будет сложно выбрать значения графика, связанные с осью x. Пожалуйста, поправьте меня, когда я ошибаюсь.
  2. создайте матрицу, которая содержит точки и производные в этих точках, и решите эту матрицу, используя разложение LU или что-то эквивалентное.

Пока у меня нет глубокого понимания этих методов, поэтому я могу пропустить какую-то замечательную технику или алгоритм, о которых я еще не знал.

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

alt textальтернативный текст альтернативный текстальтернативный текст


person st-h    schedule 16.12.2010    source источник


Ответы (3)


Вы понимаете, как получаются сплайны?

Резюме выполнения сплайнов

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

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

Результатом является набор параметров для кусочной функции. Вообще кусочно-непрерывная и дифференцируемая функция, ибо какой в ​​противном случае смысл.

Как вы можете использовать это в этом случае

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

Для n общего количества баллов у вас будет D*(n-2) параметров, если каждый сегмент имеет D параметров. У вас есть четыре ограничения конечных точек f(start)=y_0, f(end)=y_n, f'(start) = f'(end) = 0) и некоторый набор ограничений соответствия между сегментами:

f_n(between n and n+1) = f_n+1(between n and n+1)
f'_n(between n and n+1) = f'_n+1(between n and n+1)
...

плюс каждый сегмент ограничен своим отношением к контрольной точке (обычно либо f(point n) = y_n, либо f'(point n) = 0, либо и то, и другое (но вам решать).

Сколько соответствующих ограничений вы можете иметь, зависит от количества степеней свободы (общее количество ограничений должно равняться общему количеству DoF, верно?). Вы должны ввести некоторые дополнительные ограничения конечной точки в форме f''(start) = 0 ..., чтобы все было правильно.

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

Большинство книг по численным методам охватывают этот материал.

person dmckee --- ex-moderator kitten    schedule 17.12.2010
comment
хорошо, спасибо за ответ ... Думаю, вы меня зацепили, и я попробую использовать кубические сплайны. - person st-h; 17.12.2010
comment
Я нашел кое-что интересное здесь: korf.co.uk/spline.pdf Они описывают, как для создания сплайнов, которые не выходят за рамки и могут быть рассчитаны без решения матрицы и т. д. В основном это упрощение кубического сплайна, но, похоже, он делает именно то, что мне нужно. Написал код на C++ в соответствии с их математикой. Выглядит довольно хорошо до сих пор. Однако я не уверен, как ввести параметр, позволяющий управлять крутизной кривой. Надо будет над этим поработать. Кто-нибудь намекает? - person st-h; 19.12.2010
comment
@codey: сплайн, описанный в этой статье, позволяет вам получить решение в закрытой форме, прежде чем вы начнете. Это не всегда возможно. После того, как я написал этот ответ, мне пришло в голову задаться вопросом, рассматривали ли вы B-сплайны как вариант. Прошло некоторое время с тех пор, как я использовал их, поэтому я не уверен, что они удовлетворят ваши потребности, но они характеризуются простой математикой. - person dmckee --- ex-moderator kitten; 19.12.2010
comment
Я не уверен, что вы пытаетесь сказать о сплайне, описанном в статье. Что касается Безье- или B-сплайнов: в своей базовой форме они просто аппроксимируют точки, поэтому они не проходят через точки. Затем идут интерполирующие b-сплайны. Они, вероятно, будут работать, но они также кажутся более дорогостоящими для расчета. Во-вторых, они все равно могут выйти за пределы диапазона, поэтому они не соответствуют моему требованию относительно y-диапазона. - person st-h; 19.12.2010

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

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

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

Удачи!

person SEngstrom    schedule 17.12.2010
comment
разве приращение сплайна по отношению к оси x не зависит от расположения двух точек? Если две точки расположены близко друг к другу относительно их значений x, это приведет к большему количеству точек выборки на оси x, чем когда они расположены близко. Поэтому мне нужно было бы связать количество точек выборки с их x-значениями (если сначала не рисовать график). Думаю, это должно сработать. Однако я искал возможность получить дискретные значения такой функции без особых вычислений. То же самое и с матрицами: теоретически это должно работать, но нет ли чего-то более элегантного? - person st-h; 17.12.2010
comment
@codey: на выходе вы получите кусочную функцию (это и есть сплайн), которую вы можете оценить в произвольных точках. То есть вы можете рисовать кривую так плотно и ровно, как хотите. - person dmckee --- ex-moderator kitten; 17.12.2010

Почему бы не использовать известные решения вашей проблемы? Прочтите о линейной регрессии и полиномиальная регрессия. Это алгоритмы, которые вы ищете. ОБНОВЛЕНИЕ: вас интересует полиномиальный

person matcheek    schedule 17.12.2010
comment
На первый взгляд они были бы... однако они довольно нестабильны, что приводит к тому, что не получается плавная кривая... Например, поместите две точки на ось x, а третью где-нибудь еще.. вы получите огромные волны... - person st-h; 17.12.2010
comment
OP хочет, чтобы кривая проходила через все контрольные точки с дополнительным ограничением, состоящим в том, что наклон равен нулю в начальной и конечной точках. Линейная или полиномиальная регрессия обычно не обладает этими свойствами. - person Jim Lewis; 17.12.2010
comment
@codey: полиномиальные результаты гладкие по математическому определению. Чем они не являются, так это надежно обладают нулевым наклоном на концах. - person dmckee --- ex-moderator kitten; 17.12.2010
comment
@dmckee, вы говорите о гладкости как о дифференцируемой и непрерывной? (надеюсь, я выбрал правильные слова) Я не математик, поэтому могу ошибаться в некоторых выражениях. Однако мне нужна кривая, которая будет не только максимально плавной, но и настолько плоской, насколько это возможно. Я надеялся, что рисунки ясно иллюстрируют то, о чем я говорю. - person st-h; 17.12.2010
comment
что вы подразумеваете под "нестабильным"? пробовали реализовать? - person matcheek; 17.12.2010
comment
Ну, в любом случае график не проходит через все точки - он только аппроксимирует график, для чего обычно используется регрессия. Или повышаешь степень. Но поведение похоже на полиномиальную интерполяцию, которую я бы не назвал плоской. Есть апплет, чтобы попробовать: arachnoid.com/polysolve - person st-h; 17.12.2010
comment
@codey: я говорил именно об этом. Я подчеркнул математическую часть, потому что мне было интересно, не имеете ли вы в виду что-то другое. Чтобы справиться со стремлением к плоскостности, нам (или, по крайней мере, мне) потребуется более точное понимание того, что вы имеете в виду под этим. Стандартный подход к сплайну справится со всем остальным за вас, но на самом деле он не соответствует этой идее (не беспокойтесь о параметре s, он здесь для удобства и может быть очень легко преобразован в x, хотя это должно быть сделано на сегменте). по сегментам...). - person dmckee --- ex-moderator kitten; 17.12.2010