Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Система квадратных уравнений. (2 стр)

Система квадратных уравнений. (2 стр)

Поделиться

Страницы: 1 2 3 4 Следующая

thevladПостоялецwww21 окт. 201715:37#15
Suslik
в общем какой шажок можно сделать, заменить на:

      [ n_0 ] 
M=  [ ...    ]
      [ n_N-1]
      [ n_N  ]

A =  [ a _0  0  ...    ]
        [ 0  a_1  ..    ]
        [....  ....  ...      ]
        [ 0  0      ... a_N ]

trace((M_i*A)^T*(M_i*A)) = trace(G_i^T*G_i) = k_i

в таком виде это будет по сути dot product https://en.wikipedia.org/wiki/Trace_(linear_algebra)
получится в каком-то смысле линейная система, надо только поискать в литературе как это решается
еще интересное свойство, что trace равняется сумме собственных значений
если попробовать, все это как-то связать вместе, может что-то получится...

Правка: 21 окт. 2017 16:24

thevladПостоялецwww21 окт. 201717:06#16
Suslik
продолжение
trace(A^T*M_i^T*M_i*A) = 0 применяем cyclic property получаем
trace(M_i^T*M_i*A*A^T) = 0 так как матрица диагональная то A^T=A
trace((M_i^T*M_i)*(A^2)) = 0

trace(Q) = 0 эквивалентно тому, что сумма собственных значений Q = 0

дальше такая связь trace(XY) -> bilinear form B(X, Y)

PS:
похоже нашел нужные кейворды, "system of bilinear equations"
посмотри: http://publish.wm.edu/cgi/viewcontent.cgi?article=1424&context=honorstheses

PSS: нужная там матрица A получается тривиально, (M_i*X)^T*(M_i*X) = X^T*(M_i^T*M_i)*X

Правка: 21 окт. 2017 18:34

thevladПостоялецwww21 окт. 201720:50#17
Suslik
в общем в твоем, более частном случаи - x^T*A*x совсем просто получается, решаем линейную систему к которой сводится билинейная, и тупо берем корень из диагональных элементов, никакая rank-1 factorization нам не нужна.
SuslikМодераторwww22 окт. 20175:55#18
thevlad
ЯННП, что за элементы а? как система из #15 связана с системой из #0? какое отношение к моей задаче имеют билинейные системы, у если у меня вектор неизвестных всего один?
ZegalurПостоялецwww22 окт. 201710:04#19
+ Показать
SuslikМодераторwww22 окт. 201710:20#20
Zegalur
сама идея — линейным преобразованием лямбд перейти к чему-то, что можно решить легко, мне очень нравится. но в деталях реализации я что-то не понимаю.

вот с этого момента начинается что-то странное:
Изображение

ты рассматриваешь одно уравнение системы или уже всю систему вместе взятую? в каждом уравнении все вектора — обычные трёхкомпонентные трёхмерные вектора. [cht]N[/cht] — произвольно большое число, около сотни на практике. поэтому вектор [cht]v[/cht] в каждом уравнении по идее тоже трёхкомпонетный и таких векторов всего [cht]N[/cht]. как именно ты предлагаешь преобразовать лямбды, чтобы что-то упростилось?

ZegalurПостоялецwww22 окт. 201712:32#21
+ Показать

Правка: 22 окт. 2017 12:49

ZegalurПостоялецwww22 окт. 201712:38#22
а все, я не так понял.
я только уравнение [cht](\vec{m}+\sum_{i=1}^N \vec{n}_i \lambda_i)^2=k^2[/cht] решаю.. а их там дальше N ..
кароче тот ответ неверный :)

MrShoor
> Да, я чушь написал, ибо это независимые уравнения. Просто я подумал что ты как
> то верхнее уравнение превратил в систему ниже. А ты просто масштабировал это
> уравнение на N разных уравнений.
так само подумал

Правка: 22 окт. 2017 12:51

thevladПостоялецwww22 окт. 201713:46#23
Suslik
> ЯННП, что за элементы а? как система из #15 связана с системой из #0? какое
> отношение к моей задаче имеют билинейные системы, у если у меня вектор
> неизвестных всего один?
из #15 это были промежуточные размышления.
то что тебе нужно это билинейные системы, твой случай просто более частный, по крайней мере это то что мне удалось найти из известной математики, там есть хоть какая-то теория от которой можно оттолкнуться.
можно на простом примере показать, как это работает:
            [ n1 ]
M_i =  [ n2 ]
          [  m ]

(M_i*X)^T*(M_i*X) = X^T*(M_i^T*M_i)*X

                            [ a_1_0 ]
A_i = M_i^T*M_i = [ a_2_0 ]
                            [ a_3_0 ]
X = [x1, x2, 1]
                                        [ a_1_0 a_1_1 a_1_2 ]    [ x1 ]                            [x1*a_1_0 + x2*a_1_1 + 1*a_1_2]   
X^T*A_i*X = [x1, x2, 1] x [ a_2_0 a_2_1 a_2_2 ] x  [ x2 ]  =  [x1, x2, 1]  x  [x1*a_2_0 + x2*a_2_1 + 1*a_2_2] = x1*(x1*a_1_0 + x2*a_1_1 + 1*a_1_2) + x2*(x1*a_2_0 + x2*a_2_1 + 1*a_2_2) + 1*(x1*a_3_0      + x2*a_3_1      + a_3_2) =
                                        [ a_3_0 a_3_1 a_3_2  ]    [  1  ]                          [x1*a_3_0  + x2*a_3_1 + 1*a_3_2]

= x1*x1*a_1_0 + x1*x2*a_1_1 + x1*a_1_2 + x2*x1*a_2_0 + x2*x2*a_2_1 + x2*a_2_2 + x1*a_3_0  + x2*a_3_1  + a_3_2
теперь мы можем перейти к линейной системе относительно комбинации членов X то есть
для единичного уравнения получаем

x1*x1*a_1_0 + x1*x2*a_1_1 + x1*a_1_2 + x2*x1*a_2_0 + x2*x2*a_2_1 + x2*a_2_2 + x1*a_3_0  + x2*a_3_1  + a_3_2

x1*x1*a_1_0 + x1*x2*(a_1_1 + a_2_0) + x2*x2*a_2_1 + x1*(a_1_2 + a_3_0)  + x2*(a_2_2 + a_3_1) + a_3_2

                                                                                                        [ x1*x1]
                                                                                                        [ x1*x2]
[a_1_0, a_1_1+a_2_0, a_2_1, a_1_2+a_3_0, a_2_2 + a_3_1, a_3_2] x[ x2*x2] = k
                                                                                                        [ x1    ]
                                                                                                        [ x2    ]
                                                                                                        [ 1      ]
дальше тупо добиваем до систему

                                                                                                                        [ x1*x1]
[a0_1_0, a0_1_1+a0_2_0, a0_2_1, a0_1_2+a0_3_0, a0_2_2 + a0_3_1, a0_3_2]  [ x1*x2]    [k0]
[a1_1_0, a1_1_1+a1_2_0, a1_2_1, a1_1_2+a1_3_0, a1_2_2 + a1_3_1, a1_3_2] x[ x2*x2] = [k1]
[a2_1_0, a2_1_1+a2_2_0, a2_2_1, a2_1_2+a2_3_0, a2_2_2 + a2_3_1, a2_3_2]  [ x1    ]    [k3]
                                                                                                                          [ x2    ]
                                                                                                                          [ 1      ]
         

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

PS: сорри за аски-арт, TeX не знаю :(

Правка: 22 окт. 2017 14:00

SuslikМодераторwww22 окт. 201713:46#24
так, последние рассуждения меня навели на мысли. без ограничения общности эту систему:
[cht]
\left\{\begin{matrix}
(\vec m_1 + \sum_{i=1}^N\vec n_{1i} \lambda_i)^2=k_1^2 \\ 
\dots \\
(\vec m_N + \sum_{i=1}^N\vec n_{Ni} \lambda_i)^2=k_N^2 \\ 
\end{matrix}\right.
[/cht]
можно упростить, просто разделив каждое уравнение на [cht]k_i^2[/cht] и переименовав [cht]\vec m^*_j=\frac{\vec m_j}{k}[/cht][cht]\vec n^*_i=\frac{\vec n_i}{k}[/cht]:

[cht]

\left\{\begin{matrix}
(\vec m^*_1 + \sum_{i=1}^N\vec n^*_{1i} \lambda_i)^2=1 \\ 
\dots \\
(\vec m^*_N + \sum_{i=1}^N\vec n^*_{Ni} \lambda_i)^2=1 \\ 
\end{matrix}\right.
[/cht]

а теперь финт ушами. сделаем переход [cht]\lambda^*_i = \lambda_i+c_i[/cht] таким образом, чтоб [cht]\sum_{i=1}^N\vec n*_{ji}c_i=-\vec m^*_j[/cht] [UPD: тут баг, система из 3N уравнений и N неизвестных, так нельзя .____.] (просто решить линейную систему) тогда ведь вуаля:

[cht]

\left\{\begin{matrix}
(\sum_{i=1}^N\vec n^*_{1i} \lambda^*_i)^2=1 \\ 
\dots \\
(\sum_{i=1}^N\vec n^*_{Ni} \lambda^*_i)^2=1 \\ 
\end{matrix}\right.
[/cht]
а это ведь уже — пересечение концентрических эллипсоидов! то есть теоретически выглядит более осязаемо. мне кажется, для начала было бы полезным найти хотя бы общий радиус всех таких эллипсоидов в точке общего пересечения. разумеется, у меня нет никаких идей, как это сделать :D можно даже привести к виду просто системы квадратичных форм:

[cht]

\left\{\begin{matrix}
\lambda^TA_1\lambda=1 \\
\dots \\
\lambda^TA_N\lambda=1
\end{matrix}\right.

[/cht]

где [cht]\lambda[/cht] понимается вектор-столбец неизвестных. и по запросу "quadratic form system" уже можно даже что-то найти! http://www.numdam.org/article/MSMF_1979__59__115_0.pdf только внутри — какой-то ад :( задача NP-полная, лол. ну бог с ним, я согласен даже на экспоненциальное время решения, если это нужно.

Правка: 22 окт. 2017 14:26

SuslikМодераторwww22 окт. 201713:52#25
thevlad
> да наша линейная система получается
я, вроде, понял, о чём ты говоришь, но такая система получается недоопределённая. то есть у неё решений будет — целое линейное пространство. и чтобы её разрешить, нужно пользоваться тем свойством, что неизвестные в такой системы вовсе не независимы, а являются комбинациями реальных неизвестных, которых в твоём случае всего 3.
thevladПостоялецwww22 окт. 201714:05#26
Suslik
>я, вроде, понял, о чём ты говоришь, но такая система получается недоопределённая. то есть у неё решений будет — целое линейное пространство.
да и конкретно, по кейворду "system of bilinear equations" можно найти теорию, где это более менее обсуждается, так как в большинстве случаев y^T*A*x, тоже получается неопределенной, я думаю может помочь...
SuslikМодераторwww22 окт. 201714:57#27
у меня все выходные прошли под знаменем генерирования нерабочих идей. ещё одна?:

положим что пространство не трёхмерное, а для начала хотя бы двумерное. тогда каждый вектор [cht]\vec n_{ji}[/cht] можно разложить в сумму двух векторов, один из которых перпендикулярен [cht]\vec m_j[/cht], а второй — параллелен: [cht]\vec n_{ij}={\vec n_{ij}}\limits^\perp + {\vec n_{ij}}\limits^\parallel[/cht] тогда от геометрических векторов можно перейти к скалярам. для этого подставим:
[cht]
((\vec m^_j + \sum_{i=1}^N{\vec n_{ji}}\limits^\parallel \lambda_i)+(\sum_{i=1}^N{\vec n_{ji}}\limits^\perp \lambda_i))^2=1 \\ 
[/cht]
и, воспользовавшись тем, что выражения в скобках перпендикулярны друг другу, перейдём к скалярам, где векторами без стрелочек обозначены их модули:
[cht]
(m^_j + \sum_{i=1}^N{n_{ji}}\limits^\parallel \lambda_i)^2+(\sum_{i=1}^N{n_{ji}}\limits^\perp \lambda_i)^2=1 \\ 
[/cht]

не могу сказать, что стало существенно легче. но векторов не стало.

fun fact. сейчас я решаю систему, её линеаризуя. а это математически эквивалентно тому, чтобы принять [cht]{n_{ji}}\limits^\perp=0[/cht]. до этого момента я никаких допущений не применял, просто преобразовывал исходное, так что мне подойдёт решение в любом допущении слабее этого. может, как-то хитрее линеризовать, учитывая члены с перпендикулярным n? если это как-то поможет, то можно принять, что m >> n

Правка: 22 окт. 2017 15:40

thevladПостоялецwww22 окт. 201717:50#28
Suslik
в общем вот, лучшее что есть http://publish.wm.edu/cgi/viewcontent.cgi?article=1424&context=honorstheses
тезисно:
введем опреатор vec(M), которые последовательно склеивает столбцы матрицы в вектор, то есть

      [ x1 y1 ]      [x1]
vec([ x2 y2] ) = [x2]
                        [y1]
                        [y2]
введем так же обратный оператор M = unvec(V) который назад превращает вектор в матрицу, M = unvec(vec(M))

теперь, аналогично тому что выше, пусть у нас есть, линейная система:
A*v = g
при этом
v = [x1*x1, x2*x2, x1*x2, x2*x1, 1]
                                                       
                                    [x1]                      [x1*x1, x1*x2, x1*1]
K = unvec(v) = x*x^T = [x2] x [x1, x2, 1] = [x2*x1, x2*x2, x2*1]
                                    [ 1]                        [x1,            x2,      1]

то есть смысл в чем, пусть у нас есть какой-то вектор v который является решеним системы (в общем случаи это некоторое линейное пространство)
среди этих векторов, нам интеренны те для которых матрица K = unvec(v) является одно ранговой
так как система не до конца определенная пространство решений можно в общем случаи представить в виде V(Z) = V0 + V1*Z_1 + V2*Z_2 + .. + Vn*Z_n (найти базис решений системы V0..Vn, относительно просто и решается стандартными алгоритмами линейной алгебры)
Z - вектор свободных переменных, эквивалентно применяя операцию unvec, получаем матричную функцию от свободного вектора параметров Z
K(Z) = K0 + K1*Z_1 + K2*Z_2 + ... + Kn*Z_n
среди всех возможных матричных функций (получаемых вариированием Z) нам интересны только те которые имеют ранк 1(так как решение у нас имеет вид x*x^T).
это эквивалентно тому, что все 2x2 миноры матрицы K равняются нулю, в общем случаи получаем choose(N, 2)^2 миноров которые сводятся к квадратным уравнениям, для которых надо найти Z которое их обнулит.
теперь идет интересное, доказывается, что если у K(Z) есть константная строка или столбец(не зависящая от вариирования Z),то достаточно проверить только (N-1)^2 миноров на ноль, которые включают эту строку или столбец.
а так как эти миноры включают константу, и элемент K(Z) который является линейной функцией от Z, то получаем из миноров, линейную систему которую надо разрешить относительно Z.
получаем Z, находим K(Z), получаем x*x^T = K
вопрос в том при каких условиях получаются такие K(Z) с константным столбцом или строкой, я это честно говоря до конца не врубился....

PS: но это чисто калька с общего случаи y^T*A*x возможно если хорошо подумать, можно что ни буть поинтереснее придумать...

Правка: 22 окт. 2017 23:24

}:+()___ [Smile]Постоялецwww22 окт. 201722:09#29
Suslik
> тогда каждый вектор [cht]\vec n_{ji}[/cht] можно разложить в сумму двух векторов
Такое можно сделать для произвольной размерности пространства, подкручивая [cht]\vec m[/cht] и [cht]\vec n[/cht] подходящей ортогональной матрицей.
Но смысла в этом я не вижу, ибо финальное уравнение не меняется.

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

[cht]\[A^\alpha_{ij}\lambda_i\lambda_j+B^\alpha_i\lambda_i+C^\alpha=0.\][/cht]

А отличие состоит в том, что у тебя ранг матриц [cht]A^\alpha_{ij}[/cht] равен 3.
Но как это можно использовать, я не вижу. Да, одно уравнение можно свести к

[cht]\[\lambda_1^2+\lambda_2^2+\lambda_3^2=1,\][/cht]

однако как это может помочь, я не знаю.

thevlad
Пиши плиз с помощью [ cht ] [ /cht ], а то нереально сложно понять, что ты имеешь в виду.

Страницы: 1 2 3 4 Следующая

/ Форум / Программирование игр / Физика

2001—2017 © GameDev.ru — Разработка игр