2014 dxdy logo

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

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




На страницу 1, 2, 3  След.
 
 Минимизировать сумму расстояний
Сообщение02.01.2011, 16:27 
Аватара пользователя
Даны три точки на плоскости: $(1,9)$, $(2,14)$, $(3,20)$. Нужно найти уравнение прямой, сумма расстояний до которых имеет наименьшее значение.

Пусть $ax+by+c=0$ -- эта прямая. Тогда нам нужно найти минимум функции $f(a,b,c)=|a+9b+c|+|2a+14b+c|+|3a+20b+c|$ ($a,b\neq 0$). Если находить критические точки, приравнивая частные производные нулю, то получается система 3-х уравнений, содержащая штуки типа $\operatorname{sgn}(a+9b+c)$. Не представляю, как решать её. Может как-то проще можно?

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

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 16:39 
Эта прямая проходит через одну из этих точек.

Хм через две? :?:

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 16:41 
Аватара пользователя
Null, почему? Мне казалось, что прямая должна где-то между ними пройти.

(Оффтоп)

В учебнике есть параграф про псевдорешения СЛАУ, но там минимизируется сумма квадратов невязок СЛАУ (то есть метод наименьших квадратов), а мне нужно минимизировать сами расстояния.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 16:44 
А вы ее подвигайте параллельно себе.(тут лучше спроектировать все на нормаль к прямой)

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 16:57 
Аватара пользователя
М... всё равно не догоню. Если мы приближаем прямую к одной точке, то отодвигаем от других...
А то, о чем вы говорите, справедливо для любых трёх точек? (меня больше интересует как решать в общем случае)

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 16:59 
Приближаем к 2ум отдаляем от одной.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 17:08 
Аватара пользователя
А как нибудь без этих догадок можно решить?

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 17:37 
Прежде всего, ясно, что задача сводится к тому, чтобы загнать эти 3 точки в полосу наименьшей ширины. Отсюда уже вытекает, что один из краев такой полосы проходит через 2 точки, а второй через оставшуюся 3-ю. Надо перебрать 3 варианта и выбрать лучший. Тут весьма кстати будет формула для площади треугольника. Идея дифференцировать модули - крайне неудачная.

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 18:00 
Аватара пользователя
caxap в сообщении #394513 писал(а):
Тогда нам нужно найти минимум функции $f(a,b,c)=|a+9b+c|+|2a+14b+c|+|3a+20b+c|$

все-таки условный минимум... тут есть условие $a^2+b^2=1$

-- Вс янв 02, 2011 18:13:57 --

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


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

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

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 18:35 
Аватара пользователя
paha в сообщении #394559 писал(а):
тут есть условие $a^2+b^2=1$

Зачем? Если прямая $ax+by+c=0$, то $p(x,y)=|ax+bx+c|$ будет некоторой константой, умноженной на расстояние от прямой до точки $(x,y)$. Разве обязательно делать ту константу единицей?

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 18:45 
Не константой а зависеть от $a$ и $b$

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 18:49 
Аватара пользователя
caxap в сообщении #394573 писал(а):
Разве обязательно делать ту константу единицей?

подумайте)

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

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

неть)

вернее, сначала неть, а потом -- да... ищем уравнение прямой в нормальной форме

 
 
 
 Re: Минимизировать сумму расстояний
Сообщение02.01.2011, 19:14 
Аватара пользователя
paha в сообщении #394586 писал(а):
неть)

вернее, сначала неть, а потом -- да... ищем уравнение прямой в нормальной форме

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

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


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