Отделение корней систем нелинейных уравнений

vmil · Сообщение **vmil** » 23 авг 2012, 20:38

Уважаемые участники!
Часто сталкиваюсь с системами нелинейных уравнений Fi(x1,x2...xn)=0. Каждое уравнение задается очень сложной функцией с плохо предсказуемым поведением, зависящим от параметров. Область определения функций не является непрерывной.
В литературе хорошо описано отделение и уточнение корней одного уравнения с одной переменной, а также, уточнение корней систем уравнений. Но мне не удалось найти ничего про отделение корней систем уравнений.
Пользуюсь простым в реализации, но очень медленным способом исключения переменных. Пишем программу отделения и уточнения корня x1 из первого уравнения при произвольных значениях x2....xn. Программа позволяет вычислить функцию x1=Ф1(x2,x3,....,xn) с произвольной точностью. Во втором уравнении подставляем F2(Ф1(x2,x3,....,xn),x2...xn) и пишем аналогично программу вычисления функции x2=Ф2(x3,x4,...). Далее аналогично F3(Ф1(Ф2(x3,....,xn),x3,....,xn),Ф2(x3,....,xn),x3...xn), x3=Ф3(x3,x4,...) и.т.д. Большое число ненужных повторов вычислений приводит к снижению производительности.
Можно ли реализовать подсчет функций на сетке с равным шагом по каждой переменной? Как правильно определить интервал изоляции корня чтобы держать в памяти минимум значений?
С уважением.
Виктор.

vicvolf · Сообщение **vicvolf** » 24 авг 2012, 15:17

Существует много методов приближенного решения систем нелинейных уравнений: Ньютона, итерационные методы и др. Посмотрите здесь [url=http://solidbase.karelia.ru/edu/meth_calc/files/11.shtm]http://solidbase.karelia.ru/edu/meth_calc/files/11.shtm[/url]

folk · Сообщение **folk** » 24 авг 2012, 20:04

Априори вы не сможете по значению F в четырех углах решетки угадать есть или нет корень - если нет ограничений по гладкости на F. Если функция не гладкая или разрывная то непонятно в общем то как подступаться. В первую очередь чтобы хорошо работали методы а ля ньютон надо обеспечить гладкость F. Тогда начиная с какой то точки вы будете спускаться к корню. А вот как изолировать это вопрос...

Ian · Сообщение **Ian** » 24 авг 2012, 21:42

Об этом столько всего в сети, что перечитать невозможно физически. Дам ссылку на конец своей темы, а там и ссылки и специалисты которым можно написать. Попробую угадать, что бы они посоветовали.
Надо угадать, какое из n уравнений выкинуть, чтобы для оставшейся системы n-1 уравнений
1)Решение представляло собой связную кривую
2)Хотя бы одно конкретное решение этой системы n-1 уравнений можно было предъявить (ну или найти численно).То есть знаем точку на кривой, нужно найти всю кривую.
Она удовлетворяет дифуру
$\displaystyle \sum_j\frac{\d F_i}{\d x_j}(x_1,...x_n)\frac{dx_j}{dt}=0,i=1,...n-1$ ,
который решается чмсленно, с начальными условиями в той точке. Это решение можно нормировать условием $\displaystyle \sum_j\left(\frac{dx_j}{dt}\right)^2=1$ , то есть проходить численным методом кривую с единичной скоростью, тогда каждая точка кривой достижима. Либо кривая замкнута, либо пройти по t от 0 вперед и по t от 0 назад. При прохождении проверять условие, не обратится ли выкинутое вначале уравнение в равенство, и каждый раз , когда обратится, будет Вам корень.
Это я вульгаризовал т.н. "метод Драгилева", для многих случаев дающий и быстрый счет, и большую точность. Он симпатичен мне тем, что другие известные методы требуют сначала локализовать корни, здесь же наоборот, корни объединяются, укладываются на одну кривую, и решение идет более "зряче".
При проблемах дальше лучше спрашивать не меня, а людей с экспоненты, у которых большая практика реализаций этого.

vmil · Сообщение **vmil** » 25 авг 2012, 08:12

Большое спасибо!

Априори вы не сможете по значению F в четырех углах решетки угадать есть или нет корень - если нет ограничений по гладкости на F

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

О методе Драгилева до этого ничего не слышал. Попробую на Экспоненте... (сомневаюсь в связности кривой).

alekcey · Сообщение **alekcey** » 02 сен 2012, 13:41

Ian писал(а):Source of the post
Это я вульгаризовал т.н. "метод Драгилева", для многих случаев дающий и быстрый счет, и большую точность. Он симпатичен мне тем, что другие известные методы требуют сначала локализовать корни, здесь же наоборот, корни объединяются, укладываются на одну кривую, и решение идет более "зряче".
При проблемах дальше лучше спрашивать не меня, а людей с экспоненты, у которых большая практика реализаций этого.

[font=Calibri]Никогда сюда не заглядывал, но вот "метод Драгилева" привёл. Вы, вижу, не просто разобрались с сутью метода Драгилева, но и практически разобрались с вариантами его применения. На сегодняшний день на вооружении имеются возможности пакетов по полному решению алгебраических систем, и метод Драгилева великолепно дополняет ту часть, где решения присутствуют как бесконечное множество. Пакетами находятся точки на всех связных участках, а уже потом по этим точкам находятся сами участки. То есть, в данном случае мы не отбрасываем уравнения, а поступаем наоборот. В случае же когда система трансцендентная мы запускаем метод Драгилева самостоятельно или совместно с мощным пакетом оптимизации для Maple Сергея Моисеева. И ещё всё это с вариантами. И, конечно, ни о каких ньютоновких методах речь не может идти на фоне возможностей этих алгоритмов.

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

[/font]

[size="3"][/size]

folk · Сообщение **folk** » 02 сен 2012, 17:57

А можно для законченности указания дать название какого нибудь конкретного пакета и ссылку на пакет Моиссеева?

alekcey · Сообщение **alekcey** » 03 сен 2012, 07:36

Пакеты Мэпл и Математикаимеют функции полного решения СНАУ.
]На сайте экспоненты на форуме Мэпл поимени mois илина официальном сайте разработчика Мэпл найдётся пакет Сергея Моисеева…

alekcey · Сообщение **alekcey** » 22 май 2015, 16:35

Ещё немного о методе Драгилева. Это визуализация работы классического варианта метода на примере решения системы двух нелинейных уравнений:
$\begin{cases} & \(4*(x1^2+x2-11))*x1+2*x1+2*x2^2-14+cos(x1)=0; \\ & \2*x1^2+2*x2-22+(4*(x1+x2^2-7))*x2-sin(x2)=0; \end{cases}$
Для одного начального приближения находятся 9 (похоже, это все) решений системы через 3d (пространство $R^{^{2+1}}$ ).

alekcey · Сообщение **alekcey** » 24 май 2015, 15:47

Опыт показывает, идея метода Драгилева распространяется на довольно широкий круг прикладных задач. Например, на расчёт геометрии и кинематики рычажных механизмов с любым числом степеней свободы (с точки зрения математики нет необходимости делить механизмы на плоские и пространственные, и не надо придумывать индивидуальные подходы к расчёту внешне различных видов рычажных механизмов).
http://www.exponenta.ru/educat/systemat/selitskiy-ivanov/index.asp http://www.exponenta.ru/educat/systemat/se...vanov/index.asp

yourdomain.com