Инволютивные методы исследования моделей, описываемых системами алгебраических и дифференциальных уравнений Блинков Юрий Анатольевич

Введение к работе

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

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

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

[1] Самарский, А. А. Математическое моделирование: Идеи. Методы. Примеры. / А. А. Самарский, А. П.

Михайлов. — 2-е, исправленное изд. — Физматлит, 2001. — С. 320. [2] Бухбергер, Б. Базисы Грёбнера. Алгоритмический метод в теории полиномиальных идеалов / Б. Бухбер-

гер // Компьютерная алгебра. Символьные и алгебраические вычисления.— М. Мир, 1986.— С. 331-372.

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

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

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

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

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

[3] Buchberger, В. Grobner Bases and Applications / В. Buchberger, F. Winkler. — Cambridge University Press, 1998.

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

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

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

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

2. Разработан алгоритм построения минимальных инволютивных базисов,

[4] Riquier, С. Les Systemes d'Equations aux Derivees Partielles / C. Riquier. — Gauthier-Villars, Paris, 1910.

[5] Janet, M. Systemes d'equations aux derivees partielles / M. Janet // Journals de mathematiques, 8e serie. — 1920.-Vol. 3.-Pp. 65-151.

[6] The database of polynomial systems, .

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

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

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

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

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

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

8. Для логистического отображения найдено значения параметра /і, при котором происходит образование 9-й периодических циклов. До настоящего времени^ были найдены значения до п < 8.

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

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

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

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

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

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

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

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

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

'Объединенный институт ядерных исследований (Дубна, Россия) ²Рейнско-Вестфальский технический университет (Ахен, Германия)

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

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

4. Создана специализированная система компьютерной алгебры GINV с открытым кодом, написанная на языке C++ и организованная в виде модуля языка 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 г.; Sankt-Augustin, Германия, 1998 г.; Mannheim, Германия, 2002 г.; Basel, Германия, 2006 г.); на Международной конференции "Приложения компьютерной алгебры IMACS/ACA" (Санкт-Петербург, Россия, 2000 г.); в Высшей технической школе Рейна-Вестфалии RWTH (Аахен, Германия, 2001, 2003, 2006 гг.); на Международной конференции "Компьютерная алгебра и ее приложения в физике СААР'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.

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

8. Gerdt, V. P. Involutive bases of polynomial ideals / V. P. Gerdt, Yu. A. Blinkov II Mathematics and Computers in Simulation. — 1998. — Vol. 45. — Pp. 519-542.

9. 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 Grobner 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 наименование.

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

Качественные и численные методы исследования математических моделей динамических систем, описываемых дифференциальными уравнениями с почти периодическими коэффициентамиПронькин Валентин Семенович

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

Разработка и исследование методов программного моделирования устойчивости систем линейных дифференциальных уравнений на основе матричных мультипликативных преобразований разностных схемБуланов Сергей Георгиевич

Теоретические и вычислительные аспекты исследования одного варианта метода прямых для системы моментных уравнений переноса заряда в полупроводникахИбрагимова Алеся Сергеевна

Применение метода моментных уравнений для построения и исследования устойчивости математических моделей со случайными параметрамиБанько Мария Анатольевна

Методы продолжения по параметрам и комплексы программ для численного исследования нелинейных многопараметрических моделей микропроцессов, описываемых волновыми уравнениямиЗемляная Елена Валериевна

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

Спектральные методы исследования математических моделей электромеханических систем, включающих звенья с распределенными параметрамиПирожков Станислав Леонидович

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

Аналитически-численный метод исследования математических моделей динамических систем с распределёнными параметрамиШумаков, Александр Александрович