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

'С | и V ^

ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ

5-95-363

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

БЛИНКОВ Юрий Анатольевич

ИНВОЛЮТИВНЫЕ АЛГОРИТМЫ ДЛЯ ИССЛЕДОВАНИЯ НЕЛИНЕЙНЫХ

АЛГЕБРАИЧЕСКИХ И ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

Специальность: 05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Дубна 1995

Работа выполнепа в Лаборатории пмчиглпгглмшП юхники п автоматизации Объединенного института ядерных пгслсдопаинП

Научный руководитель:

Доктор физико-математических паук В.П.Гердт Официальные оппоненты:

Доктор физпко-математпчеекпх наук, М.Г.Дмитриев профессор

Кандидат физико-математических наук Е.В.Панкратьев

Ведущая организация:

Научно-исследовательский институт ядерной физики МГУ, Москва.

г. в и и час.

Защита диссертации состоится 'Ч ) п й&и^сЯ-^}^ 1995 г. в ^ ^ час. иа заседании диссертационного совета Д 047.0Т.04 при Лаборатории вычислительной техники и автоматизации Объединенного института ядерных исследований, г.Дубна Московской области.

С диссертацией можно ознакомиться в библиотеке ОИЯИ.

Автореферат разослан 1995 года

Ученый секретарь диссертациоппого совета

(у, З.М.Иванченко

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

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

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

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

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

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

подсистемы, то мы, очевидно, действовали эквивалентным способом, т.е. не потеряли и не добавили решения, которые допускает первоначальная система. Ярким примером канонического представления является базис Гребнера для полиномиального случая и его дифференциального аналог для систем дифференциальных уравнений в частных производных (ДУЧП).

Каноническое представление мошет быть также полученно приведением системы к инволютивному виду. История этого вопроса возвращает нас к работам французских математиков Рикье (1910) и Жане (1920), которые заложили основы инволютивного повода к анализу ДУЧП. Современная математическая трактовка ДУЧП с точки зрения инволютивности может была дана в работах Поммаре.

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

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

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

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

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

Разработан комплекс программ в системе компьютерной алгебры REDUCE 3.5 для построения инволютивных базисов Поммаре для полиномиальных идеалов и преобразования систем линейных дифференциальных уравнений к инволютивной форме.

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

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

• проверку совместности уравпепий;

• вычисление размерности пространства решений;

• исключение некоторого подмножества переменных;

• редукцию системы к копечпому числу "более простых" подсистем;

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

• анализом симметрий;

• распознаванием специальных внутренних алгебраических свойств, таких, например, как интегрируемость ДУЧП методом обратной задачи рассеяния.

Одной из важных прикладных задач является нахождение симметрий нелинейных дифференциальных уравнений. Наиболее трудоемким по объему вычислений является преобразование определяющих липейпых ДУЧП для генераторов симметрии к стандартной инволютивиой форме. Это не только дает возможность значительно упростить задачу интегрирования определяющих уравнений, но также позволяет определить размерность группы симметрий и даже найти ее алгебру Ли без явного интегрирования.

На защиту выносятся следующие результаты:

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

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

3. Для описания с единой точки зрения различных ипволютнвных алгоритмов впервые введено общее понятие ипволютивного деления мономов, позволяющее

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

4. На основе инволютивного деления введено понятие инволютивной нормальной формы и частичной инволютнвности. Последнее позволило ввести в инволютивных алгоритмах аналоги критериев Бухбергера, используемых при построения базисов Гребпера с целью пропуска необязательных редукций. Доказано окончание инволютивного алгоритма для любого конечного инволютивного деления.

5. Инволютивные алгоритмы реализованы в виде пакета в системе REDUCE для построения инволютивных базисов Поммаре полиномиальных идеалов и преобразования систем линейных дифференциальных уравнений к инволютивной форме. На ряде полиномиальных систем показан значительный выигрыш по сравнению со стандартным пакетом построения базисов Гребнера.

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

Апробация работы.

Основные результаты работы докладывались на:

- международном симпозиуме "International IMACS Symposium on Symbolic Computation: New Trends and Developments", Лиль, 1993;

- международном симпозиуме "Quantifier Elimination and Cylindrical Algebraic Decomposition", Линц, 1993;

- международной конференции "Interval and Computer-Algebraic Methods in Science and Engineering", Санкт-Петербург, 1994;

- международном совещании "Rhein Workshop on Computer Algebra", Карлсруэ, 1994;

- международном совещании "New Computer Techologics in Control Systems", Переславль-Залесский, 1994;

- международном совещании "PoSSo Software Workshop", Париж, 1995.

- на научных семинарах СГУ, МГУ, ЛВТА ОИЯИ, ИК АН Украины, университетов Гренобля, Кана, Лейпцига, Лиля, Лиможа, Исследовательского научного Центра им. Копрада Цузэ в Берлине.

Публикации. Основные результаты диссертации опубликованы в 8 научных работах, которые приведены в списке литературы.

Структура диссертации. Диссертация состоит из введения, четырех глав и заключения; содержит 75 страниц наборного текста, включая 5 таблиц и библиографический список литературы из 51 названия.

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

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

Во второй главе обсуждаются вопросы приведения к каноническому виду мноя£еств мономов. Свойства этих множеств являются общими для систем полиномов и ДУЧП.

В раздые 2.1 рассматривается вопрос приведения к напоническому виду для деления мономов по полной степени (обычное делеаие). В данном случае каноническим является авторедуцироваппое множество мономов.

Определение 1 Множество U называется авторедуцированным если оно не содержит элементы, которые кратны другим элементам U.

В разделе 2.2 вводится повое понятие инволютивного деления, обобщающее деления Томаса, Жане, Поммаре, и па его основе строятся инволютивпые множества мономов.

Определение 2 Будем говорить, что на множестве U определено инволюти-вное деление на М и записывать u\¡w для инволютивного делителя и £ U монома w € М, если верны следующие утверждения:

(i), из u\¡w следует u\w.

(ii). u¡/u для любого и £ U.

(iii). Если u\[W и г>|/ги для u,v € I/ и ю € М то и|/г> или ti|/ti. fiv). Если u\¡v и v\iw для u,v £ U и w 6 М то u\¡w (транзитивность). (v). u\¡uv и «|/utu, если и только если w|/u(t>w) (непрерывность).

Заметим, что обычпое деление мономов удовлетворяет условию (iii) только в случае одной независимой переменной. Так, например, уже в случае двух переменных: x|(xi/) и 2/1(21/), но -ix|y и -'j/lx. Определенное выше инволютивное деление позволяет ввести соответствующие правила умножения.

Определение 3 Если u|í(uj = uv), то моном v будем называть мультипликативным для и, и, соответственно, записывать w = и х v. Если же и является делителем w, но не инволютивным, то будем записывать w = u-v, a v называть немультипликативным для и.

Это определение, вместе со свойством непрерывности (и) инволютивного деления для каждого и € U, разделяет множество переменных х = М(и, U) U NM(u,U) на два непересекающихся подмножества (М П NM = 0) мультипликативных M(u,U) и немультипликативных NM(u,U) переменных. Рассмотрим мономиальное множество U. Введение па нем инволютивного деления, удовлетворяющего (iii) — (iv), возможно

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

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

Определение 4 Деление Томаса. Пусть II — конечное множество и

А,- = тах{<1ед{(и) | и £ [/} .

Переменная а;; является мультипликативной для и € и, если ёед{(и) = Л,-, и немультипликативной в противном случае.

Определение 5 Деление Жане. Пусть множество и конечно и все мономы иеи разбиты на группы [¿1,.. .,</,-], где = йед^и). Тогда ц будет мультипликативной для члена группы и € [¿1,. ..,¿,-1], если ее степень (!ед{(и) = /г,. Здесь = тах{^е</!(и) | и € С/} и

}ц = тах{с%Дг;) | V € ..,¿¿-1]} (г > 1).

Если ¿ед^и) < Л,-, то х,- является немулътипликативной.

Определение 6 Деление Поммаре. Для монома • • ■ с г'ь > О переменные х1 при ] > к являются мультипликативными и, наоборот, хпри ] < к немультипликативными.

Заметим, что

• Деление Томаса не зависит от упорядочения переменных х;. Наоборот, деления Жане и Поммаре, по их определению, основаны на упорядочении переменных II >- х2 X • • • >- хп.

• Разбиение переменных на мультипликативные и немультипликативные в случае делений Томаса и Жане зависит, вообще говоря, от структуры всего множества мономов II. Напротив, деление Поммаре целиком определяется рассматриваемым мопомом безотносительно к другим элементам и. определено.

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

Предложение 7- Мономиальные деления Томаса, Жане и Поммаре инволюти-вны.

Определение 8 Множество II называется авторедуцированным по инвоАюти-вному делению (обозначается АЫо11е<1исе1(и) = 11), если оно не содержит элементы, которые имеют инволютивного делителя среди других элементов II.

Введенное определение авторедуцированного множества по инволютивпому делению не является каноническим представлением множества, в отличие от Определения 1. Это будет ясно из дальнейшего изложения.

Пример 9 17 = {ху,у2, г} (х У у у г).

мономы Томас Жане Поммаре

МТ NMт ЛЬ N^3 МР NMp

■ху X У, г - 1Л г X

У2 У х, г У, г X У.г X

г г х,У г Х,У 2

Определение 10 Множество и называется инволютивным, ес.ги для любого и) € М, умноженного па какой-нибудь элемент и 6 1}, существует инволюти-вный делитель V € II, вообще говоря, отличный от и. Другими словами

(V« € и) (Уш € М) (Зу.е и) [ г>|/(иш) ].

Определение 11 Для конечного множества (У инволютивное деление называется конечным для множества 1}, если существует конечное инволютивное множество V, такое что У С {У. Множество I/ называется инволютивным замыканием II. Инволютивное деление называется конечным, если существует конечное инволютивное замыкание для любого конечного множества.

Предложение 12 Деления Томаса и Жане конечны.

Теорема 13 Авторедуцированное инволютивное замыкание конечного множества единственно.

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

Пример 14 (продолжение Примера 9). Авторедуцированное инволютивное замыкание множества 1} = (ху,у2,г) (х У у >- г) для делений Томаса, Жане и Поммаре имеет вид

йт = {ху,у2,г,хг,уг,ху7,хуг,у2х,ху2г} , й] - хг,уг],

VР = {ху, у2, г, хг,уг,х2у, х2г,...,хку,.. .,хтаг,...} ,

где к,т 6 N. Этот пример показывает, что деление Поммаре. не. является конечным. Однако, деление Поммаре конечно для и, но в другом порядке переменных г У у У х) для которого Ор =11.

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

В разделе 2.3 для характеристики пространства решений систем полиномов и ДУЧП используются понятия полинома Гильберта, характеров Картана, сила (жесткость) дифференциальных уравнений по Эйнштейну, методы построения которых основаны на полученных канонических представлениях.

Третья глава посвящена вопросам исследования систем полиномов.

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

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

Следствие 15 Если множество Р1 авторедуцированно, то инволютивиая нормальная форма, для произвольных полиномов рх, р2 и Р> обладает свойствами:

(г). Единственность: если Ь.х = Л^.Р/(р, .Р) и Ь-г.= ЫР1(р,Р) то /га =

(и). Линейность: МР]^! +р2,Р) = Л^/(рь.Р) + .

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

Определение 16 Умножение полинома / на моном и называется продолжением /. Продолжение называется мультипликативным, если и является мультипликативным термом для /£(/), и немультипликативным, в противном случае.

Определение 17 Авторедуцированное множество F называется инволюти-виым, если

(V/ € /Ч (Уи е М) [ NF1{fu,Р) = 0 ].

Теорема 18 Множество Р инволютивно тогда и только тогда, когда выполнены следующие условия инволютивности

(V/ е Г) (VI,- е мму, F)) [ вд/ • Р) = о ].

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

Определение 19 Множество полиномов Р будем называть частично инво-лютивным до V € М если

(V/ € Л (V« € М) (/т(/) • и X у) [ NFI(fu, Л = 0 ].

Следствие 20 Множество полиномов F частично инволютивно до монома v, тогда и только тогда, когда

(V/ € F) (Vz € NM(f, F)) (lm(f) • x X „) [ NFi(f ■ x, F) = 0 ].

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

Затем доказывается, что инволютивный базис является нередуцироваппым базисом Гребпера. Ниже приводится одна из версий инволютивного алгоритма. Здесь через /£(/) обозначается лидирующий терм полинома / для заданного упорядочения

Алгоритм InvolutiveBasis:

Input: F — множество полиномов

Output: G — инволютивный базис для Jdeal(F)

begin

G := AutoReducei(F) P := 0 "

while {(¡t(g),x) \ g € G,x 6 NM(g)} \ P ф 0 do choose (g,x) such that

g € G, x € NM(g,G), (lt(g), x) £ P and \t{g) ■ x - minimal >-P:=PU{(lt(g),x)} h := NFi{g ■ x, G) ■ if НфО then

G := AutoReducej{G U {h})

end end

• Пример 21 Циклические корни 4-го порядка.

NMj NMP Начальное множество полиномов

Х2,Х3,Х4 Х3,Х4 Х4 Xl Xi,X2 хг,х2,хз Xl + х2 + х3 + х4 xix2 + X2X3 + Х3Х4 + 3:4X1 Х1Х2Х3 -f Г2Х3Г4 + Х3Х4Х1 -f- Х4Х1Х2 Х1Х2Х3Х4 — 1

Здесь выбранно упорядочение: сначала по полной степени, а затем обратное лексикографическое с порядком переменных Х\ >■ х2 >~ х% У- х4. В таблице приведены немультипликативные переменные для каждого полинома системы. Применение алгоритма 1пуо1иИьеВаз{з дает следующий вид инволютивных базисов по делениям Жане и Поммаре

ИМ] ЛГМР Базисы Жане и Поммаре

XI XI, 12 ' Х1,Х2,Х3 Х\,Х2,Х3 XI,х2 Х\,Х2,Х3 XI хих2 Хх,Х2,Хз Х1,Х2,Х3 х1,х2,х3 Х\,Х2,Х3 XI 4" Х2 4" Х3 4" х4 Х2 4- 2х2х4 + х\ Х2Х3 4" Х3Х4 Х2Х4 — Х2Х3Х4 -1- Х3Г4 — Я2Х4 4- Х3Х4 — х\ — 1 х2х\ 4- х\ — х2 — х4 Х^Х^ Х^Х^ Х3 3/4 2§Х4 4- Х2Х3 — Х2Х4 4- Х3Х4 — 2^4

Х1,Х2,Х3 .Т1,Х2, Хз х\х\ 4- Х2Х3 — х3 — х2х4 4- Х3Х4 — х\

х3{х^х\ 4- х2х3 — х\ — х2х4 4- х3х4 —

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

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

Раздел содержит развитие идей построения базиса Гребнера для дифференциального случая.

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

__... х<">

1

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

Соответственно, мультипликативные и немультипликативные переменные для дифференциальных термов определяются по их мономиальным аналогам.

Определение 22' Мультипликативные и немультипликативпые переменные дифференциального полинома и, соответственно, мультипликативные и немультипликативпые продолжения определяются по его лидирующему терму (моному).

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

Приводится описание алгоритма DifflnvolutiveBasis для систем линейных дифференциальных уравнений. Подчеркиваются преимущества инволютивных базисов перед редуцироваппыми дифференциальными базисами Гребнера как канонической формы для липейпых ДУЧП. Дифференциальное отображение нульмерной полиномиальной системы имеет общее решение точно зависящее от количества произвольных констант, дающего число корпей системы с учетом их кратности. Размерность полиномиального идеала совпадает с числом произвольных функций в общем решении соответствующих ДУЧП.

Ипволютивпая форма линейных ДУЧП может называться канонической не только потому, что это - дифференциальный базис Гребнера, но также благодаря факту, что инволютивпые системы особенно удобны для выбора начальных условий, которые обеспечивают существование единственного и локально голоморфного решения. Кроме того, мояшо, вычислять такие списки начальных условий, которые находятся во взаимно-однозначном соответствии с произвольными константами или функциями в общем решении.

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

В разделе 5.1 описываются пакет INVBASE, реализующий полиномиальные ин-волютивные алгоритмы для делепия Поммаре. и приводятся примеры использования пакета для вычисления полиномиальных инволютивных базисов. Демонстрируется преимущество пакета INVBASE по сравнению со стандартным пакетом GROEB-NER системы REDUCE реализующем алгоритм Бухбергера для построения базисов Гребнера. Разность в быстродействии варьируется от 2-х до 20 раз, причем рлзница во времени счета возрастает с ростом сложности примера.

Во всех вычислениях с пакетами INVBASE и GROEBNER использовано упорядочение мономов по полной степени, а при равных полных степенях по обратному лексикографическому порядку (DegRevLex). Расчеты проводились па компьютере АТ/386 с 8 Mb RAM и частотой 25 MHz под управлением MS-DOS. Ниже представлены результаты вычислений для следующих примеров:

Пример (I)

+ х^хз + Х1Х2Х3 4- xix2x3 + Х]Х2 + xix3 4- х2х3 = 0, x\xlx3 + xix\x\ + х\х2х3 + XlS2X3 + х2х3 + х, + х3 = 0, х\х\х\ + xjx2x3 + XiXjX3 -I- х^г^з + х^з -f х3 -f 1 =0.

Пример (II)

XI + х2 + х3 4 х4 + х5 = О,

Х)Х2 4 Х2Хз + Х3Х4 4 Х4Х5 + Х5Х) = О,

Х!Х2Х3 4- Х2Х3Х4 + Х3Х4Х5 + Х4Х5Х1 4 Х5Х1Х2 = О,

Х1Х2ХзХ4 + Х2ХзХ4Х5 4 Х3Х4Х$Х1 + Х4Х$Х1Х2 4 Х5Х1Х2Х3 = О,

Х1Х2Х3Х4Х5 —1 = 0.

Пример (III)

XI 4 Х2 4- Хз 4 х4 + х5 = О,

х^х2 4- х2хз + х3х4 4 х4х5 + 25X1 = О,

Х1Я2Х3 + Х2Х3Х4 4 Х3Х4Х5 4- Х4Х5Х1 4 Х5Х1Х2 = О,

Х.2Х3Х4 4 Х2Х3Х4Х5 4- Х3Х4Х5Х1 4 Х4Х5Х1Г2 4 Х5Х1Х2Х3 = О,

Х1Х2Х3Х4Х5 —1=0.

Пример (IV)

XI 4 х2 4- х3 4- х4 4 х5 4 х6 = О,

Х]Х2 4 х2хз + Х3Х4 4- Х4Х5 + Х5Х6 4 х6хх = О,

Х1Х2Х3 4 Х2Х3Х4 4 Х3Х4Х5 4 х4х5х6 4 х5х6Х1 4 Х6Х1Х2 = 01

Х1Х2Х3Х4 4 Х2Х31415 4- Х3Х4Х5Х6 4-

Х4Х5Х6Х1 + Х5Х6Х1Х2 4 Х6Х1Х2Х3 = О,

Х1Х2Х3Х4Х5 4- Х2Х3Х4Х5Х6 + Х3Х4Х5Х6Х1 4

Х415ХеХ1Х2 4" ®5Хб®1£2®3 4 Х6Х1Х2Х3Х4 = О,

цх2х3х4х5ха — 1 = 0. В приводимой ниже таблице использованы обозначения:

• Т\ - время счета ннволютивного базиса, затраченное пакетом ШУВАБЕ

• Тг - время вычисления редуцированного базиса Гребнера, затрачен вое пакетом СШЕВКЕ11"

» N1 - число элементов ипволютивного базиса

» N2 - число элементов редуцированного базиса Гребпера

(пример) порядок переменных Ti(sec.) r2(sec.) Ni Ni

(I) хх У x2 У х3 16 33 15 15

(II) xt У х2 У х3У х4 У xs 11 8 23 20

(II) xi У х2 У х5 У х3 у х4 9 7 23 20

(III) x-i У х2 У х3 У х4 У Xs 149 341 31 25

(III) Xi У х2 V х5 У х3 У х4 1948 3050 32 24

(III) х4 У хг У xs У х2 У х3 87 1190 32 23

(III) Xj У х5 У хг У х3 У х4 94 2410 25 24

(IV) ХХУ Х2У Х$У Х3У Х4У Х5 7657 >140000 46 —

(IV) х$ У х4 У х3 У xs У х2 У xi 3795 77400 46 45

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

Приведенная ниже таблица показывает времена счета с помощью пакета IN-VBASE при различных порядках переменных для системы (IV) на рабочей станции IBM RS/6000-550 с частотой 41 Мгц.

порядок переменных время (sec.)

xi У х2 У х3 У х4 У xs У xg 1085

xs У х4 У х3 У xs У х2 У Х\ 694

<- У х6 X Х3 У Х4 >- Х5 869

Хб >- х2 У Х3 У Х5 У Х4 У Xi 446

х3 У хг У Х5 У Xs У Х2 У х4 233

х6 У х$ У х2 у хг У х3 У х4 662

х4 У хв У Xi У х2 У х5 У х3 543

Х2 У х3 У х5 У Xi У хе У Хв 729

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

В разделе 5.2 содержится описание пакета DINVBASE, реализующего на языке REDUCE алгоритм DifflnvolutiveBasis для приведения систем линейных ДУЧП к инволютивному виду. Здесь же на примере линейной системы ДУЧП из трех Уравнений третьего порядка и с тремя независимыми переменными демонстрируются вычислительные преимущества работы по вышеописанной аналогии с полиномиальными уравнениями вместо прямого счета дифференциального редуцированного базиса Гребнера.

В разделе 5.3 в качестве приложения разработанных алгоритмов и пакетов решается задача нахождения симметрий для нелинейного трансзвукового уравнения газовой динамики Линя-Рейснера-Тзяна

uv

2uxt + uxulx - ип - w— = 0,

для плоского w = 0 и осесимметричного w = 1 случаев. Условие того, что /(i, х,у, и, ut, их, иу) является производящей функцией инфинитезимальных симме-трий уравнения дается следующей системой из 12 линейных дифференциальных уравнений

/utut = 0, /utiii — 0, /u(Uy = 0, 1ихия ' 0) fuxliy = 0) fuylLy ~ 2{fix + "1 fxu + «I /.„ + U, U* /uu) + Ux (fxx + 2 Ux Jxu + 2 Ur U* lull) -

(/»» + 2 uv fyu + Щ uy /««) + ™ у (2 + 2 u„ /„Uy + /„) - — (/у + Vy /„) - W Ц /„ = 0, /xu, + ux fuu, = 0,

У У

2 (Л + /го, + /г«, + «г /„, + «г Ли,) + Ux (2 + 2вг /„«,) -2 (2 /уи„ + 2 uy /uu„ + /и) = 0, (/*„„ -+ их /гш„) - (/„„, + иу /„„,) = 0,

2 (/iu, + Ли,) + (Л + их /и) + "г (/и + 2

их (2 /¡/иу "f* 2 Uy„fUUji + /„) = о,

/(и, + 11 i Ли») + "г (Ли, + «I Ли, ) — /уц, — Uy /,

: 0.

При w = 1 инволютивный базис с упорядочением переменных

ut>-u:c'yus>~uyx>~y'?~t

вычисленный с помощью пакета DINVBASE, состоит из 25 уравнений:

класс ut /„t„t = 0, класс их fn,Vx = 0,

fuxUx =

класс иу /u,Us = 0, /и*!», = 0,

класс и /„,„ = 0,

/«,» = о, /«,»= о, /« = о,

класс х JUyX = О,

fuxx ~f Л — 0, Л* = о" Л* — 0,

Jutx =

класс у jyy (2 г/2 /*< - Л, Л) = 0,

/«., = о. /«,» = о,

Л, = О,

futy ~ О, fry = О,

класс t fUtt - - /и = О,

/«.t+g («. /- + 3 Д) = 0,

/«,« = о,

/* = О.

Характеры Картапа для этого варианта системы говорят о том, что в решении будет три произвольные функции от младшей, в смысле упорядочения, переменной t:

а\ = 3, а\ = 0, aij = 0, а2 = 0, = О, а® = 0, а\ = 0.

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

/-¿Л, <=1

где

/i = 2ахих + ауиу — 4au,

/2 = 5but -f Ьхих + 3byity -f 3bu,

/з = 5ci2u( -(- c(2xy -(- 3y2)ux + 6ctyuy + 6ciu — lex1,

/4 = 7«r - 272 - 27V, /5 = dut, /в = lny,

h=T.

Здесь a, b, с, d — произвольные постоянные, а 7, er, г — произвольные функции t. В осесимметричпом случае решение получено впервые.

В заключении перечислены основные результаты, полученные в диссертации.

Результаты, вошедшие в диссертацию, опубликованы в работах:

1. Блинков Ю.А., Чернов И.А. "Редукция нестационарного трансзвукового уравнения к квазистационарному", Аэродинамика, Саратов, 1988, вып. 11 (14), 110-131.

2. Zharkov A.Yu. and Blinkov Yu.A. (1993). Involutive Approach to Solving Systems of Algebraic Equations. In: Proceedings of "SC 93", International IMACS Symposium on Symbolic Computation: New Trends and Developments, Jacob, G., Oussous, N.E., Steiberg S. (eds.), Laboratoire d'Informatique Fondamentale de Lille, Lille, pp. 11-16.

3. Жарков A.10., Блинков 10.А. Инеолютивные системы алгебраических уравнений., Программирование, 1094, 1, 53-56.

4. Zharkov A.Yu. and Blinkov Yu.A. Algorithm for Constructing Involutive Bases of Polynomial Weal. International Conference on Interval and Computer-Algebraic Methods in Science and Engineering. Interval'94. March 7-10, 1994. St-Petersburg, Russia. 258-260.

5. Zharkov A.Yu. and Blinkov Yu.A. INVBASE: A Package for Computing Involutive Bases. Proceeding of the Rhein Workshop on Computer Algebra (Karlsruhe, Germany, March 22-24, 1994). J. Calmet (Ed.), Institute of Algorithms and Cognitive Systems, University of Karlsruhe, 1994, 179-181.

6. Zharkov A.Yu. and Blinkov Yu.A. Algorithm for Reducing Systems of PDEs to Involutive Form. Proceeding of the International Workshop New Computer Techologics in Control Systems. (Pereslavl-Zalessky, July 11-15, 1994), Program Systems Institute, Pereslavl-Zalessky, 1994, 90-92.

7. Zharkov A.Yu. and Blinkov Yu.A. - Involutive Bases of Zero-Dimensional Ideals, Preprint JINR E5-94-318 (Dubna, 1994). Submitted to J. Symb. Сотр.

8. Gerdt V.P. and Blinkov Yu.A. - Involutive Polynomial Bases. Publication IT-95-271, Laboratoire d'Informatique Fondamentale de Lille. Lille, 1995.

Рукопись поступила в издательский отдел 8 ашуста 1995 [ ода.