Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертационная работа:

Поляков Станислав Петрович. Символьные алгоритмы, связанные с задачами суммирования: автореферат дис. ... кандидата физико-математических наук: 05.13.11 / Поляков Станислав Петрович;[Место защиты: Федеральном государственном бюджетном учреждении науки Вычислительном центре им. А.А. Дородницына Российской академии наук].- Москва, 2012.- 19 с.

смотреть введение
Введение к работе:

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

Первая глава посвящена частному случаю суммирования гипергеометрических последовательностей — суммированию рациональных функций. Задача неопределенного суммирования рациональных функций, впервые поставленная С.А. Абрамовым в 1971 г. в [1], состоит в поиске для заданной рациональной функции f(x) рациональной функции д(х): удовлетворяющей

д{х + 1) - д(х) = f(x).

Неопределенное суммирование является дискретным аналогом неопределенного интегрирования. Как и в случае интегрирования, не всякая рациональная функция имеет рациональную неопределенную сумму. Поэтому начиная с опубликованной в 1975 г. статьи С.А. Абрамова [2] изучается задача аддитивной декомпозиции рациональных функций — представления их в виде

f(x) =д(х + 1) - д(х)+г(х),

где г(х) — минимальная в некотором смысле рациональная функция, называемая остатком. Как правило, минимизируется степень знаменателя остатка — в такой постановке задача является аналогом задачи выделения рациональной части неопределенного интеграла рациональных функций, классические методы решения которой были предложены Остроградским [3] и Эрмитом

М-

Для задачи аддитивной декомпозиции разными авторами был предложен ряд алгоритмов решения, в частности, [2, 5-9]. Общей чертой этих алгоритмов является использование в том или ином виде дисперсии исходной функции /(ж), т.е. максимального целого к такого, что знаменатели f(x) и f(x + к) имеют общие множители. Это позволяет избежать полной факторизации знаменателя /(ж), заменив ее частичной факторизацией, основанной

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

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

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

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

Алгоритм Цейлбергера [12], которому посвящена вторая глава диссертации, является важным компьютерно-алгебраическим инструментом, применяемым для суммирования многомерных гипергеометрических последовательностей и автоматического доказательства тождеств. Для заданной гипергеометрической последовательности F(x,y) алгоритм строит рекурренцию вида

G(x,y + 1) -G(x,y) = LxF(x,y),

где Lxсвободный от у разностный оператор минимального порядка с по-

линомиальными коэффициентами, G(x, у) — гипергеометрическая последовательность. Случай однородной цейлбергеровской рекурренции, т.е. случай, когда последовательность F(x, у) обращается оператором Lx в нуль, заслуживает внимания как с теоретической, так и с практической точки зрения. К этому случаю неприменимо доказательство корректности алгоритма Цейл-бергера, предложенное в [12] и впоследствии воспроизведенное в ряде монографий и учебников (например, [13, 14]). Кроме того, однородный случай был исследован в работе [15], поскольку он вызывал ошибки в работе реализации алгоритма в ряде версий системы компьютерной алгебры Maple [16]. Исходное предположение авторов о некорректности работы самого алгоритма в однородном случае ошибочно, однако некоторые их результаты представляют интерес, поскольку предложенный ими алгоритм в однородных случаях может оказываться намного эффективнее алгоритма Цейлбергера.

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

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

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

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

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

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

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

В системе компьютерной алгебры Maple [16] реализована процедура аддитивной декомпозиции рациональных функций с минимизацией степени знаменателя остатка и возможностью дополнительной минимизации степени знаменателя просуммированной части либо степени числителя остатка; пользователю предоставлена возможность выбора между алгоритмами, основанными на полной факторизации знаменателя входной функции (используемыми по умолчанию) и алгоритмами, избегающими ее. Реализованы процедура построения аннулирующего оператора минимального порядка для гипергеометрических последовательностей и модифицированный алгоритм Цейлбергера, использующий построение аннулирующих операторов в однородном случае. Проведено экспериментальное сравнение основанного на полной факторизации алгоритма аддитивной декомпозиции с алгоритмами [2, 5, 9], а также алгоритма Цейлбергера с модифицированной версией в однородном случае.

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

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

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

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

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

  2. Предложено полное (включающее однородный случай) обоснование алгоритма Цейлбергера определенного суммирования многомерных гипергеометрических последовательностей. Разработан алгоритм поиска аннулирующего оператора минимального порядка для двумерных гипергеометрических последовательностей.

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

тов, продемонстрировавших практическую ценность предложенных алгоритмов.

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

Семинар МГУ "Компьютерная алгебра", Москва, 2005, 2009 гг.

Международный семинар по компьютерной алгебре и информатике (посвященный 30-летию ЛВМ МГУ), Москва, 2005 г.

Совместное заседание семинаров ВМК МГУ, НИИЯФ МГУ и Лаборатории информационных технологий ОИЯИ, Дубна, 2006 г.

XLIII всероссийская научная конференция по проблемам математики, информатики, физики и химии, Москва, 2007 г.

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

Личный вклад автора. Гезультаты получены автором самостоятельно под руководством д.ф.-м.н., профессора С.А. Абрамова.

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


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net