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

[caxap]

ewert в сообщении #395030 писал(а):

И даже если заменить в Вашем исходном условии сумму расстояний на сумму квадратов расстояний -- всё равно это будет не задача на псевдорешения

Но ведь псевдорешение обеспечивает минимальную норму (евклидову) невязок, то есть для СЛАУ $x_1\vec a_1+\ldots+x_k\vec a_k=\vec b$ псевдорешение даёт минимальную $\|\vec b-(x_1\vec a_1+\ldots+x_k \vec a_k)\|^2=\sum\limits_{i=0}^k\left(b_i-(x_1 a_{1i}+\ldots+x_k a_{ki})\right)^2$. То есть, применительно к моей задаче, для прямой $y=cx+d$, СЛАУ будет $\{x+d=9;\ 2x+d=14;\ 3x+d=20\}$. Псевдорешение: $c=\frac {11}2$, $d=\frac{10}3$ (если я правильно посчитал), то есть прямая $y=\frac {11}2 x+\frac{10}3$ будет давать минимальную сумму квадратов расстояний до точек $(1,3)$, $(2,14)$, $(3,20)$.
Разве это не верно?

[мат-ламер]

ewert в сообщении #395030 писал(а):

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

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

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

Насчёт кусочной линейнойсти я поторопился. Скорее всего функция кусочно-гладкая. Но факт, что гладкость нарушается, когда прямая проходит через точки. Насчёт параметризации, то она может быть разная. Если рассуждать на словах, то она не нужна. А если автор темы хочет навести строгость, то пусть вводит параметризацию, как ему будет удобней. Как экзотический вариант, можно предположить, что прямая неподвижна, а двигаются точки. В этом случае задача действительно кусочно-линейна. Но тут осложнение, что это уже будет задача с ограничениями (а не на всём пространстве).

[caxap]

(Глупый вопрос)

Мне всегда было интересно, почему, когда хотят найти "линию тренда", чтобы уложить все экспериментальные точки на прямую (или другую функцию -- не важно), то минимизируют квадраты расстояний до точек, а не сами расстояния или их, скажем, 4-ю степень? То есть почему именно квадраты? (Может тупо из-за того, что квадраты минимизировать легче всего?)

[мат-ламер]

Ответ на вопрос сахара. Если ошибки распределены нормально, то метод максимального правдоподобия приводит к методу наименьших квадратов, который использовал ещё Гаусс. В других случаях можно использовать и другие функции вместо квадратичной. Например, если надо, чтобы максимальное отклонение было минимальным (чебышевская аппроксимация), то можно минимизировать сумму каких-то больших степеней (четвёртых, восьмых,...). В пределе получим то, что нужно.

[paha]

caxap

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

ошибки распределены нормально

!

[caxap]

Ясно!

[ewert]

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

То есть, применительно к моей задаче, для прямой $y=cx+d$, СЛАУ будет $\{x+d=9;\ 2x+d=14;\ 3x+d=20\}$.

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

[caxap]

ewert в сообщении #395479 писал(а):

Это Вы пытаетесь минимизировать расстояния по вертикали

Аа... А из чего это видно? Что-то в учебнике об этом не написано, а из формулок я тоже не вижу
А вы можете написать, какое будет уравнение для прямой, если минимизировать "по нормали"? Чтобы сравнить можно было с моим. (И можно ли решить задачу минимизации (квадратов) "по нормали" методами линейной алгебры)?

[ewert]

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

Аа... А из чего это видно? Что-то в учебнике об этом не написано, а из формулок я тоже не вижу

Из условия:

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

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

Если сказано просто "расстояние до прямой", то это означает именно расстояние по нормали.

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

А вы можете написать, какое будет уравнение для прямой, если минимизировать "по нормали"?

Конкретное уравнение лень, а искать его надо так. Прямая должна проходить через центр масс, нормальным же вектором к ней будет собственный вектор матрицы $\begin{pmatrix}\sum x_k^2 & \sum x_ky_k \\ \sum y_kx_k & \sum y_k^2\end{pmatrix}$, отвечающий наименьшему собственному числу. Как видите, ничего общего с МНК (не считая того, что через центр масс она в обеих постановках задачи проходит).

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

[caxap]

ewert в сообщении #395519 писал(а):

Из условия:

Не, я уже не исходное условие рассматриваю. В условии требуется найти такую прямую, чтобы сумма расстояний до всех точек была минимальна. Я же хочу найти такую прямую, чтобы сумма квадратов расстояний до всех точек была минимальна (то есть мы имеем экспериментальные точки и нам нужна "линия тренда". Как сказали мат-ламер и paha, если ошибки распределны нормально (а так оно и есть), то надо использовать МНК). Прямая $y=\frac {11}2x+\frac {10}3$ такой не будет? Если нет, то почему?

[ewert]

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

Я же хочу найти такую прямую, чтобы сумма квадратов расстояний до всех точек была минимальна (то есть мы имеем экспериментальные точки и нам нужна "линия тренда"

Это две разные задачи. Когда говорят о "линии тренда" -- имеют в виду, что пары чисел $(x_k,y_k)$ отвечают некоторой экспериментальной зависимости $y(x)$, которую мы приближаем линейной функцией $y(x)\approx kx+b$; тогда нужен действительно МНК, а то, что эти пары чисел задают ещё и точки на плоскости -- всего лишь некоторая условность. Если же речь именно о точках как геометрических объектах, то тут, напротив, условностью являются координатные оси, и минимизировать надо расстояния именно по нормали.

Различие между этими задачами проявляется, в частности, и в том, что у них разные инварианты. Если минимизируются расстояния по вертикали, то решение инвариантно относительно растяжений по любой из осей (в том смысле, что прямая растягивается ровно так же), но не инвариантно относительно поворотов картинки. Если минимизируются расстояния по нормали, то всё в точности наоборот.

[caxap]

Всё, дошло!