Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.85.167.119] |
|
Сообщ.
#1
,
|
|
|
Итак, даны прямая и три точки на плоскости. Точки лежат вне прямой.
Нужно найти на прямой точку сумма расстояний от которой до данных точек минимальна. Подходящим ответом будет сведение этой задачи к уравнению степени меньше 5. Прямой можно считать ось Х. Для двух точек задача решается легко. А для трёх у меня получается уравнение 6-й степени. Коэффициенты не расписывал, может там что-то сокращается. |
Сообщ.
#2
,
|
|
|
Нет желания минимизировать вместо этого сумму квадратов расстояний?
Судя по описанию задачи с двумя степенями свободы по минимизации суммы расстояний, функционал выглядит гладким, и численные методы должны неплохо сходиться. |
Сообщ.
#3
,
|
|
|
Как нам в своё время объясняли, минимизация суммы квадратов - это игра в метрике L2, а вот минимизация суммы - игра в метрике L1, что является более естественным для глаза, сколь бы неожиданным это ни казалось. Ну и широко известно, что в гильбертовом то пространстве (L2) всё решается намного легче.
|
Сообщ.
#4
,
|
|
|
Не понимаю, как на такой фигне можно получить аж шестую степень... речь идёт о тривиальнейшем поиске минимума квадратичной функции...
|
Сообщ.
#5
,
|
|
|
Цитата Akina @ У него сумма не квадратов расстояний, а самих расстояний.речь идёт о тривиальнейшем поиске минимума квадратичной функции... То есть сумма трёх квадратных корней от квадратичных функций. Избавляясь от корней, он и получает выражение шестой степени. MBo, все встречавшиеся мне когда-либо задачи на минимизацию суммы расстояний (в метрике L1) имеют гладкий вид. За исключением заданных точек, где их гладкость нарушается. Впрочем, причина тривиальна. Само расстояние от точки - функция, гладкая везде, кроме самой этой точки. А сумма гладких функций является гладкой функцией. |
Сообщ.
#6
,
|
|
|
Цитата amk @ У него сумма не квадратов расстояний, а самих расстояний. То есть сумма трёх квадратных корней от квадратичных функций. Упс... Цитата amk @ Избавляясь от корней, он и получает выражение шестой степени. Ему нужен минимум функции вида f(x) = SUM(SQRT(x+a)*SQRT(x+b)) - аналитически это получится вроде как 5 степень. |
Сообщ.
#7
,
|
|
|
Цитата MBo @ численные методы должны неплохо сходиться. Численными методами я результат нахожу. Но появился спортивный интерес, ведь для похожей задачи ( без требования, чтобы точка лежала на прямой ) есть геометрические решения для трёх и четырёх точек. |
Сообщ.
#8
,
|
|
|
Цитата prografix @ А для трёх у меня получается уравнение 6-й степени. Я ошибся. Уравнение получается 12-й степени. |
Сообщ.
#9
,
|
|
|
Цитата prografix @ Уравнение получается 12-й степени. Этого не может быть! ищи ошибку. |
Сообщ.
#10
,
|
|
|
Да, у меня тоже 12-ой. Ещё и думал, как это вы до 6-й скостили...
|
Сообщ.
#11
,
|
|
|
Цитата prografix @ Причём решения принципиально разные. А для пяти точек такого решения уже нет.Численными методами я результат нахожу. Но появился спортивный интерес, ведь для похожей задачи ( без требования, чтобы точка лежала на прямой ) есть геометрические решения для трёх и четырёх точек. Так и в этой задаче, для двух точек есть простое геометрическое решение, а для трёх универсального решения может уже не быть. Добавлено У меня, кстати, тоже к 12 степени всё сводится. |
Сообщ.
#12
,
|
|
|
Цитата amk @ Причём решения принципиально разные. А для пяти точек такого решения уже нет. А где про это почитать можно? |
Сообщ.
#13
,
|
|
|
Цитата OpenGL @ Где почитать можно не знаю, а насчёт пяти точек - правильнее было сказать, что я просто нигде так и не нашёл упоминания о таком решении, в отличие от 3 точек. Для 4 и 2, решения тривиальны. При этом оба могут быть найдены из условия равновесия сил - есть такой «физический» способ решения - берём лист, в заданных точках сверлим отверстия, пропускаем через них невесомые верёвочки, связываем их над столом, к свободным концам привязываем одинаковые грузы. Если в отверстиях не будет трения, узел окажется над искомой точкой. Для 2, 3 и 4 точек получаем способ нахождения точки, а для 5 ответ получить уже не получается. А где про это почитать можно? |
Сообщ.
#14
,
|
|
|
Цитата OpenGL @ А где про это почитать можно? http://www.mccme.ru/free-books/mmmf-lectures/book.31.pdf |