ПРОГРАММИРОВАНИЕ, 2011, No 2, с. 28-39
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
РАЦИОНАЛЬНЫЕ РЕШЕНИЯ ЛИНЕЙНЫХ РАЗНОСТНЫХ УРАВНЕНИЙ: УНИВЕРСАЛЬНЫЕ ЗНАМЕНАТЕЛИ И ГРАНИЦЫ ЗНАМЕНАТЕЛЕЙ *
© 2011 г. С.А. Абрамов*, А. Геффар**, Д.Е. Хмельнов*** * Вычислительный центр РАН 119991 Москва, 119991, ГСП-1, ул. Вавилова, 40
**Лиможский университет, XLIM, CNRS 141980 123, ав. А. Тома, 87060, Лимож, Франция
***Вычислительный центр РАН 119991 Москва, 119991, ГСП-1, ул. Вавилова, 40 E-mail: sergeyabramov@mail.ru, f_gheffar@yahoo.fr, dennis_khmelnov@mail.ru
Поступила в редакцию 12.10.2010 г.
Исследуются сложности некоторых известных алгоритмов поиска рациональных решений линейных разностных уравнений с полиномиальными коэффициентами.
1. ВВЕДЕНИЕ
будем записывать как L(y) = ^(ж) с оператором
Поиск рациональных решений (т.е. решений, имеющих вид рациональных функций) линейных разностных уравнений входит как часть во многие компьютерно-алгебраические алгоритмы. Исследования путей построения таких решений представляют интерес для компьютерной алгебры.
Пусть к - поле характеристики 0. Мы будем рассматривать уравнения вида
у(ж + n) + ara_i(x)y(x + n - 1) + ...
■ ■ + ai(x)y(x + 1) + ao(x)y(x) = <^(ж),
(1)
^>(ж), a1 (ж),..., ап-1(ж) € k(x), a0(x) € k(x) \ {0}. Если избавиться от знаменателей, то уравнение приобретет вид
bn(x)y(x + n) + ...
+ bi(x)y(x + 1) + bo(x)y(x) = ^(ж),
(2)
■0(ж), b1 (ж),..., Ьп-1(ж) € k[x], Ь0(ж), Ьп(ж) € k[x] \ {0}. Последнее уравнение мы довольно часто
L = bn (ж)фп + ■ ■ ■ + Ь1(ж)ф + bo (ж), Ф(у(ж)) = у(ж + 1).
(3)
*Частичная поддержка РФФИ, грант 10-01-00249-а и
ECONET, грант 21315ZF.
Запись f (ж)±д(ж) будет обозначать взаимную простоту полиномов f (ж),д(ж) € к [ж]; если ^(ж) € к(ж), то ёеп^(ж) представляет собой нормированный (со старшим коэффициентом 1) полином такой, что ^ (ж) = ¿^^(ж) для некоторого f (ж) € к [ж],/ (ж)±ёеп^ (ж). Множество нормированных неприводимых полиномов из к [ж] будет обозначаться через 1гг(к[ж|). Если р(ж) € 1гг(к[ж|), / (ж) € к [ж], то уа1р(ж)/ (ж) определяется как максимальное т € N такое, что рт(ж)|/(ж) (уа1р(Х)0 = то),
и уа1Р(Ж)^(ж) = уа1р(х)/ (ж) - уа1р(х)д(ж) для Р (ж) = ЦХу, / (ж),д(ж) € к [ж].
Первый алгоритм построения всех рациональных решений уравнений вида (2) был предложен в [2]. Позднее появился алгоритм [3], а за ним еще ряд алгоритмов [5, 11, 8, 10, 7] (эти последние применимы как в скалярном случае, так и в случае систем линейных уравнений). Все известные алгоритмы поиска рациональных
решений описываются схемой, которую мы будем называть схемой RS:
RS1: Построить рациональную функцию S(ж) над к такую, что любое рациональное над к решение исходного уравнения может быть представлено как S (ж)/ (ж) с / (ж) € к [ж].
RS2: Преобразовать исходное уравнение в такое уравнение (тоже с полиномиальными коэффициентами и правой частью), что / (ж) € к [ж] является решением преобразованного уравнения если и только если S (ж)/(ж) является решением исходного уравнения.
RS3: Построить все полиномиальные решения преобразованного уравнения.
Каждая рациональная функция S (ж), которая обладает указанным в RS1 свойством, называется границей знаменателей для исходного уравнения.
Если выделить задачу построения границы знаменателей из общей задачи построения рациональных решений, т.е. рассмотреть шаг RS1, то, прежде всего, надо упомянуть, что алгоритмы из [2, 3, 5, 8, 10, 7] строят S(ж) в виде щху, где U(ж) — полином над к, называемый универсальным знаменателем для уравнения (2). Алгоритм из [11] строит рациональную функцию, которую мы будем обозначать через Я(ж). Числитель функции Я(ж) может иметь положительную степень, и в таком случае числитель любого рационального решения исходного уравнения делится на числитель функции Я(ж).
Наиболее старый алгоритм, описанный в [2], является самым медленным, и мы в дальнейшем его рассматривать не будем. Предложенный в [10] алгоритм Au построения универсальных знаменателей был усовершенствован в [7], и там же было показано, что новый вариант AU этого алгоритма имеет меньшую сложность, чем алгоритмы из [3, 5, 8]. Он имеет также меньшую сложность, чем Aи. Алгоритмы Aи, AU и алгоритмы из [3, 5, 8] находят один и тот же универсальный знаменатель U(ж). Алгоритм из
[11] в более общем виде был представлен в [10] (вместо комплексных полюсов рациональных функций над С рассматриваются неприводимые делители знаменателей рациональных функций над произвольным полем к характеристики 0).
Используя один из алгоритмов А и, А и, А в на шаге И81 и привлекая на шаге ИБЭ какой-то (один и тот же) алгоритм поиска полиномиальных решений, например, один из алгоритмов, предложенных в [1, 6, 5, 8], мы получаем алгоритмы (Аи), (Аи), (Ав) построения всех рациональных решений. В разделе мы покажем, что при естественных предположениях относительно используемого алгоритма поиска полиномиальных решений сложность алгоритма (Ав) больше сложности алгоритма (Аи). Доказанное будет подтверждено экспериментальной проверкой (раздел 4). Это позволит сделать вывод о предпочтительности (Аи) среди рассматриваемых алгоритмов поиска рациональных решений.
Заключительный раздел (5) касается систем вида
У (ж + 1) = А(ж)У (ж), (4)
У (ж) = (У1(ж), У2(ж),..., Уп(ж))т, А(ж) = (а^ (ж)) € Ма^(к(ж)). Предполагается, что существует обратная матрица А-1 (ж) = (а^(ж)) € Ма^(к(ж)). Если изначально была задана система У (ж + 1) = А(ж)У (ж) + С(ж), в которой матрица А(ж) такая же, как в (4), и С(ж) € к(ж)п, то, добавляя к У (ж) компоненту с номером п + 1 и со значением 1, мы можем преобразовать заданную систему в однородную систему с обратимой матрицей, принадлежащей Ма1га+1(к(ж)) (см., например, [11]). Поэтому мы ограничиваемся случаем однородных систем. Рассматриваются модифицированные алгоритмы (Аи), (Ав), предназначенные для поиска рациональных решений
Y (ж) = (Г1(ж),12(ж),...,1П(ж))т,
Уг(ж) € к(ж), i = 1, 2,...,n, ( )
систем. Приводятся доводы в пользу модификации (Аи) в сравнении с модификацией (Ав).
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ 2.1. МНОЖЕСТВО М
В алгоритмах Аи, Аи и Ав шаг И81 начинается с построения конечного множества М таких неприводимых полиномов, что если для какого-то рационального решения у(ж) исходного уравнения и р(ж) € 1гг(к[ж]) выполнено уа1р(х)у(ж) < 0, то р(ж) € М ([10]). Это множество кандидатов в неприводимые делители знаменателей рациональных решений строится исходя из полиномов
V (ж) = bn (ж — n), W (x) = bo (ж)
(6)
(см. (2)). Если р(ж) € Irr(k[x]), f (ж) € к[ж] \ {0}, то можно рассматривать конечное множество
Np(x)(f(ж)) = {m € Z : р(ж + m)|f(ж)}. (7)
Для случая NP(x)(f (ж)) = 0 полагаем
maxNp(x)(f(ж)) = -то, minNp(x)(f(ж)) = +то.
Множество M определяется как
M = (р(ж) € 1гг(к[ж]) : minNp(x)(W(ж)) ^ 0, maxNP(x)(V(ж)) ^ 0.
При построении M сначала находится полная факторизация полиномов V (ж),^ (ж), затем находится конечное множество Q С 1гг(к[ж]) такое, что д(ж) € Q если и только если
minNq(x)(W(ж)) = 0, maxNq(x)(V(ж)) ^ 0.
Пусть Q = 0 и Q = {qi(ж), q2(ж),..., &(ж)}, s ^ 1. Для каждого 1 ^ i ^ s рассмотрим
Mqi(x) = {9г(ж), 5г(ж + 1), . . . , д,(ж + di)}, (8)
где
Получаем
di = max Nqi(x)(V (ж)).
M = US=i Mqi(x) -
(9)
(10)
В [11] вместо М рассматривается другое множество кандидатов, названное там 5. В [10] показано, что М С 5 при к = С, и что часто М является собственным подмножеством множества >5.
Число
совпадает с дисперсией dis(V (x),W (x)) полиномов (6), т.е. с наибольшим целым m, для которого deggcd(V(x),W(x + m)) > 0; если таких целых нет, то по определению dis (V(x), W(x)) = -то.
2.2. АЛГОРИТМЫ A^ И AU
Для каждого qt(x + j) € M алгоритм Au вычисляет
Yj,t = min { E Valqt(x+j+i)V (ж)
U N
E Valqt(x+j-i)W(ж) ^
ie N
(12)
и находит затем
U(ж)= П ^(ж + j)-
(13)
04J4dt
Полином и (ж) — универсальный знаменатель для уравнения (2): любое решение у (ж) € к(ж) может быть представлено как ЦХу, (ж) € к [ж]; рациональная функция щ^у является, тем самым, границей знаменателей для этого уравнения.
Алгоритм Аи отличается от Аи тем, что учитывает возможность равенства показателей для различных (иногда многих) ] при фиксированном ¿; к опирающимся на формулу (12) арифметическим вычислениям алгоритм А'и прибегает только когда ^¿(ж + делит V(ж) или Ш(ж).
2.3. АЛГОРИТМ Ав
Алгоритм Ав использует возможность построения для положительных целых N (с помощью сдвигов уравнения (1) и гауссовых исключений) уравнений
у(ж) = зд, п—1 (ж)у(ж - N) + ...
----+ ЗД, о(ж)у(ж - N - п + 1) + зд, —1(ж),
(14)
d = max{d1, d2,..., ds}
(11)
у(ж) = WN, n—i (ж)у(ж + N ) + ... ----h WN, о(ж)у(ж + N + n — 1) + WN, —1(ж),
(15)
ум, -1(ж),зд,о(ж),... ,Ум,п-1(ж),мм, — 1 (ж), мм,0(ж),..., эдм>п-1(ж) € к(ж), N = 1, 2,..., А + 1 (см. (11)), которым удовлетворяют все рациональные решения исходного уравнения. Например, при переходе в (14) от N к N + 1 используется исключение у (ж — N) с помощью сдвинутого уравнения (1), записанного в виде
у (ж — N) + ап-1 (ж — п — N)у(ж — N — 1) + ...
■ ■ ■ + а0(ж — п — N )у(ж — п — N ) — ^(ж — п — N) = 0.
Пусть р(ж) € 1гг(к[ж]) и N — положительное целое. Определим B(p(ж),N) как минимум значений функции уа1р(х) для всех коэффициентов Ум, -1(ж),гм, о (ж),... , У М, га— 1(ж), входящих в (14), и, аналогично, определим В(р(ж), —N) как минимум значений функции уа1р(Х) для всех коэффициентов №м, —1(ж),мм, 0(ж), ..., мм,п- 1(ж), входящих в (15). Алгоритм А в последовательно строит уравнения (14) для N = 1,2,..., А + 1 и
Ь(5(ж)/(ж)) = ф(ж) выполняется если и только если К(/(ж)) = д(ж).
Обсуждение шага ИБЗ нуждается в предварительном комментарии. Оператору Ь сопоставляется алгебраическое уравнение I(Л) = 0, называемое определяющим уравнением в то. Мы будем говорить просто об определяющем уравнении, в нашем контексте это не будет приводить к недоразумениям. Основное свойство уравнения I(Л) = 0 состоит в том, что если уравнение Ь(у) = 0 имеет решение
5 (ж) = , в 1 (ж), в2 (ж) € к [ж], то целое число
(х)
уа1те5(ж) = deg в1(ж) — deg в2(ж)
является корнем определяющего уравнения ([9]). В частности, если /(ж) является полиномиальным решение
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.