Символьные алгоритмы, связанные с задачами суммирования

• Автор: Поляков, Станислав Петрович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 71 с.

Содержание
Введение
Глава 1. Неопределенное суммирование рациональных функций с дополнительной минимизацией
1.1. Варианты постановки задачи
1.2. Алгоритмы неопределенного суммирования
1.3. Прямой алгоритм суммирования с разложением на простейшие дроби
1.4. Множество решений задачи неопределенного суммирования
1.5. Подходы к минимизации просуммированной части
1.6. Прямой алгоритм с минимизацией просуммированной части
1.7. Расщепляющий алгоритм минимизации степени знаменателя
просуммированной части
1.8. Минимизация степени числителя остатка
Глава 2. Однородные цейлбергеровские рекурренции
2.1. Предварительные сведения
2.2. Алгоритм Цейлбергера в однородном случае
2.3. Минимальные аннулирующие операторы
Глава 3. Реализация и экспериментальное сравнение алгоритмов
3.1. Реализация
3.2. Экспериментальное сравнение алгоритмов
Заключение

Литература
Введение
Актуальность работы. Суммирование гипергеометрических последовательностей является одной из важных математических задач, имеющей применения в различных областях науки и техники, например, в комбинаторике. В компьютерной алгебре сумма ищется в символьном виде, то есть явно в виде математической функции.
Первая глава посвящена частному случаю суммирования гипергеометрических последовательностей — суммированию рациональных функций. Задача неопределенного суммирования рациональных функций, впервые поставленная С.А. Абрамовым в 1971 г. в [1], состоит в поиске для заданной рациональной функции f(x) рациональной функции д(х), удовлетворяющей
д(х + 1) - д(х) = f{x).
Неопределенное суммирование является дискретным аналогом неопределенного интегрирования. Как и в случае интегрирования, не всякая рациональная функция имеет рациональную неопределенную сумму. Поэтому начиная с опубликованной в 1975 г. статьи С.А. Абрамова [2] изучается задача аддитивной декомпозиции рациональных функций — представления их в виде
f(x) = д(х + 1) - д{х) + г(х),
где г(х) — минимальная в некотором смысле рациональная функция, называемая остатком. Как правило, минимизируется степень знаменателя остатка — в такой постановке задача является аналогом задачи выделения рациональной части неопределенного интеграла рациональных функций, классические методы решения которой были предложены Остроградским [3] и Эрмитом
[4].
Для задачи аддитивной декомпозиции разными авторами был предложен ряд алгоритмов решения, в частности, [2, 5-9]. Общей чертой этих ал-
делит q. Тогда, если условие
( к-х _ ( к _
den I g — Уг(ж + j) І = qßk{x + к) den I g — yV(a: + j) І ,
V j=о / j=о
ßk Є Z, выполнено при всех к — О
туральное число, для которого справедливо неравенство к
max(0, -ßk) > min_ deg den (5%); (1-24)

то для к такого, что
к—1 к
тах УУ = У Д,
0<к<к
справедливо
0<к<к п
j=0 j
min degden(a,o
fcie Z
Доказательство. Если для некоторого целого к, 0 < к < h — 1, выполнено условие (1.23), то
Ml,А: М ’ — ßki поэтому ДЛЯ любого целого к > к И произвольных &2,

degden(bfc2

Поэтому из (1.22) и (1.24) следует, что
mindegden(pfcli0v,.i0) = min _ degden(1;0v..j0). fc:eZ fci=0
Степени degden(.bo;...io) и deg den gy. достигают минимума при k — к в силу предложения 9.
Теорема 4 дает следующий алгоритм решения задачи 2:
Алгоритм 1.3.
Ввод: рациональная функция /(ж)