2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:22 
Аватара пользователя


21/03/13
8
Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной ($d(p)$ - расстояние от точки $p$ до сдвинутой параболы).
Для упрощения можно считать, что расстояние до параболы считается как разница $y$ (как в регрессионной модели), но хотелось бы использовать реальное расстояние.

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

Буду очень благодарен за любую помощь.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:32 
Заслуженный участник
Аватара пользователя


23/08/07
4671
Нов-ск
oliver в сообщении #726194 писал(а):
Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной

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

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:41 
Заслуженный участник
Аватара пользователя


18/05/06
13214
с Территории
Если расстояние до параболы считается как разница $y$, то перед нами классический линейный МНК. Там не то что кубическим, там и квадратичным уравнениям неоткуда быть.
Если расстояние реальное, то всё плохо, плохо...

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:48 
Заслуженный участник
Аватара пользователя


23/08/07
4671
Нов-ск

(Оффтоп)

ИСН в сообщении #726210 писал(а):
Если расстояние реальное, то всё плохо, плохо...
$\text{то плохо}^{\text{плохо}^\text{...}}$

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 13:48 
Аватара пользователя


21/03/13
8
TOTAL в сообщении #726205 писал(а):
oliver в сообщении #726194 писал(а):
Задача:

Задано параболу $ax^2+bx+c$ и набор $k$ точек ${p_i=(x_i, y_i)}$.
Минимизыровать сумму квадратов расстояний от точек до параболы,
то есть найти такое смещение параболы ${(x_0, y_0)}$, чтобы сумма $\sum\limits_{i=1}^k d(p_i)^2$ была минимальной

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


Пусть смещение параболы равно $((x_0,y_0))$
Тогда новая парабола будет иметь вид: $y^* =ax^*^2+bx^*+(c-y_0)= a(x-x_0)^2+b(x-x_0)+(c-y_0)$
1. Пусть $d((x_i,y_i))=y^*-y_i=(a(x-x_0)^2+b(x-x_0)+(c-y_0))\ -\ y_i$
Минимизировать $\sum\limits_{i=1}^k d(p_i)^2$

2. (Усожненный вариант - расстояние на плоскости) Пусть $d((x_i,y_i))=\sqrt{(x^*-x_i)^2+(y^*-y_i)^2}
Тогда: $d((x_i,y_i))=\sqrt{(x-x_0-x_i)^2+((a(x-x_0)^2+b(x-x_0)+(c-y_0))-y_i)^2}$
Минимизировать $\sum\limits_{i=1}^k d(p_i)^2$

-- 20.05.2013, 12:54 --

ИСН в сообщении #726210 писал(а):
Если расстояние до параболы считается как разница $y$, то перед нами классический линейный МНК. Там не то что кубическим, там и квадратичным уравнениям неоткуда быть.


$\sigma=\frac12\sum\limits_{i=1}^k (y_i-(a(x_i-x_0)^2+b(x_i-x_0)+(c-y_0))^2$

При дифференциировании по $x_0$ появляются степеня.

Если у меня ошибка - укажите, пожалуйста.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:01 
Заслуженный участник
Аватара пользователя


18/05/06
13214
с Территории
Зачем Вы дифф... а, нет, понял.
Не надо искать никакое смещение. Смещения нет (0). Ищите саму параболу. Тупо: a, b, c. По ним же и дифференцируйте в процессе.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:04 
Заслуженный участник
Аватара пользователя


23/08/07
4671
Нов-ск
ИСН в сообщении #726218 писал(а):
Тупо: a, b, c. По ним же и дифференцируйте в процессе.
Если $a$ фиксировано, то тупо по b, c.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:17 
Аватара пользователя


21/03/13
8
TOTAL в сообщении #726219 писал(а):
ИСН в сообщении #726218 писал(а):
Тупо: a, b, c. По ним же и дифференцируйте в процессе.
Если $a$ фиксировано, то тупо по b, c.


А, понял.
a - фиксирует форму кривой, b, c - задают смещение.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:20 
Заслуженный участник
Аватара пользователя


18/05/06
13214
с Территории
Можно сказать и так, да.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:50 
Аватара пользователя


21/03/13
8
Надо было сразу написать, что форма кривой - фиксирована.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 14:56 
Заслуженный участник


11/05/08
31548
Там фиксирована не только форма, но и направление параболы (строго вверх). В этой ситуации совершенно непонятно, какую пользу может принести сельскому хозяйству минимизация расстояний именно по нормалям, а не по вертикали. Впрочем, фиксация формы ещё более непонятно зачем.

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 18:57 
Аватара пользователя


21/03/13
8
ewert в сообщении #726235 писал(а):
Там фиксирована не только форма, но и направление параболы (строго вверх). В этой ситуации совершенно непонятно, какую пользу может принести сельскому хозяйству минимизация расстояний именно по нормалям, а не по вертикали. Впрочем, фиксация формы ещё более непонятно зачем.


Представте себе, что точки на плоскости - места на зубах куда будут крепится брекеты, а парабола - это заранее подготовленная проволочка, к которой они будут прикреплены :-)

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение20.05.2013, 22:09 
Заслуженный участник
Аватара пользователя


18/05/06
13214
с Территории
В такой формулировке имеется ещё одна степень свободы - можно всю параболу как целое наклонить набок. Или Вы это и собираетесь делать в дальнейшем?

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение21.05.2013, 14:29 
Аватара пользователя


21/03/13
8
Да, такой поворот возможен , но он будет осуществлятся только по указаниям пользователя с помощью манипуляторов в 3D.

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

 Профиль  
                  
 
 Re: Минимизировать расстояние от набора точек до параболы
Сообщение21.05.2013, 17:10 
Заслуженный участник
Аватара пользователя


18/05/06
13214
с Территории
Не очень понял (размещение параболы параллельно заданной плоскости всё-таки оставляет нам свободу её наклонять в этой самой плоскости), ну да неважно. Значит, находите первоначальное положение по МНК, а потом численно подгоняйте по реальным расстояниям.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group