2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Решение системы полиномиальных уравнений
Сообщение19.02.2013, 17:23 
Заслуженный участник


15/05/05
3445
USA
Yuri Gendelman в сообщении #682034 писал(а):
Первый пример, на который я наткнулся - это решение системы 2-х уравнений 3-го порядка:...
Я сам этот пример не решал, а скопировал решение с интернетовской страницы (alexBlack: Алгоритм Бухбергера)
AndrewSu в сообщении #685536 писал(а):
результирующий базис зависит от порядка следования исходных полиномов.
Результирующий базис зависит от упорядочения переменных, от "модификации алгоритма Бухбергера" (Аржанцев, стр.34-36).

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение19.02.2013, 20:11 


09/02/13
31
Yuri Gendelman в сообщении #685771 писал(а):
(alexBlack: Алгоритм Бухбергера)

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение19.02.2013, 22:51 


09/02/13
31
Аржанцев в своей книге писал(а):
Теорема 5.1. Система S несовместна тогда и только тогда,
когда базис Грёбнера идеала I(S) содержит ненулевую константу

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение20.02.2013, 01:05 


09/02/13
31
AndrewSu в сообщении #685896 писал(а):
Видимо ошибка в программе

Так и есть. Из-за округления неправильно S-полином редуцировался.
Теперь при любом порядке уравнений работает.
AndrewSu в сообщении #685536 писал(а):
И кстати в WolframAlpha базис не зависит от порядка следования полиномов, хотя в описании они используют тот же алгоритм Бухбергера.

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение21.02.2013, 14:10 


09/02/13
31
AndrewSu в сообщении #683715 писал(а):
Для произвольной степени уравнения, мне на ум проходит только построение матрицы, для которой данное уравнение является характеристическим многочленом. Если степень велика, то получить решение не очень просто (с вычислительной точки зрения).

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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение02.03.2013, 19:52 
Модератор
Аватара пользователя


11/01/06
5660
Утундрий в сообщении #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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение18.03.2013, 00:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Решение системы полиномиальных уравнений
Сообщение24.03.2013, 07:01 


09/03/09
46
Если нелинейность имеет вид $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-ти.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 23 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group