ПРОГРАММИРОВАНИЕ, 2011, No 4, с. 23-27
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
НЕОПРЕДЕЛЕННОЕ СУММИРОВАНИЕ РАЦИОНАЛЬНЫХ ФУНКЦИЙ С ФАКТОРИЗАЦИЕЙ ЗНАМЕНАТЕЛЕЙ
© 2011 г. С. П. Поляков
Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 E-mail: s.p.polyakov@gmail.com Поступила в редакцию 31.05.2011
Предлагается компьютерно-алгебраический алгоритм неопределенного суммирования рациональных функций, основанный на полной факторизации знаменателей. Для данной / алгоритм находит пару рациональных функций д, г таких, что / = д(х +1) — д(х) + г, и степень знаменателя г минимальна. Также предлагается модификация алгоритма, дополнительно минимизирующая степень знаменателя д. Доказано, что без учета затрат на факторизацию знаменателя алгоритмы имеют вычислительную сложность 0(т2), где т - степень знаменателя /.
1. ВВЕДЕНИЕ
Пусть К — поле характеристики 0, / £ К(х). Функция д называется неопределенной суммой функции /, если
f = g(x + 1) - g(x).
(1)
Неопределенная сумма является дискретным аналогом неопределенного интеграла.
В компьютерной алгебре известна задача неопределенного суммирования, состоящая в поиске д, удовлетворяющей (1). Для случая д £ К(х) эта задача была впервые сформулирована и решена в [1]. В [2] предложена
Задача 1. Представить f <Е K(x) в виде f = g(x + 1) - g(x) + r,
(2)
где д,г — рациональные функции, причем г имеет знаменатель минимальной степени.
(Знаменателем и числителем рациональной функции г называются полиномы ц и р такие, что г = р, gcd(p, ц) = 1, и ц имеет единичный старший коэффициент. Будем обозначать знаменатель и числитель г соответственно den(г) и пиш(г).) Функции д и г будем называть просуммированной частью / и остатком.
Для этой задачи известен ряд алгоритмов решения — например, [2], [3], [4], [5], [6], [7]. Общим для этих алгоритмов является использование в том или ином виде дисперсии функции /, т.е. максимального целого к такого, что знаменатели / (х) и / (х + к) имеют общие множители. Это позволяет избежать затрат на полную факторизацию знаменателя /(х). Однако с появлением более эффективных алгоритмов факторизации полиномов необходимость в этом отпала: так, в работе [8] показано, что для функций из Р(х) наиболее эффективным среди существующих алгоритмов вычисления дисперсии был алгоритм, основанный на полной факторизации. В данной работе предлагается алгоритм решения задачи 1, использующий полную факторизацию знаменателя /.
Если / не имеет рациональной неопределенной суммы, то задача 1 имеет бесконечно много решений, причем среди них найдется решение со сколь угодно большой степенью знаменателя просуммированной части. Поэтому представляет интерес
Задача 2. Для данной рациональной функции / найти решение задачи 1 с минимальной степенью знаменателя просуммированной части д.
Эта задача сформулирована в [5], [9]. В [5] предложен алгоритм решения задачи 1, во многих случаях строящий решение задачи 2. Полное решение задачи 2 предложено автором в [10]. Однако алгоритм [10] во многих случаях требует значительных вычислительных затрат по сравнению с алгоритмами решения задачи 1. В данной работе предлагается модификация основанного на полной факторизации алгоритма решения задачи 1, строящая решение задачи 2 со сравнимыми затратами.
Доказано, что предложенные алгоритмы без учета затрат на факторизацию знаменателя f имеют вычислительную сложность O(m2), где m — степень знаменателя f.
Алгоритмы реализованы в системе компьютерной алгебры Maple.
Эти результаты докладывались на исследовательском семинаре по компьютерной алгебре в Московском Государственном университете им. М.В. Ломоносова в сентябре 2009 г. [11].
2. ПРЯМОЙ АЛГОРИТМ НЕОПРЕДЕЛЕННОГО СУММИРОВАНИЯ
Будем полагать, что рассматриваемая функция f удовлетворяет условию degnum(f) < degden(f) (в противном случае ее легко представить в виде суммы полинома и правильной дроби и просуммировать полиномиальную часть отдельно).
Напомним, что разложением на простейшие дроби называется представление рациональной функции в виде суммы дробей вида qa, где q — неприводимый полином, degp < deg q, a — натуральное число.
Алгоритм 1.
Ввод: рациональная функция f (x)
Вывод: д, r — 'решение задачи 1 для f (x)
1. Положить P := num(f (x)), Q := den(f(x)) и найти разложение Q на неприводимые множители.
2. Разбить множество неприводимых полиномов, делящих Q, на непересекающиеся подмножества следующим образом: полиномы qi, qj оказываются в одном подмножестве если и только если degx qd = degx q,, ad,o = aj,o
tti 1 — ttj 1 _ rw
и ai 0 ' G Z, где ai,o,ai,i и aj,o,aj,i — соответственно коэффициенты qi и qj при
ж^, ж^ \ = degx дг. Найти в каждом подмножестве полином Ог такой, что а' 1 аг' 1 > 0 для
аг' 0
любого полинома д, из того же подмножества, и
7 а,' л —а,- л
положить к, := —- для всех д, , входящих в
-3 а,' 0
подмножество.
3. Для каждого неприводимого полинома Ог, делящего найти дг(ж — Кг). Разбить неприводимые делители Q на наборы так, чтобы полиномы Ог и д, входили в один набор если и только если дг(ж — Кг) = д,(ж — К,). Упорядочить полиномы Ог внутри каждого набора по возрастанию соответствующих им
4. Представить Q в виде произведения QoQl, где неприводимые полиномы, делящие Ql, входят в наборы, содержащие более одного элемента, а полиномы из Qo — в наборы из одного элемента. Найти полиномы Ро, Р такие, что
f (ж) = Р0 + Р..
Q0 Q1
5. Используя найденное разложение знаменателя, представить ^ в виде суммы простейших дробей.
6. Пусть N — число построенных на шаге 3 наборов, содержащих более одного полинома. Для каждого такого набора = (дгд,..., д^), г = 1, ...,N, найти максимальную степень ¿¿, с которой полиномы из этого набора входят в Q, и заполнить матрицу М(г) е К: М(] := Рг,,^(ж — кг,,), где Рг,,,^ — числитель простейшей дроби со знаменателем дг, в разложении ^.
7. Для каждой матрицы М(г), г = 1, ...^, заполнить матрицу А(г) того же размера следующим образом: ^-й столбец должен содержать сумму + 1,..., од столбцов M(г).
8. Положить
N
ki, j 1
д-ЕЕЕ Е
i=1 d=1 j=2 k=ki , j—1
j (x + k)
qi!,-(x - ki,j +k),
r :=
Po
Qo
N
+
i=1 d=1
^ A1id(x)
и завершить работу.
Теорема 1. Найденные Алгоритмом 1 д, г являются решением задачи 1 для f (ж).
НЕОПРЕДЕЛЕННОЕ СУММИРОВАНИЕ РАЦИОНАЛЬНЫХ ФУНКЦИЙ
25
Доказательство. Согласно [2], пара 0, / является решением задачи 1 для / если и только если / имеет нулевую дисперсию. При разбиении неприводимых полиномов на наборы на шаге 3 два неприводимых полинома ^ попадут в один набор если и только если -¿(х + к) = qj(х) для целого к, следовательно, найденный алгоритмом остаток г имеет нулевую дисперсию. Для д, г справедливо
д(х + 1) — д(х) = г(0
М$(х + к„-) М« (х)
= /(х) — г,
1.-7. Соответствуют шагам 1-7 Алгоритма 1.
8. Для каждой матрицы М(г), г = 1,...,Ж,
-г(^)
заполнить матрицу А того же размера
—(¿)
следующим образом: _?-й столбец А должен содержать сумму 1,..., ^ столбцов М(г).
9. Для г = 1,..., N, j = 1,..., ад найти — максимальный номер ненулевого элемента в j-м столбце А« (если все элементы нулевые, положить dг)j := 0). Найти аналогичные
значения для матрицы А . Найти
1 < ^ < ад, при котором сумма
Ш;- 1
У^ (ki,j+1 — ki,j)^¿^ + Е (ki,j — кад-1)йi,j j=1 + 1
поэтому они являются решением задачи 1. а
Теорема 2. Пусть degx О = т. Тогда для выполнения алгоритма 1 начиная с шага 2 достаточно 0(т2) операций над элементами поля.
Доказательство. Для выполнения шага 2 достаточно 0(т2) операций, поскольку число различных неприводимых полиномов, делящих О, не превосходит т. Для р(х) £ К[х],к £ Ъ вычисление коэффициентов полинома р(х + к) требует O((degр(х))2) операций над элементами К, поэтому, поскольку сумма степеней полиномов q¿, для которых нужно найти q¿(x—ki) на шаге 3, не превосходит т, то вычисление коэффициентов -¿(х + ki) требует не более 0(т2) операций. Разложение на простейшие дроби требует 0(т2) операций согласно теореме 5.31 из [12]. Суммарное число коэффициентов в ненулевых полиномах (г = 1, ...,N,
й = 1,..., ¿¿, j = 1,..., ад) и, следовательно, их суммарная степень не превосходят т, поэтому для построения р^Дх — ki) и суммирования столбцов матриц, составленных из этих полиномов, также достаточно 0(т2) операций.
3. СУММИРОВАНИЕ С МИНИМИЗАЦИЕЙ ПРОСУММИРОВАННОЙ ЧАСТИ
Алгоритм 2. Ввод: рациональная функция /(х). Вывод: д, г — 'решение задачи 2 для /(х)
минимальна. 10. Положить
N 6; Ш;
1
д-ЕЕ Е Е
(х + к)
-О!, (х — ki,j + к)
¿=1 ¿=1 ¿>.?
N 6; Ш;-1 -1 (х + к)
¿=1 ¿1 ¿1 ^ «Р^лТ^:
г:= оо+ ^ ^
¿=1 ¿=1
и завершить работу.
Чтобы доказать, что алгоритм 2 строит решение задачи 2, нам понадобится несколько вспомогательных утверждений.
Пусть нам известно какое-то решение д, г задачи 1 для / £ К(х), г = 0. Остаток г имеет нулевую дисперсию, следовательно, его можно представить в виде
г = г(1) + ••• + г(п) = + ■■■ + -рП, (3)
где -1,..., — неприводимые полиномы такие, что для любого целого к и любых г, 1 < г < j < п, выполнено
gcd(q¿(x),qj (х + к)) = 1.
(4)
В [13] предложено полное описание семейства решений задачи 1:
а
Теорема 3. Пусть остаток r имеет вид (3). Тогда пара правильных дробей g',r' будет решением задачи 1 если и только если
n max(-i,ki-i)
g' = gkb...,k„ = g-^ sign(ki) 53 r(i)(x+j^
i=1 j=min(0,fci)
(5)
r' = rfcl,...,fc„ = r(i)(x + ki) + ••• + r(n)(x + kn), (6) где ki,..., kn — целые числа.
Для i = 1, ...,n, ki g Z обозначим степени вхождения ^¿(ж + ki) в знаменатели go,...,o,ki,o,...,o и go,...,o,ki+i,o,...,o как ^¿,ki и ^i,ki соответственно.
Лемма 1. Пусть 1 < i < n, k, — произвольное целое число. Тогда степень вхождения qi(x+ Ki) в знаменатель просуммированной части (5) любого решения задачи 1 равна , если ki < k,, и , если ki > Ki.
Доказательство. Это следует из (4) и из того, что для любых ki,..., kn знаменатели просуммированных частей gk1,...,ki,...,kn и gk1,...,ki+i,...,kn отличаются только степенями вхождения ^¿(ж + ki). а
Лемма 2. Если
min degden(go,...,o,ki,o,...,o) = degden(go,...,o,k*,o,...,o), kieZ i
то найдется 'решение (55), (6) задачи 2, в котором ki = k*.
Доказательство. Это следует из того, чт
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.