2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 19:17 
Аватара пользователя
"Неть" -- это по отношению к $f(a,b,c)=\sqrt{a^2+b^2}\cdot(\text{сумма расстояний до всех точек})$?
paha в сообщении #394586 писал(а):
ищем уравнение прямой в нормальной форме

А что изменится, если мы зафиксируем $\sqrt{a^2+b^2}$ не на 1, а на 2? Просто $|ax+by+c|$ будет давать вдвое большое расстояние, но ведь это будет во всех слагаемых и получим $f(a,b,c)=2\cdot(\text{сумма расстояний до всех точек})$. На минимум 2-ка (или другая константа) не влияет.

Ну я так и не понял, можно ли решить задачу без всяких догадок типа
Null в сообщении #394519 писал(а):
Эта прямая проходит через одну из этих точек.

paha в сообщении #394559 писал(а):
прямая -- та, которая содержит наибольшую сторону

которые мне не кажутся очевидными. Задача эта по линейной алгебре. Может быть возможно как-нибудь её связать с псевдорешениями СЛАУ (то есть когда СЛАУ $Ax=b$ заменяется на СЛАУ $Ax=b_{\parallel}$ (или $A^{\mathsf T}Ax=A^{\mathsf T}b$), где $b_{\parallel}$ -- ортогональная проекция $b$ на линейную оболочку векторов, составляющих столбы $A$). Только псевдорешения дают минимальные квадраты невязок, а мне нужны минимумы модулей невязок?

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 19:17 
Аватара пользователя
Mathusic в сообщении #394588 писал(а):
Что-то я не понял. ТС же изначально ищет минимум для прямой в нормальной форме (пост #1). И все с этим соглашаются, вроде бы :shock:

я перечел первый пост... о нормальной форме -- ни КАПЛИ!

-- Вс янв 02, 2011 19:20:45 --

caxap в сообщении #394585 писал(а):

Появился: 07/01/10
Сообщения: 906
А... вроде понял, у нас получается $f(a,b,c)=\sqrt{a^2+b^2}\cdot(\text{сумма расстояний до всех точек})$, поэтому нам нужно зафиксировать $\sqrt{a^2+b^2}$. В частности на $1$.

да... я просто не понял, что у Вас \mbox стоит...


вот же правильный способ решения и ответ:
paha в сообщении #394559 писал(а):
-- Вс янв 02, 2011 18:13:57 --

Null в сообщении #394528 писал(а):
А вы ее подвигайте параллельно себе.(тут лучше спроектировать все на нормаль к прямой)


Мне кажется, искомое число равно наименьшей высоте треугольника

Соответственно, прямая -- та, которая содержит наибольшую сторону


просто фиксируйте направление и двигайте прямую... а потом -- меняйте направление:)))

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 19:28 
Аватара пользователя

(Оффтоп)

paha в сообщении #394590 писал(а):
я перечел первый пост... о нормальной форме -- ни КАПЛИ!

А почему тогда никто не предъявил претензий, мол прямая одна, а функция не такая и о нормальности ни слова? Я подумал, все подумали, автор подразумевает норм. вид... :roll:

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 19:29 
Аватара пользователя

(Оффтоп)

Mathusic в сообщении #394592 писал(а):
Я подумал, все подумали, автор подразумевает норм. вид...

ну... бывает... И -- не говорите за всех))

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 20:02 
Аватара пользователя

(Оффтоп)

paha в сообщении #394593 писал(а):
ну... бывает... И -- не говорите за всех))

Говорить за всех не буду, но вот что-то подумать, пускай и неверное, про всех, вроде не криминал.


-- Вс янв 02, 2011 21:05:44 --

caxap в сообщении #394513 писал(а):
P. S. Задачка по линейной алгебре.

Это значит, что задача из сборника/учебника по линалгебре? Вы в таком случае название не подскажете (интересно, что за теория идёт до)?

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 20:12 
Аватара пользователя
Mathusic в сообщении #394605 писал(а):
Это значит, что задача из сборника/учебника по линалгебре? Вы в таком случае название не подскажете (интересно, что за теория идёт до)?

Канатников, Крищенко -- Линейная алгебра. Я уже говорил, что идёт до, издалека похожее на задачу -- псевдорешения СЛАУ. Я уже встречал в книге одну опечатку, возможно здесь вторая и на самом деле нужно минимизировать не сами расстояние, а их квадраты. Тогда всё легко.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 20:30 
Аватара пользователя
caxap в сообщении #394608 писал(а):
возможно здесь вторая и на самом деле нужно минимизировать не сами расстояние, а их квадраты. Тогда всё легко.

Неквадраты интереснее :-)
Хочется увидеть чисто геометрическое (ну или почти) решение. Понятно, как доказать, что прямая должна проходить через одну т-ку хотя бы. А дальше..?

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 20:37 
Аватара пользователя
Mathusic в сообщении #394610 писал(а):
А дальше..?

так рецепт дан... ответ: прямая, содержащая наибольшую сторону

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 20:43 
Аватара пользователя
paha в сообщении #394614 писал(а):
Mathusic в сообщении #394610 писал(а):
А дальше..?

так рецепт дан... ответ: прямая, содержащая наибольшую сторону

Это с "фиксацией"? Я только вижу только как д-ть, что через одну проходит т-ку.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 21:22 
Аватара пользователя
Mathusic в сообщении #394616 писал(а):
Это с "фиксацией"? Я только вижу только как д-ть, что через одну проходит т-ку.

и так для каждого направления

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 21:26 
Чё-то на ерунду похожее написал. Удаляю. Подумать надо.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 21:40 
Аватара пользователя
paha в сообщении #394623 писал(а):
и так для каждого направления

Ну, я так и делал.
Сейчас понятно, - доказываем сначала, что направление должно быть параллельно стороне.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 23:18 
Прямая проходит через первую и третью точки.При этом искомая сумма равна 0.089

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение03.01.2011, 21:58 
Аватара пользователя
функция из первого поста - это не то расстояние, которое нужно минимизировать. Причём тут линейная алегебра - непонятно. Интуитивно кажется, что минимизируемая функция кусочно-линейная, и градиент её не существует, если прямая проходит через две из трёх точек. Для кусочно-линейной задачи минимум должен быть в точке, где градиент не существует (т.е. прямая проходит через какие две точки из трёх). По трём точкам рисуем треугольник и смотрим, которая из трёх высот меньше. Эта высота и задаёт минимум суммы расстояний.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение04.01.2011, 00:47 
paha в сообщении #394590 писал(а):
просто фиксируйте направление и двигайте прямую... а потом -- меняйте направление:)))

Лучше без параллельных переносов, иначе теряется "локальная единственность" решения. Лучше сразу вращать: если проходит хоть через одну из точек, то вокруг этой точки, а если не проходит ни через одну точку, то вокруг любой фиксированной. И доказывать тем самым, что прямая, не проходящая через хотя бы две точки, заведомо неоптимальна. Это легко (через проекции на нормаль к прямой), причём независимо от количества точек.

caxap в сообщении #394589 писал(а):
Может быть возможно как-нибудь её связать с псевдорешениями СЛАУ (то есть когда СЛАУ $Ax=b$ заменяется на СЛАУ $Ax=b_{\parallel}$ (или $A^{\mathsf T}Ax=A^{\mathsf T}b$), где $b_{\parallel}$ -- ортогональная проекция $b$ на линейную оболочку векторов, составляющих столбы $A$). Только псевдорешения дают минимальные квадраты невязок, а мне нужны минимумы модулей невязок?

Эта задача не на псевдорешения и вообще не на СЛАУ. И даже если заменить в Вашем исходном условии сумму расстояний на сумму квадратов расстояний -- всё равно это будет не задача на псевдорешения, это существенно более сложная задача (даже сложнее, чем для суммы просто расстояний).

мат-ламер в сообщении #394979 писал(а):
Интуитивно кажется, что минимизируемая функция кусочно-линейная

Это как-то уж слишком интуитивно. Принципиальный вопрос: минимизируемая функция -- это функция чего?...

 
 
 [ Сообщений: 42 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group