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

0.1 ВВЕДЕНИЕ.

1 Теория декомпозиции дифференциальных многочленов. Общий случай.

1.1 О структуре мультипликативной группы обратимых элементов д'Аламберова кольца.

1.2 Отношения порядка.

1.3 Неоднозначность в определении R и Q. 3]

1.4 Определение Q при известных Р и R.

1.5 Ключевые наблюдения.

1.6 Декомпозиция многочленов многих переменных.

1.7 Определение сепаранты дифференциального многочлена R. Полное определение дифференциального многочлена R в некоторых случаях.

1.8 Алгоритм декомпозиции для случая Jq Ф 0.

1.9 Пример декомпозиции, где согласно теореме 1 д.м. R, определяется сразу

1.10 Переход от декомпозиции Р = Q(R) к декомпозиции

Р = Q(R), где сепаранта Sq = 1.

1.11 Дифференциальная теорема Вандермонда. Алгоритм декомпозиции в общем случае.

2 Упрощение алгоритма декомпозиции для некоторых частных случаев. Метод однородного спуска.

2.1 Случай декомпозиции Р = Q(R), где Q — ПОДО.

2.2 Упрощение декомпозиции в случае декомпозиции Р = Q(R), где Q — ПОЮ, a degRyin > ord{Q) {к > ч)

2.3 Определение старшей однородной части Rs в дифференt циальном многочлене R.

2.4 "Однородный спуск" при известном Rs.

2.5 Алгоритм непараметрической декомпозиции

2.5.1 Блок 1 (подготовительный).

-—- А Л

2.5.2 Переход к декомпозиции Pw = QV(RS), где Qv —

JIО ДО. Определение Qv.

2.5.3 Блок "определение Rs из декомпозиции Pw = QV(RS) при известном Qv".

2.5.4 Блок "определение Qv при известном Rs. Определение Я".

2.5.5 Блок "определение Q по известному Я".

2.6 Применение методов декомпозиции к уравнениям Пен леве

2.7 Определение д.м. R при известных д.м. Р и Q.

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

3.1 Отношения порядка.7G

3.2 Обобщение основных результатов.

3.3 Обобщение дифференциальной теоремы Вандермонда и алгоритма декомпозиции.

3.4 Однородный спуск. Пример декомпозиции.

I . i

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

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

Все современные системы компьютерной алгебры (Maple. Mathe-matica. M11PAD и др.) включают полуэвристические пакеты интернирования дифференциальных уравнений. Количество задач, решаемых алгоритмически, сравнительно невелико — это алгоритм Ри-ша неопределенного интегрирования элементарных функций, алгоритмы нахождения решений линейных обыкновенных дифференциальных уравнений в квадратурах (алгоритмы Ковачича и М.Зингера. [35], [36]) а также алгоритмы факторизации линейных обыкновенных дифференциальных уравнений. Пакеты, реализующие алгоритмы Ковачича и Риша, имеются практически во всех системах компьютерной алгебры. Упомянутые выше системы компьютерной алгебры включают пакеты декомпозиции многочленов. Имеется реализация одного из алгоритмов факторизации линейных обыкновенных дифференциальных уравнений в системе Maple (М. van Hoeij. 1995) [48], [49].

Все упомянутые алгоритмы неприменимы к нелинейным обыкновенным дифференциальном уравнениям, тем самым нахождение алгоритмов, упрощающих решение таких уравнений, весьма актуально. Одним из подобных методов упрощения является декомпозиция — представление данного алгебраического дифференциального уравнения Р(х:у(х),у'(х):. :у(п\х)) = 0 в виде суперпозиции уравнений меньших порядков: Q(x,r(x),r'(x),. ,г^(х)) = 0 и R(x,y(x),y'(x).,y^Hx))=r(x).

Ознакомим теперь читателя с основными обозначениями, необходимыми для поннмания основной части диссертации — теории декомпозиции дифференциальных многочленов. Под R'. R". . /?"'. у'. у". . ?/'• будем понимать соответственно первую, вторую. . . . /-ю полную производную по х функций R и у. Выражения (R,^)1''' и (//'■/))/' обозначают соответсвенно к,-ю и kj-ю степени этих производных. Пусть Р - некоторый многочлен от п + 1 неизвестных у(х), у'(х),. у^пЦх) с коэффициентами, являющимися элементами некоторого дифференциального поля К характеристики ноль. Запишем представление многочлена Р(х.у) в виде суммы мономов:

Р(х-,у)= Е .• x/i0 • (г/')*1 ■ (2/")ia ----- (.v4,,:)'"r (o.i)

O-'l -'2.hi

Многочлен P{x.y) называется дифференциальным многочленом от функции у. в дальнейшем, для краткости, просто д.м. Число п называется порядком д.м. Р. а наибольшая из степеней мономов deg(P) = max E/—U ?/.• — его полной степенью. Тогда, если на неизвестную функцию у(х) имеется дифференциальное алгебраическое уравнение

Р(х:у(х):у'(х),у"(х).:у^(х)) = 0: ((.-л где в левой части стоит известный д.м. Р, а в правой — ноль, то весьма актуальной является проблема упрощения этого дифференциального алгебраического уравнения. Большинство возникающих в приложениях дифференциальных уравнений являются как раз дифференциальными алгебраическими уравнениями. Поэтому все вопросы, связанные с изучением дифференциально-алгебраических уравнений, представляют огромный интерес и фактически эквивалентны исследованиям кольца дифференциальных многочленов одной или многих переменных.

Теория декомпозиции, которой посвящена данная диссертация, состоит в решении следующей задачи: по данному д.м. Р, зависящему от одной (первая и вторая главы) или нескольких (третья глава) функций найти д.м. Q и Я такие, что Р = Q(R, Я'. Я",. Я^).

Линейным обыкновенным дифференциальным оператором (в дальнейшем. для краткости. ЛОДО) называется выражение

L = а„(х) ■ Dn + a„i(:t) • Dn~l + . + а^х) ■ D + а0(х), (0.3) где Dk = означает оператор взятия к-ой производной, а все коэффициенты а; (ж) принадлежат некоторому дифференциальному полю характеристики ноль: а.;(х) £ К, например, полю рациональных функций от х: К = Q(x). Дифференциальное поле — это поле, в котором определена операция дифференцирования, удовлетворяющая следующим свойствам:

Ща-Ь) = D{a)-b + a-£){Ь).

D(a + Ъ) = D(a) + D{b), D{ 1) = D(0) = 0, a, b £ K, (0.4) см. [33]. [24]. ЛОДО называется приведённым, если его старший коэффициент равен единице: av(x) = 1. Как правило, если не оговор'"!?'.1 обратное, мы будем иметь дело с приведёнными операторами. Под порядком дифференциального оператора будем понимать степень наибольшего дифференцирования, то есть п. Будем говорить, что функция f(x)— решение оператора L, если L • (f(x)) = 0. Если функция f(x) — решение ЛОДО первого-порядка: (D + h(x)) • f(x) = 0. где h(x) 6 К, то она называется гиперэкспоненциальной, так как f(x) = e-Jh(x)dx

ЛОДО называется д'Аламберовским оператором, если он разлагается в произведение ЛОДО первого порядка:

L = {Ь + аг(х)) ■ ф±а2{х)) ■ . • [D + а„ (./■))■ (0.5) где все о/(:/:) -с К. Множество всех решений д:Аламберовскнх ЛОДО образуют д;Аламберово кольцо (см. [4], [5]), элементы которого молено обозначать как

И - / dx- j\{x) J dx ■ f2{x) • . ■ I (i.r • ./,(•' i. для удобства мы пишем дифференциал dx перед функцией, которую следует интегрировать, как это принято в физике), где оператор интегрирования понимается лишь как правый обратный к оператору дифференцирования: D-J = 1. Два таких элемента считаются равными. если после последовательного применения оператора дифференцирования п преобразований получаются тождественные выражения.

Множество ЛОДО над дифференциальным полем образуют некоммутативное кольцо, где под произведением ЛОДО понимается их композиция: L = L] о L2, то есть для произвольной функции f(x) верно равенство L(f(x)) = Li(L2(f(x))). Аналогично понимается сумма и разность ЛОДО. В этом кольце есть левый (и правый) алгоритмы Евклида деления с остатком, а также для любых двух ЛОДО /. п

Р имеется их левое (правое) наименьшее кратное, то есть сз'ществу-ют операторы М и TV", такие, что М о L N о Р. Поэтому у этого кольца есть некоммутативное поле (тело) частных, (см. [32]) с элементами, которые можно записывать в виде L\ о LJ1 или L3 1 о Z4, Л 1 Л 1 Л а отношение эквивалентности следующее: L\ о L^ = о L4, есл1*

L30L1 = L40L2. Два элемента, M0L3 1 и Z^o/V"-1 будут перемножаться как (MoLzl)o(L4oN~l) = Mo(L^loL4)oN~l = Мо^оЬ^оЙ'1 = (М с L\) о (N о L2)-1. Аналогично определяется левое (и правое) деление.

Вообще, кольца, в которых любые два элемента, одни из которых не является делителем нуля, имеют левое (правое) общее кратное (не обязательно наименьшее!) называются кольцами Оре (!30],[31],[32]). Практически все дифференциальные кольца оказываются кольцами Оре. Например, кольцом Оре является кольцо операторов в частных производных, с элементами вида г> . dh (Р- ()>■■

ЧЛ2.J„.7i.jl;.J„ Ux2 U-h" где AilJ2.,-I(!jbj,.ju G A, a A — коммутативная область целостности.

Это кольцо называется алгеброй Вейля (см. [14]).

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

1. С. А. Абрамов. Рациональные решения линейных дифференциальных и разностных уравнений с полиномиальными коэффициентами // ЖВМ и МФ, 1989. Т. 29. N. 11. стр 1611-1620.

2. S.A. Abramov, E.V. Zima. D'Alambertian Solution of Inhomoge-neous Linear Equations (differential, difference, and some other) // In: Proceedings of ISSAC'96, (New York, 1996), Y. N. Lakshman, Ed, ACM Press, pp. 232-240.

3. S.A. Abramov. EG-eliminations. // Journal of Difference Equations and Applications, 1999, v. 5, pp. 393-433.

4. S. A. Abramov, E. V. Zima. Completely Faetorabe Annihilators. // In: Proceedings of ISSAC'97 pp. 290 297.

5. S. A. Abramov, M. D. Petkovsek. D'Alembertian Solutions of Linear Differential and Difference Equations.// In: Proceedings ISSAC'94, pp. 169 174.6. .4. Акритас. "Основы компьютерной алгебры с приложениями". М.:"Мир", 1994.

6. М. Атьл. М. Макдоналъд. "Введение в коммутативную алгебру". М.:"Мир", Москва, 1972.

7. M. A. Barkatou. On Rational Solution of Systems of Linear Differential Equations. // Journal Symb. Сотр., 1999, v. 28. pp. 547-567.

8. M. Barkatou, Eckhard Pflugel. An Algorithm Computing the Regular Formal Solutions of a System of Linear Differential Equations. JI In: Proceedings ISSAC'97, pp. 569-587.

9. D.R. Barton, R.E. Zippel. Polynomial Decomposition Algorithms. -// Journal Symb. Сотр., 1985, v. 1, pp. 159-168.

10. E. Веке. Die Irreducibilitat der homogenen linearen Differentialgle-ichungen. // Math. Ammlcn Jf5 (1894), 278-300.

11. M. Bronstein. An improved algorithm for factoring linear ordinary differential operators // In: Proceedings of ISAAC'94 ■ ACM Pics--. 1994, pp. 336-340.

12. H. Бурбаки. "Коммутативная алгебра", M.: "Мир". 1971.

13. J. Е. Bjork. Rings of differential operators. 1979, North-Holland.

14. Б.Л.Ван дер Варден. "Алгебра", // М.: "Наука", 1979.

15. Ф. Р. Гаитмахер. "Теория матриц", // М.: "Наука", 1988.

16. В. В. Голубев. "Лекции по аналитической теории дифференциальных уравнений", М.-Л.: ГИТТЛ, 1950.

17. Дж. Дэвенпорт., И. Сире. Э. Турнъе. "Компьютерная алгебра. Системы и алгоритмы алгебраических вычислений", М.: "Мир", 1991.

18. R. Zippel Rational function decomposition // Tech. Rep. TR 911209, Department of Computer Science, Cornell University. 199 i.

19. Э. Камке. Справочник по обыкновенным дифференциальш уравнениям. М.: "Наука", 1971.

20. D. Kozen, S. Landau. Polynomial decompositions. J. Symbc Comput. v. 7 (1989), P. 445-456.

21. D. Kozen, S. Landau, R. Zippel. Decomposition of algebraic fui tions. J. Symbolic Comput. 22 (1996), 235-246.

22. D. Kozen, S. Landau. Polynomial Decomposition Algorithms. r. 86-773, 1986, Department of Computer Science, Cornell Universi Ithaca, NY 14853.

23. E. Kolchin. Differential Algebra and Algebraic Groups. 1973, N Academic Press.

24. А. Г. Курош. "Лекции по обшей алгебре". M.: "Наука". 1973

25. С. Лет. "Алгебра", М.: :'Мир\ 1968.

26. A. Loewy. Uber reduzible lineare homogene Differentialgleichun^: // Math. Annalen 56 (1903), 549-584.

27. A. Loewy. Uber vollstandig reduzible lineare homogene Differ tialgleichungen // Math. Annalen 62 (1906), 89-117.

28. П. Олвер. "Приложение групп Ли к дифференциальным урав ниям", М.: "Мир", 1989.

29. O. Ore. Theory of non-commutative polynomials // Annals of Mathematics v. 34 1933, P. 480-508.

30. J.F. Ritt. Differential Algebra. Dover Publications, Inc., 1966.

31. A. H. Рублев. "Линейная алгебра". M.: "Высшая школа", 1968.

32. Singer M.F. Testing reducibility of linear differential operators: a group theoretic perspective. Applicable Algebra in Engineering, Communication and Computing. 199U. v. 7. p. 77-104.

33. Singer M.F., Ulmer F. Galois groups of second and third order linear differential equations. Journal of Symbolic Compulation. 1993. v. 10, p. 9-36.

34. M. В. Соснип. "Кольца дифференциальных операторов и алгоритмы факторизации" // Тезисы доклада на Международной конференции "Математические модели и методы их исследования" 25-30 августа 1997 года, стр. 170.

35. М. В. Соснин. "Упрощение алгебраических дифференциальных уравнений с помощью алгоритма декомпозиции дифференциальных многочленов" // Красноярск. (2001. 38 с. Препринт 3-01 РАН. Сиб. Отделение. Институт вычислительного моделирования;).

36. М. В. С оспин. "Алгоритм декомпозиции дифференциальных многочленов" // Сборник "Комплексный анализ и дпфферснииальные операторы", Изд-во Красноярский Государственный Университет, Красноярск, с. 147-161:

37. М. В. Соснин. "Алгоритм непараметрической декомпозиции дифференциальных многочленов", "Программирование", 2001 г., № 1, с. 59-66. Компьютерная алгебра УДК 681.3.06.

38. М. В. Соснин. "Алгоритм декомпозиции дифференциальных многочленов" // Сборник "Кубатурные формулы и их приложение. . V Международный семинар- совещание", 13-18 сентября, 1999 г. Тезисы докладов. КГТУ, под редакцией М. В. Носкова. Красноярск, с. 36-37.

39. М. В. Соснин. "Полный алгоритм декомпозиции дифференциальных многочленов". // "Научный ежегодник Красноярского Государственного Педагогического Университета", выпуск 2 том 1. Красноярск, 2001, с. 48-59.

40. С. Л. Фиников. "Метод внешних дифференциальных форм Кар-тана в дифференциальной геометрии." (Теория совместности систем дифференциальных уравнений в полных дифференциальных и в частных производных.) ОГИЗ, ГИТТЛ, М.-Л., 1948.

41. С. Л. Царев. О нелинейных уравнениях с частными производными. интегрируемыми по Дарбу. // Труды Матем. Ин-та им. В.А.Стеклова. 1999, Т. 225. С. 389-399.

42. E. Япкс. Ф. Эмде., Ф. Jleui. Специальные функции. (Формулы, графики, таблицы). М.: "Наука", 1968.ГС- <5