Решение системы полиномиальных уравнений

[Yuri Gendelman]

Yuri Gendelman в сообщении #682034 писал(а):

Первый пример, на который я наткнулся - это решение системы 2-х уравнений 3-го порядка:...

Я сам этот пример не решал, а скопировал решение с интернетовской страницы (alexBlack: Алгоритм Бухбергера)

AndrewSu в сообщении #685536 писал(а):

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

Результирующий базис зависит от упорядочения переменных, от "модификации алгоритма Бухбергера" (Аржанцев, стр.34-36).

И вообще,

Аржанцев писал(а):

Следует отметить, что в этом направлении остается еще много нерешенных задач и, видимо, еще преждевременно говорить о том, что удовлетворительная теория здесь построена. (стр.36)

[AndrewSu]

Yuri Gendelman в сообщении #685771 писал(а):

(alexBlack: Алгоритм Бухбергера)

Я и сам начал своё знакомство с алгоритмом Бухбергера с просмотра этой страницы)

[AndrewSu]

Аржанцев в своей книге писал(а):

Теорема 5.1. Система S несовместна тогда и только тогда,
когда базис Грёбнера идеала I(S) содержит ненулевую константу

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

[AndrewSu]

AndrewSu в сообщении #685896 писал(а):

Видимо ошибка в программе

Так и есть. Из-за округления неправильно S-полином редуцировался.
Теперь при любом порядке уравнений работает.

AndrewSu в сообщении #685536 писал(а):

И кстати в WolframAlpha базис не зависит от порядка следования полиномов, хотя в описании они используют тот же алгоритм Бухбергера.

С этим тоже все понятно. В WolframAlpha считается "Минимальный" базис Грёбнера. Я свой базис "минимизировал" - совпало с WolframAlpha с точностью до константы.

[AndrewSu]

AndrewSu в сообщении #683715 писал(а):

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

Пока нагуглил еще два метода: метод Лагерра и метод Дженкинса-Трауба

[maxal]

Утундрий в сообщении #683156 писал(а):

Подскажите, а вот если уравнения все однотипные: суммы мономов вида $x_i x_j$ ($i \ne j$), равные то ли нулю, то ли некоторой константе, то можно ли надеяться что-то такое нетривиальное руками выкрутить или проще применить грубую вычислительную силу?

Если еще $x_i\in\{0,1\}$, то можно попробовать применить "расширенную разреженную линеаризацию": http://en.wikipedia.org/wiki/XSL_attack

-- Sat Mar 02, 2013 11:58:53 --

Если кому-то вдруг интересно, то вот моё решение одной оптимизационной задачи с помощью базисов Грёбнера и алгоритма Бухбергера с исходниками на Паскале: http://algolist.ru/maths/combinat/payment1.php
Там же на форуме я дал кое-какие дополнительные пояснения: http://forum.algolist.ru/algorithm-math ... netah.html

[Утундрий]

Хотел бы выразить, хотя и с некоторым опозданием, свою благодарность сабджевому методу за объяснение неудачности своих дилетантских попыток получить коэффициенты явного симплектического интегратора четвёртого порядка вручную. Наверное, трудно придумать более наглядного объяснения, чем километровый полином с двеннадцатизначными целыми коэффициентами, коий я непосредственно узрел и устыдился.

[rtfai]

Если нелинейность имеет вид $x_i x_j$ то можно попытаться применить аналог метода Адамса: $A( \alpha_1 x^{i-1}+\alpha_2 x^{i-2}..+\alpha_k x^{i-k})x^i=f$, \Sigma_{r=1}^{r=k}\alpha_r=1. Я решал аналогичные большие системы когда нелинейность имеет вид: $|x_i^p|x_i$, т.е. сумма таких мономов. Там удается доказать единственность и сходимость не зависит от начального приближения. Число итераций практически не зависит от размерности матрицы и равно примерно 15-20-ти.