[Dmitry_B 0]

А какой в этом смысл?

Это оправдано тогда и только тогда, когда у вас данные без шума (шум нулевой).

Это же относится к попыткам решить задачу аналитически.

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

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

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

ТС не говорил о природе исходных точек на плоскости. Возможно, это шум. Но это для решения задачи ничего не даёт, поскольку:

- статистические характеристики неизвестны;

- если даже они были бы известны - ТС уже задал критерий оптимизации (минимум СКО).

Численно решая (по какому алгоритму?) можно придти к несходящейся процедуре, да и решений может быть бесконечно много.

Для демонстрации последнего утверждения рассмотрим две точки. Какое количество эллипсов можно провести с нулевой ошибкой?... Что в подобном случае будет делать алгоритм?

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

[Major 0]

Я не виду основы для спора.

Для данных без шума тоже приходится искать решение, это наверное 90% вычислительных задач.

Забудьте про СКО. Минимум квадрата нормы (евклидовой) невязки. В нее может быть замешана мат статистика, а можно не мешать.

Смотрите на задачу с точки зрения функана.

 

Теперь по теме:

Пусть есть аналитический критерий существования. Вы применили его на хорошие данные с шумом и забраковали!

Решатель сможет найти псевдорешение.

Если решения не существует, то он вернет решение с границы области ОДЗ либо вернет ошибику что решение в ОДЗ не может быть найдено (но это совсем редко).

Проверьте численно вашу идею, и удивитесь сколько потенциальных решений вы отбросите если данные с шумом.

 

Определиться с областью сходимости - внести АПРИОРНУЮ информацию.

 

Для двух точек нормальный алгоритм автоматически вернет вернет решение z=0, решение с нулевой нормой, которое по определению должно входить в область определения оператора.

 

Гарантия глобального минимума в нелинейной задаче - это предмет исследования для каждой задачи. Это зависит от решателя и типа задач.

Цитировать Остапа Бендера или просто классические работы по этому поводу нет смысла.

 

Самое простое по статье сделать алгоритм (все описано, кроме глобальной сходимости) и сверять его со своим самописным.

Алгоритм общий, проблемы его общие и понятные.

Если автор по другому решит задачу и захочет обсудить, то тогда продолжим.

 

Если есть вопросы, то продолжать можно в личке, так как это уже не тема ЦОС.

 

[andrewn 0]

Цитируя (не дословно) древнекитайских философов, можно сказать, что дорога заблуждений широка, пряма и безопасна. Смело вперёд...

Изменено 25 сентября, 2012 пользователем AndrewN

[Pechka 1]

К чему такие споры? И так всем ясно, что раз уж эллипс имеет 5 параметров - значит необходимым условием является наличие как минимум 5 точек, чтобы решение было единственным, иначе по определению система уравнений будет иметь бесконечное множество решений. Что касается глобального минимума - нужно проверять, в численных методах обычно ищется как раз локальный минимум, а дальше, используется дополнительная информация чтобы доказать глобальность этого минмума.

 

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

 

Если по теме, то нашёл 2 метода:

1. пересчитывать точки в канонический базис текущего эллипса и в нём всё решать

http://www.geometrictools.com/Documentatio...aresFitting.pdf

2. Проводить из точки кратчайшее расстояние до эллипса и минимизировать квадрат этих расстояний.

http://ieeexplore.ieee.org/xpl/login.jsp?t...number%3D813057

 

К сожалениею, не имею полного доступа к материалам ссылки 2. Если у кого-нибудь есть - поделитесь плз. полным pdf.

 

Задача для случая когда оси симметрии эллипса параллельны осям или расположены произвольно?

Аналитически решаются оба случая.

Оси произвольно расположены.

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

[Major 0]

В книге которую я рекомендовал полистать (про кривые второго порядка) показано что для любого эллипса существует преобразование, которое переводит его в окружность.

Для каждого пробного эллипса переводить его в окружность.

После того как преобразование перехода вычислено, необходимо все точки на плоскости проецировать с помощь него.

После чего решать задачу для окружности. И так много раз, перебирая пробные эллипсы.

Надо только проверить можно ли невязку в проекции использовать для минимизации (монотонна она или нет).

Про обусловленность проектора пока сказать не могу.

 

Если отбросить возможную обусловленность, то может быть "This problem is more dicult than that of fitting circles" будет простой на каждом шаге.

На выходных попробую проверить корректность перехода для данных с шумом.

 

[fontp 0]

К сожалениею, не имею полного доступа к материалам ссылки 2. Если у кого-нибудь есть - поделитесь плз. полным pdf.

 

Sci-Hub представляет по ссылке вашу статью, забирайте, если успеете

 

sci-hub.org/pdfcache/79cab939b0b85e2f48f3e2ae8692a600.pdf

 

Что касается самой нелинейной оптимизации - конечно гарантии сходимости к глобальному минимуму быть не может.

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

а групповые по типу PSO или ещё более продвинутые "генетические" алгоритмы этого типа.

PSO совершенно элементарный алгоритм для реализации, но при грамотном задании области поиска 5-мерную задачу на современных компьютерах он успешно переберет с вероятностью почти 1.0

http://en.wikipedia.org/wiki/Particle_swarm_optimization

[Pechka 1]

Sci-Hub представляет по ссылке вашу статью, забирайте, если успеете

 

sci-hub.org/pdfcache/79cab939b0b85e2f48f3e2ae8692a600.pdf

Успел! Спасибо большое!

[andrewn 0]

К чему такие споры? И так всем ясно, что раз уж эллипс имеет 5 параметров - значит необходимым условием является наличие как минимум 5 точек, чтобы решение было единственным, иначе по определению система уравнений будет иметь бесконечное множество решений. Что касается глобального минимума - нужно проверять, в численных методах обычно ищется как раз локальный минимум, а дальше, используется дополнительная информация чтобы доказать глобальность этого минмума.

Я даже не буду оспаривать математическую "ценность" подобных измышлений...

 

Упростите для начала задачу. Представьте, что данные раньше измерялись с погрешностями sigma_1 и sigma_2 для координат x_1 и x_2, а после того, как в измерительную систему вселился гремлин, x_1 измеряется с погрешностью 0, а x_2 с погрешностью sigma_1 + sigma_2. Задайте аналитически произвольный эллипс. Внесите погрешности (исказите) в случайный набор точек на эллипсе. Найдите параметры "измеренного" эллипса по МНК, считая, что измерительная система населена гремлином.

 

Если полученное решение не слишком далеко от истинного (задайте метрику), то пользуйтесь упрощённой моделью.

 

Если решение "далеко", увеличьте количество измерений. Если и это не помогает, то пересмотрите модель - считайте честно овал ошибки.

 

 

 

[Alecsej 0]

Статью наврятли смогу привести, но суть в следующем:

% Генератор исходных данных
a = .8
b = 1.4
for i = 1:6
    t = (i-1)/6*2*pi;
    x(i) = a*cos(t) + 2;
    y(i) = b*sin(t) + 1;
end

XX = x.*x;
YY = -y.*y;
XY = -x.*y;
DATA = [ x' y' YY' XY' ones(1,length(x))'];
%LSQ X = (H'*H)^-1 * H * W
H = DATA' * DATA;
H = inv(H);
H = H * DATA';
X = H * XX';

AA = X(4)/2/X(3);

x0 = (X(1) - X(2)*AA)/(2-X(4)*AA)
y0 =  (-X(4)*x0 + X(2))/2/X(3)

A = X(5) + x0*x0 + X(3)*y0*y0 + X(4)*x0*y0 
B = A/X(3)
C = A/X(4)

a0 = sqrt(A)
b0 = sqrt(B)

%(x - x0)^2 / a^2 + (y - y0)^2 / b^2 + (x - x0)(y - y0)/c^2 = R^2

[Solitonuz 0]

Вашу задачу давным давно я решал следующим образом:

 

Эллипс на плоскости аппроксимируется алгебраической кривой заданной в неявной функцией.

Используем для этого уравнение второго порядка.

F(x,y)=a11*x^2 + a12*xy+ ...+a33 =0 (6)

где: aij = aji - коэффициенты соответствующей квадратичной формы с матрицей A:

Подставим в (6) измеренные координаты (xk,yk) и получим

F(xk,yk)=a11*xk^2 + a12*xkyk+ ... = dk

В случае малости расстояния от точки до эллипса, получаемая невязка δk также будет мала, что

позволяет определить ее как расстояние от точки (xk,yk) до кривой . Минимизируем

невязки для n точек методом наименьших квадратов:

Ф(aij) = SUM(dk^2) -> 0

для чего решим систему из шести уравнений:

dФ/daij = 0 для i,j,=1..3

Получаемую систему удобно записать в матричном виде:

Xu=0 (7) ,

где X – симметричная матрица, равная:

и вектор искомых коэффициентов

u=[a11,....a33]

Получившуюся систему можно решить численным методом. Найдем собственные значения для матрицы X любым из известных методов [3]. Минимальному собственному значению будет соответствовать собственный вектор , который и будет являться решением системы (7), т.е представлять набор коэффициентов эллипса.

 

Попробуйте например, с помощью Матлаба, это легко.