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

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

Поделиться

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

SuslikМодераторwww21 окт. 20174:31#0
рассмотрим уравнение вида:
[cht](\vec m + \sum_{i=1}^N\vec n_i \lambda_i)^2=k^2[/cht]
здесь под умножением векторов понимается скалярное произведение, вектор [cht]\vec m[/cht] и векторы [cht]\vec n_i[/cht], а также число [cht]k^2[/cht] — известны. таких уравнений — N и теоретически можно составить систему из N уравнений относительно N неизвестных [cht]\lambda_i[/cht]:
[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](m^{(j)}_{i}+n^{(j)}_{ip}\lambda_p)(m^{(j)}_{i}+n^{(j)}_{iq}\lambda_q)=k^{(j)}k^{(j)}[/cht]
здесь по (j) суммирование не ведётся, это просто N уравнений системы.

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

Правка: 21 окт. 2017 4:54

SuslikМодераторwww21 окт. 20174:46#1
пробовал копать в сторону квадратичных форм и приведения их к диагональному виду: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%… 8%D0%B4%D1%83

судя по всему, каждое уравнение моей системы описывает эллипсоид в N-мерном пространстве. теоретически я могу найти собственные оси каждого из этих эллипсоидов, их центры, найти преобразование системы координат, в которой они имеют каноничный вид в духе [cht]x^TAx=1[/cht], но для каждого уравнения системы это преобразование будет разным и задача оказывается эквивалентной поиску пересечения N эллипсоидов в N-мерном пространстве и я не уверен, что это решается .____.

Правка: 21 окт. 2017 5:25

Iron ManПостоялецwww21 окт. 20175:33#2
Помнится в школе за полурока написал на пятёрку контрольную по квадратным уравнениям :)))
Там, где сначала находится дискриминант, единственное, что легко вкурил по математике, но за 25 лет уже наглухо забыл :)

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

MrShoorУчастникwww21 окт. 20175:59#3
Suslik
Я нихрена не понял как ты из первого уравнения получил систему ниже. Почему m, которая находится за суммой вдруг внезапно получает индекс? Допустим m было частью суммы, но почему тогда в системе у тебя осталась сумма? wtf?
Я так понимаю должно быть что-то в духе:
summ | Система квадратных уравнений.
?
А само N большое? Если небольшое - то можно метод Ньютона через матрицу Якоби.
MrShoorУчастникwww21 окт. 20176:03#4
Вот даже несколько методов есть:
http://mathhelpplanet.com/static.php?p=metody-resheniya-sistem-ne… ykh-uravneniy
Но конкретного ничего подсказать не могу, ибо нелинейные системы на практике решал только один раз в жизни на одной из самостоятельных работ по численным методам лет 10 назад (если не больше).
SuslikМодераторwww21 окт. 20176:27#5
MrShoor
> Я нихрена не понял как ты из первого уравнения получил систему ниже
я сначала рассмотрел одно уравнение, а потом сказал, что уравнений этого типа на самом деле N, коэффициенты для всех известны.

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

MrShoor
> метод Ньютона
Suslik
> требуется аналитически

Правка: 21 окт. 2017 6:29

MrShoorУчастникwww21 окт. 20176:49#6
Suslik
> ты выписал систему уравнений, в каждом из которых всего одна переменная, тут решать нечего
Да, я чушь написал, ибо это независимые уравнения. Просто я подумал что ты как то верхнее уравнение превратил в систему ниже. А ты просто масштабировал это уравнение на N разных уравнений.

> неправильно понимаешь. ты выписал систему уравнений, в каждом из которых всего
> одна переменная
Теперь понял. Ну таки да, численно оно решается все теми же методами Ньютона, а вот аналитически хрен знает даже, жди смайла :)

Правка: 21 окт. 2017 6:50

FordPerfectПостоялецwww21 окт. 20177:03#7
>из смысла задачи я знаю, что хотя бы одно решение будет всегда, но я даже не могу понять, сколько будет ещё действительных решений и будут ли они.
https://en.wikipedia.org/wiki/System_of_polynomial_equations
Bézout's theorem asserts that a well-behaved system whose equations have degrees d1, ..., dn has at most d1...dn solutions. This bound is sharp.
SuslikМодераторwww21 окт. 20177:22#8
FordPerfect
ну, допустим, с количеством корней ещё более-менее. но как найти сами-то корни? мне бы хотя бы один набор, любой. рассматриваю уже полуаналитические методы, которые хоть как-то аналитически используют структуру системы в итерациях.

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

eugenelozaПостоялецwww21 окт. 20178:26#9
Suslik
> требуется аналитически найти действительные корни.
Вряд-ли. Только приближённо. Задача сводится к уравнению 2N-й степени, т.е. она не имеет на сегодня аналитического решения в общем случае.
Но сколько я работал с полиномами высоких степеней, там даже итерационные методы буксуют.
SDCПостоялецwww21 окт. 201712:18#10
Suslik
Я правильно понимаю задачу?: Есть кучка векторов и нужно их отскейлить так, чтобы длина их суммы была k.

SuslikМодераторwww21 окт. 201713:08#11
SDC
нет, ничего общего
thevladПостоялецwww21 окт. 201713:18#12
Suslik
можно попробовать через это решить, так как система у тебя выпуклая: https://en.wikipedia.org/wiki/Lagrange_multiplier
оптимизируемую функцию заменить константой.
в форме множителей лагранжа там все должно сильно упростится, и сведется к сумме квадратичных форм, которую скорее всего можно будет решить, через ту же спектральную декомпозицию.
(ну и еще ключевые слова это convex programming feasibility problem)

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

Правка: 21 окт. 2017 13:28

SuslikМодераторwww21 окт. 201713:33#13
thevlad
на самом деле задача фактически свелась от множителей лагранжа, это по сути — система уравнений на ограничения. я с трудом понимаю, как её можно ещё раз применить. но ключевые слова вроде спектральной декомпозиции и квадратичных форм — это где-то по делу, надо только понять, как именно их применить.

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

thevladПостоялецwww21 окт. 201713:45#14
Suslik
> на самом деле задача фактически свелась от множителей лагранжа
там суть в том что, если у тебя есть система функций вида: g1(X) = 0, g2(X) = 0, g3(X) =0, gN(X) =0, то их можно заменить на функцию вида f(X) = a1*g1(X) + a2*g2(X) + a3*g3(X), и решать безусловную задачу оптимизации

PS: просто то что ты описываешь это частный случай https://en.wikipedia.org/wiki/Convex_optimization (более точно feasibility problem). в конкретно данном случаи, даже если ничего не придумывать особо, для выпуклой задачи градиентный спуск должен сойтись очень быстро, но даже если и придумывать то лучше попробовать через ту же спектральную декомпозицию, но в форме множителей лагранжа...

Правка: 21 окт. 2017 15:01

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

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

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