Алгоритмические методы в дифференциальной теории идеалов

• Автор: Овчинников, Алексей Игоревич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 61 с.

1 Введение

1.1 Актуальность темы

1.2 Цель работы

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

1.4 Основные методы исследования

1.5 Практическая ценность

1.6 Апробация работы

1.7 Публикации

1.8 Структура и объем диссертации

1.9 Благодарности

2 Основные понятия и обозначения

3 Классические результаты конструктивной дифференциальной алгебры
4 Канонические характеристические множества
4.1 Определения и свойства
4.2 Оценка порядка
4.3 Оценка порядков в каноническом характеристическом множестве
5 Оценка числа дифференцирований в алгоритме ЯоьепБеИбгоЬпег
5.1 Введение
5.2 Стандартный алгоритм ПоьеМеИ-СгоЬпег
5.3 Использование алгебраической редукции
5.4 Модификация алгоритма
6 Заключение

1 Введение
1.1 Актуальность темы
За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также методов изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами. Настоящим прорывом в данной области стало появление базисов Гребнера и алгоритма их вычисления, предложенного Бухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному виду.
В данной работе мы имеем дело с алгебраическими дифференциальными уравнениями и теорией исключения для систем таких уравнений. Основной объект теории — радикальный дифференциальный идеал, порожденный заданной системой дифференциальных уравнений. Теория исключения для такого идеала состоит в его разложении в пересечение характеризуемых идеалов, представленных своими характеристическими множествами. Основной вопрос данной теории — оценка работы подобных алгоритмов разложения, в частности, их теоретической сложности.
На сегодняшний день результаты о порядках дифференцирований, которые присутствуют в характеристических множествах и производятся в ходе алгоритма характеристического разложения, нуждаются в систематизации и углублении. Кроме того, актуальной является и задача построения достаточно общей теории оценки порядков дифференцирований, без ограничения на обыкновенный случай.
1.2 Цель работы
Целью настоящей работы является исследование радикальных дифференциальных идеалов в кольцах дифференциальных многочленов. Более точно, оценить порядки характеристических множеств характеризуемых дифференциальных идеалов, возникающих в ходе разложения радикальных дифференциальных идеалов на характеризуемые компоненты. Эта задача успешно решена автором в данной работе.

1.3 Научная новизна
В диссертации получены следующие основные результаты:
1. Впервые получена оценка порядка дифференцирований для элементов, входящих в каноническое характеристическое множество характеризуемого дифференциального идеала.
2. Впервые получена оценка сверху на число дифференцирований, выполняемых алгоритмом БозегФеЫ-СгбЬпег, который разлагает радикальный дифференциальный идеал на характеризуемые компоненты.
1.4 Основные методы исследования
В работе используются методы и результаты теории базисов Гребнера, коммутативной алгебры, дифференциальной алгебры [21, 22, 28]. При исследо-ваниии канонических характеристических множеств характеризуемых дифференциальных идеалов используются и улучшаются результаты, полученные Ф. Булье, Д. Лазаром, Ф. Оливье и М. Петито [8, 9]. В диссертации приводится новое, более простое определение канонического характеристического множества, не ограничиваясь на случай характеризуемых идеалов.
Первые оценки на порядки характеристических множеств были получены Б. Садиком [29]. Эти результаты касались лишь исключающих ранжиров и простых дифференциальных идеалов. В диссертации же получены результаты, не имеющие таких ограничений: ранжиры допускаются любые, а идеалы должны быть лишь характеризуемыми дифференциальными. Простые дифференциальные идеалы таковыми являются. Для доказательства основных результатов о канонических характеристических множествах в диссертации также используются утверждения, доказанные Э. Юбер [18]:
• о связи между характеристическим множеством характеризуемого дифференциального идеала и характеристическими множествами его минимальных дифференциальных простых компонент;
• о соответствии между характеристическим разложением регулярного дифференциального и регулярного алгебраического идеалов.
Для получения оценки на порядки для алгоритма разложения радикального дифференциального идеала на характеризуемые компоненты в диссертации используются и улучшаются методы Дж. Ф. Ритта [28], которые были им разработаны для:

Собирая (30) и (31), мы получаем, что
к п
М1ус(ЯиВ°иЯ) = (п-к)^2^+ ^ т* (^иВ°и Й) <
г=1 г=&+1
к п
^ (п — к) с?г + пц (С? и В и Я)
г=1 г=£+1
£ п
^ (тг — &) <1{ + т, (С и С и Д”) +
г=1 г=Ы

+ (п-к) 5^(т,- (С и С и Я) - <*,-)

А: гг
= (гг - Л) ^ т* (С и С и Я) + тг- (в и С и Я) = 1=1 «=&+1
= м1уС(с?исия)
и если к = п, то

м (я и в0 и Я) = ^ <& + о = м (с и с и я),

так как гкС = гкВ0. Таким образом,
М1уС(ЯиВ°иЯ) <М!уе(Си€иЯ), к < п
М (Я и В0 и Я) ^ М {в и С и Я) , к = п. 1 }
Применяя теперь (27), (28) или (29) с К = (7иСиЯ = ЯиСиЯ, мы получаем
М1ус (Я и В0 и Я) ^ М1уС(ЯиСиЯ), I = к < п
м1уС (я и в° и Я) ^ (п - I - 1 )МЫС (я и в° и Я) <
^ (гг — I — 1) • М1Ус(Я и С и Я), I < к < п
м (я ив0 и я) <м(сисия)
= м(я и с и Я)
^ М1Ус(ЯиСиЯ), I < к — п
м(яи®°ия) ^м(си<сия)
= м(яисия), I — к — п.
Принимая во внимание то, что инвариант 15 выполнен для тройки (Я, С, Я), мы таким образом получаем этот инвариант для тройки (Я,В0,Я).