ПРОГРАММИРОВАНИЕ, 2011, No 4, с. 9-15
КОМПЬЮТЕРНАЯ АЛГЕБРА -
УДК 681.3.06
АЛГОРИТМ ДЕКОМПОЗИЦИИ ДИФФЕРЕНЦИАЛЬНЫХ МНОГОЧЛЕНОВ В ОБЩЕМ СЛУЧАЕ
© 2011 г. М.В. Соснин Красноярский государственный аграрный университет, Кафедра высшей и прикладной математики 660017 Красноярск, пр-т Мира, 90
E-mail: mickhail@akadem.ru Поступила в редакцию 12.10.2010
Работа посвящена теории декомпозиции дифференциальных многочленов (в дальнейшем, для краткости, д. м.). Для данного дифференциального алгебраического уравнения
P (x,y(x),y'(x),...,y(n)(x)) =0
исследуется возможность представления дифференциального многочлена P в виде композиции д. м. Q и R: P = Q(x, R, R',..., R(q)), R = R(x, y(x),..., y(r)(x)). Показано, что проблема декомпозиции сводится к проблеме факторизации линейных обыкновенных дифференциальных операторов (ЛОДО). Приводится общий алгоритм декомпозиции д. м., основанный на дифференциальной теореме Вандермонда.
1. ВВЕДЕНИЕ
Задача выяснения по данному д. м. P(x,y(x),y'(x),... ,y(n\x)) возможности его представления в виде композиции P = Q(R) д. м. является естественным обобщением таких классических задач, как задача декомпозиции обыкновенных многочленов и задача факторизации линейных обыкновенных дифференциальных операторов (ЛОДО). Эти задачи были подробно рассмотрены в работах ([11]), ([6]).
В статье [3] были разработаны основы теории, и приведен алгоритм декомпозиции для непараметрического случая, то есть когда в процессе выполнения шагов алгоритма не возникает ЛОДО, допускающих параметрическую факторизацию. Решение задачи в общем случае было изложено в работах автора [4] и [5] и подробно приведено в его диссертации на соискание ученой степени кандидата физико-математических наук, защита которой состоялась в марте 2003 г. в Красноярске. В 2004 г. появились работы [7], [8], посвященные
той же задаче, как в параметрической, так и непараметрической форме, в которых было дано несколько иное решение общей задачи декомпозиции, основанное на так называемом «методе однородного спуска» (см. [3]). В данной работе, являющейся кратким изложением результатов диссертации автора, приводится более короткое решение задачи декомпозиции и общий алгоритм декомпозиции д. м., основанный на так называемой дифференциальной теореме Вандермонда (см. [4] и [5]), являющейся аналогом известной теоремы для обычных многочленов.
2. ПОСТАНОВКА ЗАДАЧИ
Пусть к(х){у} — дифференциальное расширение некоторого дифференциального поля (не обязательно поля рациональных функций, как это можно понять из обозначений) одной переменной х с коэффициентами из некоторого вычислимого числового поля к и обычным дифференцированием f' = . Для удобства записи введем обозначения
/ // (п)
Уо = У,У1 = у ,У2 = у ,...,Уп = у(
Дифференциальным многочленом (в дальнейшем, для краткости, д. м.) порядка п и степени и> будем называть выражение
Р (х, у)
Ра(х)уа =
Е
Р цао ■■■Уап
Рао,...,ап у0 Уп ,
Р(х, у) = ^(ж, К(х, у)).
(2.2)
Уп > Уп—1 > > Уа+1 > Уа, то есть
Уа° Уа+^11 ■ ■ ■ У'п > уО+У ■ ■ ■ уПп, если Зк > а :
ап = Дп ап—1 = в'п— 1, . . ак+1 = А+Ъ ак > Рк.
Обозначим через 1та(Р) и 1са(Р) старший моном и старший коэффициент д.м. Р относительно порядка 1еха,
(2.1)
где Ра(х) € к(х), |а| = а0 + ... + ап, причем полужирным шрифтом мы далее будем обозначать последовательность из функции и ее производных по х до порядка, легко определяемого из контекста. Порядок д.м. Р далее часто будем обозначать через огё Р.
В данной работе рассматривается проблема декомпозиции, которую можно сформулировать следующим образом: для заданного д.м. Р(х, у) найти (если они существуют) такие д.м. ф(х, у) и Я(х, у) меньших порядков, что
1та(Р) = уа° ■ ■ ■ у'
1Са(Р) = £
ао,...,аа-1
_1 Раоо,...,аа-1,1а,...,1т
(х)Уо
а о
уа-1 .
В частности, 1т0(Р) = у0о ••• у'п и 1со(Р) = Р/0,— ,1п — обычные старший моном и старший коэффициент многочлена Р(У) как элемента кольца многочленов к(х)[у0,..., уп] относительно лексикографического порядка с условием уп > ■ ■ ■ > у0. Далее через Иа(Р) будем обозначать старшее слагаемое многочлена Р относительно 1ех^, Иа(Р) = 1са(Р)1та(Р).
Нетрудно видеть, что, не ограничивая общности рассуждений, мы можем считать (см. [3], Лемму 1), что Р0 = Ро,о,..,о = 0 и 1с0(Р) = 0. В таком случае, если существует декомпозиция Р = ^(К) с некоторыми Q и Я, то существует декомпозиция Р = <3(!К) с условием
0?о = Яо = о, 1со(0?) = 1со(Я) = 1, (3.1)
поэтому далее мы будем искать Q и Я, удовлетворяющие условиям (3.1).
4. ОПРЕДЕЛЕНИЕ Q ПРИ ИЗВЕСТНОМ Я
Приведем две несложные леммы, доказательство которых читатель может найти в ([3]):
Лемма 1. Пусть Q(R) и Я(у) - некоторые д.м., с коэффициентами, зависящими только от х. Тогда, если Я(у) не является функцией только от х, то д.м. Р(у) = Q(R(y)) не равен тождественно нулю.
Лемма 2. Если в формуле (2.2) нам известен явный вид д.м. Я(х, у), то мы можем однозначно восстановить д.м. Q(x, К) как д.м. от Я.
Положительное решение проблемы декомпозиции заданного д.м. Р(х, у) имеет очевидное применение к поиску решений нелинейного дифференциального уравнения Р(х, у) = 0. Действительно, если возможно найти представление (2.2), то поиск решений уравнения Р(х, у) = 0 сводится сначала к решению уравнения Q(x, z(x)) = 0, а потом к решению уравнения Я(х, у) = ¿+(х), где г+(х) — общее решение уравнения Q(x, z(x)) = 0. Порядки (или степени) этих двух уравнений меньше порядка (или степени) уравнения Р(х, у) = 0 и тем самым, возможно, поиск решений упрощается.
3. ОТНОШЕНИЯ ПОРЯДКА И ПРЕДВАРИТЕЛЬНЫЕ УПРОЩЕНИЯ
В дальнейшем будет удобно обращаться с дифференциальными многочленами как с обычными многочленами от некоторых из переменных у, например, от переменных уа, уа+1..., уп, относя переменные у0, у1 ..., уа—1 к коэффициентам многочлена. В соответствии с этим будем через 1еха обозначать лексикографический порядок на множестве мономов {уаа у^1 ••• уап} от переменых уа, уа+1,..., уп с условием
п
5. ОПРЕДЕЛЕНИЕ СЕПАРАНТЫ
многочлена 1е^Я) = Я11.....тп (х,У0) по пере-
МНОГОЧЛЕНА К. ПОЛНОЕ ОПРЕДЕЛЕНИЕ менной У0 отлична от нуля, то из уравнения
К В НЕКОТОРЫХ СЛУЧАЯХ
Напомним, [12], [10] что сепарантой д.м. К(х, у) порядка г называется д.м. Б и = . Для Уг > 0 имеем очевидное на по переменной уг степени к, выражение для г-ой производной К: К(г\х, у) = Би ■ уг+г + 1ех0 (младшие слагаемые в смысле лексикографического отношения порядка).
Пусть Я — д.м. порядка д и И1(Я) =
(5.2) можно алгоритмически найти К(х, у), и, следовательно Я(х, г).
Доказательство. Запишем К в виде многочле-
К(х, уо,...,Уг) = ^ Кц(х, уо,..., Уг-1)У(5.3)
Ял1.....л,(х,Уо)Угг ■■■ Уд4, где Ялъл2.....лч(х,уо) -многочлен степени ,1о по уо:
Ло
Ялъл2,...,л,(х,уо) = ^ Яг,лг,л2,..,лч(х) ■ Уо,
г=о
тогда
Я(х, Я) = Яли...,лч (х, К)БЛк1+...+Лулг\ 1 ■ ■ ■
■ ■ ■ Уг+д + 1ехг+1 - мл. слаг.
Следовательно, если Р(х, у) = Я(х, Я(х, у)), то г + д = п и
^Г+1(Р (х, у)) := р1г+1 ...,1п (x,yо,..., У г )У^++11 ■ ■ ■ ■■■ уПп =1tr+l(Я(x, Я(х, у))) = = ЯЛ1.....Л,(х, К)БЛ+...+ЛуЛ\_ 1 ■ ■ ■ уЛ+д (5.1)
Аналогично представим 1ег+1(Р) и 1е1(Я),
I
1ег+1(Р) = ^ Ри(х,уо,..., Уг—1 К = 1сг (Р)уГ + и=о
+ мл. слаг., (5.4)
о
1С1(Я) = ЯЛ1.....л,(х,уо) = ^ дк(х)Уо , (5.5)
к=1
причем 1ео(Я) = дЛо (х) = 1, до = 0 в соответствии с нашими соглашениями (3.1). Подставив
Би = дУ = ^ ^Кц(х, уо,..., Ут-1Ж °Уг М=1
1
Значит, За = 1г+а, а = 1,... ,д и
1ег+1(Р ) = Я/г+1...../„ (х,К)Б11Т+1
и (5.3 - 5.5) в уравнение (5.2), получим
(5.2)
I / Ло
Ру (х, уо,..., ут-1)у? = дк (х)
и=о \к=1
о К„у?У (ри ^У^-1)Т (5.6)
Аналог следующей теоремы читатель может найти в [3] — ряд результатов из этой статьи, в которой был рассмотрен непараметрический случай декомпозициии, автоматически дублируется и для общего
случая. Автор привел здесь формулировку где Т = ^ + ... + 1п. Сравнивая степени
по уг в правой и левой частях формулы (5.6),
получим соотношение I = 7ок + Т(к — 1), то
есть, I + Т = (7о + Т)к. Тем самым, к — степень
Теорема 1. Если существует декомпозиция К(х, у) по старшей производной — находится
Р(х, у) = Я(х, Я(х, у)) с неизвестным Я, среди таких делителей числа I + Т, для которых
МЯ) = 1 и заданным огё К(х, у) = г, то из ^о = + — Т неотрицательно. Если 7о = 0,
уравнения (5.2) можно алгоритмически найти то Би = (1ег+1(Р))1/Т. В противном случае,
сепаранту Б и. Более того, если степень ,1о запишем систему уравнений на неизвестные
и доказательство теоремы в целях полноты изложения.
п
Я1,Я2,...,Я^, сравнивая коэффициенты при одинаковых степенях уг в (5.6):
I :
I - 1 :
= Ри,
кТ яТ+2° = Р,
(7окТ + кТ - кТ-1)Е/0+Т-1^_1 =
Мы видим, что в первые к уравнений будут входить лишь неизвестные Я1,..., Я^, причем Я1,...,Я&_1 будут присутствовать только в первой степени, поэтому, вычислив Я^ = (к_ТРг)1/(Т+2о), мы последовательно найдем Я&_1,...,Я1 из этой системы. Таким образом, мы найдем коэффициенты возможной сепаранты
Разделив обе части уравнения (5.6) на (£д)Т, получим
2°
^ д*(ж)(Яо(ж, уо,..., уг_1)+Я(ж, Уо,.. . , Уг))к =
К=1
= /о Р* (ж,уо,...,уг_1)у?, (5.7) где Я = £^=1 Я^Уг — найденная уже часть Я. Приравняв коэффициенты при у2°_й в (5.7), получим соотношение
2°_1(ж)+7оЯо(ж, Уо,..., Уг_1) = Р&2°—^(ж, Уо,..., Уг_1), (5.8)
откуда, применяя (3.1), находим
2°_1(ж) = (ж, 0, 0,..., 0),
Ио = 2° (Ра/о^ж, у) - 2°_1(ж)) .
Последовательно приравнивая коэффициенты при в уравнении (5.7), найдем
оставшиеся коэффициенты 2°_2,..., С помощью проверки убеждаемся в правильности найденной декомпозиции. Проверка необходима, так как мы имеем, вообще говоря, переопределенную систему уравнений, из которой для наших целей используем лишь некоторые уравнения. Теорема доказана.
Таким образом, действуя так, как описано в доказательстве теоремы 1, мы либо найдем декомпозицию, (если 7о > 0), либо найдем сепаранту многочлена Я и определим, что старшее слагаемое 1^(() не зависит явно от Уо, то есть, 1^(() = фол+1,..,/„ (ж)у[г+1 ■ ■ ■ у1п.
6. ПЕРЕХОД ОТ ДЕКОМПОЗИЦИИ
Р = ((Я) К ДЕКОМПОЗИЦИИ Р = ((Я), ГДЕ СЕПАРАНТА = 1
Нам понадобится следующее полезное понятие оператора линеаризации д.м. Понятие линеаризации час
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.