Минимизировать сумму расстояний

[caxap]

"Неть" -- это по отношению к $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$). Только псевдорешения дают минимальные квадраты невязок, а мне нужны минимумы модулей невязок?

[paha]

Mathusic в сообщении #394588 писал(а):

Что-то я не понял. ТС же изначально ищет минимум для прямой в нормальной форме (пост #1). И все с этим соглашаются, вроде бы

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

-- Вс янв 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 писал(а):
А вы ее подвигайте параллельно себе.(тут лучше спроектировать все на нормаль к прямой)


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

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

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

[Mathusic]

(Оффтоп)

paha в сообщении #394590 писал(а):

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

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

[paha]

(Оффтоп)

Mathusic в сообщении #394592 писал(а):

Я подумал, все подумали, автор подразумевает норм. вид...

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

[Mathusic]

(Оффтоп)

paha в сообщении #394593 писал(а):

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

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

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

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

P. S. Задачка по линейной алгебре.

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

[caxap]

Mathusic в сообщении #394605 писал(а):

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

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

[Mathusic]

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

возможно здесь вторая и на самом деле нужно минимизировать не сами расстояние, а их квадраты. Тогда всё легко.

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

[paha]

Mathusic в сообщении #394610 писал(а):

А дальше..?

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

[Mathusic]

paha в сообщении #394614 писал(а):

Mathusic в сообщении #394610 писал(а):

А дальше..?

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

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

[paha]

Mathusic в сообщении #394616 писал(а):

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

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

[Алексей К.]

Чё-то на ерунду похожее написал. Удаляю. Подумать надо.

[Mathusic]

paha в сообщении #394623 писал(а):

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

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

[vvvv]

Прямая проходит через первую и третью точки.При этом искомая сумма равна 0.089

[мат-ламер]

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

[ewert]

paha в сообщении #394590 писал(а):

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

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

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

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

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

мат-ламер в сообщении #394979 писал(а):

Интуитивно кажется, что минимизируемая функция кусочно-линейная

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