Авторефераты по всем темам >> Авторефераты по техническим специальностям

На правах рукописи

Блинков Юрий Анатольевич

ИНВОЛЮТИВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОДЕЛЕЙ, ОПИСЫВАЕМЫХ СИСТЕМАМИ АЛГЕБРАИЧЕСКИХ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

Саратов 2009

Работа выполнена в ГОУ ВПО Саратовский государственный университет имени Н. Г. Чернышевского.

Научный консультант:

доктор физико-математических наук профессор Гердт Владимир Петрович

Официальные оппоненты:

доктор физико-математических наук профессор Абрамов Сергей Александрович доктор физико-математических наук профессор Михалев Александр Александрович доктор физико-математических наук профессор Утешев Алексей Юрьевич

Ведущая организация:

Санкт-Петербургское Отделение Математического института им. В. А. Стеклова РАН

Защита состоится л 2009 г. в на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, дом 3.

С диссертацией можно ознакомиться в научной библиотеке Российского университета дружбы народов по адресу: 117198, г. Москва, ул. МиклухоМаклая, дом 6.

Автореферат разослан л 2009 г.

Ученый секретарь диссертационного совета Фомин М.Б.

Общая характеристика работы

Актуальность работы. Область применимости методов качественного анализа математических моделей, описываемых алгебраическими и дифференциальными уравнениями, весьма ограничена[1]. Гораздо более универсальным способом исследования дифференциальных систем является переход к их дискретным аналогам. В результате, такое понимание математического моделирования означает не просто уточнение количественных характеристик явлений, но также изучение основных их качественных свойств, прежде всего для нелинейных объектов. Проблемы численного моделирования не снимаются сами собой по мере появления все более мощных и дешевых компьютеров. Это связано, по меньшей мере, с двумя причинами: усложнением выдвигаемых как практикой, так и теорией задач и необходимостью проведения большого числа серий вычислительных экспериментов для достаточно полного изучения объекта. Поэтому разработка эффективных вычислительных алгоритмов всегда остается одной из ключевых задач математического моделирования. Для их конструирования широко используются методы, идеи и подходы, применяемые при построении исходных математических моделей. Эта связь хорошо прослеживается на примере очень широкого класса моделей - тех, которые сводятся к дифференциальным уравнениям.

Приведение систем алгебраических, дифференциальных и разностных уравнений к канонической форме, называемой базисом Грёбнера[2], представляет собой качественный аналитический метод исследования математических моделей.

В частности, таким образом удается: проверять совместность системы; осуществлять проверку выполнимости дополнительного уравнения на ее решениях; проверять эквивалентность уравнений на решениях системы; определять обладает ли система конечным или бесконечным числом решений; в случае [1] Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры. / А. А. Самарский, А. П.

Михайлов. Ч 2-е, исправленное изд. Ч Физматлит, 2001. Ч С. 320.

[2] Бухбергер, Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбергер // Компьютерная алгебра. Символьные и алгебраические вычисления. Ч М. Мир, 1986. Ч С. 331Ц372.

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

Для систем уравнений полиномиального типа их инволютивная форма является специальным случаем базисов Грёбнера. Базисы Грёбнера являются универсальным алгоритмическим инструментом[3] во многих областях математики: алгебраическая геометрия, коммутативная алгебра, теория полиномиальных идеалов, теория инвариантов, автоматическое доказательство геометрических теорем, теория кодирования, целочисленное программирование, дифференциальные уравнения в частных производных, гипергеометрические функции, символьное суммирование, статистика, некоммутативная алгебра, численные (например вейвлет-) преобразования, теория управления и др. В настоящее время алгоритм построения базисов Грёбнера встроен во все современные системы компьютерной алгебры достаточно универсального характера: Magma, Axiom, CoCoA, Reduce, Macaulay, Maple, Mathematica, Maxima, MuPAD, SINGULAR.

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

Цель работы. Разработка теории инволютивных алгоритмов для эффективного построения базисов Грёбнера как метода качественного исследования математических моделей.

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

[3] Buchberger, B. Grbner Bases and Applications / B. Buchberger, F. Winkler. Ч Cambridge University Press, 1998.

Методы исследований основаны на приведении в инволюцию систем многочленов и восходит к конструктивным методам, разработанным французскими математиками Рикье[4] и Жане[5]. В работе также используются известные методы построения разностных схем и их обобщения, полученные с помощью техники базисов Грёбнера.

Достоверность и обоснованность. Разработана аксиоматическая теория инволютивного мономиального деления, на основе которой строго исследованы вопросы корректности и завершаемости полученных алгоритмов в зависимости от свойств задаваемого инволютивного деления. Корректность работы инволютивных алгоритмов подтверждена также компьютерными расчетами на многочисленных примерах, взятых из международной базы данных[6]. Это база данных специально создана для тестирования программных продуктов, предназначенных для вычисления базисов Гребнера. Предложенный алгоритмический подход к построению разностных схем для дифференциальных уравнений, опирающийся на метод базисов Гребнера, позволил воспроизвести целый ряд хорошо известных разностных схем. Свойства найденных с помощью этого метода принципиально новых разностных схем строго исследованы теоретически.

Теоретические результаты подтверждены численными расчетами на математических моделях физических процессов, допускающих точное решение.

Научная новизна.

1. Разработан новый алгоритмический подход к вычислению базисов Грёбнера, альтернативный классическому методу Бухбергера. В его основе лежит новое математическое понятие Ч инволютивное деление мономов.

Это деление мономов обобщает известные в литературе разделения переменных, используемые для приведения в инволюцию дифференциальных систем.

2. Разработан алгоритм построения минимальных инволютивных базисов, [4] Riquier, C. Les Systmes dТEquations aux Drives Partielles / C. Riquier. Ч Gauthier-Villars, Paris, 1910.

[5] Janet, M. Systmes dТquations aux drives partielles / M. Janet // Journals de mathmatiques, 8e srie. Ч 1920. Ч Vol. 3. Ч Pp. 65Ц151.

[6] The database of polynomial systems. каноническое представление исходной системы уравнений для произвольного инволютивного деления.

3. При построении инволютивного базиса, значительная часть вычислений не приводит к получению нового элемента базиса. Установлены критерии равенства нулю инволютивной нормальной формы, позволяющие оптимизировать процесс вычисления.

4. Поиск мономиального делителя - одна из наиболее часто выполняемых операций при построении базисов Грёбнера. Найдены оптимальные структуры данных для быстрого поиска инволютивного делителя, представляющие собой деревья специального типа.

5. Минимальный инволютивный базис, в некоторых случаях, может значительно превосходить авторедуцированный базис Грёбнера по числу элементов, а следовательно и по требуемой памяти. Разработано новое мономиальное деление, основанное на понятии немультипликативных степеней переменных, дающее более компактное представление базиса.

6. Разработан полностью алгоритмический метод построения разностных схем, использующий технику базисов Грёбнера. Данный метод является обобщением известных процедур построения разностных схем метода конечных объемов, Лакса, Лакса-Вендроффа и ряда других.

7. Для нелинейного уравнения околозвуковых течений Кармана-Фальковича найдена принципиально новая разностная схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей.

8. Для логистического отображения найдено значения параметра , при котором происходит образование 9-и периодических циклов. До настоящего времени[7] были найдены значения до n 8.

[7] Kotsireas, I. S. Exact computation of the bifurcation point b4 of the logistic map and the bailey-broadhurst conjectures / I. S. Kotsireas, K. Karamanos // Journal Bifurcation and Chaos. Ч 2004. Ч Vol. 14. Ч Pp. 2417Ц2423.

Практическая значимость.

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

2. На основе предложенных алгоритмов создана специализированная система компьютерной алгебры GINV с открытым кодом, доступная для широкого использования и успешно применяющаяся в ОИЯИ1 и RWTH2 для различных научных и прикладных задач. Кроме того, GINV используется в программном модуле Involutive, написанном на языке системы компьютерной алгебры Maple.

3. Программный модуль INVBASE, реализующий полиномиальные инволютивные алгоритмы, включен в качестве стандартного в систему компьютерной алгебры Reduce.

4. Представлен полностью алгоритмический метод генерации разностных схем, использующий технику базисов Грёбнера. Данный метод позволяет обобщить традиционные методы генерации разностных схем. Эти обобщения приводят к новым, нестандартным и эффективным разностным схемам.

Основные результаты, выносимые на защиту.

1. Создана теория инволютивных базисов. Теория основана на понятии инволютивной делимости мономов, для которого сформулированы аксиомы и дополнительные свойства (нётеровость, непрерывность и конструктивность), обеспечивающие алгоритмичность построения инволютивных базисов. Доказано, что инволютивные базисы являются базисами Грёбнера специального вида.

2. Разработан новый алгоритм вычисления базисов Грёбнера, альтернативный классическому алгоритма Бухбергера, названный инволютивным и Объединенный институт ядерных исследований (Дубна, Россия) Рейнско-Вестфальский технический университет (Ахен, Германия) значительно превосходящий по эффективности алгоритм Бухбергера. Инволютивный алгоритм основан на приведении систем уравнений к инволютивному виду, который определяется заданием инволютивного деления и линейного упорядочения мономов. Для повышения эффективности вычислений установлены критерии распознавания ряда бесполезных нулевых редукций.

3. Построено мономиальное деление, близкое по своим алгоритмическим свойствам классическому делению Жане, и поэтому названное степенным делением Жане, но вычислительно более эффективное. Для обоих делений разработаны специальные структуры данных, названные деревьями Жане, позволяющие значительно быстрее, чем при бинарном поиске, находить инволютивный делитель и тем самым существенно ускорить процесс редукции - наиболее трудоемкую часть вычисления инволютивных базисов.

4. Создана специализированная система компьютерной алгебры GINV с открытым кодом, написанная на языке С++ и организованная в виде модуля языка Python. Ядро системы составляют инволютивные алгоритмы. Система доступна для широкого использования и успешно применяется в ряде организаций для решения научных и прикладных задач. По скорости вычисления базисов Грёбнера система GINV является самой быстрой в мире среди систем с открытым кодом.

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

6. Путем вычисления разностного идеала, для нелинейного уравнения Кармана-Фальковича, описывающего околозвуковые течения в газовой динамике, найдена принципиально новая разностная схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей. В частности, для одномерного течения газа в канале с прямым скачком уплотнения зона ударного перехода, при использовании данной схемы, имеет протяженность порядка шага сетки.

ичный вклад соискателя. Все результаты, изложенные в единоличных публикациях, получены автором самостоятельно. Из совместных публикаций в диссертацию включены лишь те результаты, которые получены лично автором. Вклад автора в реализацию специализированной системы компьютерной алгебры GINV, модулей Janet и INVBASE является основным.

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

Гранты РФФИ: 98-01-00101-а инволютивный анализ динамических систем со связями (1998-2000); 99-01-00192-а развитие кватернионных моделей и методов механики космического полета (1999-2000); 00-15-96691 поддержки ведущих научных школ (2000-2002); 01-01-00708-а компьютерные методы инволютивного анализа дифференциальных уравнений и их применение к калибровочным теориям поля (2001-2003); 04-01-00784-а компьютерное приведение нелинейных систем в инволюцию с приложением к обобщенной гамильтоновой динамике и построению разностных схем для уравнений в частных производных (2004-2006); 07-01-00660-а компьютерный анализ совместности систем уравнений с приложением к квантовым вычислениям, калибровочным моделям теории поля и численному решению уравнений в частных производных (2007-2009).

Гранты Президента Российской Федерации: НШ-2339.2003.2 развитие и применение новых аналитических и численных методов в теоретической и математической физике; НШ-5362.2006.2 развитие и применение новых аналитических и численных методов в теоретической и математической физике.

Гранты ИНТАС: 93-0030 Computer algebra, symbolic and combinatorial tools in differential algebra and differential equations (1994-1995); 99-1222 Involutive Systems of Differential and Algebraic Equations (2000-2002).

Апробация работы. Основные результаты, полученные в диссертации, докладывались: на Международной конференции УСимпозиум по символьным вычислениям IMACSФ (Lille, Франция, 1993 г.); на совместных с МГУ семинарах по компьютерной алгебре в Лаборатории информационных технологий ОИЯИ (Дубна, 1994, 1998, 2001, 2002, 2003, 2004, 2005, 2006, 2007 гг.);

на Международной конференции УНовые компьютерные технологии в системах управленияФ (ПереславльЦЗалесский, 1994 г.); на Международной конференции УИнтервальные и компьютерно-алгебраические методы в научных вычислениях IntervalТ94Ф (Санкт-Петербург, 1994 г.); Современные тенденции в вычислительной физике (Дубна, 1998, 2000 гг.); на Международных конференциях УRhein Workshop on Computer Algebra RWCAФ (Karlsruhe, Германия, 1994 г.; SanktAugustin, Германия, 1998 г.; Mannheim, Германия, 2002 г.; Basel, Германия, 2006 г.); на Международной конференции УПриложения компьютерной алгебры IMACS/ACAФ (Санкт-Петербург, Россия, 2000 г.); в Высшей технической школе РейнаЦВестфалии RWTH (Аахен, Германия, 2001, 2003, 2006 гг.); на Международной конференции УКомпьютерная алгебра и ее приложения в физике CAAPТ2001Ф (Дубна, 2001 г.); на пятом Международном конгрессе по математическому моделированию (Дубна, 2002 г.); на Международных конференциях УКомпьютерная алгебра в научных вычислениях CASCФ (Konstanz, Германия, 2001 г.; Passau, Германия, 2003 г.; Kalamata, Греция, 2005 г.); на всероссийском семинаре УСЕТОЧНЫЕ МЕТОДЫ ДЛЯ КРАЕВЫХ ЗАДАЧ И ПРИЛОЖЕНИЯФ (Казань 2004 г.); на семинаре по компьютерной алгебре на факультете ВМиК МГУ им. М.В.Ломоносова (Москва, 2005 г.); на Международной конференции УSymmetry in Nonlinear Mathematical PhysicsФ (Киев, 2005 г.);

на Международной конференции УComputer Algebra and Differential EquationsФ (Turku, Финляндия, 2007 г.); на семинаре по алгебре на механико-математическом факультете МГУ им. М.В.Ломоносова (Москва, 2007 г.); на Международной конференции УПолиномиальная компьютерная алгебраФ (Санкт-Петербург, 2008 г.).

Публикации. По теме диссертации опубликовано 32 работы. Основные результаты представлены 8 в российских и 5 зарубежных журналах рекомендованных ВАК для представления результатов докторских диссертаций:

1. Жарков, А. Ю. Инволютивные системы алгебраических уравнений / А. Ю.

Жарков, Ю. А. Блинков // Программирование. Ч 1994. Ч № 1. Ч С. 53Ц56.

2. Zharkov, A. Yu. Involution approach to investigating polynomial systems / A. Yu. Zharkov, Yu. A. Blinkov // Mathematics and Computers in Simulation.

Ч 1996. Ч Vol. 42, no. 4-6. Ч Pp. 323Ц332.

3. Гердт, В. П. Инволютивные деления мономов / В. П. Гердт, Ю. А. Блинков // Программирование. Ч 1998. Ч Т. 24, № 6. Ч С. 22Ц24.

4. Gerdt, V. P. Involutive bases of polynomial ideals / V. P. Gerdt, Yu. A.

Blinkov // Mathematics and Computers in Simulation. Ч 1998. Ч Vol. 45. Ч Pp. 519Ц542.

5. Gerdt, V. P. Minimal involutive bases / V. P. Gerdt, Yu. A. Blinkov // Mathematics and Computers in Simulation. Ч 1998. Ч Vol. 45.

Ч Pp. 543Ц560.

6. Гердт, В. П. Быстрый поиск делителя Жане / В. П. Гердт, Д. А. Янович, Ю. А. Блинков // Программирование. Ч 2001. Ч Т. 27, № 1. Ч С. 32Ц36.

7. Блинков, Ю. А. Метод сепарирующих мономов для инволютивных делений / Ю. А. Блинков // Программирование. Ч 2001. Ч Т. 27, № 3. Ч С. 43Ц45.

8. Блинков, Ю. А. Вычисление базисов Жане торических идеалов / Ю. А.

Блинков // Программирование. Ч 2002. Ч Т. 28, № 5. Ч С. 65Ц68.

9. Gerdt, V. P. Janet-like monomial division / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. Ч Springer Berlin / Heidelberg, 2005. Ч Vol. 3718 of Lecture Notes in Computer Science. Ч Pp. 174Ц183.

10. Gerdt, V. P. Janet-like Grbner bases / V. P. Gerdt, Yu. A. Blinkov // Computer Algebra in Scientific Computing. Ч Springer Berlin / Heidelberg, 2005. Ч Vol. 3718 of Lecture Notes in Computer Science. Ч Pp. 184Ц195.

11. Блинков, Ю. А. Генерация разностных схем для уравнения Бюргерса построением базисов Грёбнера / Ю. А. Блинков, В. В. Мозжилкин // Программирование. Ч 2006. Ч Т. 32, № 2. Ч С. 71Ц74.

12. Гердт, В. П. О стратегии выбора немультипликативных продолжений при вычислении базисов Жане / В. П. Гердт, Ю. А. Блинков // Программирование. Ч 2007. Ч Т. 33, № 3. Ч С. 34Ц43.

13. Блинков, Ю. А. Специализированная система компьютерной алгебры GINV / Ю. А. Блинков, В. П. Гердт // Программирование. Ч 2008. Ч Т. 34, № 2. Ч С. 67Ц80.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения и одного приложения. Работа изложена на 251 страницах машинописного текста, из них основного текста 176 страниц.

Работа содержит 23 рисунка, 10 таблиц, 20 описаний алгоритмов и одного приложения. Список литературы включает 281 наименование.

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

В последующем будут использованы следующие обозначения:

R = K[X] кольцо полиномов над полем K с независимыми переменными X = x1,..., xn;

f, g, h, q, r полиномы из R;

F, G, H конечные подмножества из R;

(F ) идеал из R порожденный F ;

n M = {xd xd | di Z0} - множество мономов;

1 n u, v, w, s, t множество мономов или термов;

U, V, W конечные подмножества из M;

допустимое мономиальное упорядочение с порядком переменных x1... xn;

u | v означает, что моном u делит моном v;

u v означает, что моном u делит моном v и u = v.

В первой главе кратко рассмотрена теория базисов Грёбнера. Сформулирована концепция инволютивного деления и доказаны его основные свойства.

Разработаны основные алгоритмы, использующие инволютивное деление, и доказаны их корректность и завершаемость. Введено новое деление, названное степенным делением Жане, и исследованы его основные свойства.

Определение 1. Инволютивное деление L задано на M, если для любого конечного множества U M и для любого u U определен подмоноид L(u, U) M, удовлетворяющий условиям:

1. (u, v U) [uL(u, U) vL(v, U) = u vL(v, U) или v uL(u, U)];

2. (v U) [v uL(u, U) L(v, U) L(u, U)];

3. (u V ) [V U L(u, U) L(u, V )].

Определение 1 для каждого u U задает разбиение множества переменных {x1,..., xn} = ML(u, U) N ML(u, U) на два непересекающихся множества мультипликативных ML(u, U) и немультипликативных N ML(u, U) переменных. В результате, инволютивное деление для монома может быть задано через определение множеств мультипликативных и немультипликативных переменных.

Пусть заданы инволютивное деление L и U, тогда для каждого u U L(u, U) M определяет множество всех мультипликативных мономов для u. В этом случае условие v uL(u, U) будем записывать в виде u |L v и говорить, что моном u является инволютивным делителем монома v.

В дальнейшем будем использовать обозначение v = u w, если u Ч инволютивный делитель v. В этом случае, моном w будем называть мультипликативным множителем. В случае, когда u является делителем v в обычном смысле, но не является его инволютивным делителем мы будем использовать обозначение v = u w. В этом случае w называется немультипликативным множителем для u.

Рассмотрим три различных примера инволютивных делений, соотвествующих разбиениям, введеным Жане и Томасом для анализа систем дифференциальных уравнений.

Определение 2. Разбиение Томаса[8]. На U переменная xi считается мультипликативной для u U если degi(u) = max{degi(u) | u U} и немультипликативной в противном случае.

Определение 3. Разбиение Жане[5]. Разобьем U на подмножества, задаваемыми числами d0, d1,..., di Z0:

[d0, d1,..., di] = {u U | d0 = 0, d1 = deg1(u),..., di = degi(u)}.

Переменная xi считается мультипликативной для u [d0, d1,..., di-1] если degi(u) = max{degi(v) | v [d0, d1,..., di-1]} и немультипликативной в противном случае.

1 k Определение 4. Разбиение Поммаре[9]. Для монома xd xd с dk > 0 пере1 k менные xj с j k считаются мультипликативными, а xj с j < k немультипликативными. Для u = 1M все переменные мультипликативные.

Применяя определение 1 можно построить еще два разбиения переменных.

Определение 5. Разбиение I. На U переменная xi немультипликативна для u U, если имеется v U такой, что 1 m xd xd u = lcm(u, v), 1 m [n/2], dj > 0 (1 j m), i1 im и xi {xi,..., xi }, и мультипликативна в противном случае.

1 m 1 n Определение 6. Разбиение II. Для монома u = xd xd переменная xi бу1 k дет мультипликативной если di = max{d1,..., dn} и немультипликативной в противном случае.

[8] Thomas, J. Differential Systems / J. Thomas. Ч American Mathematical Society, New York, 1937.

[5] Janet, M. Systmes dТquations aux drives partielles / M. Janet // Journals de mathmatiques, 8e srie. Ч 1920. Ч Vol. 3. Ч Pp. 65Ц151.

[9] Поммаре, Ж. Система уравнений с частными производными и псевдогруппы Ли / Ж. Поммаре. Ч М. Мир, 1983. Ч С. 400.

Замечание 7. Разбиения Томаса, I и II не зависят от упорядочения переменных xi. В отличии от них, разбиения Жане и Поммаре основаны на выбранном упорядочении переменных x1 x2 xn.

Разделение переменных на мультипликативные и немультипликативные в случае разбиений Томаса и Жане зависит от остальных мономов множества U.

Напротив, разбиения Поммаре и II не зависят от остальных мономов множества U и по этой причине называются глобальными.

Для обозначения рассматриваемых делений будем использовать сокращения T, J, P, I, II.

Пример 8. U = {xy, y2, z} (x y z).

Таблица 1. Разбиения Томаса, Жане, Поммаре, I и II MT N MT MJ N MJ MP N MP MI N MI MII N MII x2 x y, z x, y, z - x, y, z - x y, z x y, z xy y x, z y, z x y, z x y x, z x, y z z z x, y y, z x z x, y y, z x z x, y Предложение 9. Мономиальные деления Томаса, Жане, Поммаре, I, II являются инволютивными.

Определение 10. U называется инволютивно авторедуцированным по делению L или L-авторедуцированным, если это множество не содержит инволютивных делителей своих элементов кроме них самих.

Предложение 11. Инволютивное авторедуцированное множество может содержать не более одного инволютивного делителя для любого заданного монома.

Определение 12. Для заданного инволютивного деления L множество U называется инволютивным или L-инволютивным, если для любого u U, умноженного на любой моном, существует инволютивный делитель в U.

Определение 13. Обозначим через C(U) дискретный конус uUuM порожденный U. Множество uUuL(u, U) будем называть инволютивным конусом, порожденным U и записывать CL(U).

Определение 14. Инволютивное деление L называется нётеровым, если U является конечно порожденным относительно L.

Предложение 15. Для нётерового инволютивного деления L, каждый мономиальный идеал U имеет конечный инволютивный базис.

Предложение 16. Деления Томаса, Жане, I, II нётеровы.

Определение 17. Умножение u U на переменную x называется продолжением u. Для инволютивного деления, определенного на U, продолжение называется мультипликативным, если x мультипликативно для u и немультипликативным в другом случае.

Определение 18. U называется локально инволютивным относительно деления L, если (u U)(xi N ML(u, U))(v U) [v |L u xi]. (1) Определение 19. Инволютивное деление L будем называть непрерывным, если для любого конечного множества U и для любой конечной последовательности {ui}(1ik) элементов из U выполнено (i < k)(xj N ML(ui, U)) [ui+1 |L ui xj ui = uj для i = j]. (2) Теорема 20. Если инволютивное деление L непрерывно, то из локальной инволютивности любого U следует его инволютивность.

Следствие 21. Деления Томаса, Жане, Поммаре, I и II непрерывны.

Определение 22. Будем называть непрерывное инволютивное деление L конструктивным, если (v U)(xj N ML(v, U))(v xj u xi) [v xj uU u L(u, U)] и выполнены условия:

(w uU u L(u, U)) [u xi wL(w, U {w})]. (3) Предложение 23. Деления Томаса, Жане, Поммаре, I и II конструктивны.

Теорема 24. Для конструктивного деления L процедуру пополнения U до L-инволютивного множества U можно провести немультипликативными продолжениями его элементов.

Определение 25. На F мультипликативные и немультипликативные переменные для f F определяются по старшему моному lm(f) полинома f относительно и множеству lm(F ) старших мономов F.

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

Для записи L-нормальной формы f по модулю G введем обозначение NFL(f, G), а обычную нормальную гребнеровскую форму[2] будем записывать ввиде NF(f, G).

Определение 26. F называется инволютивно авторедуцированным по инволютивному делению L, или L-авторедуцированному, если множество lm(F ) является L-авторедуцированным и каждое f F не содержит мономов имеющих инволютивного делителя во множестве lm(F ).

Теорема 27. Если F L-авторедуцированно, то NFL(p, F ) = 0 тогда и только тогда, когда p представляет собой конечную сумму термов вида p SF R, SF = { fi uij | fi F, uij T } (4) ij с lm(uij) = lm(uik) для j = k.

Следствие 28. Если F L-авторедуцированно то, тогда L- нормальная форма для любых полиномов p1, p2 и p имеет следующие свойства:

1. Единственность: если h1 = NFL(p, F ) и h2 = NFL(p, F ) то, тогда h1 = h2.

2. Линейность: NFL(p1 + p2, F ) = NFL(p1, F ) + NFL(p2, F ).

Определение 29. L-авторедуцированное множество F называется L-инволютивным базисом идеала (F ), если (f F )(u M) [NFL(f u, F ) = 0]. (5) Следствие 30. Если множество F L-инволютивно, то p (F ) тогда и только тогда, когда NFL(p, F ) = 0. Также имеет место равенство SF = (F ).

Теорема 31. L-авторедуцированное множество F инволютивно относительно непрерывного деления L тогда и только тогда, когда выполнены следующие условия локальной инволютивности (f F )(xi N ML(lm(f), lm(F ))) [NFL(f xi, F ) = 0]. (6) Теорема 32. Если F является L-инволютивным, то имеет место равенство (p R) [NF(p, F ) = NFL(p, F )]. (7) Следствие 33. Инволютивный базис есть базис Грёбнера.

Предложение 34. Если инволютивное деление L нётерово, то тогда любой полиномиальный идеал (F ) имеет конечный L-инволютивный базис.

Следующая теорема дает инволютивную форму для цепного критерия Бухбергера Теорема 35. Пусть задано F L-авторедуцированное множество полиномов и g x - немультипликативное продолжение g F. Тогда NFL(g x, F ) = 0 если (h F )(u M) [lm(h) u lm(g x) NFL(h u, F ) = 0], (8) lm(f0) | lm(f), lm(g0) | lm(g) (f, f0, g0 F ). (9) lm(f) |L lm(g x), lcm(f0, g0) lm(g x) lt(f) lt(g) NFL f0 , F = NFL g0 , F = lt(f0) lt(g0) Алгоритм 1 InvolutiveBasis(F, , L) Вход: F конечное множество полиномов Выход: G инволютивный базис идеала (F ) 1: G := AutoReduce(F ) 2: T := 3: для всех g G 4: T := T {(g, lm(g), )} 5: пока существуют (g, u, P ) T и x N ML(lm(g), lm(G)) \ P 6: выбрать (g, u, P ) и x с наименьшим lm(g) x относительно 7: T := T \ {(g, u, P )} {(g, u, P {x})} 8: если существует f (f, v, D) T такое, что lm(f) |L lm(g x) то 9: если lcm(u, v) = lm(g) x то 10: h := NFL(g x, G) 11: если h = 0 то 12: T := T {(h, lm(h), )} 13: иначе 14: h := NFL(g x, G) 15: T := T {(h, u, )} 16: G := AutoReduceL(G {h}) 17: Q := T 18: T := 19: для всех g G 20: если существует (f, u, P ) Q такой, что lm(f) = lm(g) то 21: выбрать g1 G такое, что lm(g1) |L u 22: T := T {(g, lm(g1), P )} 23: иначе 24: T := T {(g, lm(g), )} Алгоритм 1 был включен с именем INVBASE в стандартную библиотеку системы Reduce, начиная с версии 3.5.

Определение 36. Немультипликативная степень. Разобьем U на подмножества аналогично определению 3. Для каждого u U и 1 i n рассмотрим hi(u, U) Z0 определенного по формуле hi(u, U) = max{degi(v) | u, v [d0,..., di-1]} - degi(u).

i Если hi(u, U) > 0, то тогда степень xk, где i ki = min{degi(v) - degi(u) | v, u [d0,..., di-1], degi(v) > degi(u)} будем называть немультипликативной степенью для u.

Будем обозначать через N MP(u, U) все немультипликативные степени для u U.

Определение 37. Степенное деление Жане. Для u U элементы моноида N M(u, U) = {v M | (w N MP(u, U)) [w | v]} (10) будем называть JL-немножителями, а элементы MP(u, U) = M \ N M(u, U) соответственно JL-множителями. u будем называть степенным делителям Жане или JL-делителем монома w M и записывать u |J w, если w = u v L с v MP(u, U).

Предложение 38. Для U с элементом u U и w M из делимости по Жане w на u следует делимость по степенному делению Жане. В общем случае, обратное неверно.

Предложение 39. Моном w не может иметь два различных JL-делителя на любом множестве мономов.

Для степенного деления Жане в диссертации показано выполнение алгоритмических свойств: непрерывности, нётеровости и конструктивности.

Во второй главе для канонического представления инволютивных базисов введено понятие минимального инволютивного базиса. Разработаны алгоритмы его построения и доказаны их корректность и завершаемость. Для быстрого поиска инволютивного делителя для деления Жане разработана структура дерево УЖанеФ. Разработаны алгоритмы его построения и модификации, и доказаны их корректность и завершаемость. Сделано обобщение структуры Удерево ЖанеФ на произвольное инволютивное деление с помощью метода сепарирующих мономов. Разработаны специализированные алгоритмы для деления Жане, степенного деления Жане, торических идеалов и для допустимых упорядочений совместимых со степенью. Доказаны их корректность и завершаемость.

Определение 40. L-инволютивный базис U будем называть минимальным, если для любого другого L-инволютивного базиса V (U) выполнено включение U V.

Предложение 41. Пусть L конструктивное инволютивное деление определенное на U, то тогда (U) имеет минимальный L-инволютивный базис.

Определение 42. Пусть L конструктивное инволютивное деление, инволютивный базис G идеала (G) будем называть минимальным, если lm(G) минимальный L-инволютивный базис мономиального идеала, порожденного {lm(f) | f (G)}.

Пусть даны F и конструктивное инволютивное деление L. Тогда для совместимого со степенью допустимого упорядочения, представленный в диссертации алгоритм, строит минимальный инволютивный базис (F ) если этот базис конечен. В случае нётеровости инволютивного деления L алгоритм строит базис для любого допустимого упорядочения.

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

Определение 43. w называется сепарирующим для V U и заданного инволютивного деления L если он удовлетворяет следующим условиям:

1. V = V1 V2, V1 = и V2 = ;

2. u V1, v uL(u, U), то тогда w v;

3. u V2, v uL(u, U), то тогда w | v.

Поскольку условие 3 является отрицанием условия 2 для множеств V1, V2, из определения 43 следует V1 V2 = .

На приведенных ниже рисунках показаны сепарирующие мономы для делений Томаса и Жане для U = {x2y, xz, y3, yz, z2} с порядком переменных x y z. Мономы, расположенные в листьях, принадлежат исходному множеству. Согласно определению 43 моном расположенный в вершине является сепарирующем. Для всех мономов в листьях в его правом поддереве не может находиться инволютивный делитель монома, который имеет делителем в обычном смысле моном, расположенный в вершине.

y yyx yxxy xy yx2y zzyz xz xz x2y zzРис. 1. Пример деревьев для деления Томаса и Жане Теорема 44. При выполнении условий определения 43 следующие два утверждения равносильны:

1. u V2 и v, то тогда w | v и v uL(u, U);

2. u V2 и ( w1, w2) w = w1w2 следует w1 L(u, U) и w2 u.

Данная теорема дает конструктивный метод нахождения сепарирующих мономов. Введем следующие обозначение: gcd(uL(u, U), w) = v если (v uL(u, U), v | w) и (s uL(u, U), s | w) следует, что s | v.

Следствие 45. При выполнении условий определения 43 необходимо и достаточно:

1. (u V1) gcd(uL(u, U), w) = w;

2. (u V2) gcd(uL(u, U), w) = w.

Для некоторых видов инволютивных делений возможно построение специализированных деревьев поиска. По определению 3 деления Жане множество мономов U разбивается на группы. На рис. 2 показано бинарное дерево, которое будем называть деревом Жане. Его структура отражает разделение элементов в U на группы, которые отсортированы по степенях переменных в пределах каждой группы. Такая структура данных позволяет эффективно искать делитель Жане и вычислять мультипликативные переменные для элементов U.

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

xxx1yxxz x2y x0yx0yzyz yРис. 2. Пример дерева Жане (в вершинах мономы) В отличии от метода сепарирующих мономов, моном расположенный в вершине должен быть равен вплоть до текущей переменной, моному, для которого ищется делитель Жане. Равенство подмонома означает движение направо: если степень меньше, то делителя нет, а если степень монома, для которого ищется делитель Жане, больше, то движение налево.

Теорема 46. Пусть d - максимальная полная степень мономов от n переменных, из которых состоит конечное множество U. Тогда временная сложность алгоритма поиска по Удереву ЖанеФ и алгоритма бинарного поиска может быть выражена следующим образом tJ -divisor(U) = O(d + n), tBinarySearch(U) = O(n((d + n) log(d + n) - n log(n) - d log(d))).

Для степенного деления Жане алгоритм поиска делителя совпадает с алгоритмом поиска по Удереву ЖанеФ. Поскольку при построении торических идеалов, возникающих например в задачах целочисленного линейного программирования, отсутствует целочисленная арифметика, применение Удеревьев ЖанеФ для степенного деления значительно сокращает время вычислений.

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

Система компьютерной алгебры GINV (сокращение от Grbner INVolutive), разработанная для исследования и решения систем алгебраических, дифференциальных и разностных уравнений полиномиального типа методами их приведения в инволюцию. В основе системы лежат авторские алгоритмы построения инволютивных базисов Жане и степенных базисов Жане для полиномиальных идеалов и модулей, а также приведенных базисов Грёбнера. GINV состоит из библиотеки программ на языке C++, являющейся модулем языка Python.

GINV доступен на сайте распространяется на условиях GPL v2.

Из внешних библиотек используется кроссплатформенная библиотека GMP для арифметики целых, рациональных и чисел с плавающей точкой произвольной точности. Документация системы GINV состоит из Уруководства пользователяФ и Уруководства разработчикаФ. Первая из них построена с помощью стандартных средств для документирования модулей языка Python, а вторая с помощью системы Doxygen. Документация поддерживается на двух языках, русском и английском, и доступна на сайте форматах pdf и html. Руководство разработчика содержит более 1000 страниц формата A4.

Алгоритмы построения базисов Грёбнера имеют экспоненциальную сложность как по времени выполнения, так и по требуемой памяти. Поэтому, при реализации этих алгоритмов бывает трудно соблюсти их универсальность, не забывая при этом об эффективности. Как показывает сравнение GINV с реализацией на C этого удалось достичь. Сравнение результатов расчета c последней версией GINV доступны на вышеуказанном сайте.

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

0..n AbstractClass AbstractInterface # m Realization Int er af ce>

Допустимые порядки на мономах можно разделить на следующие группы:

Исключающие упорядочения: Lex, Elim, PosElim, PotLex, PotDegRevLex, TopLex и TopElim.

Упорядочения, совместимые с полной степенью: DegRevLex, TopDegRevLex, DegRevLexByte и TopDegRevLexByte.

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

В названии групп для коэффициентов используются следующие обозначения: Z - целые числа, Q - рациональные числа, ModularShort - числа по модулю (квадрат модуля при этом умещается в машинное слово), Gmp - используется библиотека GMP, AlgebraicFieldExtension - расширение алгебраического поля задаваемое многочленом, One - один параметр, Two - два параметра, N - n параметров.

Коэффициенты можно разделить по их алгебраическим свойствам.

Поле: GmpQ, ModularShort, AlgebraicFieldExtensionGmpQ и AlgebraicFieldExtensionModularShort.

Кольцо: GmpZ, OneParameterGmpZ, OneParameterModularShort, TwoParameterGmpZ, TwoParameterModularShort, NParameterGmpZ и NParameterModularShort.

Четвертая глава посвящена исследование математических моделей.

В диссертации предлагается новый подход к построению разностных схем, основанный на построение переопределенной системы разностных уравнений, получаемой из апроксимации интегральных законов сохранения и интегральных соотношений связывающих искомые функции и их производные. Разностная схема определяется как условие совместности для данной системы.

Этот метод позволил обобщить метод конечных объемов, схемы Лакса и Лакса-Вендроффа. Продемонстрировал возможность построения многошаговых схем и схем с переключателями. Для уравнения околозвуковых течений Кармана-Фальковича получена схема с единым шаблоном в эллиптической и гиперболической области без схемной вязкости и переключателей. При одномерном течении в канале с прямым скачком уплотнения зона ударного перехода имеет протяженность порядка шага сетки.

Рассмотрим применение техника базисов Грёбнера для генерации схем типа Лакса на примере уравнения Бюргерса ut + fx = uxx, = const (11) Применяя в качестве метода интегрирования квадратурную формулу прямоугольников со средней точкой по переменной x и явную формулу интегрирования по переменной t, получим следующую систему разностных соотношений для уравнения (11) и интегральных связей функций и их производных ut n + fx n = uxx n j j j ut n = un+1 - un j j j (12) 2fx n h = fjn - fjn j+1 + 2ux n h = un - un j+1 j+2 j 2uxx n h = ux n - ux n.

j+1 j+2 j Здесь h = h2 - h1, = 2 - 1 - шаги по переменным x и t, а n, j номера узлов сетки по x и t соответственно. Через u обозначенно место для замены Лакса. Заменяя во втором уравнении в системе (12) значение u с предыдущего временного слоя средним значением соседних точек по оси x, получим систему разностных соотношений для вывода схемы типа Лакса ut n + fx n = uxx n j j j un +un j+2 j ut n = un+1 j j (13) 2fx n h = fjn - fjn j+1 + 2ux n h = un - un j+1 j+2 j 2uxx n h = ux n - ux n.

j+1 j+2 j Выбирая допустимое упорядочение для функций uxx ux ut fx u f с позицией старше терма, получим в качестве элемента базиса Грёбнера разностное соотношение 2un+1 - (un + un ) fjn - fjn un - 2un + un j+2 j+3 j+1 +3 +1 j+4 j+2 j + = (14) 2 2h 4hсодержащие только искомые функции u и f. Соотношение (14) является классической схемой Лакса для уравнения (11).

В предложенном подходе для вывода схемы типа Лакса его основным элементом была замена во втором уравнении в системе (13) значения u с предыдущего временного слоя средним значением соседних точек по оси x. Применяя в качестве квадратурной формулы для восстановления производной по x, например, формулу трапеций, можно получить другие разностные схемы. Поскольку в системе (13) интегрирование по переменной x применяется для разностных производных uxx, ux, fx общее количество различных вариантов равно 8 с различными схемами.

Газовая динамика рассматривает теорию трансзвуковых течений, когда характерное число Маха M мало отличается от 1. Двумерное нестационарное течение невязкого газа в околозвуковом приближении может быть описано потенциалом скорости , который удовлетворяет уравнению КарманаЦФальковича[10] xx(K - ( + 1)x) + yy = 0, где x, y Цдекартовы координаты, K = (1 - M)-2/3 - параметр трансзвукового подобия, - характерный угол наклона вектора скорости к невозмущенному потоку, > 1 - показатель адиабаты. Уравнение КарманаЦФальковича относится к смешанному типу: эллиптическому при K > ( + 1)x и гиперболическому при K > ( + 1)x.

В нестационарном варианте при медленном изменении параметров потока по времени t уравнение КарманаЦФальковича переходит в уравнение ЛиняЦРейснераЦТзяна[11,12] 2xt + xx(K - ( + 1)x) + yy = 0.

Это уравнение линейной заменой координат легко свести[13,14] к уравнениям газовой динамики:Укоротких волнФ и нелинейной акустики.

Представим уравнение ЛиняЦРейснераЦТзяна в интегральной форме для построения разностной схемы, позволяющей решать нелинейное уравнение Кар[10] von Karman, T. Collected works / T. von Karman. Ч Von Karman Institute, Rhode St. Genese, 1975.

[11] Lun, C. C. Non-steady motion of a slender body in a compressible fluid / C. C. Lun, E. Reissner, H. S. Tslen // Journal of Mathematic and Physics. Ч 1948. Ч Vol. 27, no. 3.

[12] Тзян, Х. Ш. О двумерном неустановившимся движении тонкого тела в сжимаемой жидкости / Х. Ш. Тзян, Ц. Ц. Лин, Е. Рейснер // Газовая динамика. Ч М. Мир, 1950. Ч С. 181Ц196.

[13] Блинков, Ю. А. Редукция нестационарного трансзвукового уравнения к квазистационарному / Ю. А. Блинков, И. А. Чернов // Аэродинамика: Нелинейные проблемы. Межвуз. науч. сб. Ч 1988. Ч Т. 11(14). Ч С. 110Ц131.

[14] Фущич, В. И. Точные решения некоторых уравнений газовой динамики и нелинейной акустики / В. И.

Фущич, В. К. Репета // Scientific Works. Ч 2002. Ч Vol. 4. Ч Pp. 267Ц273.

манаЦФальковича методом установления.

t n+ tj+tn+1 yk+ ( + 1) -ydx + x(K - x)dydt - (2x + t) dxdy = 0. (15) tn xj yk tn Добавляя интегральные соотношения и используя для интегрирования формулу трапеций для x, y, а также формулу среднего значения для t получим в операторной форме для уравнения (15) соотношения (+1) (-(Tx - TxTy2) y + (Tx Ty - Ty) (Kx - 2)) 2 h t x -(Tt - 1)(TxTy - Ty) 2 2 h - TxTy t 4 h2 = h.

(Tx + 1) x = (Tx - 1) h (Ty + 1) y = (Ty - 1) Tt t 2 t = (Tt2 - 1) Выбирая допустимое лексикографическое упорядочение сначала по функциям x y t , затем по переменным Tx Ty Tt, построим базис Грёбнера, последнее уравнение которого, является искомой разностной схемой:

(+1) (n - 2n + n ) [((n - 2n + n )(K - (n j+1 k j k j-1 k j k j-1 k j-2 k j+1 k t -n + n - n ) + (n - 2n + n )) hj k j-1 k j-2 k j-1 k+1 j-1 k j-1 k- h (n+1 - n+1 - n + n ) - (n+1 - 2n + n-1 )2 t]+ j k j-2 k j k j-2 k j-1 k j-1 k j-1 k (16) (+1) (n - 2n + n ) [((n - 2n + n )(K - (n j k j-1 k j-2 k j+1 k j k j-1 k j+1 k t -n + n - n ) + (n - 2n + n )) hj k j-1 k j-2 k j k+1 j k j k- h (n+1 - n+1 - n + n ) - (n+1 - 2n + n-1)2 t] = 0.

j+1 k j-1 k j+1 k j-1 k j k j k j k Заметим, что разностная схема (16) обладает полной консервативностью по построению и не содержит переключателей обычно используемых при расчете трансзвуковых течений[15].

Рассмотрим в качестве примера одномерное течение в канале с прямым скачком уплотнения с результатом расчета приведенным на рисунке 4. Полученные [15] Jameson, A. Transonic flow calculations / A. Jameson // Numerical Methods in Fluid Dynamics / Ed. by H. J.

Wirz, J. J. Smolderen. Ч Hemisphere, 1976. Ч Vol. 87 of von Karman Institute for Fluid Dynamics Lecture Series. Ч Pp. 1Ц87.

0.0.0.0 0.2 0.4 0.6 0.8 x x toqnoe rexenie naqal noe pribli enie rexenie poluqennoe metodom ustanovleni Рис. 4. Решение задачи с одномерной ударной волной результаты показывают принципиальную возможность построения разностных схем для расчета трансзуковых течений газа без переключателей и с единым шаблоном в до- и сверхзвуковых областях.

огистическое отображение является является дискретным аналогом непрерывного логистического уравнения Ферхюльста xn+1 = xn(1 - xn), (17) Логистическое отображение (17) отражает тот факт, что прирост популяции происходит в дискретные моменты времени.

Нахождение таких значений при которых возникает смена поведения логистического отображения является сложной вычислительной задачей[7]. Она [7] Kotsireas, I. S. Exact computation of the bifurcation point b4 of the logistic map and the bailey-broadhurst conjectures / I. S. Kotsireas, K. Karamanos // Journal Bifurcation and Chaos. Ч 2004. Ч Vol. 14. Ч Pp. 2417Ц2423.

( x ) ( x ) может быть описана следующей системой уравнений x2 = x1(1 - x1) x3 = x2(1 - x2) ...

(18) xn = xn-1(1 - xn-1) x1 = xn(1 - xn) n n (1 - 2xk) = 1.

k=Для решения системы 18 можно построить базис Грёбнера, а затем, используя тот факт, что система имеет конечное число корней, средствами линейной алгебры получить полином от переменной . Нахождение действительных корней полинома представляет собой, с вычислительной точки зрения, значительно более простую задачу.

С помощью системы GINV было впервые найдено значение = 3.687196...

при котором возникает бифуркация для n = 9.

В заключении сформулированы основные результаты, выносимые на защиту.

В приложении приведено УРуководство пользователяФ специализированной системы компьютерной алгебры GINV.

УИНВОЛЮТИВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОДЕЛЕЙ, ОПИСЫВАЕМЫХ СИСТЕМАМИ АЛГЕБРАИЧЕСКИХ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙФ Аннотация В работе для целей исследования математических моделей, описываемых системами алгебраических, дифференциальных, а в некоторых случаях и разностных уравнений, излагается теория модифицированных базисов Гребнера, названных инволютивными и ориентированных на указанные исследования.

Для повышения эффективности вычислений разработан новый алгоритмический подход к построению базисов Грёбнера, альтернативный классическому методу Бухбергера. В его основе лежит новое математическое понятие Ч инволютивное деление мономов. Это понятие обобщает известные в литературе разделения переменных, используемые для приведения в инволюцию дифференциальных систем.

Описываемые в работе методы позволяют эффективно проверять совместность, исследовать структуру пространства решений, а в ряде случаев находить и сами решения рассматриваемых систем уравнений. Разработанные оригинальные алгоритмы и типы данных для построения инволютивных базисов Гребнера реализованы в виде специализированной системы компьютерной алгебры GINV (Groebner INVolutive).

"INVOLUTIVE METHODS APPLIED TO MODELS DESCRIBED BY SYSTEMS OF ALGEBRAIC AND DIFFERENTIAL EQUATIONS" Abstract In the given paper to investigate mathematical models which are described by systems of algebraic, differential and in some cases by difference equations a theory of modified Grbner bases called involutive is presented. The involutive bases are oriented to the investigation indicated.

To increase efficiency of computation, a new algorithmic approach to construction of Grbner bases developed which is alternative to the>

The approach is based a new mathematical notion of involutive monomial division.

This notion generalizes partitions of variables used in the literature for completion of partial differential equation systems to involution.

The methods described in the paper allow effective verification of the consistence of a given system, to study the structure of its solution space, and in certain cases to find the solutions. The original algorithms and data structures for efficient construction of the involutive Grbner bases have been implemented in the specialpurpose computer algebra system GINV (Groebner INVolutive).

Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog

ИНВОЛЮТИВНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ МОДЕЛЕЙ, ОПИСЫВАЕМЫХ СИСТЕМАМИ АЛГЕБРАИЧЕСКИХ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ