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

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

Поделиться

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

thevladПостоялецwww22 окт. 201722:31#30
Suslik
если тебе хватит численно, нашел клевый кейворд, "structured low rank approximation"
https://en.wikipedia.org/wiki/Low-rank_approximation
https://eprints.soton.ac.uk/263379/2/slra_published.pdf
https://www.ee.iitb.ac.in/~belur/pdfs/c10mtns1.pdf
S это у нас K(Z) при этом оно линейное, p - Z
и дальше долбим численными алгоритмами из этой области, конкретно чтобы найти одно ранговую апроксимацию.

PS:  первая статья по ссылки немного по кругу пошла :)) так как там опять множители лагранжа вылезли...
PSS: да, задача там другая выходит, находится апроксимация со структурой для некоторой заданной матрицы. но можно попробовать адаптировать алгоритмы оттуда, так как задачи сильно похожи.
PSSS: еще годный пэйпер http://www.csd.uwo.ca/~eschost/publications/NewtonSLRA.pdf
PSSSS: в общем если адаптировать алгоритм lift and project оттуда, то получается что-то в духе

берем начальную матрицу K
проецируем ее на пространство K(Z) так как базис не ортогональный, придется использовать что-то в духе метода наименьших квадратов, получаем матрицу M
находим SVD M, обнуляем все собственные значения кроме одного (первого наибольшего) и собираем назад, получаем матрицу G
K = G, повторить пока все собственные значения кроме одного ни станут достаточно малы

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

Правка: 23 окт. 2017 1:53

thevladПостоялецwww22 окт. 201722:41#31
}:+()___ [Smile]
> Пиши плиз с помощью [ cht ] [ /cht ], а то нереально сложно понять, что ты
> имеешь в виду.
да там есть оригинальная статья по билинейным системам, я лишь вольно ее пересказал, сорри в TeX не умею :(
SuslikМодераторwww23 окт. 20172:19#32
смаел сказал, что не знает. расходимся, пагни, тут нечего ловить.

Правка: 23 окт. 2017 2:21

SuslikМодераторwww23 окт. 20172:30#33
}:+()___ [Smile]
я думаю, можно отдохнуть от идеи решать это точно в исходной постановке. что-то нужно как-то линеризовать или принять какое-то допущение. сейчас я использую допущение достаточно грубое — считаю, что вся скобка с перпендикулярными членами равна нулю, тогда из первой скобки уходит квадрат(кстати, достаточно лишь брать один знак, потому что мне нужно всего одно решение) и всё решается, но упущенные члены иногда дают о себе знать. можно попробовать считать, что все суммы [cht]\sum \vec n^\alpha_i\lambda_i[/cht] существенно меньше по модулю [cht]\vec m^\alpha[/cht]. не забываем, что мне нужно первое попавшееся решение, а не все: например, когда я выкидываю правую скобку, я из левой просто извлекаю квадрат, не парясь со знаками, и всё прекрасно работает. как бы это использовать?

Правка: 23 окт. 2017 2:53

thevladПостоялецwww23 окт. 20172:43#34
Suslik
а градиентный спуск тебе не подходит?
можно тупо взять вектор x, найти x*x^T, подставить в матрицу A*(unvec(x*x^T)) = g, в качестве функционала взять квадратичную невязку с g, вывести аналитическую формулу для градиента не сложно, и вперед...
с теми методами что я выше описывал, действительно проблема в том, что в общем случаи размерность Z, N^2 - N, так как у нас только N уравнений... и пространство K(Z) получается плотным, то есть не несет практически ни какой структуры.

Правка: 23 окт. 2017 2:44

SuslikМодераторwww23 окт. 20172:48#35
thevlad
мне кажется, что проблема билинейного направления именно в том, что вся исходная структура задачи теряется, она решается как более вычислительно сложная. даже в виде Изображение она по сути такая же, только размерность меньше, но тоже теряется вся суть. считаю, что задачу нужно решать, по максимуму используя её исходную структуру и принимая ещё какие-то допущения, а не усложняя её.

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

для осваивания латеха рекомендую https://www.codecogs.com/latex/eqneditor.php . там можно формулы писать мышью(просто копируешь оттуда в тег [ cht ][ /cht ] ), учиться, а потом туда подсматривать, если что-то забыл

Правка: 23 окт. 2017 2:51

MrShoorУчастникwww23 окт. 20176:15#36
Suslik
А N какой? Может там N = 5, и проще 32 раза решить систему линейных?
SuslikМодераторwww23 окт. 20177:14#37
тем временем я открыл небольшую фабричку по переводу бумаги в ошибки:
Изображение

MrShoor
> А N какой? Может там N = 5, и проще 32 раза решить систему линейных?
каких и как?

thevladПостоялецwww23 окт. 20179:44#38
Suslik
в общем фигня какая-то, ты что-то не договариваешь... в том виде как у тебя она вобще какая-то комбинаторная получается.
упростим до L1 нормы, получим

sum i=1_n |n_i_m*a| = k_m
так как у нас трех мерные вектора это эквивалентно тому, что нам нужен какой-то вектор вида S = [s1, s2, s3] где s1, s2, s3 E {-1, +1 }
то есть к примеру для одного уравнения

                                                                                      [ a1]
                                  [ x1_m  x2_m x3_m  x4_m ... ]    [ a2]
[s1_m, s2_m, s3_m]* [ y1_m  y2_m y3_m  y4_m ... ] * [ a3]  = k_m
                                  [ z1_m  z2_m  z3_m  z4_m ... ]    [ a4]
                                                                                      [ a..]

как-то получается совсем нереалистично, пусть у нас есть единственное решение  - a, мы его умножили на матрицу получили какой-то вектор G = [gx, gy, gz] теперь нам надо подобрать такой S чтобы проекция G на S равнялась k_m... и так для всех m уравнений...
может у тебя есть какие-то еще предположения? например что всегда n_i_m*a >= 0 (то есть S_m = [1, 1, 1]) .. сам понимаешь тогда совсем просто получается (так как у тебя есть константный член, это эквивалентно тому что n_i_m*a + b >= 0, b всегда положительное? или всегда отрицательное? тогда какая ни буть эвристика которая, меняет знак у n_i_m..)
sum i=1_n n_i_m*a = k_m -> (sum i=1_n n_i_m)*a = k_m

PS: в общем еще какая идея, мы можем перебрать все S, получится девять вариантов, девять уравнений вида (sum i=1_n n_i_m)*a = k_m, как показано выше если S_m константно мы всегда можем выбрать одно соответствующее уравнение, и получить единственное решение.... если же S_m вариируется то мне даже как-то не очевидно как доказать что существует хотя бы одно решение. то есть нам надо как-то выбирать из этих возможных 9 уравнений одно, для каждой строки исходной системы...
PSS: то что я выше описал очевидно некоторая релаксация, так как нам надо подбирать элементы S_m в общем случаи в зависимости от знака n_i_m*a
PSSS: ну и это как-то бьется с тем что ты находил, что в общем случаи система квадратичных форм NP-complete...

Правка: 23 окт. 2017 11:47

}:+()___ [Smile]Постоялецwww23 окт. 201715:21#39
Suslik
> считаю, что вся скобка с перпендикулярными членами равна нулю, тогда из первой скобки уходит квадрат
Это ты матрицу [cht]A^\alpha_{ij}[/cht] заменяешь на [cht]\kappa B^\alpha_iB^\alpha_j[/cht] ранга 1.
Можешь попробовать это решение брать как начальное приближение и решать уравнение на отклонение от него.

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

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

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

key0Постоялецwww23 окт. 201718:23#40
Когда много  символов описывающих пространство  лет 10 назад использовали метод монте карло.
MrShoorУчастникwww23 окт. 201718:50#41
Suslik
> каких и как?
Просто извлекаешь из правой и левой части корни. После этого решаешь уже такую систему:
summ2 | Система квадратных уравнений.
ну и для решения при N = 5 надо будет решить 2^5 линейных систем.
susagePПостоялецwww23 окт. 201719:13#42
MrShoor
Меня смущает вектор и результат скаляр.  Там скорей всего не скобки, а длина вектора была.
SuslikМодераторwww24 окт. 20172:10#43
MrShoor
susageP
> Меня смущает вектор и результат скаляр.  Там скорей всего не скобки, а длина вектора была.
во-во. уравнение как бы на длины векторов.
MrShoorУчастникwww24 окт. 20172:38#44
Suslik
> во-во. уравнение как бы на длины векторов.
А какая разница на длины оно или нет. Справа и слева от знака равенства скаляр. Можно спокойно извлечь квадратный корень, поставив с одной стороны равенства +-, и равенство останется равенством. Дальше решить СЛУ для всех комбинаций +-, а это 2^N комбинаций. Для достаточно маленького N можно все варианты и перебрать.
А, блин, там же m векторная величина.

Правка: 24 окт. 2017 2:40

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

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

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