Собственные многочлены диффренциального оператора первого порядка над кольцом многочленов от двух переменных тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.Ломоносова

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 512.628.2

АСТРЕЛИН Андрей Витальевич

СОБСТВЕННЫЕ МНОГОЧЛЕНЫ ДИФФЕРЕНЦИАЛЬНОГО

ОПЕРАТОРА ПЕРВОГО ПОРЯДКА НАД КОЛЬЦОМ МНОГОЧЛЕНОВ ОТ ДВУХ ПЕРЕМЕННЫХ

Специальность 01.01.07 - вычислительная математика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва 1992 г.

Работа выполнена на кафедре вычислительной математики механико-математического факультета Московского государственного университета им.М.В.Ломоносова.

Научный руководитель - кандидат физико-математических

наук, ведущий научный сотрудник Е.В.Панкратьев.

Официальные оппоненты - доктор физико-математических наук, профессор С.А.Абрамов, кандидат физико-математических наук, ведущий научный сотрудник А.Я.Родионов.

Ведущая организация - Институт проблем механики РАН.

Защита состоится " " 19д2 г. в час.

на заседании специализированного совета К.053.05.84 в Московском государственном университете им. М.В.Ломоносова по адресу: 119899, Москва, Ленинские горы, МГУ, Научно-исследовательский вычислительный центр, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Научно-исследовательского вычислительного центра МГУ.

Автореферат разослан "_"_ 1992 г.

Ученый секретарь специализированного совета кандидат физико-математических

наук М.Н.Киоса

; t i-

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Одной из важных задач компьютерной алгебры является поиск формальных решений обыкновенных дифференциальных уравнений. В некоторых случаях эта задача сводится к следующей: д^я данного дифференциального оператора D = Р(х, у)-f Q(x, у)щ, действующего на кольце С[.х,у] найти оценку сверху на степень неприводимых собственных многочленов1). К настоящему моменту решение этой задачи известно для некоторых частных случаев, но полного решения еще нет. В случае, если задача будет решена полностью, постится возможность алгоритмически находить полиномиальные первые интегралы дифференциальных уравнений вида х = R{x,t), где R - рациональная функция, или доказывать, что их не существует.

Данная работа посвящена дальнейшему исследованию этой задачи. В последнее время, в связи с развитием вычислительной техники и ее применением в алгебраических исследованиях, усилился интерес к вопросам алгоритмизации и разработкам конструктивных методов (соответствующая область математики получила название компьютерной алгебры). В этой связи вышеупомянутая задача является актуальной.

Цель работы. Целью работы является разработка алгоритмов для поиска собственных многочленов дифференциального оператора. Алгоритмы, найденные для различных частных случаев, сформулированы в виде, приближенном к современным алгоритмическим языкам, и полностью обоснованы.

Методика исследований. Для решения задачи используются методы современной дифференциальной и компьютерной алгебры.

Научная новизна результатов. Следующие основные резуль-

1) М.Singer, Formal solutions of differential equations, Preprint, 1989

I- 14i>

таты диссертации являются новыми и получены автором самостоятельно:

1) доказаны теоремы о структуре множества собственных многочленов дифференциального оператора Р{х, + Q(x, У)щ наД различными алгебраическими областями, (доказано, что любой делитель собственного многочлена также является собственным многочленом, описано множество возможных старших однородных компонентов собственных многочленов);

2) найдены алгоритмы нахождения собственных многочленов в случаях, когда

- Р и Q - однородные многочлены одинаковой степени;

- дифференциальное уравнение ^ = — , соответствующее данному оператору, имеет конечное число алгебраических решений;

3) предложен алгоритм, позволяющий находить решения дифференциального уравнения ^ = — ^f^j в виде ряда и достаточно эффективно находить полиномиальные первые интегралы, когда они существуют;

4) разработан комплекс программ для вычислений в основных алгебраических областях;

5) на базе этого комплекса реализованы представленные алгоритмы.

Теоретическая и практическая ценность. Результаты работы могут быть непосредственно применены в системах компьютерной алгебры, как в специализированных, так и в системах общего назначения.

Апробация. Результаты диссертации докладывались и обсуждались на:

- семинарах по компьютерной алгебре на механико-математическом факультете МГУ, руководители Е.С. Голод, В.Н. Латышев,

А.В.Михалев, Е.В.Панкратьев (3 доклада);

- всесоюзном семинаре по компьютерной алгебре (мех-мэт МГУ, январь 1992 г.);

- IV Международном совещании по аналитическим вычислениям на ЭВМ в физических исследованиях (г. Дубна, май 1990

г-);

- Международном симпозиуме по символьным и аналитическим вычислениям ISSAC'91 (Бонн, июль 1991 г.).

- научно-исследовательском семинаре по компьютерной алгебре, руководитель С.А.Абрамов (октябрь 1992 г.).

Публикации. Основные результаты диссертации опубликованы в работах [1-5].

Структура работы. Диссертация состоит из введения, шести глав, приложений и списка литературы. Объем текста работы составляет 80 компьютерописных страниц. Список публикаций включает 16 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении формулируется основная проблема, которой посвящена диссертация, приведен краткий обзор работ, близких по постановке задач, дано краткое описание работы и перечислены основные результаты.

В первой главе вводятся основные обозначения и определения, которые используются в основном тексте.

Сначала вводятся стандартные обозначения некоторых алгебраических структур: символами Z, Q, С и Z+ обозначаются целые, рациональные, комплексные и целые неотрицательные числа соответственно, а К[х], К(х), К({х)) и К(х)* - многочлены, рациональные функции, степенные и дробно-степенные ряды над

кольцом или полем К (при этом под степенными рядами понима-

3

ются ряды Лорана, т.е. ряды, содержащие конечное число членов при отрицательных степенях переменной). Пусть

В = Р(х,у)-^+(}{х,у)-щ (1.1)

- дифференциальный оператор, действующий на кольце С[х,?/], где Р{Х-,У)'> (2{х,у) 6 С[х,у]. Многочлен Р, для которого выполняется свойство Р | DF, называется собственным многочленом оператора О. Через п обозначим наибольшую из степеней многочленов Р и через Р ж <2 - однородные компоненты степени п многочленов Р и <2 соответственно, а через р(г) и д(г) - многочлены Р( 1,г) и

3(1, г).

Многочлен

ф) = гр(г) - (¡{г) =-- 2Р( 1, л) - г)

назовем характеристическим многочленом оператора £). Обозначим через {ао,...,«„} множество корней этого многочлена, если он не равен тождественно нулю.

В некоторых случаях нам придется работать с объектами из таких алгебраических структур, как многочлены от одной переменной над рядами Лорана от х-1 (их множество обозначается С((х_1))[у]) и над дробно-степенными рядами также от х~! (они образуют кольцо <С(х~1)*[у]). Здесь С((х-1)) - множество формальных степенных рядов вида

N

£ Д-Л Л- б с,

к= — ос

а С(х~1)* - множество дробно-степенных рядов:

/(х) 6 СОг-'Г => ЗА- 6 N : /(**) е С((.х-1))

Как С((х-1)), так и С(ж-1)* являются полями характеристики 0.

При этом поле С((.т-1)) содержит в качестве подполя поле частных

Ч

кольца многочленов <С[ж], а поле С(гс-1)* является алгебраическим замыканием поля С((ж-1)).

Элементы колец С((а:—1 ))[у] и С(ж-1 )*[i/j мы будем называть многочленами. Для многочлена N Л'

/ = ЕЕ а^/х^ещх-'т

1—0 j = —оо

определяется полная степень

deg / = max (г + j)

и однородный компонент д степени к:_

д= аИУ%х1-i+j = k

Аналогичные понятия определяются и для многочленов из кольца

С(х_1)*[т/]. При этом полная степень многочлена может оказаться

отрицательной или дробной. Элементы F колец С((ж_1))[у] и

С(а,'-1 )*[?/] называются собственными многочленами оператора D, D F

если принадлежит тому же кольцу.

Вторая глава содержит доказательства теорем, которые потребуются в дальнейшем при обосновании алгоритмов, и основной план исследования задачи: описаны частные случаи, в которых задачу удается решить и методы ее решения в каждом из этих случаев.

Фиксируем одно из колец С[х,г/], С((аг— 1))[у], С(л_1)*[?/] и обозначим его символом К. Отметим, что К - область с однозначным разложением на множители.

Пусть F, G Е К - собственные многочлены оператора D над К,

т.е.

DF = AF, DG — BG 1-Mi' у

для некоторых А, В £ К. Тогда многочлен ЕС тоже является собственным многочленом, причем = РТ>С 4- (так как

Б - оператор дифференцирования), то есть Б (^47) — (А + В)ЕС. Значит, произведение собственных многочленов само является собственным многочленом. Верна и обратная теорема:

Теорема 2.1.

Если ? £ К - собственный многочлен оператора Б, и ? = (Е К - разложение многочлена Г на неприводимые в К множители, то все многочлены .Г,- тоже являются собственными многочленами, т.е. для них выполняется условие € К.

Из этой теоремы следует, что для описания множества всех собственных многочленов оператора О достаточно описать множество его неприводимых собственных многочленов.

Следующая теорема дает некоторые ограничения на старший однородный компонент любого собственного многочлена оператора Б. Она понадобится в дальнейшем при поиске делителей собственных многочленов.

Теорема 2.2.

Пусть характеристический многочлен <р(г) оператора О имеет степень п + 1 и корни ао,...,ап. Тогда однородный компонент максимальной степени любого его собственного многочлена имеет

вид 7 = ПГ=о(г/ - оцх)к<.

Замечание.

Если <р(г) = 0, то аналогичного утверждения не найдено. Например, у оператора О = х+ усобственными многочленами являются многочлены у — ах для всех а Е С.

В третьей главе приводится алгоритм решения задачи в однородном случае. Рассматриваются операторы Б вида

В = Р(х,у)1 + Я(Х,у)§-у, 6

где Р и (3 являются однородными многочленами равной степени п. Для таких операторов можно за конечное число шагов найти оценку на степень собственных многочленов. Этот результат сформулирован в виде теоремы 3.1.

Теорема 3.1.

Если многочлены Р, <3 6 С [г, у] являются однородными многочленами равной степени, и их коэффициенты принадлежат конструктивному алгебраически замкнутому полю, в котором алгоритмически разрешима задача проверки рациональности элемента поля, то существует алгоритм, позволяющий за конечное число операций найти оценку на степень неприводимых собственных многочленов оператора И = Р4-

Сначала доказывается следующая лемма:

Лемма. Если в уравнении + ЯЩ — АР Р и Я являются

однородными многочленами степени п, а многочлены Г и А дают некоторое его решение, то многочлен А является однородным многочленом степени п — 1.

После этого делается подстановка у = гх. При этой подстановке многочлен Р переходит в многочлен ^Т/п2)1*! коэффициенты многочленов /,• можно вычислить непосредственно. В итоге получается следующий алгоритм: Алгоритм. Определим многочлены

р(г) = Р( 1,2), ф) = <?(1,г).

Если многочлен гр(г) — q(z) тождественно равен нулю, то степень неприводимых собственных многочленов оператора О ограничена числом 1. В противном случае возьмем рациональную функцию

ГМ =_М_

гр(2)-Я(гУ

Эту функцию можно разложить в сумму простейших дробей. Оператор D может иметь нелинейные неприводимые собственные многочлены только при условии, что эта сумма имеет вид г(г) = S ¿-'а > гДе все ri являются рациональными числами. Допустим, что это условие выполнено. Определим

г0 = 1 -П-----rm, M = LCM(den(ro),...,den(rm)),

Где den (г) - знаменатель рационального числа г, представленного в виде несократимой дроби, а LCM - наименьшее общее кратное целых чисел. Тогда решение задачи 1 будет даваться числом

Любой неприводимый многочлен Г, удовлетворяющий уравнению (3.1), является делителем многочлена

где Iо = х, U = у — aiX, i > 0 для некоторого комплексного с.

В четвертой главе приводится алгоритм решения задачи в случае, когда степень многочленов Р и Q не превосходит 1.

В этом случае задачу можно свести к однородному случаю путем замены переменных х = x¡ + хо, у = у\ + уо, где хо, уо -некоторые константы. При такой замене выполняются условия

Значения констант Хо, уо подбирается таким образом, чтобы многочлены Р(х\,у{) и С2{х1,у\) были однородными многочленами первой степени.

(3.5)

Ци(х,У)Мг'-с1[11(х,УГМг<

r¡>0 Tj«¡

dF__dF_ dF _ dF дх дх\' ду ду\

Для определения этих констант рассмотрим линейную систему уравнений

Г Р1Х + Р2У = ~Ро I = -до

относительно неизвестных х, у.

В зависимости от коэффициентов и совместности этой системы возможно несколько случаев, которые рассматриваются отдельно. В каждом из них удается получить нужную оценку.

В пятой главе продолжается анализ оператора

На этот оператор накладывается только условие, что его характеристический многочлен 9(2) имеет степень п + 1, где

п = тах(с^.Р, с^<3),

и свободен от квадратов. В некоторых случаях можно получить алгоритм, решающий задачу 1. Полное описание этих случаев, а также описание алгоритма и доказательство его правильности сформулированы в виде теоремы 5.4.

Пусть Р - собственный многочлен оператора Ю. Рассмотрим этот многочлен как элемент кольца С((ж_1))[г/]. В этом кольце многочлен F можно разложить на множители вида (у — + ...

(это следует из леммы Гензеля для этого кольца). По теореме 2.2, все числа ai являются корнями характеристического многочлена оператора Ю.

Решение задачи 1 мы будем искать по следующей схеме: найдем все собственные многочлены оператора О над кольцом С((.х—1 ))[у] вида Г = (у — пх)'^ + ..., где N 6 а = для некоторого г. Для достаточно широкого класса операторов такие

й

многочлены имеют простой вид, и существует алгоритм, позволяющий найти все их произведения, лежащие в С[х,у]. Выбрав из этих многочленов неприводимые, мы решим задачу.

Для поиска многочленов F можно воспользоваться методом неопределенных коэффициентов. Оказывается, что существование и общий вид этих многочленов зависит от разложения дроби r(z) = в сумму простейших дробей: если слагаемое, со-

ответствующее корню а знаменателя этой дроби, имеет вид jz^;, где а не является положительным рациональным числом, то собственный многочлен F вида (у — ax)N + ... определен однозначно для любого N и равен где Fi = у - ах + .... Значение любого коэффициента многочлена F\ можно найти, используя метод неопределенных коэффициентов. Этот результат сформулирован в виде теоремы 5.2.

В случае, когда числители всех дробей в разложении r(z) в сумму простейших являются отрицательными или иррациональными числами, задача поиска неприводимых собстенных многочленов оператора D может быть решена полностью.

Теорема 5.4.

Пусть D - дифференциальный оператор вида (1.1), для которого выполнены следующие условия:

- коэффициенты многочленов Р и Q принадлежат алгебраически замкнутому конструктивному подполю F поля С, в котором можно эффективно (т.е. за конечное число операций) вычислять корень любого многочлена с коэффициентами из этого поля и находить рациональную зависимость любого множества элементов {ci,... ,сп}, т.е. такие рациональные числа Ai,...,A„, что выполняется условие А ¡с, = 0 (или доказывать, что их не существует). Примером поля F с такими свойствами является поле алгебраических чисел;

- характеристический многочлен ip(z) = zp(z) — q(z), имеет степень

Л"

п + 1 и свободен от квадратов;

- разложение рациональной функции ^^ в сумму простейших дробей над С имеет вид

р(г) ^ а,-

Ф)

— V--—, где Vi : а,- ¿ Q или а,- ^ О

ыог~а'

Тогда существует алгоритм, позволяющий за конечное число операций найти все неприводимые собственные многочлены оператора D в кольце С[я, у].

Для доказательства этой теоремы рассматриваются многочлены F = П-^У' и А = где Fi - собственный многочлен оператора D из С((ж_1))[у] вида у — a¡x + ..., a A¡ = Обозначим эти многочлены F(v) и A(v), где v - вектор (t>i,..., vn). Чтобы F(v) и A(v) принадлежали кольцу С[х, у], необходимо и достаточно, чтобы коэффициенты этих многочленов при х3у\ j < О равнялись нулю.

Теорема 5.5.

Условие F(v), A(v) g С[ж, г/], можно записать в виде некоторой бесконечной системы линейных уравнений от координат вектора V. Любое из этих уравнений можно эффективно построить по коэффициентам многочленов Р и Q.

Следствие.

Если для вектора v = (vq, ... ,v„) один из многочленов Л(и), F(v) не принадлежит кольцу С [ж, у], то существует алгоритм, находящий линейное уравнение из системы (5.6), (5.8), которое не выполняется для этого вектора.

Лемма 5.4.2.

Для вектора v — (va,..., vn) можно за конечное число операций проверить выполнение условия F(v), A(v) Е С[х,у].

U

Из этих утверждений следует, что для доказательства теоремы 5.4 достаточно найти эффективный алгоритм решения бесконечной системы линейных уравнений над Более точно, пусть су-

ществует алгоритм, который проверяет принадлежность вектора пространству решений системы, и в случае, когда вектор не удовлетворяет хотя бы одному из уравнений, находит коэффициенты этого уравнения. Требуется описать все пространство решений, т.е. множество тех векторов из которые удовлетворяют всем

уравнениям системы.

Описанию такого алгоритма посвящена оставшаяся часть главы 5.

В шестой главе проводится развитие метода, описанного в пятой главе, а именно, собственный многочлен оператора D раскладывается на множители в кольце многочленов над дробно-степенными рядами С(а:-1 )*[)/]. Поскольку множество С(х-1)* является алгебраически замкнутым полем, любой многочлен из кольца С(х-1)*[у] со старшим коэффициентом, равным 1, можно разложить в произведение многочленов вида у — /(.с), где f(x) £ С(ж_1)*. Если характеристический многочлен <p(z) оператора D свободен от квадратов и имеет степень п + 1, то каждый ряд f(x) имеет вид q,x + ..., где а, - один из корней характеристического многочлена.

Для решения задачи достаточно найти все ряды f(x) такого вида, для которых выполняется условие Q(x, у) — Р(х, y)f'(x) = А(х,у)(у — f(x)), А Е С(а;-1)*[?/], а затем выделить те их произведения, которые являются многочленами из С [ж, у].

В следующей теореме описывается множество собственных многочленов вида у — f(x) оператора D.

Теорема 6.1. Пусть (у — f(x)) 6 С(г 1 )*[</] - собственный многочлен оператора D, т.е.

Q(x,y)-P(x,y)f'(x) = A(x,y)(y-f(x)), А € С(ж-1)*[у], ((6.1))

причем f(x) = ах + ..., где а - корень характеристического многочлена оператора D. Положим а = . Тогда, в зависимости от значения а, возможны два варианта:

- если а не является положительным рациональным числом (в частности, если а = оо), то ряд /(х) определен однозначно и имеет вид

/{х\ где S = {к 6 Z | к < 1};

¿65

- если а является положительным рациональным числом, то f(x) имеет вид

/¡х\ где 5 = {1 - к - al | к, I е N}.

ies

При этом все коэффициенты /,• однозначно выражаются через коэффициенты при fj, j > i, за исключением коэффициента при х1-". Этот коэффициент, в зависимости от коэффициентов многочленов Р и Q, либо может быть любым комплексным числом, либо не может принимать ни одного значения. В последнем случае собственных многочленов оператора D указанного вида не существует.

Используя эту теорему, можно свести задачу к системе линейных алгебраических уравнений от бесконечного числа неизвестных (это делается примерно так же, как в предыдущей главе). Если эта система не имеет ненулевых решений (в некоторых случаях это можно установить за конечное время), то у оператора нет собственных многочленов кроме констант. В противном случае вопрос о существовании собственных многочленов оператора и об оценке их степени остается открытым.

Некоторые соображения о том, какими могут быть решения этой системы и какую информацию из них можно получить, а также описание программы, которая строит и анализирует эту систему, приводятся в приложении В.

В заключение автор выражает глубокую благодарность своему научному руководителю Евгению Васильевичу Панкратьеву за внимание к работе.

ПЕЧАТНЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1 A bound, of Degree of Irreducible Eigenpolynomial of Some Differential Operator, г. Дубна, 1990. IV международное совещание по аналитическим вычислениям на ЭВМ в физических исследованиях. стр. 84.

2 A bound of Degree of Irreducible Eigenpolynomial of Some Differential Operator. ISSAC'91 Proceedings, ACM Press, 1991. pp. 265-266.

3 Оценка степени неприводимого собственного многочлена некоторого дифференциального оператора. Вестник Московского Университета, Математика, 5 (1990)

4 A.V.Astrelin, E.V.Pankrat'ev, A.F.Slepuhin. A Project of Tool for Implementation of a Computer Algebra System. Дубна, 1990. IV международное совещание по аналитическим вычислениям на ЭВМ в физических исследованиях, стр.18.

5 A.V.Astrelin, E.V.Pankrat'ev, A.F.Slepukhin. A Project of Tool for Creating of Computer Algebra Systems. IV International Conference on Computer Algebra in Physical Research. (Dubna, USSR, 1990). World Scientific Publishing, Singapore, 1991. pp 24-27.