автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Компьютерно-алгебраические методы решения систем линейных обыкновенных уравнений, основанные на индуцированных рекурренциях

ИИ4611659

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

Хмельнов Денис Евгеньевич

Компьютерно-алгебраические методы решения

систем линейных обыкновенных уравнений, основанные на индуцированных рекурренциях

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

2 8 ОКТ 2010

Москва - 2010

004611659

Работа выполнена в Учреждении Российской академии наук Вычислительном центре им. А.А.Дородницына РАН.

Научный руководитель: доктор физико-математических паук,

профессор,

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

профессор,

Гердт Владимир Петрович кандидат физико-математических паук, Зобнин Алексей Игоревич Ведущая организация: Государственное образовательное учреждение выс-

шего профессионального образования «Российский университет дружбы народов»

Защита состоится . 2010 г. в /г часов на заседании диссертаци-

онного совета Д 002.017.02 при Учреждении Российской академии наук Вычислительный центр им. А.А.Дородницына РАН, расположенном по адресу: 119333, г.Москва, улица Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке Учреждении Российской академии наук Вычислительный центр им. A.A. Дородницына РАН.

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

2010 г.

Ученый секретарь

диссертационного совета Д 002.017.02, д. ф.-м. п., профессор

В. В. Рязанов

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

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

Традиционным компьютерно-алгебраическим подходом к решению таких систем является использование метода циклического вектора [1] или других подобных методов [2, 3], которые преобразуют систему в скалярное обыкновенное уравнение, и последующее решение этого скалярного уравнения. Главным и хорошо известным недостатком такого подхода является быстрый рост коэффициентов получающихся скалярных уравнений при увеличении числа уравнений в системе, из-за чего он может быть применен только к системам небольшого размера. Поэтому с практической точки зрения большую ценность представляют прямые методы, которые работают непосредственно с системой уравнений, не преобразуя ее к скалярному виду.

Для решения скалярных обыкновенных уравнений были предложены быстрые методы [4-6], базирующиеся на вычислении линейной рекурренции, индуцированной исходным обыкновенным уравнением (этой рекурренции удовлетворяют коэффициенты искомых решений при разложении в некотором подходящем степенном базисе). В этих методах анализ корней ведущего и трейлингового коэффициентов индуцированной рекурренции позволяет находить границы полюсов решений, границы степеней полиномиальных решений, а сами индуцированные рекурренции затем используются для построения коэффициентов разложений решений по элементам степенного базиса.

В 1999 г. С.А.Абрамов обобщил этот метод на линейные системы обыкновенных уравнений [7]. Такое обобщение на системы приводит к специфическим трудностям, которых нет в скалярном случае. Рассмотрим скалярную рекурренцию, индуцированную некоторым линейным обыкновенным уравне-

нием с полиномиальным коэффициентами

Рл{п)гпи + РЛ-\{п)гпи-1 + • • • + Ро(п)гп - 0 (1)

Р0(п),..., Рл{п) — полиномы, и Ро{п), Рл{п) не равны тождественно нулю. В этом случае эти два полинома обращаются в нуль только для конечного множества значений п, и анализ этого конечного множества значений позволяет получить важную информацию о искомых решениях исходного уравнения. Если же (1) является индуцированной рекурренцией для системы линейных обыкновенных уравнений с полиномиальными коэффициентами, к гп — это т-компонентный вектор, а Ро(п),..., Рд{п) — полиномиальные матрицы размера т хт, то роль, которую в скалярном случае играли корни ведущего и трейлингового коэффициента, теперь могут играть корни определителей матриц Р0(п) и Рй{п), при условии, что эти определители не равны тождественно нулю. Однако может оказаться, что матрица Ро(п) или Рл{п) - вырожденная (сингулярная). В этом случае, не только невозможно получигь информацию о границах полюсов и степеней искомых решений, но также становится гораздо более тяжелой вычислительной задачей использование индуцированной рекурренции (1) для построения по заданным начальным условия последовательности векторов, которые ей удовлетворяют.

Естественным решением в этом случае являются методы десингуляриза-ции, то есть проведение эквивалентных преобразований матричной рекурренции (1), которые приводят к форме, в которой или ведущая или трейлинговая матрица не являются сингулярными. При этом преобразования могут быть "квази-эквивалентными", то есть допускаются некоторые изменения в множестве решений, вызываемые этими преобразованиями, но эти изменения могут быть легко учтены при анализе результатов. С.А.Абрамовым в работе [7] был предложен метод ЕГ-исключения, позволяющий проводить десингуляри-зацию индуцированной матричной рекурренции, и основанные на этом методе прямые алгоритмы решения исходных систем линейных обыкновенных уравнений с полиномиальными коэффициентами. В 2001 г. С.А.Абрамовым и М.Бронштейном в работе [8] этот метод десингуляризации был усовершенствован (дальнейшее развитие в работах [9] и [А1]); усовершенствованный метод получил название метода ЕГ'-исключения. В 2002 г. Б.Беккерманом,

Г.Лабаном и Х.Ченгом в работе [10] был предложен еще один метод десингу-ляризации — алгоритм РРгес1исе (улучшенная версия представлена в 2006 г, в работе [11]).

Также имеется альтернативный подход построения прямых методов решения систем линейных обыкновенных уравнений с полиномиальными коэффициентами, основанный не на индуцированных рекурренциях, а на построении супернеприводимых форм матриц исходных системы во всех особых точках. Этот подход был представлен 1987 г. А.Хилали и А.Вазнером в работе [12] для дифференциального случая, и в 1989 г. в работе М.Баркату [13] перенесен на разностный случай (дальнейшее развитие — в работе 1999 г.

[14])-

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

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

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

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

• Для рассматриваемых типов обыкновенных уравнений (дифференциальные, разностные и д-разностные) проведен анализ различных совместимых базисов, которые могут быть использованы для построения индуцированных рекурренций. Введено понятие двустороннего совместимого базиса. Показано, что с точки зрения использования метода ЕГ'-исключения для получающихся в таких базисах индуцированных рекурренций, эти базисы являются предпочтительными. Такие предпочтительные базисы предложены для дифференциального, разностного и ^-разностного случая и получены соответствующие формулы для построения индуцированных рекурренций в этих базисах. Описаны практические аспекты эффективной реализации построения индуцированных рекурренций на основе этих формул.

• Разработан новый алгоритм построения полиномиальных решений систем линейных обыкновенных уравнений с полиномиальными коэффициентами, основанный на использовании индуцированных рекурренциях для построения границ степеней полиномиальных решения и вычислении коэффициентов таких решений. В алгоритме учтено использование метода ЕГ'-исключения для десингуляризации индуцированной рекурренции, а также обеспечена его эффективная работа и в случае разреженных решений (что, например, является проблемой для классического метода неопределенных коэффициентов).

• Разработан новый эвристический алгоритм построения универсального знаменателя решений систем первого порядка линейных дифференциальных уравнений с полиномиальными коэффициентами. Предложенный алгоритм является гибридным, используя эффективный алгоритм Бронштейна-Трагера [15] одновременной редукции для части особых точек системы (все эти точки гарантировано являются регулярными), и метод на основе ЕГ'-исключения только для оставшихся особых точек, считая их нерегулярными.

• В системе компьютерной алгебры MAPLE ([16]) реализован пакет Li-nearFunctionalSystems, предоставляющий процедуры поиска полиномиальных, рациональных, регулярных, логарифмических решений и решений в виде рядов систем обыкновенных уравнений с полиномиальными коэффициентами, а также лежащие в основе алгоритмов поиска этих решений процедуры для построения и десингуляризации индуцированных рекурренций. Описаны практические аспекты реализации соответствующих алгоритмов и проведено экспериментальное сравнение с программами, реализующими альтернативные современные методы.

Практическая и теоретическая ценность. Предложенные в диссертационной работе методы и алгоритмы могут быть встроены в существующие системы компьютерной алгебры, предоставляя пользователям этих систем дополнительные возможности анализа и поиска символьных решений более сложных систем линейных обыкновенных (дифференциальных, разностных и д-разностпых) уравнений с полиномиальными коэффициентами. Поскольку рассматриваемые системы уравнений возникают в различных областях науки и техники, то наличие эффективного инструмента для их решения может помочь в решении практических и теоретических задач в этих областях. Реализованный пакет LinearFunctionalSystems уже доступен пользователям системы компьютерной алгебры MAPLE ([16]).

Решение многих задач часто удается свести к решению ряда задач более простого вида. В частности, поиск решений уравнений или систем уравнений в более сложном виде часто удается свести к ряду задач поиска решений в более простом виде. Таким образом, предложенные подходы и методы могут быть востребованы в дальнейших работах по созданию алгоритмов поиска решений систем линейных обыкновенных уравнений в более сложном виде. По аналогии со скалярным случаем можно ожидать, что в дальнейшем будут разработаны, например, алгоритмы для поиска гипергеометрических, лиувил-левых решений систем, а также алгоритмы поиска решений систем в виде рядов с коэффициентами специального вида (рациональными, даламберовыми, лиувиллевыми и т.п.).

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

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

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

3. Разработан новый эвристический алгоритм построения универсального знаменателя решений систем линейных дифференциальных уравнений с полиномиальными коэффициентами на основе алгоритма Вронштей-на-Трагера [15].

4. В системе компьютерной алгебры MAPLE ([16]) реализован новый пакет LinearFunctionalSystems, предоставляющий различные процедуры поиска решений систем обыкновенных уравнений с полиномиальными коэффициентами, а также лежащие в основе алгоритмов поиска этих решений процедуры для построения и десингуляризации индуцированных рекурренций. Описаны практические аспекты реализации соответствующих алгоритмов и проведено экспериментальное сравнение с программами, реализующими альтернативные современные методы.

Апробация работы. На разных этапах работы основные результаты по теме диссертации были представлены на следующих конференциях и семинарах:

• Семинар МГУ «Компьютерная алгебра», Москва, 1998, 2000 и 2003 гг.

• Международная Франко-российская конференция «Перспективы сотрудничества по прикладной математике и информатике», посвященная 10-летию Франко-Российского Института А.М.Ляпунова, Москва, 2003 г.

• Конференция «Ninth Rhine Workshop on Computer Algebra», Nijmegen, Netherlands, 2004 r.

• Объединенный семинар «Компьютерная алгебра» МГУ и ЛИТ ОИЯИ, Дубна, 2005 г.

• Конференция «8th Annual International Workshop in Computer Algebra in Scientific Computing (CASC'2005)», Kalamata, Greece, 2005 r.

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 4 статьи в рецензируемых журналах из перечня ВАК [А2, A3, А4, А5] и 3 статьи в сборниках трудов конференций [А6, Al, А7].

Личный вклад автора. В результатах, опубликованных в соавторстве, автору диссертационной работы принадлежат:

• реализация всех предлагаемых алгоритмов в виде процедур пакета Li-nearFunctionalSystems в системе компьютерной алгебры MAPLE ([16]), включая проработку и описание практических аспектов и приемов этой реализации (например, эвристический выбор ведущего элемента и адаптация алгоритма Барейса [17] в реализации алгоритма ЕГ-исключения, описанные в работе [Al], проработка деталей реализации алгоритма поиска регулярных решений в работах [А7, А5], функциональные спецификации процедур пакета LinearFunctionalSystems в работе [А6]).

• разработка эвристического алгоритма для построения универсального знаменателя решений систем линейных дифференциальных уравнений с полиномиальными коэффициентами на основе алгоритма Брон-штейна-Трагера [15] в работе ]А5].

• подготовка примеров работы алгоритмов и примеров использования пакета LinearFunctionalSystems, проведение экспериментов и сравнение результатов работы с существующими известными альтернативами (в работах ]А6, Al, А7, А5]).

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

Результаты, опубликованные в работах [А2, A3, А4] без соавторов, получены автором диссертационной работы самостоятельно.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и пяти приложений. Общий объем работы составляет 138 страниц. Список литературы содержит 43 наименования.

Содержание работы

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

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

Рй{п)гп+<1 + Р<г-1(п)гп+(г-1 Н----+ Ро{п)гп = О,

где все Р^п) — полиномиальные т х т-матрицы, к виду, в котором матрица Ра{п) (соответственно, Ро(п)) является невырожденной. Представлено описание общей парадигмы десингуляризации - чередование шагов "редукция + сдвиг". В качестве основного вспомогательного преобразования выступает редукция системы: если ведущая (соответственно, трейлинговая) матрица вырождена (сингулярна), то редукция обеспечивает появление в ней нулевой строки или столбца. После этого осуществляется сдвиг в строке или столбце, соответствующей полученной нулевой строке или столбцу ведущей (соответственно, трейлинговой) матрицы. Рассмотрены методы ЕГ-исключения [7] и ЕГ'-исключения [8, 9] и алгоритм РРгес1исе [10, 11], основанные на различных видах редукции, и показано, что из них только метод ЕГ'-исключения является методом двухэтапной редукции. Приведены практические аспекты реализации методов ЕГ-исключения и ЕГ'-исключения, использованные при их реализации в пакете 1ЛпеагРипсЫ.опа13узгетз в системе компьютерной алгебры МАРЬЕ (в частности, эвристический выбор ведущего элемента, адаптация алгоритма Барейса [17], а также изучение возможности применение модулярного подхода при реализации метода ЕГ-исключения). Также пред-

ставлены результаты экспериментального сравнения различных методов де-сингуляризации; эти сравнения подтверждают практическое превосходство метода ЕГ'-исключения над методами одноэтапной редукции.

Результаты первой главы опубликованы в работах [А2, А6, А1].

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

Ьу(х) = 0, (2)

где у(х) - искомая функция, Ь - линейный оператор; в частности, мы интересуемся дифференциальными, разностными и ^-разностными операторами с полиномиальными коэффициентами. Для системы (2) строится индуцированная матричная рекурренция вида (1), которой удовлетворяют коэффициенты искомых решений в некотором базисе, например в "Р+ = {а;п}п>о или С = { (д) }п>о- Решения индуцированных рекурренций однозначным образом соответствуют решениям исходных уравнений при использовании так называемых "совместимых" базисов [4-6] - таким образом, задача поиска решения линейной однородной системы в соответствующем классе сводится к задаче поиска решений индуцированной рекурренций в классе последовательностей коэффициентов.

Среди операторов В,ЕХ,С1\

Ор{х) = ^р(г), Ехр(х) = р(х + 1), Яр{х) = р(дх),

первый и третий совместимы с а второй с С. С другой стороны <2 я О несовместимы с С, а Ех несовместим с "Р+.

В работе [7] для решения систем линейных обыкновенных уравнений в дифференциальном и ^-разностном случае используется базис ав разностном - базис С и указано, что имеется существенная разница между этими случаями, связанная с областью определения индуцированных рекурренций (в разностном случае приходится следить за областью определения рекурренций в системе при проведении в ней этапа сдвига при десингуляризации, так как в общем случае индуцированные рекурренции определены только при п > 0).

На основе определения совместимого базиса из работ [4-6], дано определение "двустороннего совместимого" базиса. Обозначим Сцх\ кольцо (К.-&Л-гебру) линейных операторов £ : К.[х\ —> /С[а:]. Пусть # = {¿п(а;)}п>о - последовательность полиномов из К\х] таких, что

Р1. deg6n(a;) = п,

Р2. Ьп(ж) | Ьт(х) для 0 < п < т;

и пусть В — {Ь„(а;)}п<о - последовательность рациональных функций таких, что Ьп(х) = «„(ж) 6 К.[х\ и

N1. =-п,

N2. уп(х) | ут(х) для т < п < 0.

Определение 1. Двусторонний базис В, удовлетворяющий N1, N2 при п < 0 и Р1, Р2 при п > 0, и оператор Ь совместимы, если существуют неотрицательные целые числа А, В и элементы е 1С для п € 2 и —А < г < В такие, что

в

ЬЬп{х) = Ьп+г(х). (3)

1=-Л

Элементы В при п > 0 будем называть неотрицательной частью, а при п < 0 - отрицательной частью базиса.

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

Предложение 1. Для дифференциального оператора Б и д-разностного оператора сдвига <3 примером двустороннего совместимого базиса является базис

а для разностного оператора сдвига Ех - базис

х\ п > О,

' пег

где

Т ' 1/а;'"', п < О

гп = 1](х + /с), = Д(я;-*; + !).

х

к=1 *:=1 С} к П несовместимы с Т7, в свою очередь .Ё^ несовместим с Р. При этом использовавшийся в работе [7| для Ех базис С не может быть распространен на отрицательные степени и в этом смысле является неудобным.

В базисе В = {Ьп(ж)}пе2 оператор Ь в формуле (2), рассматриваемой в данном случае как скалярное уравнение, представим в виде:

Г г <1

Ьп = = (4)

к=0 к=0 ¿=0

где Дг — один из операторов 0,ЕХ,£2, Рк{х) £ К[х\ — полиномиальные коэффициенты, й — их максимальная степень, а с^ 6 /С — коэффициенты их разложения по элементам совместимого базиса В. Оператор соответствующей индуцированной рекурренции представим в виде

в

Т^-В^К = X/ (5)

где Еп - оператор сдвига по п {Е*сп = сп+к), Аи В - некоторые целые числа.

В работах ¡4-6] были получены соотношения, позволяющие осуществлять переход от оператора в виде (4) к индуцированному оператору в виде (5) для базиса V в дифференциальном случае

П-рЬо = £ ( ¿с*-,,*(п + *)М К (6)

¡=-¡1 \к=0 /

и в д-разностном случае

¿=0 \)с=0 /

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

Предложение 2.

^=£(¿¿¿4^,-) С)(п-^{п+'И <8>

1=-Л \к=0 ¿=0 ¿=0 4 ^ /

Также описаны практические аспекты эффективной реализации построения индуцированных рекурренций на основе формул (6), (7), (8). При этом в случае, когда рассматривается не скалярное уравнение, а система таких уравнений, индуцированный рекуррентный оператор является матричным, т.е. имеет вид

1=1

где Р{(п) - матрицы с элементами из К[п\ с числом строк М, равным числу уравнений в системе, и числом столбцов N, равным числу искомых функций. Соответственно, этот оператор действует на последовательность А^-мерных векторов гп, составленных из коэффициентов искомых функций при разложении по рассматриваемому совместимому базису. Это дает нам индуцированную матричную рекурренцию

I

1)2п+г = 0, (9)

аналогичную системе (1), рассмотренной в первой главе.

Результаты второй главы опубликованы в работах [АЗ, А4]. В третьей главе рассмотрен поиск решений систем линейных обыкновенных уравнений с полиномиальными коэффициентами, основанный на использовании индуцированных рекурренций и их десингуляризации.

Дан краткий обзор видов решений (поиск всех этих видов решений реализован в пакете [лпеагГипс1;:1опа13узЪетз), которые могут быть построены с использованием индуцированных рекурренций — соответствующие решения являются векторами с компонентами некоторого определенного вида:

решения в виде рядов — решения с компонентами вида

00

771=0

где точка разложения а и коэффициенты

полинома ст — элементы основного поля 1С, Ът(х) — элементы совместимого степенного базиса В.

полиномиальные решения — решения с компонентами в К[х\, то есть решения с компонентами вида

к

771—0

где к е Л/", а коэффициенты полинома ст — элементы основного поля

/С.

рациональные решения — решения с компонентами в К, (х), то есть решения с компонентами вида

№ з{х)'

где Лх),д(х) е Цх].

регулярные и логарифмические решения (для дифференциального случая):

— регулярные решения — решения с компонентами вида

к

(х - а)х^9т{х - а) к^т(а; - а),

т—О

где к € Л/", а — элемент основного поля К., а А - элемент алгебраического расширения основного поля и дт{х) — ряды Тейлора, такие, что дт(а) ф 0 (такие решения образуют базис всех решений в окрестности регулярной особенности системы а).

— логарифмические решения — решения с компонентами в К{х) [log ж], то есть решения с компонентами вида к

^9ш{х) logm(x),

т=0

где к 6 Af, дт{х) — рациональные функции с коэффициентами в К (поиск регулярных решений является локальной задачей, то есть задачей решаемой в окрестности некоторой особой точки; поиск логарифмических решений — аналогичная глобальная задача).

Сходимость рядов в решениях не рассматривается, все ряды формальные.

Представлены два новых алгоритма.

Новый алгоритм поиска полиномиальных решений разработан с учетом использования метода ЕГ'-исключения для десингуляризации индуцированной рекурренции; также обеспечена его эффективная работа и в случае разряженных решений (что, например, является проблемой для классического метода неопределенных коэффициентов и подхода, описанного в [8]).

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

После того, как найдена верхняя граница степени полиномиального решения, в новом алгоритме используется имеющаяся матричная рекурренци-ей относительно коэффициентов решений в рассматриваемом совместимом базисе. Как и в скалярном случае ([4]), рекурренция позволяет вычислять коэффициенты либо в прямом направлении, начиная от младших к старшим, либо в обратном направлении, начиная от старших к младшим. При вычислении следующего коэффициента в случае прямого направления главную роль играет ведущая матрица, а в случае обратного направления — трейлинговая. Поскольку для поиска границы степени полиномиального решения используется десингуляризация по отношению к трейлинговой матрице, то результат этой десингуляризации разумно использовать и для построения полиномиального решения. Таким образом, в новом алгоритме используется обратное

направление построения решения (такой подход используется и М.Баркату в алгоритмах построения полиномиальных решений, предложенных в работах [14, 18], а еще раньше С.А.Абрамовым в [19]). При этом в алгоритмах [18, 20] для вычисления коэффициентов используется не рекурренция, а собственно система обыкновенных уравнения (для этого требуется ее преобразование к суперпеприводимому виду).

Отметим, что новый алгоритм, как и алгоритмы [18, 20] не обязательно перебирает последовательно все степени коэффициентов, что является важным достоинством в случае разреженных решений. Для этого используется следующее наблюдение.

Предложение 3. Пусть трейлинговая матрица РДп) рекурренции (9) не является вырожденной при всех п, Я - множество целочисленных корней с^ Р((п), а г = {гп} - последовательность, удовлетворяющая (9), и все гь+г, • ■ • 2*+/-1 равны 0 для некоторого к 6 Z. Тогда гш = 0 для всех г 6 Ъ: Гк < г < к, где г= тах{г : г 6 Л, г<к}.

Новый эвристический алгоритм для построения универсального знаменателя решений систем первого порядка линейных дифференциальных уравнений с полиномиальными коэффициентами вида ^ = А(х)У(х), А(х) е Макн(К,(х)), являющихся частным случаем систем (2). Задача поиска универсального знаменателя решения является вспомогательной для поиска рациональных и логарифмических решений (полином <1{х) 6 К\х] — универсальный знаменатель, если й(х)у(х) е К[х] для любого рационального решения у(х) 6 /С(х); в работе [14] указано, что универсальный знаменатель также применим и для поиска логарифмических решений).

Предложенный новый эвристический алгоритм является гибридным, используя эффективный алгоритм Бронштейна-Трагера [15] одновременной редукции для части особых точек системы (все эти точки гарантировано являются регулярными), и метод на основе ЕГ'-исключения только для оставшихся особых точек, считая их нерегулярными.

Используемый алгоритм редукции Бронштейна и Трагера исходно предназначен для систем только с регулярными особенностями. Он заключается в повторении следующего единичного шага редукции: пока знаменатель А

не свободен от квадратов, выбрать строку Л, такую, что ее общий знаменатель й 6 К[х\ не свободен от квадратов; далее используя только вычисления расширенных наибольших общих делителей, вычислить невырожденную матрицу Т € Ма^(£(х)), чьи строки формируют /С[х]-базис свободного /С[:г]-модуля ^С[ж]1хЛГ + К\х]ш, где /С[х]1хЛГ — модуль вектор-строк, а и — выбранная строка А, умноженная на часть й, свободную от квадратов; а затем произвести замену переменных У = ТУ в дУ/йх = АУ. В [15] показано, что повторение конечного количества таких шагов приведет к матрице со знаменателем, свободным от квадратов.

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

Предложение 4. Пусть 5 - подмножество неприводимых множителей знаменателя матрицы А, соответствующих ее регулярным особенностям, а <1 = Пре5 Ре" 9е' ~ факторизованный вид знаменателя строки А для которой ер > 1 для некоторого р 6 5. Тогда при выполнении единичного шага редукции метода Бронштейпа-Трагера и> может быть взята равной этой строке А, умноженной на

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

Для повышения эффективности работы алгоритма используется еще одно наблюдение.

Предложение 5. Пусть А,А1,...,А{ - матрицы систем, полученных в результате последовательного применения единичного шага редукции ме-

moda Бронштейна-Трагера, а щ £ К\х\ - множитель универсального знаменателя, вычисленный для системы с матрицей A¡. Тогда щ является множителем универсального знаменателя и для исходной системы с матрицей А.

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

Для описанных новых алгоритмов также представлен псевдокод.

Результаты третьей главы опубликованы в работах [А4, А5, А7].

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

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

В завершение представлены результаты проведенного сравнения эффективности работы пакета LinearFunctionalSystems с программами решения систем дифференциальных и разностных уравнений, основанными не на десипгуляризации индуцированных рекурренций, а на альтернативном подходе — супернеприводимой форме ([12-14, 18]). Результаты показывают, что несмотря на то, что во многих случаях подход, основанный па ЕГ'-исключении, выигрывает, существуют случаи, в которых предпочтителен подход, основанный на супернеприводимости. При этом едва ли могут быть предложены практические критерии, по которым можно было бы понять какой из методов будет лучше для данного конкретного примера. Наличие нескольких альтернатив позволяет пользователю самостоятельно попробовать применить различные методы, что увеличивает шанс все-таки получить решение и в до-

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

Результаты четвертой главы опубликованы в работах [А4, А5, А6, А1,

А7].

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

Диссертационная работа также включает следующие приложения:

• Приложение А. Псевдокод метода ЕГ'-исключения.

• Приложение Б. Пример использования метода ЕГ'-исключения.

• Приложение В. Общая схема поиска регулярных решений.

• Приложение Г. Общая схема поиска логарифмических решений.

• Приложение Д. Пример использования алгоритма поиска регулярных решений.

Список публикаций

Al. Abramov S. A., Bronstein М., Khmelnov D. Е. Regularization of linear recurrence systems // Transactions of French-Russian Lyapunov Institute. 2003. Vol. 4. Pp. 158-171.

A2. Хмельнов Д. E. МЕГ-исключения // Программирование. 2001, № 1. С. 18-26.

A3. Хмельнов Д. Е. Выбор базиса при решении линейных функциональных уравнений // Программирование. 2002. № 2. С. 61-65.

А4. Хмельнов Д. Е. Поиск полиномиальных решений линейных функциональных систем с помощью индуцированных рекурренций // Программирование. 2004. № 2. С. 8-16.

А5. Abramov S. A., Bronstein М., Khmelnov D. Е. On regular and logarithmic solutions of ordinary linear differential systems // Lecture Notes in Computer Science (Proceeding of CASC 2005). 2005. Vol. 3718. Pp. 1-12.

А6. Abramov S. A., Glotov P. E., Khmelnov D. E. A scheme of eliminations in linear recurrent systems and its applications // Transactions of French-Russian Lyapunov Institute. 2001. Vol. 3. Pp. 78-89.

A7. Abramov S. A., Khmelnov D. E. A note on computing the regular solutions of linear differential systems // Proceedings of Ninth Rhine Workshop on Computer Algebra (RWCA'04). 2004. Pp. 13-27.

Цитированная литература

1. Cope F. T. Formal Solutions of Irregular Differential Equations // Am. J. Math. 193G. Vol. 58. Pp. 130-149.

2. Murray F. J., Miller K. S. Existence Theorems for Ordinary Differential Equations. New York: New York University Press, Intersciences, 1954.

3. Abramov S. A., Zima E. V. A Universal Program to Uncouple Linear Systems // Proc. of CMCP (Dubna, Russia). 1996. Vol. 58. Pp. 16-26.

4. Abramov S. A., Bronstein M., Petkovsek M. On polynomial solutions of linear operator equations // Proc. ISSAC '95. 1995. Pp. 169-174.

5. Abramov S. A., Petkovsek M. Special power series solutions of linear differential equations // Proc. FPSAC '96. 1996. Pp. 1-7.

6. Abramov S. A., Petkovsek M., Ryabenko A. A. Special formal series solutions of linear operator equations // Discrete Mathematics. 2000. Vol. 210. Pp. 3-25.

7. Abramov S. A. EG-eliminat,ions // Journal of Difference Equations and Applications. 1999. Vol. 5. Pp. 393-433.

8. Abramov S. A., Bronstein M. On solutions of linear functional systems // Proc. of ISSAC'2001. 2001. Pp. 1-6.

9. Abramov S. A., Bronstein M. Linear algebra for skew-polynomial matrices // Rapport de Recherche INRIA RR-4420, March 2002, http://www.inria.fr/RRRT/RR-4420.html. 2002.

10. Beckermann В., Cheng H., Labahn G. Fraction-free row reduction of matrices of skew polynomials // Proc. of ISSAC'2002. 2002. Pp. 8-15.

11. Beckermann В., Cheng H., Labahn G. Fraction-free Row Reduction of Matrices of Ore Polynomials // Journal of Symbolic Computation. 2006. Vol. 41, no. 5. Pp. 513-543.

12. Hilali A., Wazner A. Formes super-irréductibles des systèmes différentiels linéaires // Num. Math. 1987. no. 50. Pp. 429-449.

13. Barkatou M. Contribution à l'étude des équations différentielles et aux différences dans le champ complexe. France: thèse soutenue le 6 juin 1989 à l'institut national polytechnique de Grenoble, 1989.

14. Barkatou M. On rational solutions of systems of linear differential equations // Journal of Symbolic Computation. 1999. Vol. 28. Pp. 547-567.

15. Bronstcin M., Trager B. A reduction for regular differential systems // Proceedings of MEGA'2003, in CD-ROM. 2003.

16. Maple online help. URL: http://www.maplesoft.com/support/help/.

17. Bareiss Б. H. Sylvestr's identity and multistep integer-preserving Gaussian elimination // Math. Сотр. 1968. Vol. 22. Pp. 565-578.

18. Abramov S. A., Barkatou M. Rational solutions of first order linear difference systems // Proc. of ISSAC'98. 1998. Pp. 124-131.

19. Абрамов С. А. Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений // Вестник Моск. Ун-та, Сер. 15, Вычислительная математика и кибернетика. 1989. № 3. С. 56-60.

20. Barkatou M. Rational solutions of matrix difference equations: problem of equivalence and factorization // Proc. of ISSAC'99. 1999. Pp. 277-282.

Подписано в печать: 26.09.10

Объем: 1,5 усл.л. Тираж: 100 экз. Заказ № 765 Отпечатано в типографии «Реглет» 119526, г.Москва, пр-т Вернадского,39 (495) 363-78-90; www.reglet.ru

Введение

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

1.1. Рекуррентные срхстемы с полиномиальными коэффициентами

1.2. Общая парадигма десингуляризации - чередование шагов "редукция + сдвиг".

1.3. Одпоэтапные редукции.

1.4. Двухэтапная редукция - метод ЕГ'-исключения.

1.5. Сравнение различных методов десингуляризации.

Глава 2. Системы линейных обыкновенных уравнений с полиномиальными коэффициентами и индуцированные ими ре-курренции.

2.1. Совместимые базисы

2.2. Свойства различных базисов в ЕГ(')-исключениях

2.3. Расширение базисов на отрицательные степени.

2.4. Предпочтительные и неудобные базисы.

2.5. Построение индуцированных рекуррепций.

Глава 3. Поиск решений систем линейных обыкновенных уравнений с полиномиальными коэффициентами.

3.1. Поиск решений на основе индуцированных рекуррепций

3.2. Новый алгоритм поиска полиномиальных решений.

3.3. Новый эвристический алгоритм построения универсального знаменателя

Глава 4. Пакет LinearFunctionalSystems.

4.1. Архитектура пакета.

4.2. Детали реализации.

4.3. Примеры использования.

4.4. Экспериментальное сравнение с подходом, основанном на супернеприводимости

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

Традиционным компьютерно-алгебраическим подходом к решению таких систем является использование метода циклического вектора [1] или других подобных методов [2, 3], которые преобразуют систему в скалярное обыкновенное уравнение, и последующее решение этого скалярного уравнения. Главным и хорошо известным недостатком такого подхода является быстрый рост коэффициентов получающихся скалярных уравнений при увеличении числа уравнений в системе, из-за чего он может быть применен только к системам небольшого размера. Поэтому с практической точки зрения большую ценность представляют прямые методы, которые работают непосредственно с системой уравнений, не преобразуя ее к скалярному виду.

Для решения скалярных обыкновенных уравнений были предложены быстрые методы [4-6], базирующиеся на вычислении линейной рекурренции, индуцированной исходным обыкновенным уравнением (этой рекурренции удовлетворяют коэффициенты искомых решений при разложении в некотором подходящем степенном базисе). В этих методах анализ корней ведущего и трейлингового коэффициентов индуцированной рекурренции позволяет находить границы полюсов решений, границы степеней полиномиальных решений, а сами индуцированные рекурренции затем используются для построения коэффициентов разложений решений по элементам степенного базиса.

В 1999 г. С.А.Абрамов обобщил этот метод на линейные системы обыкновенных уравнений [7]. Такое обобщение на системы приводит к специфическим трудностям, которых нет в скалярном случае. Рассмотрим скалярную рекурренцию, индуцированную некоторым линейным обыкновенным уравнением с полиномиальным коэффициентами

Pd(n)zn+d + Pd-i(n)zn+d-i H-----h Po(n)zn = 0 (1)

Po(n),. Pd(n) — полиномы, и Po(n), Pd{n) не равны тождественно нулю. В этом случае эти два полинома обращаются в нуль только для конечного множества значений п, и анализ этого конечного множества значений позволяет получить важную информацию о искомых решениях исходного уравнения. Если же (1) является индуцированной рекурренцией для системы линейных обыкновенных уравнений с полиномиальными коэффициентами, и zn — это то-компонентный вектор, а Ро(п),., Pd(n) — полиномиальные матрицы размера m х то, то роль, которую в скалярном случае играли корни ведущего и трейлингового коэффициента, теперь могут играть корни определителей матриц Р0(п) и Pd(n), при условии, что эти определители не равны тождественно нулю. Однако может оказаться, что матрица Ро(п) или Pd(n) - вырожденная (сингулярная). В этом случае, не только невозможно получить информацию о границах полюсов и степеней искомых решений, но также становится гораздо более тяжелой вычислительной задачей использование индуцированной рекурренции (1) для построения по заданным начальным условия последовательности векторов, которые ей удовлетворяют.

Естественным решением в этом случае являются методы десингуляриза-ции, то есть проведение эквивалентных преобразований матричной рекурренции (1), которые приводят к форме, в которой или ведущая или трейлинговая матрица не являются сингулярными. При этом преобразования могут быть "квази-эквивалентными", то есть допускаются некоторые изменения в множестве решений, вызываемые этими преобразованиями, но эти изменения могут быть легко учтены при анализе результатов. С.А.Абрамовым в работе [7] был предложен метод ЕГ-исключения, позволяющий проводить десингуляри-зацию индуцированной матричной рекурренции, и основанные на этом методе прямые алгоритмы решения исходных систем линейных обыкновенных уравнений с полиномиальными коэффициентами. В 2001 г. С.А.Абрамовым и М.Бронштейном в работе [8] этот метод десингуляризации был усовершенствован (дальнейшее развитие в работах [9] и [10]); усовершенствованный метод получил название метода ЕГ'-исключения. В 2002 г. Б.Беккерманом, Г.Лабаном и Х.Чеигом в работе [11] был предложен еще один метод десингуляризации — алгоритм FFredu.ce (улучшенная версия представлена в 2006 г. в работе [12]).

Также имеется альтернативный подход построения прямых методов решения систем линейных обыкновенных уравнений с полиномиальными коэффициентами, основанный не на индуцированных рекурренциях, а на построении супернеприводимых форм матриц исходных системы во всех особых точках. Этот подход был представлен 1987 г. А.Хилали и А.Вазпером в работе [13] для дифференциального случая, и в 1989 г. в работе М.Баркату [14] перенесен на разностный случай (дальнейшее развитие — в работе 1999 г. [15]).

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

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

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

• Для рассматриваемых типов обыкновенных уравнений (дифференциальные, разностные и д-разностные) проведен анализ различных совместимых базисов, которые могут быть использованы для построения индуцированных рекурренций. Введено понятие двустороннего совместимого базиса. Показано, что с точки зрения использования метода ЕГ'-исключения для получающихся в таких базисах индуцированных рекурренций, эти базисы являются предпочтительными. Такие предпочтительные базисы предложены для дифференциального, разностного и ^-разностного случая и получены соответствующие формулы для построения индуцированных рекурренций в этих базисах. Описаны практические аспекты эффективной реализации построения индуцированных рекурренций на основе этих формул.

Разработан новый алгоритм построения полиномиальных решений систем линейных обыкновенных уравнений с полиномиальными коэффициентами, основанный на использовании индуцированных рекурренци-ях для построения границ степеней полиномиальных решения и вычислении коэффициентов таких решений. В алгоритме учтено использование метода ЕГ'-исключения для десингуляризации индуцированной рекурренции, а также обеспечена его эффективная работа и в случае разреженных решений (что, например, является проблемой для классического метода неопределенных коэффициентов).

Разработан новый эвристический алгоритм построения универсального знаменателя решений систем первого порядка линейных дифференциальных уравнений с полиномиальными коэффициентами. Предложенный алгоритм является гибридным, используя эффективный алгоритм Бронштейна-Трагера [16] одновременной редукции для части особых точек системы (все эти точки гарантировано являются регулярными), и метод на основе ЕГ'-исключения только для оставшихся особых точек, считая их нерегулярными.

В системе компьютерной алгебры МАРЬЕ ([17]) реализован пакет nearFшlctionalSystems, предоставляющий процедуры поиска полиномиальных, рациональных, регулярных, логарифмических решений и решений в виде рядов систем обыкновенных уравнений с полиномиальными коэффициентами, а также лежащие в основе алгоритмов поиска этих решений процедуры для построения и десингуляризации индуцированных рекурренций. Описаны практические аспекты реализации соответствующих алгоритмов и проведено экспериментальное сравнение с программами, реализующими альтернативные современные методы.

Практическая и теоретическая ценность. Предложенные в диссертационной работе методы и алгоритмы могут быть встроены в существующие системы компьютерной алгебры, предоставляя пользователям этих систем дополнительные возможности анализа и поиска символьных решений более сложных систем линейных обыкновенных (дифференциальных, разностных и д-разностных) уравнений с полиномиальными коэффициентами. Поскольку рассматриваемые системы уравнений возникают в различных областях науки и техники, то наличие эффективного инструмента для их решения может помочь в решении практических и теоретических задач в этих областях. Реализованный пакет LinearFunctionalSystems уже доступен пользователям системы компьютерной алгебры МАРЬЕ ([17]).

Решение многих задач часто удается свести к решению ряда задач более простого вида. В частности, поиск решений уравнений или систем уравнений в более сложном виде часто удается свести к ряду задач поиска решений в более простом виде. Таким образом, предложенные подходы и методы могут быть востребованы в дальнейших работах по созданию алгоритмов поиска решений систем линейных обыкновенных уравнений в более сложном виде. По аналогии со скалярным случаем можно ожидать, что в дальнейшем будут разработаны, например, алгоритмы для поиска гипергеометрических, лиувил-левых решений систем, а также алгоритмы поиска решений систем в виде рядов с коэффициентами специального вида (рациональными, даламберовыми, лиувиллевыми и т.п.).

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

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

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

3. Разработан новый эвристический алгоритм построения универсального знаменателя решений систем линейных дифференциальных уравнений с полиномиальными коэффициентами на основе алгоритма Бронштей-на-Трагера [16].

4. В системе компьютерной алгебры МАРЬЕ ([17]) реализован новый пакет Ьд.пеагРш1с1;:1опа13узЪеп1з, предоставляющий различные процедуры поиска решений систем обыкновенных уравнений с полиномиальными коэффициентами, а также лежащие в основе алгоритмов поиска этих решений процедуры для построения и десингуляризации индуцированных рекурренций. Описаны практические аспекты реализации соответствующих алгоритмов и проведено экспериментальное сравнение с программами, реализующими альтернативные современные методы.

Апробация работы. На разных этапах работы основные результаты по теме диссертации были представлены на следующих конференциях и семинарах:

• Семинар МГУ «Компьютерная алгебра», Москва, 1998, 2000 и 2003 гг.

• Международная Франко-российская конференция «Перспективы сотрудничества по прикладной математике и информатике», посвященная 10-летию Франко-Российского Института А.М.Ляпунова, Москва, 2003 г.

• Конференция «Ninth Rhine Workshop on Computer Algebra», Nijmegen, Netherlands, 2004 r.

• Объединенный семинар «Компьютерная алгебра» МГУ и ЛИТ ОИЯИ, Дубна, 2005 г.

• Конференция «8th Annual International Workshop in Computer Algebra in Scientific Computing (CASC'2005)», Kalamata, Greece, 2005 r.

Публикации. Материалы диссертации опубликованы в 7 печатных работах, из них 4 статьи в рецензируемых журналах из перечня ВАК [18-21] и 3 статьи в сборниках трудов конференций [10, 22, 23].

Личный вклад автора. В результатах, опубликованных в соавторстве, автору диссертационной работы принадлежат:

• реализация всех предлагаемых алгоритмов в виде процедур пакета Li-nearFunctionalSystems в системе компьютерной алгебры MAPLE ([17]), включая проработку и описание практических аспектов и приемов этой реализации (например, эвристический выбор ведущего элемента и адаптация алгоритма Барейса [24] в реализации алгоритма ЕГ-исключения, описанные в работе [10], проработка деталей реализации алгоритма поиска регулярных решений в работах [21, 23], функциональные спецификации процедур пакета LinearFunctionalSystems в работе [22]).

• разработка эвристического алгоритма для построения универсального знаменателя решений систем линейных дифференциальных уравнений с полиномиальными коэффициентами на основе алгоритма Брон-штейна-Трагера [16] в работе [21].

• подготовка примеров работы алгоритмов и примеров использования пакета LinearFunctionalSystems, проведение экспериментов и сравнение результатов работы с существующими известными альтернативами (в работах [10, 21-23]).

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

Результаты, опубликованные в работах [18-20] без соавторов, получены автором диссертационной работы самостоятельно.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и пяти приложений. Общий объем работы составляет 138 страниц. Список литературы содержит 43 наименования.

Основные результаты диссертационной работы:

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

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

3. Разработан новый эвристический алгоритм построения универсального знаменателя решений систем линейных дифференциальных уравнений с полиномиальными коэффициентами на основе алгоритма Бронштей-на-Трагера [16].

4. В системе компьютерной алгебры МАРЬЕ ([17]) реализован новый пакет LinearFшlctionalSystems, предоставляющий различные процедуры поиска решений систем обыкновенных уравнений с полиномиальными коэффициентами, а также лежащие в основе алгоритмов поиска этих решений процедуры для построения и десингуляризации индуцированных рекурренций. Описаны практические аспекты реализации соответствующих алгоритмов и проведено экспериментальное сравнение с программами, реализующими альтернативные современные методы.

Заключение

1. Cope F. T. Formal Solutions of 1.regular Differential Equations // Am. J. Math. 1936. Vol. 58. Pp. 130-149.

2. Murray F. J., Miller K. S. Existence Theorems for Ordinary Differential Equations. New York: New York University Press, Intersciences, 1954.

3. Abramov S. A., Zima E. V. A Universal Program to Uncouple Linear Systems // Proc. of CMCP (Dubna, Russia). 1996. Vol. 58. Pp. 16-26.

4. Abramov S. A., Bronstein M., Petkovsek M. On polynomial solutions of linear operator equations // Proc. ISSAC '95. 1995. Pp. 169-174.

5. Abramov S. A., Petkovsek M. Special power series solutions of linear differential equations // Proc. FPSAC '96. 1996. Pp. 1-7.

6. Abramov S. A., Petkovsek M., Ryabenko A. A. Special formal series solutions of linear operator equations // Discrete Mathematics. 2000. Vol. 210. Pp. 3-25.

7. Abramov S. A. EG-eliminations // Journal of Difference Equations and Applications. 1999. Vol. 5. Pp. 393-433.

8. Abramov S. A., Bronstein M. On solutions of linear functional systems // Proc. of ISSAC'2001. 2001. Pp. 1-6.

9. Abramov S. A., Bronstein M. Linear algebra for skew-polynomial matrices // Rapport de Recherche INRIA RR-4420, March 2002, http://www.inria.fr/RRRT/RR-4420.html. 2002.

10. Abramov S. A., Bronstein M., Khmelnov D. E. Regularization of linear recurrence systems // Transactions of French-Russian Lyapunov Institute. 2003. Vol. 4. Pp. 158-171.

11. Beckermann В., Cheng H., Labahn G. Fraction-free row reduction of matrices of skew polynomials // Proc. of ISSAC'2002. 2002. Pp. 8-15.

12. Beckermann В., Cheng H., Labahn G. Fraction-free Row Reduction of Matrices of Ore Polynomials // Journal of Symbolic Computation. 2006. Vol. 41, no. 5. Pp. 513-543.

13. Hilali A., Wazner A. Formes super-irréductibles des systèmes différentiels linéaires // Num. Math. 1987. no. 50. Pp. 429-449.

14. Barkatou M. Contribution à l'étude des équations différentielles et aux différences dans le champ complexe. France: thèse soutenue le 6 juin 1989 à l'institut national polytechnique de Grenoble, 1989.

15. Barkatou M. On rational solutions of systems of linear differential equations // Journal of Symbolic Computation. 1999. Vol. 28. Pp. 547-567.

16. Bronstein M., Trager В. A reduction for regular differential systems // Proceedings of MEGA'2003, in CD-ROM. 2003.

17. Maple online help. URL: http://www.maplesoft.com/support/help/.

18. Хмельнов Д. E. МЕГ-исключсния // Программирование. 2001. № 1. С. 18-26.

19. Хмельнов Д. Е. Выбор базиса при решении линейных функциональных уравнений // Программирование. 2002. № 2. С. 61-65.

20. Хмельнов Д. Е. Поиск полиномиальных решений линейных функциональных систем с помощью индуцированных рекурренций / / Программирование. 2004. № 2. С. 8-16.

21. Abramov S. A., Bronstein M., Khmelnov D. E. On regular and logarithmic solutions of ordinary linear differential systems // Lecture Notes in Computer Science (Proceeding of CASC 2005). 2005. Vol. 3718. Pp. 1-12.

22. Abramov S. A., Glotov P. E., Khmelnov D. E. A scheme of eliminations in linear recurrent systems and its applications // Transactions of French-Russian Lyapunov Institute. 2001. Vol. 3. Pp. 78-89.

23. Abramov S. A., Khmelnov D. E. A note on computing the regular solutions of linear differential systems // Proceedings of Ninth Rhine Workshop on Computer Algebra (RWCA'04). 2004. Pp. 13-27.

24. Bareiss E. H. Sylvestr's identity and multistep integer-preserving Gaussian elimination // Math. Сотр. 1968. Vol. 22. Pp. 565-578.25. van Hoeij M. Rational solutions of linear difference equations // Proc. of ISSAC'98. 1998. Pp. 120-123.

25. McClellan M. T. The Exact Solutions of Systems of Linear Equations with Polynomial Coefficients // Journal of the ACM. 1973. Vol. 28, no. 4. Pp. 563-588.

26. Mulders T., Storjohann A. Rational solutions of singular linear systems // Proc. of ISSAC'2000. 2000. Pp. 242-249.

27. Askey R. Orthogonal polynomials and special functions / Richard Askey. Philadelphia: Society for Industrial and Applied Mathematics, 1975.

28. Abramov S. A., Barkatou M. Rational solutions of first order linear difference systems // Proc. of ISSAC'98. 1998. Pp. 124-131.

29. Абрамов С. А. Задачи компьютерной алгебры, связанные с поиском полиномиальных решений линейных дифференциальных и разностных уравнений // Вестник Моск. Ун-та, Сер. 15, Вычислительная математика и кибернетика. 1989. № 3. С. 56-60.

30. Абрамов С. А. Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами // ЖВМ и МФ. 1989. Т. 29, № 11. С. 1611-1620.

31. Абрамов С. А. Рациональные решения линейных разностных и g-разностных уравнений с полиномиальными коэффициентами // Программирование. 1995. № 6. С. 3-11.

32. Хмельнов Д. Е. Улучшенные алгоритмы решения разностных и g-разностных уравнений // Программирование. 2000. № 2. С. 70-78.

33. Barkatou М. Rational solutions of matrix difference equations: problem of equivalence and factorization // Proc. of ISSAC'99. 1999. Pp. 277-282.

34. Abramov S. A. Rational solutions of First Order Linear q-Difference Systems // Proc. FPSAC '99. 1999. Pp. 1-9.

35. Abramov S. A. A direct algorithm to compute rational solutions of first order linear q-difference systems // Discrete Math. 2002. Vol. 246, no. 1-3.

36. A.Gheffar, S.Abramov. Valuations of rational solutions of linear difference equations at irreducible polynomials // Adv. in Appl. Maths. 2010. P. (submitted).

37. Coddington E., Levinson N. Theory of ordinary differential equations. New York: McGraw-Hill, 1955.

38. Гантмахер Ф. P. Теория матриц. Москва: Наука, 1988.

39. Barkatou M., Pflügel E. An algorithm computing the regular formal solutions of a system of linear differential equations // Journal of Symbolic Computation. 1999. Vol. 28. Pp. 569-587.

40. Frobenius G. Uber die Integration der linearen Differentialgleichungen mit veränder KoefRcienten // Journal für die reine und angewandte Mathematik. 1873. Vol. 76. Pp. 214-235.

41. Poole E. Introduction to the Theory of Linear Differential Equations. New York: Dover Publications Inc., 1960.

42. Heffter L. Einleitung in die Theorie der linearen Differentialgleichungen. Leipzig: Teubner, 1894.