КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.92+004.94
ЗНАМЕНАТЕЛИ РАЦИОНАЛЬНЫХ РЕШЕНИИ ЛИНЕИНЫХ РАЗНОСТНЫХ СИСТЕМ ПРОИЗВОЛЬНОГО ПОРЯДКА *
© 2012 г. С. А. Абрамов, Д. Е. Хмельнов
Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 E-mail: sergeyabramov@mail.ru, dennis_khmelnov@mail.ru Поступила в редакцию 31.05.2011
Предлагается алгоритм поиска универсального знаменателя рациональных решений системы линейных разностных уравнений с полиномиальными коэффициентами. Уравнения системы могут иметь произвольные порядки.
1. ВВЕДЕНИЕ
Поиск рациональных решений (т.е. решений, имеющих вид рациональных функций) линейных разностных уравнений и систем представляет самостоятельный интерес и, кроме этого, входит как часть в различные компьютерно-алгебраические алгоритмы.
Пусть к — поле характеристики 0. Для кольца полиномов и поля рациональных функций от х с коэффициентами в поле к мы в дальнейшем используем обычные обозначения к[х] и к(х). В статье рассматриваются системы вида
Аг (х)у(х + г) + ■ ■ ■ + А1(х)у(х + 1) +
+ Ао(х)у(х) = Ь(х), (1)
где
А0(х), А1(х),..., Аг (х) суть квадратные матрицы порядка т, элементы которых принадлежат к[х] (запись: А0(х), А1(х), ..., Аг(х) е Ма^(к[х])), при этом предполагается, что матрицы А0(х), Аг (х) ненулевые,
Ь(х) = (Ь1(х),Ь2(х),...,Мх))т е к[х]т —
Число r называется порядком системы. Система
Ar (x)y(x + r) +
+ Ai(x)y(x + 1) +
+ Ao(x)y(x) = 0
(2)
— однородная система, соответствующая (1). Мы предполагаем, что ее уравнения независимы над к[х, ф], где ф — оператор сдвига:
Ф(у(х)) = у(х + 1).
Решение у(х) = (ш(х), У2(х),..., Ут(х))т е к(х)т системы (1) называется рациональным. Если у(х) е к[х]т, то это решение также является полиномиальным (частный случай рационального решения).
Хорошо известны (см. [7, 11, 13, 12, 10]) алгоритмы поиска всех рациональных решений нормальных систем уравнений первого порядка:
y(x + 1) = A(x)y(x),
(3)
где А(х) обратимая в Ма^(к(х)) матрица. Алгоритмы из [7, 11, 12, 10] основаны на нахождении некоторого универсального знаменателя рациональных решений исходной системы, или, как для краткости мы будем писать, универсального знаменателя для исходной системы, т.е. такого полинома и(х) е к[х], что если система имеет рациональное решение у(х) е к(х)т, то * Частичная поддержка РФФИ, грант 10-01-00249-а. оно может быть представлено как цщ ^(х), где
правая часть системы,
y(x) = (yi(x),y2(x),... ,ym(x))T — столбец неизвестных.
¿(ж) е к[ж]т. Зная универсальный знаменатель, можно сделать подстановку и преобразовать исходную систему в систему для ¿(ж), а затем применить один из известных алгоритмов (см., например, [7, 11, 5]) поиска полиномиальных решений.
Предложенный в [12] алгоритм А и построения универсальных знаменателей для систем вида (3) был усовершенствован в [10], и там же было показано, что новый вариант Аи этого алгоритма имеет меньшую сложность, чем алгоритмы из [7, 11]. Он имеет также меньшую сложность, чем А и. Алгоритмы А и, Аи и алгоритмы из [7, 11] находят один и тот же универсальный знаменатель и (ж).
В разделе 2 вводятся необходимые понятия и рассказывается об основной идее алгоритма Аи. В разделе 3 мы показываем, как эта идея обобщается на случай систем вида (1); важную роль здесь играет построение так называемых охватывающих систем, о которых будет заранее сказано в разделе 2.3. Новый алгоритм построения универсального знаменателя вместе с алгоритмом из [5] построения полиномиальных решений дает эффективный (как показывают наши эксперименты) алгоритм построения всех рациональных решений. Насколько известно авторам, это первый алгоритм такого рода, применимый к произвольным системам вида (1).
Построение универсального знаменателя и собственно рациональных решений может быть выполнено и с помощью преобразования исходной системы в систему первого порядка. В разделе 5 мы показываем преимущества предлагаемого в статье алгоритма перед алгоритмом, основанном на этом преобразовании.
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
2.1. Порядки по отношению к неприводимым полиномам
Введем ряд обозначений. Запись / (ж)±д(ж) будет обозначать взаимную простоту полиномов / (ж), д(ж) е к [ж]; если ^ (ж) е к(ж), то ёеп^ (ж) представляет собой нормированный (со старшим коэффициентом 1) полином такой, что ^(ж) = аепл>) для некоторого
/ (ж) е к [ж], /(ж)±ёеп^(ж). Множество нормированных неприводимых полиномов из к[ж] будет обозначаться через 1гг(к[ж]). Если р(ж) е 1гг(к[ж]), /(ж) е к [ж], то уа1р(х)/(ж) определяется как максимальное п е N такое, что рп(ж)|/(ж) (уа1р(х)0 = те), и уа1Р(х)^(ж) = уа1р(х)/ (ж) - уа1р(х) 5(ж) для Р (ж) = ¿(Х), / (ж),#(ж) е к [ж]. Для двух произвольных ненулевых рациональных функций г(ж), «(ж) и р(ж) е 1гг(к[ж]) выполняются соотношения
уа1р(х)(г(ж)в(ж)) = уа1р(ж)г(ж) + уа1р(л)в(ж), уа1р(х)(г(ж)+«(ж)) ^ ш1п{уа1р(ж)г(ж), уа1р(ж)«(ж)}.
Если ^(ж) = (^1 (ж),^2(ж),...,^т(ж))т е к(ж)т, то ёеп^(ж) = 1ешт=1ёеп^г(ж) и уа1р(х)^(ж) = шт^ уа1р(Х)^г(ж), где 1еш — обозначение наименьшего общего кратного полиномов.
Для произвольной матрицы А(ж) = (а^ (ж)) е Ма^(к(ж)) мы определяем ёепА(ж) = 1ешт=1 кшт^еп а^ (ж).
2.2. Нормальные системы уравнений первого порядка
Для системы (3) положим
V(ж) = ёепА(ж - 1), Ш(ж) = ёепА-1(ж).
Тогда для любого рационального решения у (ж) этой системы и для любого р(ж) е 1гг(к[ж]) выполнено неравенство
уа1р(х)У(ж) ^ - ш1п ^ ^ уа1р(х+^-) V(ж), 3 N
^ уа1р(ж-^)Ш(ж)(4)
зе N
([12]), пользуясь которым можно, во-первых, эффективно найти такое конечное множество М неприводимых полиномов, что если знаменатель некоторого рационального решения этой системы делится на р(ж) е 1гг(к[ж]), то р(ж) е М, и, во-вторых, определить некоторый универсальный знаменатель
и (ж) = ^ (ж),
р(х)ем
где 7р(ж) обозначает абсолютную величину правой части неравенства (4).
Алгоритм А^ отличается от А и тем, что учитывает возможность равенства показателей 7р(ж) для различных (иногда многих) р(х), отличающихся друг от друга сдвигом на целое число. Входными данными для АЦ^ служат полиномы V (х) и Ш (х), связь которых с какой-либо системой уравнений для этого алгоритма значения не имеет.
В разделе 3 мы покажем, как находить V(х) и Ш(х) для системы (2), чтобы затем универсальный знаменатель для нее мог вычисляться алгоритмом Аи. Существенную роль здесь играет возможность построения так называемых охватывающих систем для данной системы.
2.3. Охватывающие системы
Для любой системы 5 вида (1) можно построить I-охватывающую систему 5
Аг (х)у(х + г) + ■ ■ ■ + А1(х)у(х + 1) +
+ Ао(х)у(х) = Ь(х), (6)
ведущая матрица которой обратима в Ма^(к(х)), а множество решений содержит все решения системы 5. Аналогично, можно построить охватывающую систему 5
Аг (х)у(х + г) + ■ ■ ■ + А1 (х)у(х + 1) +
+ Ао(х)у(х) = Ь(х), (7)
ее трейлинговая матрица обратима в Ма1т(к(х)), и множество решений содержит все решения системы 5. При этом элементы матриц и правых частей, входящих в (6), (7), принадлежат к[х]. Не исключается равенство нулю матриц Ао(х), Аг (х) — как одной из них, так и обеих.
Построение охватывающих систем может быть выполнено алгоритмами ЕС ([6]) и ЕС ([8]); алгоритм ЕС является усовершенствованной версией алгоритма ЕС.
Примечание 1. Если 5 и 5 являются I- и £-охватывающими системами, построенными алгоритмом ЕС' для (1), то I- и Ь-охватываю-щие системы, построенные алгоритмом ЕС' для (2), совпадают с однородными системами, соответствующими 5 и 5.
Алгоритм ЕС заключается в последовательном повторении двух этапов — редукции и сдвига; повторение продолжается пока строки ведущей (трейлинговой) матрицы остаются линейно зависимыми над к. На этапе редукции находятся коэффициенты зависимости, а затем уравнение, отвечающее одной из зависимых строк, заменяется линейной комбинацией других уравнений, и строка ведущей (трейлинговой) матрицы становится нулевой. На этапе сдвига к новому уравнению применяется оператор ф (или соответственно ф-1). Следование некоторому простому правилу выбора заменяемых зависимых строк гарантирует завершение выполнения алгоритма.
3. УНИВЕРСАЛЬНЫЙ ЗНАМЕНАТЕЛЬ РАЦИОНАЛЬНЫХ РЕШЕНИЙ СИСТЕМЫ ПРОИЗВОЛЬНОГО ПОРЯДКА
Вначале рассмотрим однородный случай (2). Если ведущая матрица Аг (х) системы (2) обратима в Ма1т(к(х)), то эту систему можно переписать как систему вида (3):
У (х + 1) = А(х)У (х),
где
0
А(х) =
1т
00 V Ао (х) А1(х)
Аг-1(х) )
(Ак (х) = -А-1(х)Ак (х), /„ матрица порядка т),
У (х) = (у(х)т ,у(х + 1)т,...,
единичная
у(х + г - 1)т)т , (9)
матрица А(х) принадлежит Ма1гт(к(х)), вектор У (х) имеет гт компонент. Если дополнительно матрица Ао(х) обратима в Ма^(к(х)), то А(х) обратима в Ма^т(к(х)):
А-1(х)=
( А1(х)
!т 0
А-1(х) Аг (х) \ 00
1т 0 /
(10)
0
т
(Лк(ж) = — Л-^ж^^(ж)). Следовательно, если матрицы Ло(ж), А1(ж) обратимы, то универсальный знаменатель для системы (2) может быть найден применением алгоритма Аи к
V(ж) = ёепЛ(ж — г), Ш(ж) = ёепЛ-1(ж);
привлечение Л(ж — г) вместо Л(ж — 1) в качестве V(ж) правомерно в силу того, что нам нужен универсальный знаменатель только для компонент у1(ж),у2(ж),... , ут(ж) вектора У (ж).
Теперь рассмотрим систему (2) без предположения об обратимости матриц Ло(ж) и Лг (ж) в Ма^(к(ж)) Для исходной системы можно найти I- и ¿-охватывающие системы вида (6) и (7) с нулевыми правыми частями. Любое решение исходной системы будет также решением системы
Доказательство. Запишем систему (11) в виде
Вг+1(ж)у(ж + г + 1) + ■ ■ ■ + В1(ж)у(ж + 1) +
+ Во(ж)у(ж) = 0,
здесь
Д.+1(ж) = Лг (ж), Во (ж) = Ло(ж). (12)
Согласно примечанию 1, найдется такая правая часть с(ж) е к[ж]т, что любое решение системы (1) будет также решением системы
Вг+1(ж)у(ж + 1) + ■ ■ ■ + В1(ж)у(ж + 1) +
+ Во(ж)у(ж) = с(ж), (13)
Добавляя к у (ж) компоненту ут+1(ж), мы можем преобразовать (13) в однородную систему
Лг (ж + 1)у (ж + г + 1) + (л4г-1(ж + 1) + + Лг (ж)) у(ж + г) + ■ ■ ■ + (Ло(ж + 1) +
Л^ж)) у(ж + 1)+ Ло(ж)у(ж) = 0, (11)
в которой ведущая и трейлинговая матрицы обратимы в Ма^(к(ж)), что позволяет применить описанный выше подход. Таким образом, получаем следующую лемму.
Лемма 1. Пусть Лг(ж) — ведущая матрица I
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.