Линия с наибольшей кривизной

[alexey007]

Привет, всем!
Дайте пожалуйста идеи, как получить алгоритм с помощью которого можно найти линию с наибольшей кривизной.
Даны два набора точек $\{x_i,Y^{\max}_i\}$ и $\{x_i,Y^{\min}_i\}$ красные и синие точки соответственно. Значения $Y^{\max}_i$ и $Y^{\min}_i$ - погрешность измерения некоторой функции $g(x)$



Я взял все точки, красные и синие и построил аппроксимацию рядом Фурье (черная линия):
$f(x) = a_0 + a_1\cos(\omega x) + b_1\sin(\omega x) + a_2\cos(2\omega x) + b_2\sin(2\omega x)$
Мне нужно выбрать такие точки $y_i$ из диапазона $(Y^{\max}_i, Y^{\min}_i)$, чтобы получить функцию $f(x)$ с наибольшей кривизной (примерно в зеленой точке).
Первое что пришло в голову, это перебрать крайние точки $Y^{\max}_i$ и $Y^{\min}_i$ во всех возможных вариантах, но простой перебор всех возможных вариантов дает $2^n$ расчетов, где $n$- число точек $(n\approx20)$. Таким образом перебор крайних значений не подходит. Посоветуйте, как выбрать такие точки из диапазона, чтобы через них проходила гладкая кривая с наибольшей кривизной.

[svv]

Это примерно так должно получиться?

Просто меня не покидает ощущение, что Вы имели в виду наименьшую кривизну (примерно как у чёрной линии).

[arseniiv]

Или наибольшая кривизна только в той точке, а в остальных поменьше?.. Тогда просто взять один узенький пик как у svv, а в остальных местах приближаться к исходной чёрной, возможно даже опустив её пониже. Но я не очень представляю, что именно при этом оптимизируется — мы могли бы всё увеличивать и увеличивать кривизну до бесконечности, уменьшая собственно радиус кривизны пика.

[alexey007]

svv в сообщении #1514516 писал(а):

Это примерно так должно получиться?

Нет, не так. У меня было ощущение, что меня не правильно поймут. Тогда, наверно все таки нужно зафиксировать, что функция всегда будет рядом Фурье: $f(x) = a_0 + a_1\cos(\omega x) + b_1\sin(\omega x) + a_2\cos(2\omega x) + b_2\sin(2\omega x) $ $(1)$
хотя вид функции заранее не известен, но у нее точно не должно быть много максимумов и минимумов.

arseniiv в сообщении #1514518 писал(а):

Или наибольшая кривизна только в той точке, а в остальных поменьше?.. Тогда просто взять один узенький пик как у svv, а в остальных местах приближаться к исходной чёрной, возможно даже опустив её пониже. Но я не очень представляю, что именно при этом оптимизируется — мы могли бы всё увеличивать и увеличивать кривизну до бесконечности, уменьшая собственно радиус кривизны пика.

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

[пианист]

alexey007 в сообщении #1514529 писал(а):

нужно зафиксировать, что функция всегда будет рядом Фурье

alexey007 в сообщении #1514529 писал(а):

у нее точно не должно быть много максимумов и минимумов

Вы полагаете, что первое влечет второе? Почему?

alexey007 в сообщении #1514529 писал(а):

У меня было ощущение, что меня не правильно поймут

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

[alexey007]

пианист в сообщении #1514532 писал(а):

alexey007 в сообщении #1514529 писал(а):

нужно зафиксировать, что функция всегда будет рядом Фурье

alexey007 в сообщении #1514529 писал(а):

у нее точно не должно быть много максимумов и минимумов

Вы полагаете, что первое влечет второе? Почему?

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

пианист в сообщении #1514532 писал(а):

Возможно, стоит побольше рассказать о задаче.

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

[Geen]

alexey007 в сообщении #1514533 писал(а):

которая даст наибольшее искривление.

Каждый позвонок выбит в свою сторону....

-- 16.04.2021, 00:41 --

А что означают точки, и почему их два семейства?

[Евгений Машеров]

У Вас не ряд Фурье. У Вас два слагаемых из него. Когда Вы получили приближение - возьмите вторую производную и найдите её максимум.

[alexey007]

ОООО, я кажется понял. Спасибо, что подтолкнули меня посмотреть на эту задачу с другой стороны.
Я думаю, что лучше всего аппроксимировать кривую полиномом 4-ой степени, потому, что у $S$-образных сколиозов всегда 3 изгиба. Т.е. задача теперь формулируется так. Нужно найти линию, которая имеет вид $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4$ и проходит внутри границ $Y^{\min}_i\ll f(x_i)\ll Y^{\max}_i$, при этом, в точках экстремума $f'(z_k)=0, k=1,2,3$ функция должна иметь максимальную кривизну, наверное условие должно быть записано как то так $f''(z_1)^2+f''(z_2)^2+f''(z_3)^2\to \max$
Вот как теперь искать точки $y_i\in[Y^{\min}_i,Y^{\max}_i]$ через которые пройдет такая кривая. Ведь у полинома 4-ой степени 5 коэффициентов, а точек $n\approx 20$

[Sender]

Всё-таки что собой представляют синие и красные точки в терминах исходной задачи?

[alexey007]

Sender в сообщении #1514572 писал(а):

Всё-таки что собой представляют синие и красные точки в терминах исходной задачи?

Это диапазон неопределенности положения центра позвонка человека во фронтальной плоскости.
Примерно как на картинке:

[Geen]

alexey007 в сообщении #1514574 писал(а):

Это диапазон неопределенности положения центра позвонка человека во фронтальной плоскости.

Тогда ведь нужно учитывать, что размер позвонков меняется?

-- 16.04.2021, 13:07 --

alexey007 в сообщении #1514566 писал(а):

и проходит внутри границ

Это плохая задача - она сильно зависит локальных выбросов.

[alexey007]

Geen в сообщении #1514575 писал(а):

alexey007 в сообщении #1514574 писал(а):

Это диапазон неопределенности положения центра позвонка человека во фронтальной плоскости.

Тогда ведь нужно учитывать, что размер позвонков меняется?

В этом диапазоне неопределенности все учтено. Нужно лишь провести линию $f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4$ в границах этого диапазона (внутри красных и синих точек), у которой будет максимальная кривизна, чтобы консервативно учесть, максимальное искривление позвоночника, которое может быть.

[Sender]

Нужен какой-никакой критерий "хорошести" искомой кривой, иначе получится нечто весьма далёкое от реальности.

[Евгений Машеров]

Если искать не кривизну $\kappa(x)=\frac {|f, а лишь максимум второй производной, пренебрегая влиянием на значение кривизны знаменателя, задача может быть сведена к задаче линейного программирования. Пусть $x_i$ есть коэффициенты при i-той степени и при этом параметры задачи ЛП (ограничение $x_i \ge 0$ не предусматривается). Тогда значения в каждой точке $z_k$ будут составлять матрицу ограничений $Y_k^{min}\le x_0+x_1 z_k+x_2 z_k^2$+x_3 z_k^3+x_4 z_k^4\le Y_k^{max}. Вторая производная в каждой точке будет
$v_k= x_1+2x_2 z_k+3 x_3 x_k^2+4x_4 x_k^3$
Если число точек не слишком велико, то можно решать задачу 2m раз, беря в качестве целевой функции вторую производную (и затем её же с обратным знаком) в каждой точке и максимизируя её. Или же можно добавить переменные и ограничения и решать задачу единожды.