Аппроксимация прямой на плоскости

[ewert]

Задачка вполне практическая. Я там на другом форуме её засадил, однако народ разобрался в ней почему-то лишь процентов на шестьдесят. Ну, может тут кому удовольствие доставит.

Всё очень просто. Есть набор точек $\{\vec r_i\},\ i=1,2,\dots,n$ на плоскости. Надо провести между этими точками прямую $L$ оптимальным образом.

Конечно, надо предложить конкретный критерий оптимальности, т.е. некую целевую функцию $F(L)$. Пусть $\rho_i$ -- расстояние от точки $\vec r_i$ до прямой $L$. Предлагается три естественных варианта постановки задачи.

Задача 1:

$$F_1(L)\equiv\sum_i\rho_i=\min$$

.

Задача 2:

$$F_2(L)\equiv\sum_i\rho_i^2=\min$$

.

Задача 3:

$$F_{\infty}(L)\equiv\mathop{\max}\limits_i\rho_i=\min$$

.

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

[zoo]

ewert писал(а):

Задачка вполне практическая. Я там на другом форуме её засадил, однако народ разобрался в ней почему-то лишь процентов на шестьдесят. Ну, может тут кому удовольствие доставит.

Всё очень просто. Есть набор точек $\{\vec r_i\},\ i=1,2,\dots,n$ на плоскости. Надо провести между этими точками прямую $L$ оптимальным образом.

Конечно, надо предложить конкретный критерий оптимальности, т.е. некую целевую функцию $F(L)$. Пусть $\rho_i$ -- расстояние от точки $\vec r_i$ до прямой $L$. Предлагается три естественных варианта постановки задачи.

Задача 1:

$$F_1(L)\equiv\sum_i\rho_i=\min$$

.

Задача 2:

$$F_2(L)\equiv\sum_i\rho_i^2=\min$$

.

Задача 3:

$$F_{\infty}(L)\equiv\mathop{\max}\limits_i\rho_i=\min$$

.

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

Выражаясь Вашим языком, а в чем пафос то? Отнормировать уравнение прямой $Ax+By+C=0$ так что бы $A^2+B^2=1$ и искать условный экстремум кусочнолинейной функции в 1 и 3 задаче, про вторую и говорить как-то неудобно -- минимум квадратичной формы. Вы что ли программирование какое-нибудь ввиду имеете? На принципиальном уровне здесь второкурснику делать нечего.

[ewert]

zoo писал(а):

Выражаясь Вашим языком, а в чем пафос то? Отнормировать уравнение прямой $Ax+By+C=0$ так что бы $A^2+B^2=1$ и искать условный экстремум кусочнолинейной функции в 1 и 3 задаче, про вторую и говорить как-то неудобно.

В первой и третьей задаче $A^2+B^2=1$ к делу категорически не относятся -- ну нетути там никаких квадратов, да и решения совершенно иные. Во второй -- да, отчасти относятся, однако решения зачастую предлагаются совершенно неверные, что и любопытно.

[zoo]

ewert писал(а):

zoo писал(а):

Выражаясь Вашим языком, а в чем пафос то? Отнормировать уравнение прямой $Ax+By+C=0$ так что бы $A^2+B^2=1$ и искать условный экстремум кусочнолинейной функции в 1 и 3 задаче, про вторую и говорить как-то неудобно.

В первой и третьей задаче $A^2+B^2=1$ к делу категорически не относятся -- ну нетути там никаких квадратов, да и решения совершенно иные. Во второй -- да, отчасти относятся, однако решения зачастую предлагаются совершенно неверные, что и любопытно.

почему не относятся?
я буду пользоваться формулой
$\rho_i(A,B,C)= \frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}}$ $r_i=(x_i,y_i)$ эта формула упрощается, если считать, что $A^2+B^2=1$

[ewert]

zoo писал(а):

я буду пользоваться формулой
$\rho_i(A,B,C)= \frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}}$ $r_i=(x_i,y_i)$

Тыпс. С Вашей точки зрения, расстояние -- это вектор??!
И в любом случае: приведите конкретный алгоритм решения.

[zoo]

ewert писал(а):

zoo писал(а):

я буду пользоваться формулой
$\rho_i(A,B,C)= \frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}}$ $r_i=(x_i,y_i)$

Тыпс. С Вашей точки зрения, расстояние -- это вектор??!

так лучше:
$\rho_i(A,B,C)= \frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}},\quad r_i=(x_i,y_i)$
формула-то школьная

ewert писал(а):

И в любом случае: приведите конкретный алгоритм решения.

алгоритм минимизации функции
$f(A,B,C)=\sum_i {|Ax_i+By_i+C|$ при условии $A^2+B^2=1$?
ну берете раскрываете модули ...

[ewert]

zoo писал(а):

так лучше:
$\rho_i(A,B,C)= \frac{|Ax_i+By_i+C|}{\sqrt{A^2+B^2}},\quad r_i=(x_i,y_i)$
формула-то школьная

Да, школьная. Осталось только сообразить, к какой из трёх задач она приплетаема. Ибо

zoo писал(а):

$f(A,B,C)=\sum_i {|Ax_i+By_i+C|$ при условии $A^2+B^2=1$?
ну берете раскрываете модули ...

-- ну валяйте, раскрывайте... Ну вот я -- компутер: алгоритм-то -- где?? а ведь надо же хоть что-то считать...

-----------------------------------------------------------
ладно, чуть конкретнее. Вы, небось, на какой-нить там множитель Лагранжа глаз навострили? -- так напрасно. Ни фига не выйдет. В этой задаче.

[Алексей К.]

На близкую тему (плоскость фитировали в пространстве, не прямую в плоскости) мы с незваным гостьем полялякали здесь. Это касается именно минимизации суммы квадратов расстояний (т.е. задача 2). Может, будет интересно. По крайней мере, укоротить матрицу 3x3 до 2x2 труда не составит.

Добавлено спустя 16 минут 4 секунды:

ща офигел --- как это я попал в Олимпиадные задачи??? Т.е. когда-то, маленьким, был и 2-м по Украине, и первым в Киеве (это уже по химии) --- но сейчас??? Выяснилось, вина не моя. ewert, похоже, лопухнулся...

[ewert]

Алексей К. писал(а):

На близкую тему (плоскость фитировали в пространстве, не прямую в плоскости) мы с незваным гостьем полялякали здесь. Это касается именно минимизации суммы квадратов расстояний (т.е. задача 2).

Ага, вроде нашёл:

Цитата:

Задача с плоскостью (как и дополнительная к ней задача с пространственной прямой) решается довольно просто. Надо найти собственные векторы матрицы (пишу всё по памяти, надеюсь не ошибаюсь, когда-то сам всё это программировал)

$$ M= \left| \begin{array}{lll} \sum x_i^2 & \sum x_i y_i & \sum x_i z_i\\ \sum x_i y_i & \sum y_i^2 & \sum y_i z_i\\ \sum x_i z_i & \sum y_i z_i & \sum z_i^2 \end{array} \right| $$

(в системе центра тяжести). Ищутся они легко, особенно если программкой, а не формулой...
Собственные значения неотрицательны; соб. вектор, соответствующий максимальному с.з., даёт направление наилучшей МНК-прямой. Чтобы найти его, достаточно взять какое-то первое приближение $v_0$ и слегка поитерировать: $v_{i+1}=M v_i$.

Всё абсолютно верно (вплоть до возможности и фактической необходимости итерирований при $n>2$). Тогда полюбопытствуйте (в качестве одного из обещанных доп.вопросов), как всё это обобщается на случай точек произвольной размерности и линейных (в смысле аффинных) многообразий тоже произвольных размерностей.

Действительно, тема это не олимпиадная, а вполне стандартная, хотя и с неким подвохом: встречаются такие, кто с азартом пытается взять её обычным МНК, а напрасно.

Некоторый элемент олимпиадности всё же добавляют первая и третья задачки. Они просты, но решаются совсем по-другому.

[worm2]

Задача 2 известна в приложениях как RMA (Reduced Major Axis) regression.
Алгоритм очень простой [кроме вырожденных случаев, когда ещё проще ]: облако точек параллельным переносом и сжатиями по обеим осям масштабируется так, чтобы его центр тяжести совпал с началом координат, а дисперсии по обеим осям стали единичными. Если после этого ковариация положительна, искомая масштабированная прямая --- y=x, если отрицательна --- y=-x (при нулевой ковариации решение не единственно). Обратным масштабированием прямой получаем результат.

[ewert]

А для случая произвольных размерностей?

[worm2]

Обобщения на случай прозвольных размерностей я не встречал.

[ewert]

Алгоритм Алексея К. довольно очевидным образом обобщается.

И всё же: как с 1-й и 3-й задачками?

[worm2]

ewert писал(а):

Я там на другом форуме её засадил...

Подождите-подождите. На каком таком другом форуме?
Не на этом ли?

[ewert]

worm2 писал(а):

Подождите-подождите. На каком таком другом форуме?
Не на этом ли?

нет, там просто к слову пришлось, я уж и забыл