научная статья по теме ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ И РАЗНОСТНЫЕ СИСТЕМЫ: EG δ И EG σ ИСКЛЮЧЕНИЯ Математика

Текст научной статьи на тему «ЛИНЕЙНЫЕ ДИФФЕРЕНЦИАЛЬНЫЕ И РАЗНОСТНЫЕ СИСТЕМЫ: EG δ И EG σ ИСКЛЮЧЕНИЯ»

КОМПЬЮТЕРНАЯ АЛГЕБРА

УДК 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 рублей.

Показать целиком

Пoхожие научные работыпо теме «Математика»