ПРОГРАММИРОВАНИЕ, 2015, No 2, с. 54-62
КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 004.421.6
ЭКСПОНЕНЦИАЛЬНО-ЛОГАРИФМИЧЕСКИЕ РЕШЕНИЯ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ СИСТЕМ С КОЭФФИЦИЕНТАМИ В ВИДЕ СТЕПЕННЫХ РЯДОВ*
© 2015 г. A.A. Рябенко
Вычислительный центр РАН 119991 Москва, ул. Вавилова, 40 E-mail: ryabenko@cs.msu.ru Поступила в редакцию 12.09.2014
Рассматривается построение формальных экспоненциально-логарифмических решений для системы линейных обыкновенных дифференциальных уравнений, коэффициенты которой являются формальными степенными рядами, заданными алгоритмически. Построение всех таких решений — в общем случае алгоритмически неразрешимая задача. Предлагается алгоритм и его реализация в среде Maple, который при условии, что известна размерность пространства решений системы полного ранга, позволяет построить базис этого пространства.
1. ВВЕДЕНИЕ
Рассматриваем систему S линейных дифференциальных уравнений
Ar (x)y(r)(x) + ...
••• + Al(x)y' (x) + Ao(x)y(x) = 0,
где y(x) = (y\(x),y2(x),... ,ym(x))T — вектор-столбец неизвестных функций, коэффициенты Ai(x) — квадратные матрицы порядка m, элементы которых являются формальными степенными рядами по x: Ai(x) G Matm(K[[x]]), K — числовое поле (Q ç K ç C).
Коэффициенты Ai(x) = ^ai(u)xn задаются с помощью алгоритмов, по номеру n вычисляющих значение ai(n). Позволяется использовать любые детерминированные алгоритмы. Из этого следует, что задача распознавания равенства нулю формального степенного ряда алгоритмически неразрешима. Поэтому, в частности, полагаем априори известным, что Ar(x) — ненулевая матрица.
Пусть также известно, что система имеет полный ранг, то есть уравнения системы линейно независимы над K((x))[^Х]. Алгоритмиче-
*Подцержано грантом РФФИ 13-01-00182-а.
екая неразрешимость задачи распознавания полноты ранга системы следует из алгоритмической неразрешимости проверки равенства нулю формальных степенных рядов (см. [1]).
В настоящей статье будет исследована возможность построения формальных экспоненциально-логарифмических решений системы. Такие решения могут быть представлены в параметрическом виде:
х = , у(х) = Ф(г), (2)
Где Q — полином с коэффициентами из К,
д _ натуральное число (число ветвлений решения). Часть ¿7Ф(Ь) называется регулярной: 7 е К Ф(1) = (Ф^),..., — вектор-
столбец с компонентами вида
8 /те \
ф^) = ЕЕ ^ (п п^
]=0 \и=0 )
где в — неотрицательное целое, (п) е к, К
К
В случае д = 1, Q е К решение называется регулярным, в противном случае — нерегулярным. В работе [2] предложен алгоритм построения всех регулярных решений для систем вида (1) полного ранга. Этот алгоритм можно применять к системе, только если известно, что она
полного ранга. В случае системы неполного ранга, алгоритм не остановится.
В работе [1] показано, что построение всех формальных экспоненциально-логарифми-
ческих решений при таких же условиях — алгоритмически неразрешимая задача. Цель настоящей работы — предложить алгоритм построения нерегулярных решений при дополнительных условиях на систему (1). Условия, которые будут предложены, невозможно проверить алгоритмически. Так же, как невозможно алгоритмически проверить неравенство нулю старшего коэффициента системы или определить ранг системы. Если какое-либо из условий не будет выполнено, алгоритм не остановится.
Далее рассматриваются следующие задачи:
Р1: Найти некоторое непустое множество нерегулярных решений системы (1), если известно, что система имеет полный ранг и нерегулярные решения у этой системы существуют.
Р2: Найти пространство всех формальных экспоненциально-логарифмических решений системы (1), если известно, что система имеет полный ранг и известна размерность пространства всех ее решений.
РЗ: Найти пространство всех формальных экспоненциально-логарифмических решений для системы (1), если известно, что ее ведущая матрица невырождена.
2. ПРЕДВАРИТЕЛЬНЫЕ СВЕДЕНИЯ
Приведем несколько известных определений и фактов, необходимых для дальнейшего.
2.1. Вычислимые ряды
Формальным степенным рядом от х над полем К называется / = ^(п) хп, где -и(п) £ К.
Кольцо степенных рядов обозначается К [[х]]. По определению, / = 0 если -и(п) = 0 для всех п. Мы рассматриваем вычислимые ряды, то есть коэффициенты ряда вычисляются с помощью
п
нии не существует алгоритма, определяющего, является ли данный ряд нулем или нет.
Сумма и произведение вычислимых степенных рядов — вычислимые ряды. Результат деления степенных рядов есть формальный ряд Лорана,
то есть ряд вида f = ^Lno v(n) жп, гдe n0 £ Z. Поле формальных рядов Лорана обозначается K((ж)). Сумма вычислимых рядов Лорана является вычислимым рядом. Для того, чтобы произведение вычислимых рядов Лорана было вычислимым, необходимо иметь информацию о ва-
f
вается число
valxf = min n.
v(n) = 0
При этом полагается, что valx 0 = те. Определить валюацию вычислимого ряда можно при выполнении двух условий: известно, что ряд ненулевой, и известна нижняя граница его ва-люации. Например, valxf > 0 для f £ K[[ж]].
В дальнейшем, упоминая формальный степенной ряд или формальный ряд Лорана, слово "формальный" будем опускать.
2.2. Система уравнений
Через Matm(R), где m £ N, обозначается кольцо квадратных матриц порядка m с компонентами из R. Здесь и далее N — множество натуральных чисел. Валюацией матрицы, принадлежащей Matm(K [[ж]]) или Matm(K((ж))), называется минимум валюаций всех ее компонент. Аналогично, валюацией системы S называется минимум валюаций всех коэффициентов системы.
2.3. Построение нерегулярных решений
Построение нерегулярных решений, как правило, осуществляется следующим образом.
Во-первых, применяется алгоритм поиска числа ветвлений q и полинома Q для (2). (В работе [4] пара q и Q называется экспоненциальной частью формального решения.) Такие алгоритмы разработаны для случаев: одного дифференциального уравнения произвольного порядка, системы вида у'(ж) = А(ж)у(ж) и системы произвольного порядка с невырожденной ведущей матрицей. Более подробно об этих алгоритмах сказано в разделе 2.4.
Во-вторых, для полученных q £ N и
Q(vt)=о-+•••+£'
(3)
где Ki G N ai G K \ {0}, в заданной системе выполняется подстановка
x = tq, y(x) = eQ(1/t)z(t),
(4)
где í — новая независимая переменная, ¿(¿) — вектор новых неизвестных функций. В результате подстановки и умножения всех уравнений на получим новую систему, которая име-
ет регулярные решения. Коэффициенты этой системы — ряды Лорана. Алгоритмы построения регулярных решений разработаны как для случая одного уравнения, так и для случая системы уравнений с коэффициентами в виде рядов. Например, если известна валюация новой системы и построены алгоритмы вычисления ее коэффициентов, можно применить алгоритм из [2].
2.4. Построение экспоненциальной части
Построение экспоненциальных частей для всех формальных решений в случае одного дифференциального уравнения порядка г > 1 с коэффициентами в виде степенных рядов выполняется с помощью алгоритма многоугольников Ньютона (см., например, [5, 6]). В этом случае существует только одно алгоритмически непроверяемое условие: Аг(х) = 0. То есть должен быть известен порядок уравнения.
Нормальной системой первого порядка называется система вида
у'(х) = А(х) у(х),
где А(х) € Ма£т(К((х)). Один из алгоритмов построения экспоненциальных частей для нормальной системы предложен в [4]. В этом случае должна быть известна валюация матрицы А(х)
ненциальной части для всех решений нормальной системы достаточно знать лишь начальные (т шах{0, —уа1жА(х)}) коэффициенты ря-А(х)
Для системы порядка г > 1с коэффициентами в виде степенных рядов и невырожденной ведущей матрицей нетрудно построить эквивалентную ей нормальную систему первого порядка
Y'(x) = A(x) Y(x),
(5)
системы и их производных до г — 1 порядка. А(х)
щим образом:
0
A(x) =
Im
0
\
00
v Ao(x) Ai(x)
Ar-l(x) /
где А(х) € Ма£тг(К((х))), У(х) — вектор, составленный из неизвестных функций исходной
где A^x) = — A-1(x)Ai(x) для 0 < i < r, Im — единичная матрица порядка m. Алгоритмически непроверяемое условие в этом случае: det Ar (x) = 0. При выполнении этого условия некоторого конечного числа начальных коэффициентов рядов из системы S достаточно, чтобы построить экспоненциальные части всех формальных решений (см. предложение 6 в [3]). Заметим, что этот подход применяется только в случае m > 1. Для случая одного уравнения (m = 1), как сказано выше, применяется алгоритм многоугольников Ньютона.
Отметим как особый случай системы с полиномиальными коэффициентами. То есть Ai(x) из (1) заданы не только алгоритмами вычисления коэффициентов ai(n), но и конечной степенью:
degx Ai(x) = max n.
ai(n)= 0
В этом случае все упоминавшиеся выше условия становятся алгоритмически проверяемыми, а задача построения всех формальных экспоненциально-логарифмических решений алгоритмически разрешимой. В разделе 5 настоящей статьи предлагается алгоритм для случая системы с полиномиальными коэффициентами (и, возможно, вырожденной ведущей матрицей), использующий ЕС^-исключения из [8].
3. ПОДСТАНОВКА S
оператор
dr d L = Ar (x) dxr + ••• + Ai(x) dx + Ao(x). (6)
Порядком, оператора L называется ord L = r, если Ar (x) = 0.
Обозначим посредством
r q,Q(i/t) r L -► Lq,Q
m
экспоненциально-логарифмические решения
57
тот факт, что в результате подстановки (4) в си- где а е Ъ\ 0 < а < г(д + к) 0 < г < г. стеме Ьу(х) = 0 получается система Отсюда нетрудно вывести, что
в^ь.я г(г) = 0.
Лемма 1. Пусть г,д е N к е N и {0} и
ordLr+i,q,K = r +1, valtLr+i,q,K > -(r + 1)(q + к).
dr
q, 1/tK
L
r,q,K ■
dxr Тогда
1) Lr,q,K g к[ 1 ][dt];
2) ord Lr,q,K = r;
3) valtLr,q,K > -r (q + к).
r
r=1
dy
dx
dt
-=- (e1/tK z)/ jt (tq )=
1
q tq-1
i/tK
ei/tK _ ei/tK к z
=e
dt 1 dz
tK+v
qtq-1 dt q tq+K
z=
= е1/1КЬ^ г(1).
г=1
И поскольку уа^ Ь\,д,к > — тах{д — 1,д + к}, то и 3) также выполняется.
Шаг индукции. Предположим, 1), 2), 3) выполняются для г. Для г + 1 получаем:
(Т+1у ( (г у (хг+1 (х (хг
= d (e1/tKL-)/d (tq) =
q tq
e1/tK — L _e1/tK_^T
-1 \e dt ,q,K e +K+1 Lr,q,K
tK+1
,1/t-
q tq
1
-T -—T
dt ,q,K tK+1 q,K
= e1/tK L — e Lr+1,q,K.
О
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.