Есть набор точек на плоскости. Как лучше минимизировать следующий функционал :
SUM ( (Ri*sin(arg(R0)+arg(Ri))-abs(R0))^2 ) -> min
Здесь:
R0 - искомый вектор_
Ri - вектор из начала отчёта до i-ой точки
arg - полярный угло, abs - модуль вектора
^2 - квдрат
Здравствуйте, shvonder, Вы писали:
S>Есть набор точек на плоскости. Как лучше минимизировать следующий функционал : S>
S>SUM ( (Ri*sin(arg(R0)+arg(Ri))-abs(R0))^2 ) -> min
S>Здесь:
S>R0 - искомый вектор_
S>Ri - вектор из начала отчёта до i-ой точки
S>arg - полярный угло, abs - модуль вектора
S>^2 - квдрат
S>
S>Есть возможность выбрать начальное приближение R0
Раз есть синус, то скорее всего локальных минимов несколько, значит градиентные методы отпадают. Можно попробовать что-нибудь вроде генетических алгоритмов. Тем более там, если я правильно понял, всего два параметра, так что справиться они должны.
Здравствуйте, shvonder, Вы писали:
S>Есть набор точек на плоскости. Как лучше минимизировать следующий функционал : S>
S>SUM ( (Ri*sin(arg(R0)+arg(Ri))-abs(R0))^2 ) -> min
S>Здесь:
S>R0 - искомый вектор_
S>Ri - вектор из начала отчёта до i-ой точки
S>arg - полярный угло, abs - модуль вектора
S>^2 - квдрат
S>
S>Есть возможность выбрать начальное приближение R0
Если еще актуально:
Я так понимаю, что функция вместо Ri все таки abs(Ri)
Будем искать a=-arg(R0) r = abs (R0);
Тогда функция приобретает вид
SUM (abs(Ri)*sin (a-ai)-r)^2
При фиксированном a минимизировать несложно. Ri*sin (a-ai) — это проецирование на прямую, образующую угол b=a+pi/2 c осью абсцис. Минимум суммы квадратов расстояний достигается в центре тяжести. Должно быть r > 0. По этому если центр тяжести получился отрицательным, то минимум достигается в 0. Если это случилось, то при a=a+pi центр тяжести будет положительным и функция уменьшится.
Таким образом нужно нам нужно искать такой угол, при котором сумма отклонений проекций точек от проекции центра тяжести будет минимальной.
Пусть v-центор тяжести. Перенесем начало координат туда. Тогда координаты точек будут vi=Ri-v, а искомая функция
SUM (abs(vi)^2*cos (b-fi)^2)
где fi=arg(vi);
Исследовать на минимум нужно точки, где производная обращается в 0:
SUM (abs(vi)^2*sin (2b-2fi)) = 0;
Пусть ui = вектор, имеющий длину abs(vi)^2 и arg(ui)=2fi, тогда условие равенства нулю производной будет:
проекция центра тяжести векторов ui на прямую, образующую угол 2b+pi/2 с осью абсцисс совпадает с началом координат, или 2b — это аргумент центра тяжести векторов ui
Заранее подсчитав все суммы, получим простую функцию вида:
sin(arg(R0))^2 * A
+ sin(arg(R0)) * cos(arg(R0)) * B
+ cos(arg(R0))^2 * C
Очевидно, а отрезке [0, 2Pi] имеется не более двух минимумов (не более 4-х экстремумов).
Так что дифференциируем функцию по arg(R0) и ищем корни, например, мотодом Ньютона.
Первое слагаемое — сумма квадратов синусов (со сдвигами на разные углы и разными весовыми коэффициентами...)
Можно разложить на синусы и косинусы двойного угла. Но, в любом случае, эта функция имеет только два минимума (отстоящие друг от друга на Pi)
Второе слагаемое — имеет только один минимум.
Можно попытаться добить задачу аналитически (мне лениво, уж очень длинные формулы получаются).
Можно посчитать значение для ряда углов (скажем с шагом Pi/8), найти окрестности локальных минимумов и дальше любым методом поиска локального минимума.
(Например, методом золотого сечения.)
Или продифференцировать выражение и искать нули ...
Здравствуйте, ival, Вы писали: I>Я так понимаю, что функция вместо Ri все таки abs(Ri) I>Будем искать a=-arg(R0) r = abs (R0); I>Тогда функция приобретает вид I>
I>SUM (abs(Ri)*sin (a-ai)-r)^2
I>
Да, правильная формулировка такая:
SUM (ri*sin (a-ai)-r)^2-> min
где r = abs(R0),ri = abs(Ri), a = arg(R0),r = abs(R0)
Насколько я вас понял, вы предлагаете зафиксировать некоторую длину вектора a=abs(R0), и затем искать минимум по одной переменной — аргументу вектора, проходящего через эту точку. Или, что то же самое (если я правильно понял термин "центр тяжести" векторов) перенести начало отсчета в точку с координатами (x0,y0), равными арифметическому среднему проекций векторов одну ось X и Y несоответственно, и искать вектор проходящий через начало кординат по одной переменной — углу. Но проблема в том, среди точек могут встречаться плохие точки, и такое решение сведётся к итеративному процессу:
— задали начало координат,
— нашли угол
— задали веса точкам (от 0 для плохих, до 1 для хороших)
— новая итерация, пока не достигнут к.-л. критерий
Собственно, я хотел найти строгое решение для совершенно неизвестного вектора R0 = (abs(R0),arg(R0)).
Гениально!!!!!
Действительно, задача сводиться к одного переменного: либо угла, либо длины вектора.
После чего требуется чертовская аккуратность и десяток метров писчей бумаги
Там в задаче была миниошибка в знаке угла:
SUM{i,N}(Ri*sin(Fi-F0) — R)->min
где R = abs(r), F = arg(r), Ri = abs(ri), Fi = arg(ri), ri — даные вектора, r — искомый вектор
В итоге имеем:
(cos(F)^2)(SS-(S*S)/N) + (sin(F)^2)(CC-(C*C)/N) — 2sin(F)*cos(F)*(SC-(S*C)/N) -> min
где
SS = SUM{i,N}( Ri^2*(sin(Fi))^2 )
S = SUM{i,N} ( Ri * sin(Fi)) )
CC = SUM{i,N}( Ri^2*(cos(Fi))^2 )
C = SUM{i,N} ( Ri * cos(Fi)) )
SC = SUM{i,N}( Ri*Ri*sin(Fi)*cos(Fi))
Ещё не считал, но всё очень логично и очень похожи на известные формулы проведения прямой МНК по набору точек с известными абциссами.
Собственно, задача и заключалась в проведении прямой по набору точек на плоскости с минимизацией евклидовой нормы.
Спасибо, вам большущий респект
Здравствуйте, shvonder, Вы писали:
S>Там в задаче была миниошибка в знаке угла: S>SUM{i,N}(Ri*sin(Fi-F0) — R)->min S>где R = abs(r), F = arg(r), Ri = abs(ri), Fi = arg(ri), ri — даные вектора, r — искомый вектор
следует читать как: S>Там в задаче была миниошибка в знаке угла: S>SUM{i,N}(Ri*sin(Fi-F0) — R)^2->min
Здравствуйте, shvonder, Вы писали:
S>Насколько я вас понял, вы предлагаете зафиксировать некоторую длину вектора a=abs(R0), и затем искать минимум по одной переменной — аргументу вектора, проходящего через эту точку.
Да нет. Я привел некоторые соображения, асилив которые способ решения будет очевидным.
Под центром тяжести векторов {(xi, yi), i=1..n} имелось ввиду
1/n*sum ((xi, yi), i=1..n)
Способ решения такой:
Находим центр тяжести:
(x0, y0) = 1/n*sum((xi, yi), i=1..n))
Находим величину
(z1, z2) = 1/n*( sum (xi^2-yi^2, i=1..n), sum (2*xi*yi)) - (x0^2-y0^2, 2*x0*y0)
Если (z1, z2) = (0, 0) то все точки совпадают (что тогда делать наверняка Вам виднее по смыслу задачи)
Из комплексного числа z1+z2*sqrt (-1) нужно извлечь квадратный корень (нужно одно любое значение) Пусть это (p1, q1)
Для каждой из точек (p1, q1) (-q1, p1), нужно посчитать следующее:
(ui, vi) = (xi*p+yi*q)/(p^2+q^2) * (p, q)
(u0, v0) = (x0*p+y0*q)/(p^2+q^2) * (p, q)
d = sum ( (ui-u0)^2+(vi-v0)^2, i=1..n)
Там (p,q) = (p1, q1) или (-q1, p1).
Нужно выбрать те значения, при которых d будет минимально.
Тогда (v0, -u0) будет ответом (а d-значением целевой функции)
Задача вполне геометрическая (я рассуждал практически без бумаги
