WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 |
Московский государственный университет имени М.В. Ломоносова Механико-математический факультет

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

УДК 512.628.2+519.688 Овчинников Алексей Игоревич Алгоритмические методы в дифференциальной теории идеалов 01.01.06 математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Москва 2008

Работа выполнена на кафедре высшей алгебры Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научные руководители: кандидат физико-математических наук, ведущий научный сотрудник Евгений Васильевич Панкратьев кандидат физико-математических наук, старший научный сотрудник Марина Владимировна Кондратьева

Официальные оппоненты: доктор физико-математических наук, профессор Александр Александрович Михалев кандидат физико-математических наук, доцент Ирина Николаевна Балаба

Ведущая организация: Вычислительный центр им. А.А. Дородницына РАН

Защита диссертации состоится 23 мая 2008 г. в 16 ч. 40 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, Московский Государственный Университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 23 апреля 2008 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор А.О. Иванов

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

Актуальность темы За последние десятилетия был достигнут значительный прогресс в области компьютерной алгебры, одной из приоритетных задач которой является развитие методов решения систем нелинейных алгебраических уравнений от нескольких переменных, а также методов изучения алгебраических идеалов, порожденных нелинейными полиномиальными системами. Настоящим прорывом в данной области стало появление базисов Гребнера и алгоритма их вычисления, предложенного Бухбергером еще в середине 60-х годов. Теория исключений, использовавшаяся ранее для решения систем, оказалась частью новой теории, позволяющей приводить произвольную систему уравнений к стандартному виду.

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

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

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

Эта задача успешно решена автором в данной работе.

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

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

2. Впервые получена оценка сверху на число дифференцирований, выполняемых алгоритмом Rosenfeld-Grbner, который разлагает радикальный дифференциальный идеал на характеризуемые компоненты.

Основные методы исследования В работе используются методы и результаты теории базисов Гребнера, коммутативной алгебры, дифференциальной алгебры1,2,3. При исследованиии канонических характеристических множеств характеризуемых дифференциальных идеалов используются и улучшаются результаты, полученные Ф. Булье, Д. Лазаром, Ф. Оливье и М. Петито4,5. В диссертации приводится новое, более простое определение канонического характеристического множества, не ограничиваясь на случай характеризуемых идеалов.

Первые оценки на порядки характеристических множеств были получены Б. Садиком6. Эти результаты касались лишь исключающих ранжиров и простых дифференциальных идеалов. В диссертации же получены результаты, не имеющие таких ограничений: ранжиры допускаются любые, а идеалы должны быть лишь характеризуемыми дифференциальными. Простые дифференциальные идеалы таковыми являются. Для доказательства основных результатов о канонических характеристических множествах в диссертации также используются утверждения, доказанные Э. Юбер7 о связи между характеристическим множеством характеризуемого дифференциального идеала и характеристическими множествами его минимальE. Kolchin, Differential Algebra and Algebraic Groups. Academic Press, New York, 1973.

M. Kondratieva, A. Levin, A. Mikhalev, and E. Pankratiev, Differential and difference dimension polynomials. Kluwer Academic Publisher, 1999.

J. Ritt, Differential Algebra. American Mathematical Society, New York, 1950.

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot, Representation for the radical of a finitely generated differential ideal. In Proceedings of ISSAC 1995, pages 158–166. ACM Press, 1995.

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot, Computing representations for radicals of finitely generated differential ideals. Technical report, IT-306, LIFL, 1997.

B. Sadik, A bound for the order of characteristic set elements of an ordinary prime differential ideal and some applications. Applicable Algebra in Engineering, Communication and Computing, 10(3):251–268, 2000.

E. Hubert, Factorization-free decomposition algorithms in differential algebra. Journal of Symbolic Computation, 29(4-5):641–662, 2000.

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

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

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

Также получена оценка на порядки элементов канонического характеристического множества характеризуемого идеала. Эта оценка позволила получить новый алгоритм преобразования характеристического разложения радикального дифференциального идеала от одного ранжира к другому8. Подобный алгоритм может быть реализован на компьютере, например, в системе компьютерной алгебры Maple. Предыдущие исследования по этому вопросу проводились Ф. Булье, Ф. Лемэром, М. Морено Маза9 и О. Голубицким10.

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

O. Golubitsky, M. Kondratieva, and A. Ovchinnikov. Algebraic transformation of differential characteristic decompositions from one ranking into another. Submitted for publication, 2007.

F. Boulier, F. Lemaire, and M. Moreno-Maza, PARDI! In Proceedings of ISSAC 2001, pages 38–47. ACM Press, 2001.

O. Golubitsky. Grbner walk for characteristic sets of prime differential ideals. In: Ganzha, V., Mayr, E., Vorozhtsov, E. (Eds.), Proc. 7th Workshop on Comp. Alg. in Sc. Comp. TU Mnchen, Germany, pp.

207–221, 2000.

Апробация работы Результаты диссертации докладывались:

• на семинаре по компьютерной алгебре Механико-математического факультета МГУ в 2003–2007 годах, • на конференции Компьютерная алгебра и ее приложения в физике (CAAP) и семинарах по компьютерной алгебре в 2001–2007 годах в Дубне, • на Международной алгебраической конференции, посвященной 250летию МГУ и 75-летию кафедры высшей алгебры в МГУ в 2004 году, • на международной конференции Приложения компьютерной алгебры в 2003 году (Роли, Северная Каролина) и 2004 году (Бомонт, Техас), • на международной конференции Компьютерная алгебра в научных вычислениях в 2002 году (Ялта, Крым) и в 2004 году (Санкт-Петербург), • на Колчинском семинаре по дифференциальной алгебре (Нью-Йорк) в 2004 и 2005 годах, • на конференции по дифференциальной алгебре в Университете Линца (RISC), Австрия, в 2006 году, • на конференции по алгебраическим методам в дифференциальных уравнениях (Эдинбург, Шотландия) в 2006 году.

Публикации Результаты автора по теме диссертации опубликованы в 8 работах, список которых приводится в конце автореферата [1–8].

Структура и объем диссертации Диссертационная работа состоит из 5 глав (первая глава является вводной) и заключения. Библиография содержит 32 наименования. Общий объем диссертации составляет 61 стр.

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

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

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

теоремы 1–3. Данные результаты используются в диссертации.

Четвертая глава посвящена каноническим характеристическим множествам характеризуемых дифференциальных идеалов. Сначала дается определение канонического характеристического множества по аналогии с редуцированным базисом Гребнера. Пусть k дифференциальное поле нулевой характеристики с основным множеством дифференцироваk1 k2 km ний = {1,..., m} и = 1 2 · · · m, ki 0. Мы также предполагаем, что зафиксирован ранжир на множестве переменных Y, где Y = y1,..., yn. Пусть A авторедуцированное множество в кольце дифференциальных многочленов k{y1,..., yn} = k[Y ] и пусть k[N][L] кольцо многочленов, ассоциированное с A, где L множество лидеров многочленов из A и N множество нелидеров, то есть, N = Y \ L.

Определение. Характеристическое множество C = C1,..., Cp дифференциального идеала I называется каноническим, если следующие условия выполнены для i = 1,..., p:

• инициал iC зависит только от нелидеров N множества C;

i • многочлен Ci не имеет делителей в I, кроме самого Ci;

• старший коэффициент Ci относительно индуцированного лексикографического упорядочения

Рассмотрим k{y1,..., yn} c = {}. Это означает, что мы находимся в обыкновенном случае. Дифференциальной размерностью простого дифференциального идеала P называется максимальное число q, такое что P k{yi,..., yi } = {0}. Если f дифференциальный многочлен, то 1 q ord f обозначает максимальный порядок дифференциальных переменных, входящих в f. Пусть A = A1,..., Ap авторедуцированное множество.

Определим порядок множества A следующим равенством:

ord A = ord A1 +... + ord Ap.

Если C характеристическое множество простого дифференциального идеала P относительно степенного ранжира, то, по определению, порядок идеала P равен неотрицательному целому числу ord C. Обозначим через P (s) множество элементов P, чей порядок меньше или равен s. Множество P (s) образует простой алгебраический идеал в соответствующем кольце многочленов. Известно1,2, что размерность P (s) многочлен от s для s h = ord P. Более точно, dim P (s) = q(s + 1) + ord P, где q дифференциальная размерность идеала P. Более того, q = n - p, где p число элементов характеристического множества идеала P относительно любого степенного ранжира. Таким образом, числа ord P и p не зависят от выбора степенного ранжира. Определим порядок характеризуемого дифференциального идеала.

Определение. Для характеризуемого дифференциального идеала I = k Pi, где Pi минимальные дифференциальные простые компоненты I, i=определим ord I = max ord Pi.

1 i k Доказательство основной оценки в этой главе диссертации (теорема 6) Теорема. Пусть C = C1,..., Cp каноническое характеристическое множество характеризуемого дифференциального идеала I. Тогда ord Ci ord I, 1 i p.

опирается существенным образом на аналогичную оценку для простых идеалов, доказанную в диссертации (теорема 4):

Теорема. Пусть P простой дифференциальный идеал порядка h в k{y1,..., yn} и > любой ранжир. Тогда существует характеристическое множество C = C1,..., Cp идеала P относительно ранжира >, такое что порядок по yt каждого Ci не превосходит h для всех 1 t n.

В пятой главе рассматривается алгоритм разложения Rosenfeld-Grbner радикального дифференциального идеала {F }, заданного конечной системой образующих F, на характеризуемые компоненты. Основной результат этой главы состоит в следующем. Пусть на вход алгоритма разложения (алгоритм 3), корректность которого доказана в предложении 5, подается конечная система F из кольца дифференциальных многочленов k{y1,..., yn}.

Определим:

n mi(F ) = max ordy f, M(F ) = mi(F ).

i fF i=Тогда все системы A, H, получающиеся на выходе и в ходе работы алгоритма, удовлетворяют оценке M(A H) (n - 1)! · M(F ).

Основной идеей доказательства данной оценки было заменить использование дифференциальной редукции на применение дифференцирования в начале вычисления, а затем алгебраической редукции (см. алгоритм 2).

Pages:     || 2 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»