ПРОГРАММИРОВАНИЕ, 2008, № 4, с. 25-31
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ПОИСК ЛИУВИЛЛЕВЫХ РЕШЕНИЙ ЛИНЕЙНЫХ РЕКУРРЕНТНЫХ УРАВНЕНИЙ В СИСТЕМЕ КОМПЬЮТЕРНОЙ АЛГЕБРЫ MAPLE*
© 2008 г. Д. Е. Хмельнов
Вычислительный Центр им. A.A. Дородницына РАН 119333 Москва, ул. Вавилова, 40 E-mail: khmelnov@ccas.ru Поступила в редакцию 10.01.2008 г.
В работе рассматривается реализация в системе компьютерной алгебры Maple алгоритма Зингера-Хендрикса поиска лиувиллевых решений линейных рекуррентных уравнений с коэффициентами в виде рациональных функций.
1. ВВЕДЕНИЕ
Решения в виде лиувиллевых последовательностей обобщают решения в виде гипергеометрических последовательностей и описывают в замкнутом виде достаточно широкий класс решений уравнения
Ly = 0, (1)
где L - линейный рекуррентный оператор, L = = En+d + rd_l{n)En+d~l + ••• + го (га), г г-(га) £ £ С (га) - коэффициенты в виде рациональных функций (С - числовое поле), а Е - оператор сдвига: Еу(п) = у(п + 1).
Отметим, что мы считаем данную последовательность решением, если она удовлетворяет уравнению для всех достаточно больших значений индекса, и считаем две последовательности равными, если они совпадают с некоторого места.
Алгоритм решения задачи поиска поиска решений уравнения (1) в виде лиувиллевых последовательностей был предложен М. Зингером и П. Хендриксом в [1]. Ко времени подготовки настоящей работы не было известно ни одной полной реализации данного алгоритма, в частности, в системе компьютерной алгебры Maple.
* Работа частично поддержана Российским фондом фундаментальных исследований, грант №07-01-00482-а.
Мы провели такую реализацию и описываем ее ниже.
В работе [2] приведена модификация алгоритма Зингера-Хендрикса и описана ее реализация. Однако, и эта реализация не является полной, позволяя находить такие решения только для уравнений второго порядка.
2. ЛИУВИЛЛЕВЫ РЕШЕНИЯ
Введем в рассмотрение кольцо последовательностей S (как указано выше, мы отождествляем последовательности, которые совпадают, начиная с некоторого места).
Напомним следующие определения [1, 3].
Определение 1. Последовательность а £ S называется гипергеометрической, если найдутся ненулевые полиномы pi,po £ С [га] такие, что
рхЕа = роа. (2)
Рациональная функция po/pi называется сертификатом гипергеометрической последовательности. Через % мы обозначаем множество всех гипергеометрических элементов из S.
Определение 2. Пусть С - наименьшее под-кольцо кольца S, содержащее И и замкнутое относительно
• Е, Е-1,
• S,
• сплетения.
Элементы С называются лиувиллевыми последовательностями.
Здесь для т последовательностей ai = (ою, an,...), a2 = (a2o, a2i,...), ..., am = (am0, ami,...) операция сплетения дает последовательность (аю, a20, • • •, am0, an, a2b ..., amb ...). В случае, когда необходимо уточнить, о сплетении какого количества последовательностей идет речь, мы будем использовать термин т-сплетение.
Также напомним, что для целых чисел т и i, где 0 < i < то, i-ым то-сечением последовательности a = (ao,ai,...) называется последовательность (a¿, am+¿, a2m+¿,...).
3. АЛГОРИТМ ЗИНГЕРА-ХЕНДРИКСА
Кратко опишем основую схему алгоритма из [1].
1. Для заданного линейного рекуррентного оператора L порядка d с коэффициентами в виде рациональных функций найти наименьшее целое число то, где 1 < то < d, такое, что существует ненулевое решение уравнения (1) в виде то-сплетения гипергеометрических последовательностей. Если такого то не существует, то и лиувилле-вых решений уравнения (1) не существует. Поиск такого то осуществляется с помощью построения оператора Lm, такого, что любое решение уравнения (1) в виде то-сплетения гипергеометрических последовательностей является решением уравнения Lmy = 0.
2. Вычислить Я1 = GCRD(Lm,L) (GCRD -наибольший общий правый делитель операторов) и определить базис В\ его решений в виде то-сплетений гипергеометрических последовательностей. При этом каждая компонента сплетения (т.е. соответствующее то-сечение решения) вычисляется с помощью поиска гипергеометрического решения соответствующим образом построенного уравнения.
3. Пусть L = RH\. Применить этот же алгоритм к оператору R. Если лиувиллевых решений не найдено, то базисом пространства лиувиллевых решений уравнения (1)
явлется В\. Если в качестве базиса решения найден базис Br, то построить базис В пространства лиувиллевых решений уравнения (1), используя В\ и Br. Для этого применяются только операции в S и
4. РЕАЛИЗАЦИЯ
Реализация алгоритма проведена в системе компьютерной алгебры Maple в виде новой функции LiouvillianSolution как расширение пакета LREtools, предоставляющего различные функции для решения линейных рекуррентных уравнений.
Приведем некоторые подробности, касающиеся нашей реализации.
4.1. Гипергеомтрические решения
Основой алгоритма Зингера-Хендрикса является поиск гипергеометрических решений на шаге 1 в приведенной в разделе 3 схеме. Пакет LREtools системы Maple предоставляет процедуру LREtools [hypergeomsol], реализующую алгоритм из работы [4]. Наша реализация алгоритма Зингера-Хендрикса использует именно эту процедуру.
Отметим, что эта процедура находит решения в виде функций, которые задают последовательности, определенные начиная с некоторого места, а не определенные всюду последовательности. Наша реализация алгоритма Зингера-Хендрикса находит решения в том же смысле. В случае, если процедура LREtools[hypergeomsol] будет расширена для нахождения решений в виде определенных всюду последовательностей, то и наша реализация будет автоматически искать лиувиллевы решения в соответствующем смысле.
4.2. Поиск Lm
Дадим более детальное описание шага 1 схемы из раздела 3.
1.1. Для заданного то найти полином Р наименьшей степени, такой, что Р(Е'т)у = = 0 для любого у, являющегося решением (1). Это делается путем представления у, Ету, Е2ту,..., Еп*ту с помощью
уравнения (1) как линейных комбинаций у, Еу,..., Еп~1у и вычисления линейных зависимостей между этими линейными комбинациями.
1.2. Для I от 0 до т — 1 построить Рг- = тЕгР, где гу(га) = у(тога). Уравнению Р(Ет)у = О удовлетворяют не только решения (1), но и все их то-сечения. Р{(Е)у = 0 задает уравнение для ¿-го т-сечения.
1.3. Найти - множество сертификатов всех гипергеометрических решений Р{(Е)у = 0.
1.4. Построить
П= и {Е-1т~\д)\деО{}, (3)
0<г<ш-1
и тогда Ьт = ЬСЬМ{£т - к}кеП.
Рациональные функции из множества Ц могут иметь коэффициенты, принадлежащие в общем случае некоторому конечному алгебраическому расширению поля С. Тем не менее, справедливо следующее предложение.
Предложение 1. Коэффициенты при степенях Е оператора Ьт, который строится в ходе вычислений с помощью алгоритма Зингера-Хендрикса на шаге 1 схемы из раздела 3, ются элементами С (га).
Доказательство. В процессе построения сертификатов гипергеометрических решений уравнений Р{{Е)у = 0 возникает необходимость разложения (над замыканием исходного поля С) ряда полиномов в произведение линейных множителей. Это разложение может быть выполнено и над некоторым конечным алгебраическим расширением С (а 1, «2, • • •, щ) исходного поля; в силу теоремы о примитивном элементе (например, [5]) найдется неприводимый полином р(х) £ С(х) такой, что поле С (а 1, «2, • • •, щ) изоморфно полю С (в), р(0) = 0. Пусть применение того или иного алгоритма нахождения сертификатов гипергеометрических решений дает нам все принадлежащие полю С(0,п) сертификаты гипергеометрических решений Р{(Е)у = 0:
9г2(0,п), ..., д1к\0,п). (4)
Поле С числовое, поэтому С (в) С С при любом выборе комплексного корня 0 полинома р(х). Построение сертификатов (4) целиком сводится к операциям поля С (в), поэтому рациональные функции
дч{0',п),д12{0',п),.. .,д1кг{0',п) € С (га)
при любом выборе комплексного корня 0' полинома р(х) будут давать сертификаты гипергеометрических решений уравнения Р{(Е)у = 0 (не исключается, что при разных комплексных корнях 0', 0" полинома р(х) мы будем получать одинаковые сертификаты). Обозначим через 01, 02, ■ ■., 0ц все корни полинома р(х) в С. Множество сертификатов всех гипергеометрических решений Р{{Е)у = 0 имеет вид
Сг = {дг1(01,п),.. .,д1кг(03,п),...,
дч(01,п),.. .,д1кг(03,п)},
и в силу (3) множество % будет содержать рациональные функции
кг (01, га),..., Ид (0е, га),..., (0Х, га),..., к9(05,п)) е ОД.
Тогда оператор Ьт может быть представлен в виде
ЬСЬМ(£т -к1(01,п),...,Ет - 1гд(03, га), ... ,Ет - к^п),... ,Ет - 1гч{08,п)). {Ь>
По построению Ьт имеет при степенях оператора Е коэффициенты в виде рациональных функций, числители и знаменатели имеют вид таких полиномов от га, коэффициенты которых, в свою очередь, являются симметрическими полиномами от 0\,02, ■ ■ ■ ,0в- (Последнее следует из того, что (5) не меняется при любой перестановке корней 01,02, ■■■, 0э ) Так как р(х) £ С, то симметрические полиномы от корней полинома р(х) имеют значения, принадлежащие С, и, как следствие (см., например, [5]), Ьт 6 С(п)[Е]. □ Процедура ЬНЕ1;оо1з []ауре^еотзо1] работает с операторами, принадлежащими (Щга)^]. В силу предложения 1 каждый из операторов Ьт будет также принадлежать (Щга)^], и, как следствие, оператор Я, возникающий на шаге 3 схемы из раздела 3, также принадлежит (Щга)^].
ХМЕЛЬНОВ
> rec := (n~2+5*n+6)*y(n+3)+y(n);
rec := (га2 + 5 га + 6) у (га + 3) + у(га)
> LiouvillianSolution(rec,у(n),explicit);
2, ,п + 3Щ-+1)
2,1
г<! ,11 + 1Щ- + I)
3,1
irem(ra, 3) = 1
r(- + i)r(^)
v3 ' v3 з7
otherwise
Рис. 1.
4.3. Решение в виде сплетений
На шаге 2 схемы из раздела 3 находятся решения в виде то-сплетений гипергеометрических последовательностей.
С точки зрения реализации, необходимо иметь возможность представлять такие то-спле-тения в удобном и наглядном виде. В нашей реализации была выбрана имеющаяся в Maple конструкция piecewise, определяющая кусочные функции.
Таким образом, например, сплетение последовательностей 2п и га! представляется в виде piecewise(irem(n,2)=l, 2~п, п!), где irem(n,m) вычисляет остаток от деления га на т.
Пример 1. Пример решения уравнения, имеющего лиувиллевы решения в виде 3-сплетения, приведен на рис. 1.
4.4. Лиувиллевы р
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.