Нахождение окружности методом наименьших квадратов

Raux

Дан набор точек на плоскости. Найти методом наименьших квадратов "проходящую через них" окружность. Подскажите плиз.

griz_a

Пусть векторы [math]$a_i=(x_i, y_i)$[/math] - данные.
Нам надо найти вектор [math]$a=(x,y)$[/math] и радиус R: сумма квадратов расстояний до этой окружности наименьшая.
[math]$\sum_{i=1}^{n} (||a_i-a||-R)^2=\sum_{i=1}^{n} a_i-a, a_i-a)+R^2-2R\sqrt{(a_i-a,a_i-a)})$[/math]
Это надо минимизировать по a и R
Дифференцируем по x, y, R
[math]$\sum_{i=1}^{n}2(x-x_i)-2R\sum_{i=1}^{n} \frac{2(x-x_i)}{\sqrt{(a_i-a,a_i-a)}}=0$[/math]
[math]$\sum_{i=1}^{n}2(y-y_i)-2R\sum_{i=1}^{n} \frac{2(y-x_i)}{\sqrt{(a_i-a,a_i-a)}}=0$[/math]
[math]$2Rn-2\sum_{i=1}^{n} \sqrt{(a_i-a,a_i-a)}=0$[/math]
Ну, собственно, аналитически, афаик эту задачу дальше не решают, решают численно

Raux

Это понятно. Я думал может есть какое другое решение. В духе линала так сказать. Чтоб ничего не дифференцировать, а "сказать умные слова" о перпендикулярности чего-то чему-то и использовать скалярное произведение. Ну может еще метод гаусса потом.
Как например в случае для прямой.

kachokslava

МНК подразумевает дифференцирование!

griz_a

я же объяснил - аналитически не решают задачу.

Brina

А если попробовать представить окружность в полярных координатах? Тогда это сводится к аппроксимации МНК точек константой, находим радиус. Это, вестимо, имеет аналитическое решение. Вот, кажется, и все.

griz_a

А если попробовать представить окружность в полярных координатах? Тогда это сводится к аппроксимации МНК точек константой, находим радиус. Это, вестимо, имеет аналитическое решение. Вот, кажется, и все.

Ага, если вдруг у искомой окружности центр в 0, то всего-то

aldo63

в свое время предлагались какие-то туманные идеи насчет инверсии:

griz_a

инверсию в одной из точек если сделать, а потом построить мнк-оценку для прямой, а потом инверсию назад, то получится оценка. Не МНК, но не очень плохая вроде, если радиус брать как среднее расстояние от центра до других точек. Единственное, надо чтобы отношение максимального и минимального расстояний до центра не было большим

Perce

Ух, бл… инверсию тут уже предлагают для приближённого решения.
Если бы мне на практике такую задачу поставили, то я бы не парился, и за "расстояние" от точки (x,y) до окружности с центром в (x_0, y_0) и радиусом r взял бы величину:
[math]$|(x-x_0)^2 + (y-y_0)^2 - r^2|$[/math]
Да, это не честное расстояние, но с ним работать на практике гораздо удобнее :grin:
После чего задача сводится к стандартному МНК:
[math]$$A = \left( \begin{array}{ccc} 1 & x_1 & y_1 \\ 1 & x_2 & y_2 \\ … & … & … \\ 1 & x_n & y_n \end{array} \right  b =  \left( \begin{array}{c}x_1^2+y_1^2\\x_2^2+y_2^2\\…\\x_n^2+y_n^2\end{array} \right)$$[/math]
Решаем систему уравнений 3×3: [math]$A^T A z = A^T b$[/math]
[math]$$z =  \left( \begin{array}{c}\alpha\\\beta\\\gamma\end{array} \right\\ x_0 = \beta/2, y_0 = \gamma/2$$[/math]
Центр будет в точке (x_0, y_0 ну и радиус там тоже вычисляется из этих данных.

luherstag

А как ты тут поборолся с модулем?

Perce

Будем искать окружность в виде [math]$x^2+y^2-\alpha-\beta x - \gamma y = 0$[/math].
Если бы наши точки лежали на этой окружности, то мы получили бы систему:
[math]$$\alpha + \beta x_k + \gamma y_k = x_k^2 + y_k^2, \quad k=1…n$$[/math]
Из которой нашли бы потом неизвестные коэффициенты в уравнении окружности. Но вот беда, система у нас скорее всего будет несовместна, поэтому будем лишь минимизировать длину вектора невязки. Заметим, что вектор невязки у нас как раз состоит из наших новых "расстояний", только со знаками, но на них пофиг, они ведь потом в квадрат возведутся, и пропадут (вот здесь модуль и пропадает). Ну а далее стандартный подход решения такой задачи на практике – домножаем на сопряжённую матрицу, и решаем. Дальше из полученного уравнения вытаскиваем центр и радиус.
PS. Если чо, это просто тупой подход математика-вычислителя, который все теоремы позабыл нафиг, и которому лениво что-либо проверять и доказывать. Единственное, что он умеет, сводить задачу к стандартной типовой, которую он уже знает как решать на практике. Так что не бейте меня сильно :grin:

griz_a

То, что ты написал минимизирует по сути не сумму квадратов отклонений, а сумму модулей. Соответственно, это заметно другая оценка чем мнк

Perce

Вполне возможно ;)

lenmas

То, что ты написал минимизирует по сути не сумму квадратов отклонений, а сумму модулей. Соответственно, это заметно другая оценка чем мнк
В принципе сойдет и так.

lenmas

Вполне возможно ;)
Ты систему-то свою решал аналитически? Или численно имеется в виду?

griz_a

Это у ридера нужно спрашивать :)
Вообще минимизация квадратичного риска и минимизация абсолютного риска могут заметно отличаться. Ответ довольно сильно сносит иногда.

griz_a

а какие проблемы с решением линейной системы?

lenmas

Ну тут видишь какие траблы. Хоть так свели к линейной системе.

lenmas

а какие проблемы с решением линейной системы?
Написать аналитическое решение, или понять где центр окружности при таком способе минимизации.

Perce

Ну уж систему уравнений 3x3 решить можно и аналитически, и численно. Кому как нравится.
Оставить комментарий
Имя или ник:
Комментарий: