Содержание
1 Введение 3
1.1 Актуальность темы............................................ 3
1.2 Цель работы ................................................. 3
1.3 Научная новизна.............................................. 4
1.4 Основные методы исследования ................................ 4
1.5 Практическая ценность........................................ 5
1.6 Апробация работы............................................. 5
1.7 Публикации................................................... 6
1.8 Структура и объем диссертации................................ 7
1.9 Благодарности................................................ 7
2 Основные понятия и обозначения 9
3 Классические результаты конструктивной дифференциальной алгебры 12
4 Канонические характеристические множества 13
4.1 Определения и свойства...................................... 13
4.2 Оценка порядка.............................................. 16
4.3 Оценка порядков в каноническом характеристическом множестве ........................................................... 25
5 Оценка числа дифференцирований в алгоритме ИоБег^еИ-
СгбЬпег 25
5.1 Введение.................................................... 25
5.2 Стандартный алгоритм РоБег^еИ-СгоЬпег....................... 27
5.3 Использование алгебраической редукции....................... 29
5.4 Модификация алгоритма....................................... 41
6 Заключение 58
2
1 Введение
1.1 Актуальность темы
За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также методов изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами. Настоящим прорывом в данной области стало появление базисов Гребнера и алгоритма их вычисления, предложенного Вухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному виду.
В данной работе мы имеем дело с алгебраическими дифференциальными уравнениями и теорией исключения для систем таких уравнений. Основной объект теории — радикальный дифференциальный идеал, порожденный заданной системой дифференциальных уравнений. Теория исключения для такого идеала состоит в его разложении в пересечение характеризуемых идеалов, представленных своими характеристическими множествами. Основной вопрос данной теории — оценка работы подобных алгоритмов разложения, в частности, их теоретической сложности.
На сегодняшний день результаты о порядках дифференцирований, которые присутствуют в характеристических множествах и производятся в ходе алгоритма характеристического разложения, нуждаются в систематизации и углублении. Кроме того, актуальной является и задача построения достаточно общей теории оценки порядков дифференцирований, без ограничения на обыкновенный случай.
1.2 Цель работы
Целью настоящей работы является исследование радикальных дифференциальных идеалов в кольцах дифференциальных многочленов. Более точно, оценить порядки характеристических множеств характеризуемых дифференциальных идеалов, возникающих в ходе разложения радикальных дифференциальных идеалов на характеризуемые компоненты. Эта задача успешно решена автором в данной работе.
3
1.3 Научная новизна
В диссертации получены следующие основные результаты:
1. Впервые получена оценка порядка дифференцирований для элементов, входящих в каноническое характеристическое множество характеризуемого дифференциального идеала.
2. Впервые получена оценка сверху на число дифференцирований, выполняемых алгоритмом РоБепГеЫ-СгбЬпег, который разлагает радикальный дифференциальный идеал на характеризуемые компоненты.
1.4 Основные методы исследования
В работе используются методы и результаты теории базисов Грсбнера, коммутативной алгебры, дифференциальной алгебры |21, 22, 28]. При исследо-ваниии канонических характеристических множеств характеризуемых дифференциальных идеалов используются и улучшаются результаты, полученные Ф. Булье, Д. Лазаром, Ф. Оливье и М. Петито [8, 9]. В диссертации приводится новое, более простое определение канонического характеристического множества, не ограничиваясь на случай характеризуемых идеалов.
Первые оценки на порядки характеристических множеств были получены Б. Садиком [29]. Эти результаты касались лишь исключающих ранжиров и простых дифференциальных идеалов. В диссертации же получены результаты, не имеющие таких ограничений: ранжиры допускаются любые, аидеалы должны быть лишь характеризуемыми дифференциальными. Простые дифференциальные идеалы таковыми являются. Для доказательства основных результатов о канонических характеристических множествах в диссертации также используются утверждения, доказанные Э. Юбер [18]:
• о связи между характеристическим множеством характеризуемого дифференциального идеала и характеристическими множествами его минимальных дифференциашных простых компонент;
• о соответствии между характеристическим разложением регулярного дифференциального и регулярного алгебраического идеалов.
Для получения оценки на порядки для ашоритма разложения радикального дифференциального идеала на характеризуемые компоненты в диссертации испол1>зуются и улучшаются методы Дж. Ф. Ритта [28], которые были им разработаны для:
4
• систем линейных дифференциальных уравнений с частными производными и
• обыкновенных систем из двух алгебраических дифференциальных уравнений.
В диссертации приводится оценка порядка дифференцирований в обыкновенном случае, но допускается любое число уравнений в системе.
1.5 Практическая ценность
Диссертация имеет как теоретический, так и прикладной характер. Данная работа закладывает основы для детального анализа производительности алгоритмов дифференциальной алгебры. Полученная верхняя оценка на порядок дифференцирований, имеющихся на выходе алгоритма Rosenfeld-Grobner, может позволить получить верхнюю оценку на число операций, производимых данным алгоритмом, пользуясь оценками на число операций в чисто алгебраическом случае.
Также получена оценка на порядки элементов канонического характеристического множества характеризуемого идеала. Эта оценка позволила получить новый алгоритм преобразования характеристического разложения радикального дифференциального идеала от одного ранжира к другому [17]. Подобный алгоритм может быть реализован на компьютере, например, в системе компьютерной алгебры MAPLE. Предыдущие исследования по. этому вопросу проводились Ф. Булье, Ф. Лемэром, М. Морено Маза [11] и О. Голуби цким [16].
Результаты диссертации могут быть полезны специалистам, которые исследуют алгоритмические проблемы алгебраических дифференциальных уравнений и используют методы конструктивной дифференциальной алгебры.
1.6 Апробация работы
Основные результаты диссертации докладывались на
• на семинаре по компьютерной алгебре на Механико-математическом факультете МГУ в 2003-2007 годах,
5
• на конференции «Компьютерная алгебра и ее приложения в физике» (СААР) и семинарах по компьютерной алгебре в 2001-2007 годах в Дубне,
• Международной алгебраической конференции, посвященной 250-летию МГУ и 75-летию кафедры высшей алгебры в МГУ в 2004 году,
• международной конференции «Приложения компьютерной алгебры» в
2003 года (Роли, Северная Каролина) и 2004 году (Бомонт, Техас),
• международной конференции «Компьютерная алгебра в научных вычислениях» в 2002 голу (Ялта, Крым) и в 2004 года (Санкт-Петербург),
• Колчинском семинаре по дифференциальной алгебре (Ныо-Йорк) в
2004 и 2005 годах,
• конференции по дифференциальной алгебре в Университете Линца (RISC), Австрия, в 2006 году,
• конференции по алгебраическим методам в дифференциальных уравнениях (Эдинбург, Шотландия) в 2006 года
1.7 Публикации
Результаты диссертации опубликованы в следующих работах:
1. А.И. Овчинников, Порядки дифференцирований в разлоэюении радикальных дифференциальных идеалов, Успехи математических наук 63 (2) (2008) 179-180 [5]
2. О.Д.. Голубицкий, М.В. Кондратьева и А.И. Овчинников, Канонические характеристические мпооюества характеризуемых дифференциальных идеалов, Вестник МГУ. Математика, 2 (2008) 49-51 [1]
3. М.В. Кондратьева, А.И. Овчинников, Характеристические множества обыкновенный; дифференциальных уравнений, Программирование 2 (2005) 56 -63 [2)
4. M.V. Kondratieva, A. Ovchinnikov, On Computing Characteristic Sets of Arbitrary Radical Differential Ideals, в трудах конференции Applications of Computer Algebra 2004 (АСА 2004) 38-48 [27]
6
- Київ+380960830922