ПРОГРАММИРОВАНИЕ, 2008, № 2, с. 48-53
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
НЕОПРЕДЕЛЕННОЕ СУММИРОВАНИЕ РАЦИОНАЛЬНЫХ ФУНКЦИЙ С ДОПОЛНИТЕЛЬНОЙ МИНИМИЗАЦИЕЙ ПРОСУММИРОВАННОЙ ЧАСТИ*
© 2008 г. С. П. Поляков
Вычислительный центр РАН 119991 Москва, ул. Вавилова, 40 E-mail: sp.p@mail.ru Поступила в редакцию 25.08.2007 г.
Предлагается алгоритм неопределенного суммирования рациональных функций, строящий для данной функции f(x) пару рациональных функций д(х),г(х) таких, что
f(x) = д(х + 1) - д{х) + г(х),
степень знаменателя г(х) минимальна, и при выполнении этого условия степень знаменателя д(х) также минимальна.
1. ВВЕДЕНИЕ
Рациональная функция / 6 К(х), где К - поле характеристики 0, называется суммируемой, если найдется д £ К(х), для которой
/(ж) = д(х + 1) - д(х).
(1)
(Для рациональных функций это определение эквивалентно суммируемости по Госперу [1].) Функция д называется неопределенной суммой /. Задачу неопределенного суммирования для произвольной рациональной функции можно сформулировать следующим образом: представить / в виде
/(ж) = g(x + 1) - д(х) + г(х),
(2)
где д,г - рациональные функции, причем функция г (называемая остатком) минимальна в некотором смысле. Функцию д будем называть просуммированной частью функции /.
Задача 1. Для данной рациональной функции / найти пару рациональных функций д, г таких, что для них выполняется (2) и г имеет знаменатель минимальной степени.
* Работа частично поддержана грантом Российского фонда фундаментальных исследований №07-01-00482-а.
В такой постановке задача неопределенного суммирования рассмотрена в ряде работ (см., например, [2-6]), известно несколько алгоритмов решения.
Поскольку одновременно с д, г решением задачи 1 является любая пара д-\-С,г при С € К, мы можем потребовать, чтобы д была равна сумме правильной дроби и полинома с нулевым свободным членом. Однако этой оговорки недостаточно, чтобы гарантировать единственность решения: если / не суммируема, то задача имеет бесконечно много решений с различными остатками. Просуммированные части при этом могут оказаться весьма громоздкими (для любой / найдется решение д, г со сколь угодно большой степенью знаменателя д).
Пример 1. Для
1
+
X X + 1
ж + 100
пары
2 1 д = - + —т
X X + 1
+
ж + 2
+ ••• +
1
ж + 99'
1
г =
и
д' =
1
1
г ж =
ж - - ж + 100 являются решениями задачи 1.
(3)
ж
Ряд алгоритмов, в том числе реализованный в системе Maple алгоритм из [6], находит именно решение (3). Решение (4) обладает рядом преимуществ, связанных с компактностью записи д и меньшим числом целых полюсов.
Задача 2. Для данной рациональной функции / найти решение задачи 1 с минимальной степенью знаменателя просуммированной части д.
Эта задача сформулирована в [4, 7]. В [4] предложен алгоритм решения задачи 1, во многих случаях строящий решение задачи 2. Достаточные условия, при которых найденное этим алгоритмом решение является решением задачи 2, сформулированы в [7]. Они состоят в следующем: если для произвольного неприводимого полинома q(x) и целых а, Ь степени вхождения q(x-\-a) и q(x-\-b) в знаменатель рациональной функции / равны, то либо найдется целое k, а < k < Ь, для которого q(x + к) входит в знаменатель / с большей степенью, или пара целых к\,к2, к\ < а < b < для которых q(x + кi), q(x + А^) входят в этот знаменатель с большей степенью, либо знаменатель / не делится на q(x + к) для целых к, если к < а или к > Ь. Приведем пример функции, для которой эти условия не выполняются, и алгоритм из [4] не дает решения задачи 2.
Пример 2. Для
ж2 + 1 1 1
J Q /
ж3 (х + 1)3 ' (х + 5)2' алгоритм из [4] находит решение задачи 1
ж2 + 1 1 1 91 =--5--Ь 7-—7^7 + 7-+
ж3 (ж+ 1)2 (ж + 2)5
1 1 + , , ОЧО +
(Ж + 3)2 ' (Ж + 4)2' ж + 2
(5)
Г1 =
(ж + 1)
2 '
Также решениями задачи 1 для этой функции являются
ж - 1 1
9о = —— +
+
1
Ж3 (ж+ 1)2 (ж + 2)2
Г +
1 1
+ , . ^о +
(ж + 3)2 (ж + 4)2'
Ж + 1
(6)
Г о =
, + 1 9 =--"а—
1
1
ж + 1 ж + 2
Г' =
ж + 3 ж + 4' ж + 6
(7)
(ж + 5)2'
Алгоритм из [6] находит решение (6). Сравнивая знаменатели д\ и до со знаменателем д' из (7), видим, что (5) и (6) не являются решениями задачи 2.
В статье предлагается полный алгоритм решения задачи 2. Используя один из имеющихся алгоритмов, он вычисляет решение задачи 1 и с его помощью строит решение задачи 2. Полная факторизация полиномов не используется. Учитывая необходимость предварительного решения задачи 1, алгоритм требует больших затрат по сравнению с алгоритмами из [4-6], однако он гарантирует минимизацию степени знаменателя просуммированной части.
В разделе 2 сформулирован ряд утверждений, использованных при построении алгоритма и оценке его сложности. Алгоритм изложен в разделе 3, раздел 4 содержит дополнительные способы уменьшения вычислительных затрат и оценку сложности алгоритма.
2. МНОЖЕСТВО РЕШЕНИЙ ЗАДАЧИ НЕОПРЕДЕЛЕННОГО СУММИРОВАНИЯ
В этом разделе мы будем полагать, что нам известно какое-то решение д, г задачи 1 для не-суммируемой / (г ф 0).
Дисперсией полинома р( ж) (обозначение: dis(p(a;))) называется максимальное целое к такое, что deggcd(p(x), р(х + к)) > 0 для р(ж) = = const dis(p(a;)) = 0. Дисперсия рациональной функции F(ж) обозначается Dis(F^)) и считается равной dis(den(_F^))), где den(F^)) - знаменатель F(ж), т.е. полином q минимальной степени, для которого найдется полином р, такой, р
что — = F{x). В [2] доказано, что дисперсия Ч
остатка в произвольном решении задачи 1 равна нулю. Это утверждение можно переформулировать следующим образом:
Предложение 1. Остаток г может быть представлен в виде
r = r(i) + ... + rW = _§_ + ...+
Рп
41 Чп
(8)
ж
где д\,..., дп - неприводимые полиномы, такие, что для любого целого к и любых 1 < I < < ] < га, выполнено gcd(gг'(ж), gj(x + к)) = 1.
Множество возможных остатков в решениях задачи 1 описано в [3]. В [8] доказано
Предложение 2. Пусть остаток г имеет вид (8). Тогда д',г' будет решением задачи 1, если и только если
д' = дки...,к„ =
П тах(-1,/гг-1) ^
= д - Х^11^') г(г)(ж + •?)>
2 = 1 ^=т1п(0,/гг)
Г = ^ь...,^ =
= г(1)(ж + ^1) Н-----Ь г(пЦх +
(10)
где к\,..., кп - целые числа.
Представим просуммированную часть ду,...,^ в виде
Доказательство. Пусть
degс!еп(г(г))'
(1; =
дкг
(0 •
где знаменатель дк', г = 1,...,га, равен произведению полиномов вида дг(ж + ]), j £ Z, & знаменатель не содержит множителей такого вида.
Следствие 1. Для двух решений д,г и до,...,о,кг,о,...,о, го,...,о,кг,о,...,о задачи 1, остатки которых различаются сдвигом компоненты Аг\ в разложениях (11) просуммированных частей совпадают все компоненты, кроме д(гК
Следствие 2. Пусть д^ = д^ + дк^+, где
с1еп(д^ ) равен произведению полиномов вида
дг(х + ]), ] < ki, а с1еп(д^+) не содержит множителей такого вида. Возьмем компоненту (0
дк, просуммированной части ду ,к',...,к'п произвольного решения задачи 1 и также представим ее в виде суммы дк) + дк)+, где знаменатель первого слагаемого равен произведению полиномов вида дг(ж + ]), ] < к{, а знаменатель второго не содержит множителей такого вида. Тогда при /гг- > ki дк/ = дк' , а при /гг- < ki
Теорема 1. Пусть т = degden((/). Тогда существуют такие целые к{, —2т < ki < 2т, г = 1,..., га, что дк1,...,к„, гк1,...,кп является решением задачи 2.
ki > 2di. Тогда
= д^-Аг\х)-Аг\х + 1)-----Аг\х + кг- 1),
degden(rW(ж) + ••• + Аг\х + ki - 1)) =
=/сг deg den(r'г') > 2 deg den((7Qг'), откуда deg den((7j:г') >
> deg den(¿(Qг''). Это же неравенство справедливо для ki < —2Следовательно, по крайней мере один из минимумов degden(gj^) достигается при \кг\ < 2йг < 2т. ' □
3. АЛГОРИТМ МИНИМИЗАЦИИ СТЕПЕНИ ЗНАМЕНАТЕЛЯ ПРОСУММИРОВАННОЙ ЧАСТИ
Пусть / - рациональная функция, д,г- решение задачи 1 для нее, причем для любого целого к > 0 выполнено gcd(den(r(ж — к)),<1еп(/)) = 1. Тогда для просуммированной части также выполняется
gcd(den(r(ж — к)), den(g)) = 1 (12)
при всех целых к > 0.
Алгоритм решения задачи 1, который для любой / находит такое решение, будем называть левосторонним. В частности, левосторонним является алгоритм из [2]. Другие алгоритмы, как правило, можно сделать левосторонними посредством модификаций, практически не влияющих на их сложность.
Если д,г - решение задачи 1, удовлетворяющее (12), то в любом решении (9), (10) задачи 2 к{ > I = 1,... ,п.
Далее в разделах 3.1 и 3.2 будем считать, что решение д, г задачи 1 построено с помощью левостороннего алгоритма.
3.1. Случай га = 1
Пусть г = — для неприводимого полинома да
д, т = degden(g). Тогда найдется решение дк,г(х + к) задачи 2, для которого 0 < к < М, 2тп
М = —;- (см. доказательство теоремы 1).
а deg д Пусть к0 = д,
^¿+1 — ^ ~~
Рг(х)
д!3' (х + г)
(13)
где Р{{х) и /Зг- выбираются так, чтобы выполнялось gcd(g(ж + г), с1еп(/гг'+1)) = 1, г = 0,1,2,... Обозначим = degden(gг'). Согласно следствию 2 для любых гД> 0 выполняется di+j > > di — degden(/гг').
Пользуясь этими неравенствами, часто можно избежать перебора всех значений сдвига к = = 0,..., М — 1. Алгоритм поиска к будет выглядеть следующим образом:
1. Найти q =
Q
deg Q
а = --, где Q =
gcd(Q,Q')' deg9
= den (г);
положить ho = g, do = degden(g), к = 0, i = 0.
2. Найти h{.|_i и соответствующие Pi(x), ßi в
(13);
найти
РЛх)
8i = deg den ( n /—;—— — r(x + i) ] —
— deg den
q!3' (ж + i Рг(х)
q>i% (X + i/
И ПОЛОЖИТЬ 6?г'_|_1 = di +
если б?г_|_1 < йь, положить к = I + 1; если б?г_|_1 — ¿к < degden(/iг'_|_l), то увеличить г на единицу и повторить шаг 2, иначе завершить работу.
Шаг 1 будем называть предварительной частью алгоритма, шаг 2 - основной.
Применяя этот алгоритм к решениям (3) и (6) из примеров 1 и 2, получим соответственно решения (4) и (7).
3.2. Общий алгоритм
Если известно разложение (8) остатка, то алгоритм из раздела 3.1 можно применить независимо к каждой из пар д,г(г\ г = 1 ,...,п. Пара (9), (Ю), построенная с использованием найденных величин сдвигов к\,..., кП1 будет решением задачи 2 в силу независимости вкладов этих сдвигов (следствие 1). Однако разложение знаменателя остатка на неприводимые множители может потребовать значительных затрат (в частности, если поле коэф
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.