КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.92+004.94
ЛИНЕИНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ И РАЗНОСТНЫЕ СИСТЕМЫ: EG^- И EGa- ИСКЛЮЧЕНИЯ *
© 2013 г. С. А. Абрамов, Д. Е. Хмельнов
Вычислительный центр РАН 119333 Москва, ул. Вавилова, 40 E-mail: sergeyabramov@mail.ru, dennis_khmelnov@mail.ru Поступила в редакцию 31.08.2012
Рассматриваются системы линейных обыкновенных дифференциальных и разностных уравнений вида Аг (ж)£г у(ж) + ••• + А1 (ж)£у(ж) + А0(ж)у(ж) = 0, £ € {, Е} (здесь Е — оператор сдвига: Еу(ж) = у(ж + 1)). Коэффициенты АДж), г = 0,..., г, суть квадратные матрицы порядка ш, их элементы — полиномы от ж над некоторым числовым полем К, при этом Аг(ж),Ао(ж) — ненулевые матрицы. Уравнения системы предполагаются независимыми над К [ж,£]. Для любой системы Б такого вида алгоритм ЕС^ в дифференциальном случае и алгоритм ЕССТ в разностном случае строят, в частности, I-охватывающую систему Б того же вида,, то с такой ведущей матрицей Аг(ж), определитель которой есть ненулевой полином. При этом множество решений системы Б содержит все решения системы Б. (Алгоритм ЕССТ предоставляет и ряд дополнительных возможностей.) Даются примеры решаемых с помощью ЕС^ и ЕССТ задач. Описывается пакет ЕС, реализующий предлагаемые алгоритмы в системе компьютерной алгебры Мар1е.
1. ВВЕДЕНИЕ
Пусть К — числовое поле: Q С К С С. Для кольца полиномов и поля рациональных функций от ж над К мы в дальнейшем используем обычные обозначения К [ж] и К (ж). Кольцо фор-
жК
ется через К [[ж]], поле формальных лорановых рядов — через К ((ж)). Есл и Я — некоторое кольцо (в частности, поле), то Ма^(Я) обозначает кольцо квадратных матриц порядка ш с элемен-Я
Будут рассматриваться системы вида
Аг (ж)£г у (ж) + • • • + А1(ж)£у(ж) + Ао(ж)у(ж) = 0,
(1)
£ € {зХ, Е}, где Е — оператор сдвига: Еу(ж) = у(ж + 1) Коэффициенты АДж), г = 0,..., г, суть
ш
рых принадлежат К[ж]: А0(ж), А1(ж),..., Аг(ж) € Ма^(К[ж]), при этом Аг(ж),А0(ж) — ненулевые ведущая и трейлинговая матрицы; у (ж) =
*Частичная поддержка РФФИ, грант 13-01-00182-а.
(у1(ж), у2(ж),..., ут(ж))т — столбец неизвестных функций (Т — знак транспонирования). Число г называется порядком системы.
Обозначив г-ю строку матрицы А^ (ж) через А^(ж), можем записать уравнения, составляющие систему (1), как
А« (ж)£г у (ж) + • • •+А« (ж)£у(ж) + А0г) (ж)у(ж) = 0,
г = 1, 2,..., ш. Если не оговорено противное, эти уравнения всюду ниже предполагаются независимыми над К [ж, £] (иначе говоря, система (1) имеет полный ранг): пусть и1 = 0, и2 = 0,..., ит = 0 — уравнения, составляющие систему (1), и ^1,Ь2, ...,Ьт € К[ж,£], тогда ¿1(^1) + ¿2(и2) + • • • + ¿т(ит) = 0 представляет собой уравнение 0 = 0, если и только если ¿1 = ¿2 =
• • • = ¿т =
В общем случае ведущая матрица необратима в Ма^(К(ж)), т.е вырождена, и это порождает известные сложности при вычислениях, связан-
ш=1
случае скалярного уравнения, полином Аг (ж) обращается в нуль для конечного множества зна-
51
4*
чений x, они представляют особый интерес при исследовании и решении уравнения. При m > 1
x
которых определитель матрицы Ar (x) обращается в нуль, но это только если определитель не равен нулю тождественно. Алгоритмы EG^ и EGo позволяют обходить препятствия такого рода. Для любой системы S вида (1) алгоритм EG^ в дифференциальном случае, а алгоритм EGo — в разностном, строят I-охватывающую систему S вида (1) с невырожденной ведущей матрицей Ar(x). При этом множество решений системы S
S
5 и а для отображений, соответственно обладающих свойствами дифференцирования и сдвига, используются в теории полиномов Ope ([46]).)
Разностный случай оказывается еще более податливым, что в значительной степени объясняется тем, что для E существует однозначно определенное обратное преобразование E-1y(x) = y(x — 1). Для разностной системы S вида (1) можно с помощью алгоритма EGo построить и t-охватывающую систему S вида_(1) с невырожденной трейлинговой матрицей Ao(x). При этом множество решений системы S содержит все решения системы S. Дополнительно алгоритм EGo находит конечное множество C линейных ограничений, т.е. линейных соотношений с постоянными коэффициентами для конечного множества значений y^(a + j), a G K, i = 1,2,..., m, j = 1, 2,... ,r (a фиксировано для любого отдельного линейного ограничения, К обозначает алгебраическое замыкание поля К). В результате применения EGo получается система (S,C), S
ственно трейлинговая матрица системы S невырождена.
Известно, что возможно сведение системы вида (1) к системе первого порядка Mi(x)£Y(x) + Mo(x)Y(x) = 0, где Mo(x),Mi(x) G Matrm(K(x)) и
Y (x) = (y(x)T, (£y(x))T,..., (£r-1y(x))T )T .
Эту систему можно переписать в виде пары, состоящей из двух систем. Первая из них — это
Bi(x){Y(x) + Bo(x)Y(x) = 0,
где B0(x),B1(x) G Mats(K(x)), s ^ rm, матрица Bi(x) невырождена и вектор У (x) содержит s
неизвестных функций, входящих в Y(ж). Вторая — алгебраическая линейная система, позволяющая выразить все не входящие в Y(x) компоненты вектора Y(ж) через компоненты Y(x). (См., например, [48], [4, разд. 2.3] — дифференциальный случай, [5, разд. 5] — разностный случай.) При £ = E, т.е. в разностном случае, возможно добиться того, чтобы и матрица Bo (ж) также была невырожденной. Если считать, что m фиксировано, а r возрастает, то сложность EG^ и EG^ есть O(r2), при этом в [4], [5] показано, что сложность описанного преобразования растет быстрее, чем r3. Это преобразование к системе первого порядка мы далее не рассматриваем.
В статье собраны вместе и изложены с единой точки зрения результаты, опубликованные в [4], [5], [10], [12], [15],'[16], [18], [23], [24]. В разделах 2, 3 описываются алгоритмы EG^ и EGCT построения охватывающих систем. В разделе 4 речь идет о том, что само существование охватывающих систем позволяет дать простые доказательства ряда важных свойств пространств решений линейных и дифференциальных систем полного ранга. В разделе 5 вводится понятие индуцированной рекуррентной системы. Такой системе должны удовлетворять коэффициенты разложения (в подходящем базисе) решения исходной системы. Показывается, как с помощью индуцированной рекуррентной системы и алгоритмов EG^, EGCT построить определяющее уравнение исходной системы. Раздел 6 посвящен меро-морфным решениям разностных систем. В разделе 7 мы даем примеры алгоритмов поиска решений различных видов; алгоритмы используют индуцированные рекуррентные системы. В разделе 8 показывается, что алгоритмы EG^ и EGCT могут применяться и к неоднородным системам, а также что если система не имеет полного ранга, то EG^ и EGCT позволяют найти ранг системы и привести ее к удобному виду. Дополнительно вкратце рассматривается случай q-разностных систем. В разделе 9 предлагается рандомизация и некоторые эвристики для EG<s и EGCT. В разделе 10 коротко упоминаются некоторые другие подходы к рассматриваемым в статье задачам. Наконец, в разделе 11 дается описание пакетов LinearFunctionalSystems и EG, реализующих обсуждаемые алгоритмы в системе компьютерной алгебры Maple ([49]).
2. ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ СИСТЕМЫ
В дифференциальном случае исходная система S имеет вид
Ar (ж)У(г)(ж) + ■ ■ ■ + + Ao(x)y(x) = 0.
(2)
S
строить ¿-охватывающую систему S
Ar (x)y(r)(x) + ■ ■ ■ + Ai(x)y'(x) + Ao(x)y(x) = 0,
(3)
с невырожденной ведущей матрицей и множеством решений, содержащим все решения систе-S
Ao(x).
Пусть г-я строка матрицы As(x), 0 ^ s ^ г, ненулевая, а г-е строки матриц As-1(x), As-2(x),..., A0(x) — нулевые. Пусть t-й элемент, 1 ^ t ^ m, является последним ненулевым элементом г-й строки As(x). Тогда (г — s) ■ m + t называется длиной г-го
г, t
элемент матрицы As(x) — последним ненулевым г
2.1. EG¡: редукция,
Алгоритм EG¿ построен на чередовании редукций и сдвигов. Объясним, как выполняется редукция.
Проверяем, являются ли строки ведущей матрицы линейно зависимыми над K(ж), и если да, то находим коэффициенты зависимости v1(x), v2(x),..., vm(x) е K[ж]. Из уравнений системы, соответствующих ненулевым коэффициентам, выбираем то, которое имеет наи-
г
г
комбинацией уравнений с коэффициентами v1(x), v2(x),..., vm(x). В результате г-я строка ведущей матрицы становится нулевой. Этот этап называется редукцией. Существенно, что длина ни одного из уравнений не увеличивается при редукции.
2.2. EG¿: дифференциальный сдвиг уравнения с нулевой ведущей частью
г
Пусть а(ж) — последний ненулевой коэффици-г
а(ж), продифференцируем его и избавимся от знаменателей. Эта операция называется диффе-
г
Слово "сдвиг" указывает на то, что, благодаря выполненному делению на последний ненулевой коэффициент, эта операция уменьшает длину г
2.3. последовательнось шагов "редукция,
+ дифференциальный сдвиг"
Схема алгоритма ЕС^ такова. Если строки ве-
К(ж) г
строка ведущей матрицы стала нулевой. Выпол-
г
должаем процесс чередования редукций и дифференциальных сдвигов, пока ведущая матрица не станет невырожденной. (Мы никогда не по-0=0
жению уравнения исходной системы независимы над К [ж, зХ].)
Теорема 1. ([4]) Алгоритм заканчивает свою ра,бот,у.
Итак, для дифференциальной системы Б вида (2) алгоритм ЕС^ строит 1-охватывающую систему Б?: ее ведущая матрица Аг(ж) невырождена и
Б
жеством множества решений системы Б. Пример 1. Рассмотрим систему 2ж2(ж + 2)(ж + 1) —ж(ж + 2)(ж + 1)
2ж2(ж + 2)
—ж(ж + 2)
У" +
+
/2ж(ж + 1)(ж — 4) —ж2 \ 2ж(ж — 4) — ж (ж + 4)
)y' + (4)
'—2(ж + 1)(ж — 4) —2N + 1 —2ж + 8 2 ' У
0.
Строки ведущей матрицы зависимы с коэффициентами ^(ж) = —1,-2(ж) = ж + 1. Уравнения имеют одинаковую длину. Заменяем второе уравнение:
2ж2(ж + 2)(ж + 1) —ж(ж + 2)(ж + 1)\ ,, + 0 0 ' У +
/2ж(ж + 1)(ж — 4) —ж2 , , + 1 0 —ж(ж + 2)2' У +
+
—2(ж + 1)(ж — 4) —2 0 2ж + 4
У = 0.
Дифференциальный сдвиг второго уравнения дает
2х2(х+2)(х+1) —х(х+2)(х+1)\ 0 —х(х+2) )
/2х(х + 1)(х —4) —х2 V 0 —2x
+
Г +
y' + (5)
+ (-2(x+1)(x-4) -02) y = 0
Последняя система имеет невырожденную ведущую матрицу и является результатом применения EG¿ к системе (4), иредставляя собой l-охватывающую систему исходной системы.
Примечание 1. Если после редукции i-e строки матриц Ar(х), Ar-i(x),..., Au+i(x) нулевы
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.