ПРОГРАММИРОВАНИЕ, 2015, No 2, с. 69-80
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 517.929
ПОИСК РАЦИОНАЛЬНЫХ РЕШЕНИЙ ДИФФЕРЕНЦИАЛЬНЫХ И РАЗНОСТНЫХ СИСТЕМ С ПОМОЩЬЮ ФОРМАЛЬНЫХ РЯДОВ *
© 2015 г. С. А. Абрамов
Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 E-mail: sergeyabramov@mail.ru Поступила в редакцию 15.09.2014
Рассматриваются линейные дифференциальные и разностные системы произвольного порядка с полиномиальными коэффициентами. Предлагается алгоритм поиска их рациональных решений, основанный на том, что формальные ряды, в которые разлагаются эти решения, после умножения на предварительно найденный универсальный знаменатель становятся полиномами. Описывается также комбинированный алгоритм с элементами эвристики. Для сокращения вычислительных затрат этот последний выбирает в некоторый момент между двумя алгоритмами — новым и стандартным, основанном на использовании универсального знаменателя для замены неизвестных в системе и последующем поиске полиномиальных решений.
1. ВВЕДЕНИЕ
Пусть К — поле характер и стики 0. Для кольца полиномов и поля рациональных функций от х над К в дальнейшем используются обычные обозначения К [х] и К (х). Поле формальных ло-рановых рядов обозначается через К((х)). Если К — некоторое кольцо (в частности, поле), то Ма^(К) обозначает кольцо квадратных матриц порядка т с элементами из К.
Мы рассматриваем системы вида
Лг (х)£г у (х) + ■ ■ ■ + А1(х)£у(х) + Ао(х)у(х) = 0,
(1)
£ € {зХ, Е}, где Е — оператор сдвига: Еу(х) = у(х + 1). Квадратные матрицы АДх), г = 0,1,..., г, имеют порядок т, их элементы принадлежат К[х], при этом Аг(х),Ао(х) — ненулевые ведущая и трейлинговая матрицы; у(х) = (у1(х),у2(х),... ,ут(х))т — столбец неизвестных функций (Т — знак транспонирования). Число г называется порядком системы. Предполагается без дополнительных оговорок, что рассматриваемая система имеет полный ранг,
или, иначе, является системой полного ранга, т.е. входящие в систему уравнения независимы над кольцом операторов К(х)[£]. Система (1) может быть записана в виде £(у) = 0 гДе ^ — это оператор
Ar (x)£r + ■ ■ ■ + + Ao(x).
Решение y(x) = (y1(x), y2(x),..., ym(x))
(2)
T
К(х)т системы (1) называется рациональным. Если у(х) € К[х]т, то это решение является полиномиальным (частный случай рационального решения).
Хорошо известны (см., например, [1, 2, 3, 4, 5]) алгоритмы поиска всех рациональных решений нормальных систем уравнений первого порядка:
£у(ж) = A(x)y(x),
(3)
*Частичная поддержка РФФИ, грант 13-01-00182-а.
где А(х) € Ма^(К(х)), при этом в разностном А(х)
в Ма^(К(х)). Алгоритмы из [1, 2, 4, 5] основаны на нахождении некоторого универсального знаменателя рациональных решений исходной системы, или, как для краткости мы будем писать, универсального знаменателя для исходной системы, т.е. такого полинома V(х) € К[х],
что если система имеет рациональное решение у(ж) € К(ж)т, то оно может быть представлено как щХ) г (ж), где г (ж) € К [ж]т. Зная универсальный знаменатель, можно сделать подстановку
У(ж) =
1
и (ж)
где г(ж) = (^1,...,гт)т — вектор новых неизвестных, и преобразовать исходную систему в систему для г(ж), а затем применить один из алгоритмов поиска полиномиальных решений (см., например, [1, 2, 6]).
Значительно реже задача поиска рациональных решений рассматривалась для систем полного ранга, имеющих вид (1), когда не исключается вырожденность матриц Ао (ж), Аг (ж) — одной из них или обеих. Тем не менее соответствующие алгоритмы были предложены в [7] (дифференциальный случай) и [8] (разностный случай). Эти алгоритмы также основаны на том, что найденный на одном из начальных этапов
и(ж)
на следующем этапе для подстановки (4), затем следует поиск полиномиальных решений получившейся новой системы.
Ниже рассматривается несколько иной подход, он основан на разложении в ряд (с произвольными постоянными, входящими линейно в его коэффициенты) общего решения исходной системы (1). После умножения на предваритель-
и(ж)
те ряды, которые соответствуют рациональным решениям, становятся полиномами. Для реализации этой общей схемы в виде алгоритма мы рассматриваем формальные ряды по убывающим степеням (можно также говорить о разложении в ряд в точке те). Каждый такой ряд
ж
неотрицательными показателями и, возможно, бесконечное число степеней — с отрицательными. Условимся называть степенью deg у(ж) ряда у (ж) наибольший показатель степени ж, входящей в ряд у (ж) с ненулевым коэффициентом (т.е. с коэффициентом, являющимся ненулевым столбцом). Если у(ж) представляет собой нулевой ряд, то полагаем deg у(ж) = —те.
В случае дифференциальной системы
Аг (ж)у(г)(ж) + ■ ■ ■ + А1(ж)у' (ж) + Ао(ж)у(ж) = 0
(5)
г (ж),
(4)
рассматриваемые ряды принадлежат Кт((ж-1)). В случае разностной системы
Аг (ж)у(ж + г) + ■ ■ ■ + А1(ж)у(ж + 1) +
+ Ао(ж)у(ж) = 0 (6)
привлекаются ряды по степеням жп (см., например, [9, гл. 10]):
ж(ж — 1)... (ж — п + 1), если п > 0,
жп ={ 1,
1
(ж+1)(ж+2)...(ж+Н):
если п = 0, если п < 0.
(7)
Двусторонние последовательности рациональных функций
мы будем привлекать как базисы для разложения (представления рядами) решений систем соответственно в дифференциальном и разностном случаях. Пусть разложение решения системы в соответствующем базисе имеет коэффициенты -и(п) = (г^(п),..., -ит(п))т. Тогда последовательность -и(п) удовлетворяет индуцированной рекуррентной системе
Вг(п)и(п + 1) + Вг_1(п)и(п + 1 — 1) + ■ ■ ■ +
+ В4(п)и(п + Ь)=0, (8)
где целые 1, Ь таковы, что 1 ^ и
В4(п),..., В1 (п) € Ма^(К[п]) ([10]).
Мы используем термин "индуцированная рекуррентная система", а не "индуцированная разностная система", подчеркивая этим особую роль индуцированных систем. Для краткости мы часто будем говорить просто об индуцированных системах. Их построение обсуждается в п. 2.2. Величина 1 — Ь называется порядком системы (8).
Рассматривая начальные члены, коэффициенты которых удовлетворяют индуцированной системе (коэффициенты при всех достаточно больших степенях по нашему соглашению представляют собой нулевые вектор-столбцы), мы можем столкнуться как с тем, что существует продолжение этого начального фрагмента до формального ряда, являющегося решением исходной системы, так и с тем, что такое продолжение невозможно. Мы будем в дальнейшем использовать осторожный термин формальная сум,мм, понимая под этим формальную сумму д(п)жп
в дифференциальном случае и д(п)хп —
в разностном, д(п) € Кт. При этом д(п) = 0 при всех достаточно больших п для каждой конкретной формальной суммы, тем самым каждая формальная сумма содержит конечное число ненулевых слагаемых. Если /(х) является формальной суммой указанного вида и д(п) — последовательность ее коэффициентов, то число N будем называть границей этой последовательности, используя для этой границы обозначение stpд(п). Наибольшее такое п, что д(п) = 0 в /(х)
/(х), используя обозначение deg/(х); при этом deg /(х) = -ю, если формальная сумма /(х) содержит только нулевые слагаемые.
Если последовательность д(п) коэффициентов формальной суммы удовлетворяет индуцированной системе, то эта формальная сумма является подчиненной исходной системе.
Новый алгоритм использует построение подчиненных системе формальных сумм, границы которых выбираются некоторым специальным образом. Вообще говоря, мы не можем без существенных вычислительных затрат определить, допускает ли та или иная формальная сумма продолжение до формального ряда, являющегося решением исходной системы. Однако те "полезные" формальные суммы, которые отбирает алгоритм, допускают такое продолжение, — мы доказываем это в п. 4.3.
Новый алгоритм обходится без подстановок вида (4), используемая им индуцированная система в достаточно общей ситуации имеет меньший порядок. При равных прочих условиях это является несомненным преимуществом нового алгоритма. Проблема может возникнуть с числом элементов последовательности, которые предстоит найти с помощью рекуррентной системы: стандартный алгоритм иногда обходится меньшим их числом.
В разделе 6 описывается комбинированный, являющийся в какой-то мере эвристическим, алгоритм, который для сокращения вычислительных затрат выбирает на основе анализа промежуточных результатов, следовать ли новому алгоритму или же стандартному, основанному на использовании универсального знаменателя для замены неизвестных в системе и последующем поиске полиномиальных решений.
Если исходная система неоднородна и правая ее часть принадлежит К[х]т, то добавлением к у (х) дополнительной (т + 1)-й компоненты ут+1(х) с постоянным значени-1
в однородную (преобразованные матрицы Ао(х), А1 (х),..., Аг(х) будут принадлежать Ма^+1(К[х])). Мы в дальнейшем рассматриваем только однородные системы.
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
2.1. Охватывающие системы
Ведущая матрица системы может оказаться необратимой в Ма^(К(х)), т.е. вырожденой, и это порождает известные трудности для поиска решений. Алгоритмы ЕС^ и ЕССТ позволяют обходить препятствия такого рода. Для любой системы 5 вида (1) алгоритм ЕС^ в дифференциальном случае, а алгоритм ЕССТ — в разностном, строят ¿-охватывающую систему 5 с невырожденной ведущей матрицей Аг (х). При этом множество решений системы 5 содержит все решения системы 5.
В разностном случае для системы 5 можно с помощью алгоритма ЕССТ помимо ¿-охватывающей системы построить и
охватывающую систему 5 вида (1) с невырожденной трейлинговой матрицей Ао(х). При этом множество решений системы 5 содержит
5
Дополнительно алгоритм ЕССТ находит конечное множество С линейных ограничений, т.е. линейных соотношений с постоянными коэффициентами для конечного множества значений уДп+ ]), г = 1,...,т ] =0,1,..., г. Каждое линейное ограничение получается из одного из уравнений системы на некотором этапе ее преобразования: в это уравнение подставляется некоторое конкретное значение переменной. Мы будем использовать линейные ограничения при рассмотрении решений в виде последовательностей с элементами из Кт, для этого нам будет достаточно линейных ограничений, для которых п € В результате применения ЕССТ получается пара (5,С), с тем же множеством решений, что и 5, при этом ве
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.