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

/Г Б С! 2 7 ОКТ 1998

На правах рукописи

УТЕШЕВ Алексей Юрьевич

ИСПОЛЬЗОВАНИЕ СИМВОЛЬНЫХ МЕТОДОВ

ЛОКАЛИЗАЦИИ РЕШЕНИЙ ДЛЯ АНАЛИЗА ПОЛИНОМИАЛЬНЫХ СИСТЕМ

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

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

Санкт-Петербург — 1998

Работа выполнена в Санкт-Петербургском государственном университете

Научный консультант: доктор физико-математических наук, профессор Зубов В.И.

Официальные оппоненты: доктор физико-математических наук, профессор Гердт- В.П. доктор физико-математических наук, профессор Зайцев В.Ф. доктор технических наук, профессор Кулаков Ф.М.

Ведущая организация: Институт математики и механики Уральского отделения РАН (Екатеринбург)

Защита состоится ". 1998 г. в Ж часов на заседа-

нии диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу: 199178, Санкт-Петербург 14 линия, д. 39

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации РАН

Автореферат разослан СкТЭ^Э, 1998 г.

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

Копыльцов А.В.

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

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

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

MX)=0,...JL(X)=a (X := (xi,... ,Xb),Tij := deg /_,) (1)

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

9i{X) > 0,... ,дк(Х) > 0 (2)

также с вещественными коэффициентами. Искомое число нулей обозначается в дальнейшем

nrz{(l) I 3i(X) > 0,... ,дк(Х) > 0},

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

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

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

Разработанные А.Акритасом, Д.Коллинзом, Д.Бини, В.Паном и другими исследователями надежные символьные алгоритмы локализации нулей в одномерном случае широко реализованы в современных CAB. Сведением к одномерному случаю задача локализации в R2 решается в пакете CAD (цилиндрического алгебраического разложения), разработанного Д.Коллинзом и С.Макколламом.

Попытки распространения этих методов на большие размерности предпринимались неоднократно. Большинство из них использовали в качестве рабочего аппарата предложенный Е.Бухбергером в 1965 г. конструктивный алгоритм построения базиса Грёбнера идеала, порождаемого полиномами /i,...,/z,. С помощью этого алгоритма систему (1), как правило, удается привести к эквивалентной ей (т.е. имеющей тот же набор нулей) системе вида

xi -ii(^) = 0,...,rL_1-$i,.1(xL) = 0,A'i(xL) = 0, (3)

т.е. произвести исключение переменных xlt... ,хь-\- Здесь Ф],.. .,5>z,-i — рациональные функции, а — полином от х

Однако эмпирически было установлено, что непосредственное применение алгоритма Бухбергера для получения системы (3) весьма затратно даже для современной вычислительной техники. Кроме того, для систем общего вида оказалось невозможной априорная оценка времени работы алгоритма. Это обстоятельство побудило исследователей искать комбинированные подходы как к исключению, так и к отделению переменных, при этом допускалось использование аппарата базисов Грёбнера на промежуточных стадиях. Некоторые из этих подходов основывались на идеях классической теории исключения и использовали различные детерминантные представления многомерного результанта Tl{fi,. - В последнее десятилетие особое внимание было привлечено к методу, намеченному Ш.Эрмитом. Идеи этого метода развивались в нескольких научных центрах США, Франции и ФРГ . Из отечественных исследований, примыкающих к этой тематике, следует отметить работы красноярской школы теории функций нескольких комплексных переменных (Л.А.Айзенберг, В.А.Болотов, А.К.Цих, А.П.Южаков и др.).

Цель работы заключается в разработке конструктивных и реализуемых на ЭВМ алгоритмов исключения переменных и локализации нулей системы полиномиальных уравнений (как частный случай — построение многомерной системы

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

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

Научная новизна. В диссертации впервые построены два рекурсивных по числу переменных детерминантных алгоритма одновременного исключения переменных и локализации нулей системы (1) общего положения. Порядок определителей — минимальный по сравнению с известными ранее. Для системы (1), не удовлетворяющей условиям общего положения, предложен новый, развивающий технику базисов Грёбнера, подход к ее решению, заключающийся в исключении части переменных. Указаны способы преобразования предлагаемых символьных методов локализации нулей в численные методы их нахождения.

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

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

Установлена чисто алгебраическая разрешимость проблемы вычисления индекса Кронекера-Пуанкаре для полиномиальных векторных полей и алгебраических многообразий и неразрешимость задачи построения полиномиальной функции Ляпунова для автономной системы двух дифференциальных уравнений в критическом случае полного вырождения матрицы линейного приближения.

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

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

Положения, выносимые на защиту.

1. Два аналитических детерминантных метода исключения переменных и локализации вещественных нулей системы полиномиальных уравнений. Техника исследования свойств нулей системы уравнений в зависимости от содержащихся в ней параметров.

2. Алгоритм решения задачи полиномиальной оптимизации в ее общей постановке.

3. Техника построения коэффициентных критериев знакоопределенности однородного полинома, устойчивости системы дифференциальных уравнений в критическом по Ляпунову случае, наличия корней полинома f(z) в произвольной алгебраической области комплексной плоскости.

Апробация работы. Диссертация в целом, а также ее отдельные разделы, докладывались на конференциях: 5-й Четаевской "Аналитическая механика, устойчивость и управление движением" (Казань, 1987), "Метод функций Ляпунова" (Иркутск, 1989), CSAM'93 по компьютерным системам и прикладной математике (С.-Петербург, 1993), Interval'94 по интервальным и компьютерно-алгебраическим методам (С.-Петербург, 1994), CASC-98 по компьютерной алгебре в научных вычислениях (С.-Петербург, 1998), конференции, посвященной 90-летию Л.С.Понтрягина (Москва, 1998); на семинарах университета Твен-та (Энсхеде, Нидерланды), центра математики и информатики (CWI, Амстердам, Нидерланды), исследовательского института по символьным вычислениям (RISC, Линц, Австрия), технического университета г.Тимошиара (Румыния), на открытом семинаре PoSSo-95 (Ираклио, Греция); на городском семинаре "Информатика и компьютерные технологии" (СПИИРАН), а также на семинарах кафедры математического моделирования энергетических систем Санкт-Петербургского государственного университета.

Работа была поддержана совместным грантом Правительства Российской Федерации и Международного Научного Фонда (№JKF-100).

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

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

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

Первая глава содержит обзор классических результатов по установлению взаимного расположения корней полиномов /(ж) и д(х) от одной переменной.

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

В §1.2 собраны некоторые ключевые определения и результаты классической теории полиномов от одной переменной: результант, дискриминант, субрезультанты, линейное представление наибольшего общего делителя полиномов /(х) и

Ф■)■

Конструктивное вычисление этих объектов возможно разными способами, и в параграфах 1.3 и 1.5 указываются два из них. Приводимые результаты являются одномерными аналогами тех, что будут получены в главе 2. Способ локализации, излагаемый в §1.3, основан на результатах Якоби, Эрмита, Сильвестра и Кронекера. Рассматриваются три ганкелевы матрицы

Я = [А;+*1&=!о, С = (4)

элементы которых вычисляются по рекуррентным формулам как коэффициенты рядов Лорана

Л = = 9 _а ч

/ ' / ¿г**-1' / '

Эти коэффициенты являются значениями определенных симметрических рациональных функций от корней А1,..., Ап полинома /(х), (например, коэффициент з] известен как ^-я сумма Ньютона: з^ = ' + А{). Сигнатура матрицы 5 оказывается равной числу различных вещественных корней полинома /(х), а по индексам инерции матриц Я или С устанавливается число вещественных корней /(ж), удовлетворяющих условию д(х) > 0 или д(х) = 0.

Преимущество при использовании " ганкелевого" подхода к локализации корней проиллюстрировано в §1.4 на примере двух известных задач. Одна из них — локализация собственных чисел вещественной матрицы А — представляет развитие метода Леверье. Вековое уравнение

/(х) •— ск^Л — хЕ) = 0 эквивалентно <1е1;[а,-+*х - з^+к+^^о = 0 ,

где значение аь может быть вычислено как Бр Ак. При этом главные миноры второго определителя позволяют установить число различных собственных значений на произвольном интервале ]а, Ь[:

пгг{/(х) = 0 | а < я < 6} = У{1, Д^а),..., Д„(а)) - Д^Ь),..., ДП(Ь)).

Здесь V означает число знакоперемен в числовой последовательности.

Вторая задача — оценка чувствительности корней полинома к возмущениям его коэффициентов: для полинома

/(х) = хп + й1Хп~1 -+ • ■ • + ап + ех'

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

Теорема 1 . Критические значения параметра е являются корнями полинома

Г(е) = V(f(x)) = 7г«(Ф(х),С?(х) + е) (5)

Здесь = п,Т> — дискриминант, 71 — результант, Ф(г) /(х) — 4/'(х)х, 0(х) := Щ-1 (х)Р(х), а обозначает остаток от деления полинома [К-Ф^ШО'а^Г1 на Ф(а).

Однако выражения для коэффициентов полинома Р(е) часто оказываются более громоздкими, чем для коэффициентов /(ж). Так, например, если порядки коэффициентов полинома Уилкинсона

Дх) = (х + 1)(х + 2) ...(* + 20) + гж19 (6)

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

пгг{Ф(ж) = 0 | С?(я) + е > 0}.

Соответствующая этой задаче ганкелева матрица Н{е) из §1.3 имеет определитель равный а ее главные миноры Я, (г) позволяют отделить корни этого полинома применением формулы

пк{^(е) = 0 | а < £ < 6} = У(1, ВД,..., Я„(Ь)) - У(1, Нх(а),..., Нп(а)).

При таком подходе само каноническое представление полинома !F(e) оказывается ненужным. В качестве иллюстрации получены оценки для примера (6): число вещественных корней не меняется при —1.3508 х Ю-10 < е < 1.4213 х Ю-10 и уменьшается по крайней мерс на два при выходе е за пределы этого интервала хотя бы на величину Ю-14.

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

В §1.5 предлагается еще один подход к решению задачи о взаимном расположении нулей полиномов, условно названный "методом Везу". Метод сводит вычисление И(/,д) к нахождению определителя матрицы, составленной из коэффициентов остатков от деления д(х)хк (к = 0,... ,deg/ — 1) на f(x). Устанавливается связь метода Везу с результатами параграфов 1.2 и 1.3.

Сведение вычисления числа

nrz{/(x) = 0 | 91(х) > 0,... ,дК(х) > 0}

при К > 1 к случаю К = 1 возможно с помощью приведенной в §1.С формулы А.А.Маркова (мл.).

Целью второй главы является разработка метода Эрмита для задачи многомерной локализации. Необходимость в таком исследовании продиктована тем, что ни Эрмитом, ни его последователями не был произведен анализ условий, при которых метод может быть использован (самим Эрмитом метод был представлен лишь для случая L = 2,ni = п2 = 2).

Теоретической основой метода служит определение многомерного результанта по Пуассону (§2.1). Для полиномов /i(X),... ,fi{X),g{X) общего положения результант вводится рекурсивно по L. Разложим fj(X) по убывающим степеням переменных:

fj(X)=fjni(X)+fjni.1(X) + ... + fj0 (j = !,...,!). (7)

Здесь 1,к{Х) — форма степени к. Если вычисленный по индуктивному предположению (Ь - 1)-мерный результант старших форм /¿„ДX)

Ао '■= ЩЛП1 ■ • •,,1),..., /ь„£ (а?1,..., Х£_1,1)) (8)

отличен от нуля, то система (1) имеет в точности N = гн • • ■ пь нулей Л* 6 С1. В этом случае Ь—мерный результант вводится формулой

К(/ь где := д(А1) ■ ■ ■ д(А„). (9)

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

Для конструктивного вычисления результанта в главе разрабатываются два детерминантных способа. Первый заключается в построении подходящей блочно-ганкелевой матрицы и основан на нахождении многомерного логарифмического вычета по методу Якоби. На основании индукционного предположения можно построить (Ь — 1)—мерные результанты

■•= ъХ1..........мх),..., д(X)), и = 1,..., ь)

(называемые элиминантами) и найти полиномы М]к{Х), задающие их линейные представления

Мц(Х)МХ) + • • • + М3ь(Х)Ь{Х) =

Обозначим "^(Х) [ЛЛ^-Х)]^^ и ЛХ) — якобиан Д,...,//,. Составим

разложение

Ь оо

vw/Е ¿п.....ьъ*-1-*?1--1 ■ (Ю)

¿=1 31.....31,

Домножив его на полином д(Х), получим новое разложение:

Ь со

д(Х)-У(Х)/ЦХ^) = £0(Х) + £ сА.....^Г*"1-*!"-1- (И)

3=1 31,--;31.

По построению, коэффициенты этого разложения рационально выражаются через коэффициенты полиномов /1,..., /х, и д. С другой стороны, они дают значения некоторых симметрических рациональных функций нулей системы (1):

<=л.....и = Е ''' аЦ (здесь Ак := (ак1,... акь)).

Следовательно, посредством формулы (И) значение произвольного симметрического полинома (или рациональной функции) на решениях системы (1) вычисляется как рациональная функция коэффициентов полиномов Д,____

Подберем теперь произвольную систему из N мономов

М:={Ф1(Х),...,ФМХ)} (12)

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

У ■= [г/1, • • •, Улг]' €

Л 5(М

ЙЛЛ,-)

n

Е у»фр(Л»

г>=1

= У*-С-У. (13)

Удалось установить, что по индексам инерции матрицы этой квадратичной формы при подходящем выборе полинома д(Х) можно получить полную информацию о решениях системы (1): найти и число вещественных из них, и число тех из них. что удовлетворяют системе неравенств (2), и, наконец, число тех из них, что являются нулями полинома д(Х).

Параграфы 2.2 — 2.6 посвящены различным способам выбора множества (12), нахождения значений симметрических функций решений и вычисления индексов инерции для матрицы квадратичной формы (13). В частности, показано, что в качестве множества (12) можно взять

М := := {*Г • • ■ | 0 < Р] < пу}. (14)

При упорядочении мономов этого множества в обратном лексикографическом порядке XI У х2 У ... У Х[, матрица С этой квадратичной формы становится блочно-ганкелевой. Так, например, для Ь = 2:

С := [Ср+/]^~о , где С, := [с^+к]^.

Наряду с матрицей С будем рассматривать еще три матрицы аналогичной структуры: £>,5 и II. Матрица В строится из коэффициентов разложения (10). Элементами матриц Б и Н являются соответственно выражения

N.. N..

:= Е «и' ■ ■ °И 11 К.....и := Е 5(Л*К'1 •'' пкь

к= 1 4=1

2

(вычисляются как коэффициенты разложения (11) при замене на ^Г(Х) или на g(X)J(X) соответственно). Для задачи локализации нулей системы (1) матрицы S,H и С играют ту же роль, что и матрицы (4) в одномерном случае.

Теорема 2 . Справедливы равенства

detC = 1lgx(fl>...,h)detD, det S = Их (/i, • • •, /l) det D , (15) dettf =7^(/b...,/£)detS; (16)

и при det D ф 0:

N - rank С = nrz{(l) | g{X) = 0}, nrz{(l )} = jP(1,51,...,5n)-K(1,51,...,5n), nrz{(l) | g(X) >0} = P(1,H1,...,HN)-V(1,S1,...,SN). (17)

Здесь P uV — числа знакопостоянств и знакоперемен в последовательностях главных миноров соответствующих матриц.

В диссертационной работе впервые удалось детализировать структуру условия det Z? ф 0 теоремы 2. Оказалось, что это условие формирует ограничения не на все коэффициенты полиномов /ь..., Д, а только лишь на коэффициенты старших форм в разложениях (7):

det £> = il/-4S1+~+nt-b+1.

Здесь fi означает произведение — L полиномов, представляющих собой

определенные миноры детерминантного представления результанта (8). Условие Ао Ф 0 оказывается ключевым в том смысле, что при его выполнении всегда можно подобрать систему из N мономов (12), чтобы соответствующая матрица D была неособенной. Так, например, для L = 2 и п2 > пг можно взять

Ml := {zf xf I 0 <P! <пи0<р2 < m + n2 -2pi -2}. (18)

Тогда

det Я := (-1Г(г')-1,/2[7г1(Л)---7гп1.1(Л)]2/^1+пг-1,

где Ao ■= Щ/1>я, (гь 1),/2,п2(®ь 1)> a fLj(Ao) — его j—R субрезультант. Теорема 2 останется справедливой при условии

АофО,П1{Ао)фО,...,Пп^1(Ао)ф ¿0. (19)

Здесь аП1 о обозначает коэффициент при х"1 в /1(3:1,ха).

В случае, когда гапкС = N—1, единственный общий нуль полиномов /¡,... и д может быть выражен рационально через их коэффициенты. Составим для этой цели матрицу С(1) той же структуры, что и матрица С, из элементов

сл+1.....- ¿су,.....у^ (т.е. коэффициентов разложения (11) при замене д(Х) на

д(Х)(х1 — ¿)). Коэффициенты при X составляют матрицу (—С), где С определена (13). Разложим (Лг — 1)-й главный минор матрицы С{1) по степеням I:

= (-1)к-1 (с^-!^-1 + 0 + ...).

Теорема 3 . Если Скт — 0,Слг-1 ф 0, то хх-компонента единственного общего нуля полиномов /1(Х),... ,/ь(Х) и д(Х) может быть найдена по формуле:

X! = зцо.....о + 0/Слг-1- (20)

Аналогично можно найти и другие компоненты общего нуля. Теоремы 2 и 3 составляют основу процесса локализации нулей системы (1). Так, при выборе д(Х) := J(X)(xl -Х^-^хь-Хь) получаем зависящую от параметров . матрицу 1,..., ¿¿), главные миноры Су которой играют роль системы полиномов Штурма для системы уравнений (1): для произвольного параллелипипеда в К1, число

пгг{(1) | а1 < XI < 6Ь... ,аь < < Ь^} '

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

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

В §2.7 обсуждается еще один способ построения результанта, являющийся конструктивным развитием метода Безу из §1.5.

Определение. Назовем полином Ь(Х) 6 Ср(] редуцированным относительно системы мономов (14), если он может быть представлен в виде линейной комбинации (с коэффициентами из С) мономов из множества М, заданного (14). Говорит, что полином И(Х) 6 С[Х] редуцируем по модулю /1,..., если существуют полиномы аи...,аъ из С[Х] такие, что полином

Ке*{Х) = ЦХ) - а,(Х)/:(Х) - ... - а^Х)/£ (X) является редуцированным относительно М. Будем обозначать этот факт:

Л(Х) -Vм

Алгоритм редукции можно рассматривать как многомерный аналог процесса деления полиномов от одной переменной. Предположим, что для любого к = произведение • д{Х) редуцируемо по модулю /1,..., /1 относи-

тельном: т.е. существуют полиномы аы(Х),... ,акь(Х)

и константы 6*1,..., такие, что

ЫХЫХ) = ак1{Х)Г1{Х) + ... + акЬ{Х)ЫХ) + дк(Х),

дн{Х) := Ък1ЩХ) + ... + ЬкцЪы{Х). (21) Составленную из коэффициентов представлений (21) матрицу

В = [&Х=1 (22) Лоран назвал матрицей Безу и доказал что

¿еЬВ = П%(/1,...,Л). (23)

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

Теорема 4 . Если матрицу (22) можно построить, то имеют место равенства:

N - гапкВ = пгг{(1) | д(Х) = 0},

В-£> = С. (24)

Кроме того, если с1е1 В = 0 и хотя бы одно из алгебраических дополнений Вд^-к элементам последней строки сЫ В отлично от нуля, то для единственного общего нуля А полиномов Л,... ,/ь и 9 выполняется отношение:

4*1 (А): Ф2(Л): ... : Ф*(Л) = ... : В^. (25)

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

строить для полшгомов J{X) или ${Х)д{Х)). Расчеты примеров показали, что матрица В строится быстрее матрицы С.

Предложенный Лораном алгоритм редукции оказался ошибочным. В §2.8 предлагается новый конструктивный алгоритм редукции и анализируются условия его применимости.

Алгоритм редукции для двух переменных заключается в решении последовательности линейных систем с коэффициентами, рационально зависящими от коэффициентов старших форм /1„, и /2„3. Для случая щ = п2 = 5 алгоритм формализуется с помощью следующей диаграммы:

Здесь скобки { } обозначают линейную систему относительно содержащихся в них мономов, тогда как ■—>■ обозначает умножение редукций, полученных на предыдущем шаге на х2 и хь Если мономы степени 5 + к — 1 редуцируемы и линейная система относительно х*, х\х2 совместна, то все мономы степени 8 + к редуцируемы. Следовательно, для полной редуцируемости в случае щ — пг необходимо и достаточно, чтобы щ соответствующих определителей были отличны от нуля.

В случае п2 > щ схема домножения остается прежней, но предварительно производится "подтягивание" меньшей степени до большей: из равенств

рекурсивно получаем редукции мономов

Алгоритм редукции для Ь > 2 переменных заключается в решении последовательности линейных систем с коэффициентами, рационально зависящими от коэффициентов старших форм /ц,..., /ы полиномов системы (1). Этот процесс можно формализовать с помощью следующей диаграммы:

х^х^/1(х1,х2) = 0, (к] =0,1,2,...; к1 + к2<п2-п1)

0 < ¿её Ф < 5 - 1

х^Ф(хь х3,. ..,Х1) 5- 1 <<^Ф <25-2

4

4 4

... ,хк.ихк+1, ...,хь)

4

26 - 2 < с^ Ф < 35 - 3 Ф € М

(5-1)

< deg Ф < (<(¿-1) Феи

(5-1)

4

(¿-2)({-1) < degФ < (¿-1)(5-1)

Ф е М

(5-1)

Здесь скобки ( ) обозначают конечную последовательность линейных систем, будем называть ее каскадом; индекс при скобках обозначает число систем в каскаде. Так, например, первый из указанных каскадов имеет вид

1 <3<Ъ

хь

^ 5 - ,

ь I хьхз, 1<3<Ь ) ( х[х^хк, 1 <j,k<L )1с1

х^х^хк, 1 < 3,к < Ь

,

,

12

Х1 1

.72 + Уз + • - - + Зь - 5 - 1

т-"

' х1-!х1> 31 + ■ • • + зь-1 = 5-1

(26)

Здесь скобки { } обозначают линейную систему относительно содержащихся в них мономов, индекс при скобках обозначает число мономов, которое для системы

deg Ф = ц ф е м

(27)

оказывается равным

(ь - к +1) 2 — + С^С^.

1+^-2-2$

Так, самая последняя система диаграммы составлена относительно всего лишь двух мономов:

5-1 „5-1 „5 ,.5-1 „ „.5-15-15

х1 ~'' хь-гхь-\хь 11 Х1 " ' хь-гхь~\хь-

Если мономы степени 5+^ — 1 редуцируемы относительно М и линейная система (27) относительно указанных мономов степени 5 4 ц совместна, то все мономы степени 6 + р редуцируемы. Переход от системы (27) к следующей в последовательности (обозначен <->) осуществляется умножением редукций, полученных на предыдущем шаге, на переменные хесли новая система содержится в том же каскаде, и на переменные хк+1,...,х[„ если она оказывается первой в следующем каскаде. Следовательно, для полной редуцируемости достаточно выполнения (Ь— 1)(5 — 1) + 1 условий.

Оказывается, что условия редуцируемости практически совпадают с условием применения теоремы 2. Именно, ключевым снова является необращение в нуль результанта (8), при выполнении этого условия всегда можно подобрать систему мономов (12), альтернативную системе (14), относительно которой любой полином д(Х) может быть редуцирован. Так, например, для 1 = 2 получаем следующий критерий.

Теорема 5 . Для редуцируемости любого полинома д{хх, х2) € С[х1,г2] по модулю /ь/г относительно системы (18) необходимо и достаточно выполнения неравенств (19).

В §2.9 устанавливается связь метода вычисления результанта как определителя матрицы Безу с детерминантным методом Маколея. Показано, что при подходящем выборе множества мономов М матрица (22) может быть получена в результате применения гауссовского алгоритма исключения к матрице Маколея. Для случая £ > 2 первые <5 условий редуцируемости, генерируемые последовательностью (26), могут быть переформулированы в терминах вложенных миноров матрицы Маколея, сформированной из коэффициентов старших форм /и, ■ ■ ■ > /¿5 для нахождения результанта Д), определенного формулой (8).

В §2.10 производится сравнение метода Безу с методом, основанном на построении базисов Грёбнера, широко используемом в последние десятилетия для исследования полиномиальных систем. Вычислим сначала базис Грёбнера ОВ(Х) идеала ... ,/ь{Х)) относительно произвольного упорядочения мономов.

Обозначим через 1шЦС?В) множество всех старших мономов полиномов из В качестве базиса факторкольца с[Х]/2 возьмем множество

Ф(Х) не делится | ^

па мономы из 1шк(С#)

Если это множество конечно (т.е. идеал нульмерен) и содержит /V* элементов: М= (Ф^Х) = 1,... то система (1) имеет в точности N* нулей Ль... (с учетом их кратностей).

Для любого полинома € можно тогда вычислить его нормальную форму относительно ОВ{Х), т.е., по определению, единственный полином Кы{Х) из линейной оболочки множества (28), такой что И(Х) — К^Х) 6 X.

Фактически это определение соответствует приведенному ранее определению редукции ЦХ) по модулю /ь... ,/ь, а алгоритмам редуцируемости можно поставить в соответствие конструирование 5-полиномов из алгоритма Бух-бергера. Отличие метода, изложеннного в параграфах 2.7 и 2.8 заключается в априорном предположении о структуре базиса (28). Именно: этот базис предполагается совпадающим со множеством М, определяемым формулой (14). Такое предположение корректно: его истинность устанавливается не по полному множеству коэффициентов полиномов, а лишь по подмножеству, содержащему коэффициенты старших форм Так, например, ключевое условие редуцируемости — отличие ог нуля выражения (8) — может быть сведено к проверке включения: 1 € 1(/1п1(х1,.. .,11-1,1),. ■■)/тЛхи---,^-1,1)); т.е. приводит к анализу идеала от меньшего числа переменных. Для полиномов общего положения это предположение будет выполнено, равно как и остальные предположения, достаточные для редуцируемости.

С другой стороны, теория базисов Грёбнера дает возможность распространения метода параграфа 2.7 на случай, когда число решений ЛГ* системы (1) оказывается меньшим числа N = «1... пЕсли сформировать матрицу В из коэффициентов нормальных форм произведений Ф*(Х)-д{Х) при к = 1,..., М", то она будет обладать теми же свойствами, что и матрица (22). В-частности, будет справедлив аналог равенства (23):

ск^В = д(А. ¡)...5(Л^.).

Привлекательность возможности распространения метода параграфа 2.7 связана с задачей исключения переменых в системе (1), т.е. приведения ее к виду (3). Хотя для радикального нульмерного идеала общего положения эта задача и может быть решена построением базиса Грёбнера относительно лексикографического упорядочения мономов х\ >~ х2 >-•••>- но реальные расчеты показали, что эта процедура, как правило, весьма дорогостоящая. В ряде исследований последних лет эта трудность обходится посредством предварительного построения базиса идеала Т относительно других способов упорядочения, например, линейного по полной степени.

Тот же прием применяется и в диссертационном исследовании с единственным отличием, что вместо базиса идеала I(/i,..., }l-i,Íl) относительно переменных xi,... предлагается вычислять базис идеала Z(/i,... ,/l-i) относительно затем элиминанту по x¿ строить как определитель матрицы Везу:

Xl(xl) = I.....л-i).

Преимущество этой модификации заключается в уменьшении числа полиномов и переменных, для которых необходимо вычислять базис Грёбнера. Недостаток — в том, что при построении множества (28) приходится учитывать возможную зависимость алгоритма построения базиса Грёбнера от переменной (параметра) xi: при некоторых её значениях может, например, произойти понижение числа общих нулей полиномов fi,...,fb-i- Положительные и отрицательные аспекты предложенного алгоритма иллюстрируются на примерах систем, в-частности тех, что служат общепризнанными тестами качества программных продуктов, разработанных на основе техники базисов Грёбнера. Даются времена счета всех этих примеров в сравнении со стандартными пакетами из системы компьютерной алгебры Maple V (Release 4 и Release 5), а также из специализированных пакетов для исследования полиномиальных систем Risa и FGB.

В приложении каждого из рассмотренных в главе методов вычисления многомерных результантов указаны способы построения системы (3), эквивалентной (1). Обладая представлением (3), мы можем свести задачу локализации к одномерной — относительно корней полинома Xl(xl). Такая возможность обсуждается в §2.11; там же анализируется условие приводимости системы к виду (3) (для случая L = 2). Однако если исходной задачей ставится именно локализация нулей системы, то не имеет смысла разделять две процедуры — исключение и отделение. Так, для метода Эрмита различие в методах исключения и отделения заключается лишь в выборе полинома условия: д(Х) или g(X)J(X); а метод исключения, основанный на соотношении (25) можно легко преобразовать в алгоритм отделения посредством равенства (24). С вычислительной точки зрения дополнительные затраты незначительны и полностью оправдываются существенностью получаемой информации. Трудности могут возникнуть при решении систем, не удовлетворяющих условиям редуцируемос-ти из §2.8. При использовании результатов из §2.10 приходится учитывать возможность вычисления базиса Грёбнера относительно упорядочения по полной степени в конкретной системе аналитических вычислений. Идея исключения может тогда быть использована для исключения в системе части переменных. Это иллюстрируется на решении системы уравнений, описывающей возможные

положения "параллельного робота", т.е. плоской многоугольной платформы, при фиксированных длинах опор и их точек крепления на земле и на платформе (Ь — 8> 2, общее число решений Ы* — 40, из них 24 вещественных).

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

1. Конечной целью алгоритма локализации нулей полиномиальной системы (1) следует считать построение блочно-ганкелевой матрицы Н из теоремы 2. Для задачи исследования зависимости структуры множества решений от параметров не следует находить каноническое разложение для <1е1 Н как полинома по этим параметрам; проще разбить параметрическое пространство "сеткой", получаемой вычислением определителя при частных значениях этих параметров, тем более, что этот процесс легко распараллеливается.

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

3. При построении матрицы Безу не стоит предварительно проверять условия выполнимости процедуры редукции поскольку, во-первых, они проявляются непосредственно в ходе алгоритма, а во-вторых, будут выполненными "с вероятностью 1". В критическом же случае (внешним признаком которого может служить, например, разреженность старших форм в разложениях (7)) стоит использовать предварительное построение базиса Грёбнера для линейного упорядочения мономов по полной степени.

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

Первая из решаемых задач — установление коэффициентных критериев знакоопределенности формы Гт(Х) произвольной степени. Практическое значение

этой задачи достаточно велико: она важна в теориях оптимизации, устойчивости и управления. С помощью результатов главы 2 в §3.1 приведен конструктивный алгоритм получения этих условий. Форма ^(а^,...,ж^-ьбудет положительно определенной тогда и только тогда, когда положительно определена форма Рт(х1,.. .,££,_!,<)), и полином := /^(21,... 1) положителен на всех вещественных нулях системы

дрЫ/дХ1 = 0,..., = 0. (29)

Последнее условие эквивалентно

пгг{(29)} = птг{(29) | > 0}

и может быть проверено с помощью теоремы 2; при этом оказывается, что условия знакоопределенности формы Рт(хх,...,аг£,_1,0) гарантируют выполнение условий теоремы 2 применительно к системе (29). Получающийся рекурсивный по числу переменных алгоритм оказывается чисто алгебраическим.

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

чп -=ПХ1.....= (30)

Имеется в виду, что при непрерывном изменении параметров нарушение свойства положительной определенности может произойти только при пересечении поверхности (30). Это обстоятельство часто позволяет уменьшить количество условий, существенных для положительной определенности. Так, например, для формы

-Е)(:Г1, х2, х3) - х^ + х* + З3+ (х\х2х3 г]ххх\х3 эти условия сводятся к двум неравенствам:

А + В- 64 < 0, 21б(Л + В - 64)4 - АВ[{А + В- 512)3 -- (А + В + 256)((А + В - 93056)2 - 27АВ - 8755167232)] > 0.

Здесь А := С4, В := Т)А-

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

Параграф 3.3 посвящен задаче поиска абсолютного и условного максимума полинома. Эта задача достаточно хорошо изучена в случае линейных ограничений или когда целевая функция (квази-)выиукла. В диссертации задача рассматривается в общей постановке. Если разложение целевой функции по убывающим степеням переменных

Р(Х) = Рт(Х) + Д^Х) + • • • + РЬ

начинается с отрицательно определенной формы Рт (это свойство проверяется методами из §3.1), то традиционный поиск абсолютного максимума сводится к исследованию стационарных точек, т.е. нулей Л,- системы

дР/дх1=0,...,дР/дхь = 0. (31)

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

Яг) := К$Х)-(дР/дх1,...,дР/дх1.) = ^(Л,) - г)... №*) - г).

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

задачу определения

пгг{(31) | Р(Х) — г > 0}.

Воспользуемся теоремой 2. Соответствующая блочно-ганкелевая матрица Н(г) имеет определитель, с точностью до множителя совпадающий с Т{г) (формула (16)); упомянутый множитель может обратиться в нуль только при наличии кратных стационарных точек у /^А") (вторая из формул (15)). При отсутствии таких точек можно воспользоваться равенством (17) для отделения критических значений, при этом оказывается, что условие теоремы 0 ф 0 гарантируется знакоопределенностью формы Рт.

Теорема в . Если не имеет кратных корней (Т>(^) ф 0), то имеет место равенство

тг {(31) | а < Р(Х) < Ь} = пгъ{Т{г) = 0|а<г<Ь} =

= У{1,ЩЬ),Яаг(Ь)) - 7(1, Я!(а),..., Нм(а)). (32)

Здесь N = (ш - 1)£.

Иными словами: последовательность главных миноров #1(2)1 ■■■ ■> H^(z) матрицы H(z) играет роль системы полиномов Штурма для T(z). Локализовав с ее помощью максимальный корень, т.е. maxF(X), и вычислив затем его значение (приближенно или точно), мы сможем восстановить координаты соответствующей стационарной точки как рациональные функции от этого значения — с помощью формул вида (20). Таким образом, предлагаемый подход к задаче оптимизации является обращением традиционной схемы стационарные точки —> критические значения; этот подход не требует традиционных для проблемы нелинейной оптимизации предположений типа выпуклости. Заметим, что явное построение !F(z), т.е. нахождение коэффициентов этого полинома, вовсе не является необходимым для локализации его корней. Для этой цели достаточно его представления в виде определителя матрицы Н. Подстановка в этот определитель числового значения z = а позволяет по знакам числовых миноров однозначно установить число корней слева и справа от этого значения.

Дополнительного исследования требует случай, когда у полинома 7{z) имеется кратный вещественный корень. Здесь возможна ситуация, когда max.F(X) не будет совпадать с максимальным вещественным корнем T(z), как это происходит, например, для

F(xь х2) ■■= —2х\ - - Ах\х\ - - 4 + ххх2 - ^Xj.

Соответствующий полином !F{z) имеет разложение

F(z) = z(z - 11/48)2(г - 1/3)2{z - 11/32)4,

но его корни г = 11/32 и г = 1/3 отвечают невещественным стационарным точкам и не дают значения шах F (в этом примере maxF = ^(±1, Т^/2) = 11/48). Использование формулы (32) для локализации критических значений дает то преимущество, что при расчетах происходит игнорирование таких "лишних" критических значений (соответствующих невещественным стационарным точкам). С другой стороны, формула (32) дает верное заключение о числе вещественных стационарных точек, в которых F(X) принимает одинаковые значения.

Для L = 1 условие существования таких точек дается следующей теоремой.

Теорема 7 . Для F{x) = А0хт + • • • + Ат имеем

V(T{z)) = Т[1>(Г)]3Фа(Лв>..., Am_i)

Здесь Т — константа, зависящая от т, а Ф — форма степени 3(m-2)(m-3)/2. Установлено, что Ф = 1 для т = 3, Ф = H(F', F'")/А0 для т = 4, и Ф = Т>(5[F'"]2 - 6F'F^)/Al~m для тп= 5, 6.

Задача поиска тах Р(Х) в области, описываемой полиномиальным неравенством £?(Х) > 0, решается в той же идеологии. Она разбивается на две подзадачи: локализации максимума г> целевой функции внутри области:

пгг{(31) | > г1в(Х) > 0} (33)

и локализации условного максимума г= на границе области:

^ =°их) > *} ■ (34)

Применение теоремы 2 и формулы Маркова позволяет построить полиномиальные по г системы для нахождения этих чисел.

Числа (33) и (34) не являются взаимно независимыми. Так, при I = 2 и в предположении, что кривая С(х1,х2) = 0 состоит только из одного овала, они связаны между собой соотношением

пгг{(31) | в > 0,Н(Р) >0}-пг2{(31) \в >0,Н(Г) <0} =

= 1 + *(пк{ в{хи х,) = о, ЛО, = о I ллв, Р),Г)> о }--пи{с(®1,®я) = о, лс,р) = о I лла,р),р)<о}),

вытекающим из теории индекса Кронекера-Пуанкаре (§3.2). 'Здесь 3 — якобиан, Н — гессиан, а первое слагаемое в левой части равенства дает число точек локального экстремума Р(х1,х2) внутри области С(х1,х2) > 0.

Аналогично исследуется и задача поиска тах F в области, заданной системой полиномиальных неравенств. Отметим, что предложенный алгоритм не требует предварительной проверки этой области на непустоту. Но при необходимости задача о совместности системы неравенств (2) и локализации ее множества решений 3 может быть решена применением метода Эрмита. Для случая Ь = 1 и Ь = 2 такая возможность иллюстрируется в §3.4. Для случая Ь — 1 множество § является объединением составляющих интервалов, границами которых служат корни полиномов системы. С помощью результатов главы 1 можно вычислить

ПГ2; := агг{д,- = 0 | д1 > 0,..., д^ > 0, > 0,... ,дк > 0}, ПГ2;,Ь,6[ = 0 | дх > 0,..., д^ > 0, д,^ > 0,...,дк > 0, о < х < Ь},

причем в §3.4 показано, как оптимально организовать подсчет второго числа, имея расчеты для первого. Тогда в развитие результата Мезерва получаем

Теорема 8 . Если Щд^дк) ф 0 для всех \ <}< к < К и Т>{д3) ф 0 для всех 1 < ] < К, то для совместности системы (2) необходимо и достаточно выполнения хотя бы одного из следующих условий:

a) <7,(0) >0,...,дК(О) >0;

b) существует индекс ] € {1,..., К} такой, что пгг^- > 0. В этом случае общее число интервалов, составляющих §, равно | (х^^шт;.,-+/), где

П:

если + оо ^ —оо ^ 3; / = 1, если только одна из + оо,—со принадлежит : если + оо € 5, -оо € §,

а число составляющих интервалов, лежащих внутри заданного интервала ]а, 6[ (а & §, Ь £ В, а ф -оо, Ь ф 4оо), равно \ пгг.,',]„,{,[.

В случае Ь = 2 исследование множества решений системы (2) общего положения на ограниченность сводится к одномерному случаю. Если д1Ш1 означает старшую форму в разложении д^(х, у), то для ограниченности достаточно, чтобы система неравенств

дш^хи 1) > 0,... ,дктк(х1,1) > 0

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

д2(хьг2) > 0,...,дк(х1,х7) > 0,

был положителен. А для решения этой задачи можно воспользоваться алгоритмом параграфа 3.3. Также, как и для одномерного случая, показано, как организовать из расчетов, произведенных для установления непустоты множества §, расчеты для локализации точек этого множества, т.е. для вычисления полиномиальной последовательности от параметров и ¿2, позволяющей установить наличие решений системы в произвольном прямоугольнике в а3. Использование метода Эрмита имеет и го преимущество, что детализирует и структуру границы множества §. Например, в развитие результата И.Г.Петровского приходим к следующему критерию.

Теорема 9 . При отрицательной определенности формы gimi(xi, х2), разность между числом положительных и числом отрицательных овалов кривой gi(xi,x2) = 0 равна

(сг(Я.) + <т{И„))/2.

Здесь а обозначает сигнатуру матриц Н. и Н„ из теоремы 2, составленных для системы dgxjdxi = 0, dgtJdx2 = 0 и для полиномов условий д{хх,х2) := gi{xux2) и д(хi,x2) := gi(zi, x2)H(gi) соответственно.

Параграф 3.5 посвящен двум задачам теории устойчивости. Первая из них касается обобщения свойства устойчивости полинома /(г) Е Дф], когда для последнего требуется указать критерий нахождения всех его корней внутри произвольной области комплексной плоскости г = х + iy, описываемой полиномиальным неравенством д[х,у2) > 0.

Задача решается сведением к вещественному случаю в к2:

f{z) = F1{x,Y) + iyF3(xJY)

где Y -у2, и

Систему уравнений Fi(x,Y) = Y) — 0 методами главы 2 можно свести

к эквивалентной

Х(х) := nY{Fu F,) = 0, Y - 8{х) = 0 в предположении Т>(Х) ф 0.

Теорема 10 . Если V{X) ф 0, то полином f(z) имеет в точности

nrz{/(a;) =0 | д(х,0) > 0} + пггСЛ'Сх) = 0 | д{х,9{х)) > 0,0(х) < 0}

корней внутри области д(х,у2) > 0.

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

Теорема 11 . Для того чтобы все корни полинома f(z) лежали в области д(х,у2) < 0 достаточно, чтобы у каждого полинома

<Px{z) :=Яг(/(х),г-$(*,0)) (г) := Y), F2{x, У), г — g{x, У))

знаки коэффициентов были одинаковыми.

Для некоторых классов областей это условие оказывается и необходимым.

Теорема 12 . Для того чтобы все корни полинома f(z) лежали в области х + у2 < 0, необходимо и достаточно, чтобы все коэффициенты /(г) были одного знака, и все коэффициенты y>2{z) := Hy(Fi(z + У, Y),F2(z -f Y, Y)) были одного знака.

Вторая задача, рассматриваемая в §3.5, касается устойчивости нулевого решения системы дифференциальных уравнений

dXj/dt=Fj{X) + ... (j = l,...,L) (35)

(в дальнейшем будем говорить просто об устойчивости системы) в критическом по Ляпунову случае полного вырождения линейного приближения. Правые части системы (35) представляют собой функции, аналитические в окрестности начала координат, разложение которых начинается с форм Fj(X) степени п > 1. Требуется найти условия устойчивости в терминах коэффициентов этих форм. В случае существования одномерного инвариантного многообразия, проходящего через начало координат, т.е. нетривиальных вещественных нулей у системы полиномиальных уравнений

F,k(X) xkF,(X) - x,Fk(X) = 0 (se{l,...,L}\{k}) (36)

эти условия были сформулированы Г.В.Каменковым: для асимптотической устойчивости системы (35) необходимо, чтобы на всех этих решениях полином

xiF1(X) + — +XlFl{X)

был отрицателен; при L = 2 это условие оказывается и достаточным.

С помощью результатов глав 1 и 2 условия этого критерия проверяются чисто алгебраически. Для L = 2,п = 3 эти условия удалось развить и на случай, когда система (36) не имеет нетривиального вещественного нуля. Установлено, например, что для системы

dxijdt = апх\ai2x\, dx2/dt = а2\х\-\-а22х\ (37)

асимптотическая устойчивость имеет место при ац < 0, «22 < 0 или при ац < 0,022 > 0, а^аде + в22а21 > 0.

В работе был произведен сравнительный анализ изложенного выше способа исследования устойчивости с тем, что основан на поиске функций Ляпунова. Теорема Красовского-Зубова гарантирует существование однородной функции У(Х), решающей задачу об устойчивости системы (35). В диссертации исследовалась возможность выбора У(А') в более узком классе — среди однородных полиномов, т.е. форм (перспектива от их использования казалась тем более привлекательной, что алгоритмы из §3.1 дают возможость проверки знакоопределенности этих форм). Результат, однако, оказался негативным уже для случая Ь-2,п = Ъ.

Теорема 13 . Для любого наперед заданного натурального М существует асимптотически устойчивая система (37) такая, что производная любой формы У^ь^г) степени М в силу этой системы

Г1(х1,х 2)дУ(х1,х2)/дх1 + Г2(х1,х3)ду(х1,х2)/дх2 не будет отрицательно определенной функцией.

Такая система получается при подходящем выборе параметров а и е в семействе

ац = а — Е,в1з = —1, а21 = 1,а22 = — а, где 0<£<а<1 (38)

(например, при а — 1/2,е = 1/4 не существует функции Ляпунова в виде квадратичной формы). Идея доказательства основывается на том факте, что полиномиальные интегралы заданной степени М для семейства (38) при е = О существуют лишь для конечного числа значений параметра а.

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

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

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

3. Дано конструктивное развитие метода Безу построения многомерного результанта; на его основе создана схема исключения переменных; проанализированы связи с известными методами исключения, в том числе использующими технику базисов Грёбнера.

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

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

6. Установлены критерии устойчивости систем обыкновенных дифференциальных уравнений в критическом по Ляпунову случае полного вырождения матрицы линейного приближения. Доказана невозможность установления свойства устойчивости выбором функций Ляпунова в классе полиномов. Для полиномиальных векторных полей конструктивно показана чисто алгебраическая разрешимость задачи вычисления индекса Кронекера-Пуанкаре алгебраического многообразия.

7. В обобщение критерия Рауса устойчивости полинома создан алгоритм проверки наличия всех корней полинома в произвольной алгебраической области комплексной плоскости.

Основные публикации по теме диссертации.

1. Утешев А.Ю. Использование однородных форм в качестве функций Ляпунова.// Депон. в ВИНИТИ №2942-В87 Деп.24.04.87, "Вестник ЛГУ, сер.мат." 13 с.

2. Утешев А.Ю., Шуляк С.Г. Критерий асимптотической устойчивости системы двух дифференциальных уравнений с однородными правыми частями.// Дифференц. уравнения. 1987. Т.23. №6. С.1009-1014

3. Утешев А.Ю. Однородные полиномы ¡знакоопределенность и использование в качестве функций Ляпунова.// Тезисы 5-й всесоюзной Четаевской конференции по теории устойчивости. 1987. Казань, С.98

4. Утешев А.Ю. Критерий положительной определенности однородных форм.// Вестник ЛГУ,сер.1. 1988. №1. С.110-112

5. Утешев А.Ю. Необходимые и достаточные условия положительной определенности однородных форм.// В сб. "Вопросы механики и процессов управления", Л. Л ГУ. 1989. №11. С.87-90

6. Утешев А.Ю., Шуляк С.Г. Метод Эрмита отделения решений систем алгебраических уравнений и его применения.// Депон. в ВИНИТИ №6319-В89 Деп.18.10.89, "Вестник ЛГУ,сер. 1" — 42 с.

7. Утешев А.Ю. К вопросу существования полиномиальной функции Ляпунова.// Дифференц. уравнения. 1989. Т.25. №11. С.2010-2013

8. Uteshev A.Yu., Shulyak S.G. Conditions for sign-definiteness of homogeneous forms and possibility of using polynomials as Lyapunov Functions.// Abstracts of the Second Colloquium on Differential Equations, Plovdiv. 1991. P. 298

9. Uteshev A.Yu., Shulyak S.G. Determination of Kronecker-Poincare index of algebraic curve relative to algebraic field on the plane.// Abstracts of the Second Colloquium on Differential Equations, Plovdiv.1991. P. 299

10. Утешев А.Ю. Вычисление индекса Кронекера-Пуанкаре алгебраических кривых относительно алгебраических полей на плоскости.// Дифференц. уравнения. 1991. Т.27. №12. С.2181-2183

11. Uteshev A.Yu., Shulyak S.G. Hermite's method of separation of solutions of systems of algebraic equations and its applications.// Linear Algebra and its Applications. 1992. V. 177. P.49-88

12. Kalinina E.A., Uteshev A.Yu. Determination of the number of roots of a polynomial lying in a given algebraic domain.// Linear Algebra and its Applications. 1993. V. 185. P. 61-81

13. Uteshev A.Yu. On the existence of a polynomial Lyapunov function.// Proceedings of the Int. Conf. on Differential Equations — Equadiff'91, Barcelona. 1993. Singapore, World Scientific. V.2. P. 943-946

14. Uteshev A.Yu., Shulyak S.G., Cherkasov T.M. Hermite's method for separation of solutions of algebraic equations systems and its realization in REDUCE.// Abstracts of the Int. Congress on Computer Systems and Applied Mathematics - CSAM'93. St.-Petersburg, 1993. P. 114

15. Uteshev A.Yu., Shulyak S.G., Cherkasov,T.M. Systems of algebraic inequalities: consistency and structure of the set of solutions.// Abstracts of the Int. Conf. on Interval and Computer-Algebraic Methods in Science and Engineering -Interval'94. St.-Petersburg, 1994. P.237-238

16. Утешев А.Ю., Черкасов T.M. Локализация решений систем алгебраических уравнений и неравенств. Метод Эрмита.// Доклады АН России. 1996. Т.347. №4, С.451-453

17. Bikker P., Uteshev A.Yu. Elimination a. la Bezout. // Extended abstracts of the Int.Conf. Computer Algebra in Scientific Computing - CASC'98. St.-Petersburg, 1998. C.20-21

18. Uteshev A.Yu., Cherkasov T.M. The search for the maximum of a polynomial.// Journal of Symbolic Computation. 1998. V. 25. №5. P.587-618

19. Утешев А.Ю., Черкасов T.M. К задаче полиномиальной оптимизации.// Доклады АН России. 1998. Т. 361. №2. С. 168-170

20. Uteshev A.Yu., Cherkasov T.M. Symbolic algorithms for polynomial optimization problems.// Abstracts of the Int. Conf. Dedicated to the 90th Anniversary of L.S.Pontryagin. Optimal Control. Moscow, 1998. C.197-198

Лицензия ЛР№ 040815 от 22.05.97г.

Подписано к печати 98 г. Формат бумаги 60X90 1/16. Бумага офсетная.

Печать ризографическая. Усл.-печ. л. 2,0. Тираж 100 экз. Заказ 470. Отпечатано в отделе оперативной полиграфии НИИ химии СПбГУ. 198904, Санкт-Петербург, Старый Петергоф, Университетский пр.2.

Список обозначений и сокращений

Введение.

Глава 1. Локализация корней полиномов от одной переменной

§1.1. Вычисление характеристик ганкелевой матрицы

§1.2. Результант и субрезультанты.

§1.3. Ганкелевы матрицы в задаче о расположении корней

§1.4. Отделение корней полинома в отсутствие его канонического представления

§1.5. Метод Безу для случая одной переменной

§1.6. Формула Маркова

Глава 2.Исключение переменных и отделение решений систем полиномиальных уравнений

§2.1. Определение многомерного результанта

§2.2. Отделение решений в случае двух переменных

§2.3. Вычисление симметрических функций решений

§2.4. Метод Эрмита для двух переменных.

§2.5. Результант трех полиномов от двух переменных

§2.6. Метод Эрмита для трех и более переменных

§2.7. Еще один способ вычисления многомерного результанта

§2.8. Редуцируемость

§2.9. Связь с методом Маколея

§2.10. Связь с методом базисов Грёбнера.

§2.11. Отделение решений через предварительное преобразование системы

СПИСОК ОБОЗНАЧЕНИЙ И СОКРАЩЕНИЙ

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

• Р(А\,., Ак) и У(А\, Аг, • • •, А*) — числа постоянств и перемен знаков для последовательности вещественных чисел А\,., А&; Е[А{\ — целая часть числа.

• Значок 1 означает транспонирование.

• а (А), га+(А), Т1(А), Ак для вещественной симметричной матрицы А обозначают соответственно сигнатуру, положительный и отрицательный индексы инерции, и к-й главный минор.

• gcd(/, Х>(/) — наибольший общий делитель, результант и дискриминант полиномов /(ж) и д(х) от одной переменной;

9)1 — к-ый субрезультант и к-ый субдискриминант

§1.2)

• Лх, 72-х, Хз{хэ) — результант,д-результант и элиминанта по ху для полиномов от нескольких переменных

§2.1).

• 3,7-1 — якобиан и гессиан.

• тг {^(Х) = О, .,Д(Х) = 0 | д(Х) >0} — число различных вещественных нулей системы уравнений, удовлетворяющих условию д> 0.

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

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

Здесь X = (xi,. ,xl) G cl, и все указанные полиномы имеют вещественные коэффициенты. Систему (2) будем часто рассматривать и при замене неравенств на строгие: > —> >.

Эта задача имеет долгую историю. Первоначально, проблема получения оценки числа вещественных корней полинома от одной переменной была поставлена, а для некоторых случаев и решена, в трудах великих математиков XVII-XVIII веков: Ньютона, Декарта, Лагранжа, Эйлера, Фурье и Пуассона. Полное решение этой задачи — как и ее обобщений на случаи расположения корней полинома в той или иной области комплексной плоскости — было получено в первой половине XIX века в работах Коши, Штурма, Якоби, Эрмита, Сильвестра и Кэли . Построение Штурмом его знаменитого алгоритма, позволяющего отделить интервалы вещественной оси, содержащие каждый по одному корню рассматриваемого полинома, индуцировало попытки его обобщения на системы полиномиальных уравнений от нескольких переменных. Самыми удачными оказались подходы, предложенные выдающимся французским математиком Эрмитом. В 1852 г. он представил к публикации в журнале Comptes Rendus статью [118], которая, после рецензирования комиссией, состоявшей из Коши, Лиувилля и Штурма, была отклонена в ее полном варианте, и напечатана лишь в виде краткой заметки h(X) = 0,., fL(X) = О (п} := deg /у)

1) gi(X)>0,.,gK(X)>0

2)

- 6

115] (полный же вариант был опубликован лишь в 1905 г., уже после смерти Эрмита). В парадигме того исторического периода развития алгебры ученых интересовали чисто алгебраические (в современной терминологии — символьные или аналитические) алгоритмы решения уравнений и систем уравнений, т.е. такие, которые позволяли решать поставленные задачи за конечное число элементарных алгебраических операций над коэффициентами полиномов. Именно в рамках такой парадигмы и решалась Эрмитом задача определения числа вещественных решений системы (1), лежащих внутри произвольного паралеллепипеда aj < xj (j = 1,. В 1856 г. итальянский математик Бриоски

89], основываясь на заметке Эрмита, обобщил одну из его идей на задачу поиска числа вещественных решений системы (1), удовлетворяющих произвольному полиномиальному неравенству д(Х) > 0. Оба ученых ограничивались случаями L = 2 и (частично) L = 3. В последующем, метод развивался некоторыми учеными [101],[119], и, особенно, Кроне-кером, в связи с его работой над теорией характеристик [72], [144].

В ХХ-м веке метод Эрмита был прочно забыт вплоть до конца 90-х годов С 1989 г. ситуация меняется: появляются работы [56], [58], [79], [111], [149], [152], [160] с историческими обзорами, развитиями метода и его приложениями к конкретным задачам. Возобновление интереса к методу объясняется потребностью в абсолютной достоверности результатов, получаемых в ходе вычислений. Известный пример Уилкинсона [50] (см. §1.4.1) показал, что даже для случая одной переменной корни полинома достаточно чувствительны к возмущениям его коэффициентов, и игнорирование этого обстоятельства при использовании метода Ньютона приводит к неверному заключению о числе вещественных корней.

Проблема достоверности информации, получаемой в ходе вычисле

Citation Index не зарегистрировано ни одной ссылки на отмеченные работы.

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

Известная трудоемкость символьных алгоритмов потребовала достаточного развития вычислительной техники, но после того как это произошло, область науки, известная как "компьютерная алгебра" стала бурно развиваться. Эта область располагается на стыке математики и информатики; интерес к ней научного сообщества выражается в быстро растущем числе публикаций, среди которых укажем только некоторые обзорные монографии [3], [14], [27], [31], [97], [98] и тематические выпуски журнала "Программирование" [39]. Компьютерная алгебра имеет дело, в основном, с точными числами и алгебраическими выражениями в их символьном представлении. В таких ее системах общего назначения как REDUCE, MACSYMA, MATHEMATICA, MAPLE, AXIOM, MuPAD алгоритмический базис составляют операции над полиномами и рациональными функциями, поэтому исследования в этой области включают в себя создание, развитие и анализ эффективности методов факторизации, вычисления наибольших общих делителей, отделения (локализации) вещественных корней полиномов, преобразования систем алгебраических уравнений к наиболее простому виду. Поскольку идеологии решения задач двух алгебр — классической и компьютерной — совпали, интерес современных исследователей к разработке научного наследия XIX века значительно возрос.

Настоящая работа также является отражением этой тенденции. Це

- 8 ли исследования: 1) разработка конструктивных алгоритмов исключения переменных и локализации решений системы (1), и, в частности, построение многомерной системы полиномов Штурма; 2) применение этих алгоритмов к некоторым конкретным задачам. В качестве рабочего аппарата используется такой раздел классической алгебры как теория исключения. Дело в том, что, как правило, возможно преобразование системы (1) к эквивалентной ей (т.е. имеющей тот же набор решений) системе вида xi - $i(xL) = 0,. .,xl-i - = 0, XL{xL) = 0. (3)

Здесь <3>i,., Ф^-! — рациональные функции, a Xi — полином от х^. В случае существования представления (3), решение системы (1) сводится к решению единственного уравнения от одной переменной: Xl(xl) = 0. В классической алгебре были разработаны несколько подходов для нахождения представления (3) (и условий его существования). Практически все они основаны на понятии результанта, т.е. некоторой полиномиальной функции коэффициентов fi(X),., Jl{X), д(Х)

Hx(fi(X)i.JL(X)ig(X))1 (4) обращение которой в нуль необходимо и достаточно для существования общего нуля этих полиномов. Исторически первым был подход Безу-Пуассона [84], [147], его конструктивное развитие также является одной из целей настоящей работы. Состояние теории на начало ХХ-го века дано в обзорах Нетто — в энциклопедии [100] и в его книге [144]. Несколько позже Маколеем [139], [140] в рамках детерминантного подхода был развит метод Кэли [93]; еще один подход, изложенный в книге Перрона [150] имеет скорее теоретическую ценность. С 30-х годов нашего века теорию постигла та же участь забвения, что и метод Эрмита. По меткому замечанию автора исторического обзора [112], теория исключения была практически исключена из современных учебников алгебры

- 9 и алгебраической геометрии. Отечественная же библиография по этому разделу состоит из единственного источника — перевода учебника Серре [46], изданного в прошлом веке 2.

Те же обстоятельства, что возбудили в последние десятилетия интерес к методу Эрмита, возродили и теорию исключения. Так, в работах [127], [128] исследуются методы Диксона [99] и Маколея, в книге [104] развивается метод Кэли. Интерес к теории стимулировало еще и потребность выяснить истоки теории базисов Гребнера [135], создание которой в 70-е годы связано с именем Бухбергера [31], [91]. Хотя предложенный последним алгоритм построения базисов Гребнера и был универсальным, но оказался своего рода "черным ящиком" — когда для конкретной системы (1) практически невозможно было оценить априори время, необходимое для ее приведения к виду (3). Вычислительным аспектам, а также модификациям и приложениям метода посвящены работы [80], [105], [106] ( см. также обзор [31]).

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

ЗАКЛЮЧЕНИЕ

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

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

2. Дано конструктивное развитие метода Безу построения многомерного результанта, на его основе создана схема исключения переменных; проанализированы связи с известными методами исключения (в том числе методом базисов Гребнера).

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

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

5. Разработана техника построения аналитических критериев знакоопределенности полинома, а также совместности системы полиномиальных неравенств; для последней задачи предложен также метод локализации множества ее решений.

6. Для систем обыкновенных дифференциальных уравнений и векторных полей в критическом по Ляпунову случае полного вырожде

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

7. В обобщение критерия Рауса-Гурвица устойчивости полинома создан алгоритм проверки наличия всех корней полинома в произвольной алгебраической области комплексной плоскости.

8. Предложена техника вычисления индекса Кронекера-Пуанкаре для полиномиальных векторных полей и алгебраических многообразий.

Из анализа проведенных теоретических исследований вытекают следующие практические рекомендации

1. Конечной целью алгоритма отделения полиномиальной системы следует считать построение ганкелевой (блочно-ганкелевой) матрицы. При этом в случае исследования зависимости структуры множества решений от параметров, не следует находить каноническое представление определителя как полинома по этим параметрам; проще разбить параметрическое пространство "сеткой", получаемой вычислением определителя при частных значениях этих параметров — тем более, что этот процесс легко распараллелить.

2. Искомую блочно-ганкелевую матрицу в одномерном и двумерном случаях следует строить непосредственно через симметрические функции решений системы. Но уже в случае трех переменных имеет смысл найти предварительно матрицу Безу, т.к. ее элементы вычисляются по более простому алгоритму. Затем известной комбинацией миноров этой матрицы (см. §2.7) можно получить миноры блочно-ганкелевой.

- 258

3. При построении матрицы Безу не стоит предварительно проверять условия выполнимости процедуры редукции из §2.8: во-первых, они проявляются непосредственно в ходе алгоритма, а, во-вторых, будут выполненными "с вероятностью 1". В критическом же случае (внешним признаком которого может служить, например, разреженность старших форм [67]), стоит использовать предварительное построение базиса Гребнера для линейного упорядочения мономов по полной степени.

4. При решении задачи поиска максимума в области, описываемой системой полиномиальных неравенств, не следует проводить предварительного исследования ни системы условий на совместность, ни самой целевой функции на наличие максимума на бесконечности. Предложенный в §3.3 алгоритм позволит проверить второе из этих условий автоматически — в ходе проверки условий применимости метода Эрмита (§§2.4, 2.6) или условий редуцируемости из §2.8. Непустота допустимого множества выяснится в ходе нахождения условного экстремума целевой функции на потенциальных граничных многообразиях этого множества. Проверка условия достижимости максимума в нескольких стационарных точках должна также производиться лишь тогда, когда за достаточное число подстановок не удается отделить критические значения.

- 259

1. Айзенберг J1.A., Болотов В.А., Цих А.К. К решению систем нелинейных алгебраических уравнений с помощью многомерного логарифмического вычета. О разрешимости в радикалах.// Доклады АН СССР. 1980. Т. 252. №1. С.11-14

2. Айзенберг Л. А., Южаков А.П. Интегральные представления и вычеты в многомерном комплексном анализе. Новосибирск. Наука. 1979.

3. Акритас А. Основы компьютерной алгебры с приложениями. М.,Мир,1994, 543 с.

4. Аминов A.B., Сиразетдинов Т.К. Условия знакоопределенности четных форм и устойчивости в целом нелинейных систем.// Прикл. мат. мех. 1984. Т.48, №3, С.339-347

5. Арнольд В.И. Индекс особой точки векторного поля, неравенства Петровского-Олейник и смешанные структуры Ходжа.// Функц.анализ и его приложения. 1978, Т.12, №1, С.3-18

6. Арнольд В.И., Олейник O.A. Топология действительных алгебраических многообразий.// Вестн.МГУ. Сер.1, 1979, №6, С.7-17

7. Барбашин Е.А. Функции Ляпунова. М.,Наука, 1970, 240 с.

8. Белоусов Е.Г., Андропов В.Г. Разрешимость и устойчивость задач полиномиального программирования. М.,МГУ,1993, 272 с.

9. Березин И.С., Жидков Н.П. Методы вычислений.Т.2. ГИФМЛ, 1960, 620 с.

10. Березовская Ф.С. Индекс стационарной точки векторного поля на плоскости.// Функц.анализ и его приложения. 1979, Т.13, №2, С. 23-30- 260

11. Бертсекас Д. Условная минимизация и метод множителей Лагран-жа. М.Радио и связь. 1987, 400 с.

12. Близняков Н.М. Оценки топологического индекса. //В сб. Геометрия и теория особенностей в нелинейных уравнениях. Воронеж. ВГУ. 1987. С.9-23

13. Бохер М. Введение в высшую алгебру. М.-Л., ГТТИ, 1933, 291 с.

14. Быков В.И., Кытманов А.М., Лазман М.З. Методы исключения в компьютерной алгебре многочленов. Новосибирск. Наука, 1991, 233 с.

15. Ван-дер Варден Б.Л. Современная алгебра.Т.2. ОГИЗ, ГИТТЛ, 1947, 260 с.

16. Веретенников В.Г. Устойчивость и колебания нелинейных систем. М.Наука.1984. 320 с.

17. Вейссенберг А.Н. Критерий знакоопределенности форм высшего порядка.// Прикладная матем. и механика. 1974, Т.38, №3, С.571-574

18. Воробьев H.H., Григорьев Д.Ю. Решение систем полиномиальных неравенств над вещественными полями в субэкспоненциальное время. // В кн. Теория сложности вычислений.III. Зап.научн.семин. ЛОМИ. 1988, Т.174, С.3-36

19. Гантмахер Ф.Р. Теория матриц. М. Наука, 1966, 576 с.

20. Гилмор Р. Прикладная теория катастроф. М.Мир, 1984. Т.1 - 350 е., Т.2 - 285 с.

21. Горин Е.А. Об асимптотических свойствах многочленов и алгебраических функций от нескольких переменных.// Успехи мат.наук. Т.16, №1, С. 91-118-261

22. Горушкина Е.А. О знакоопределенности однородного полинома при ограничениях в виде однородых полиномиальных уравнений и неравенств.// Депон. в ВИНИТИ №3786-В90 Деп.09.07.90,"Вестник ЛГУ,сер. 1" 27 с.

23. Григорьев Д.Ю. Разложение многочленов над конечным полем и решение систем алгебраических уравнений. //В кн. Теория сложности вычислений. Зап.научн.семин. ЛОМИ. 1984, Т.137. С.20-79

24. Григорьев Д.Ю., Чистов А.Л. Быстрое разложение многочленов на неприводимые и решение систем алгебраических уравнений.// Доклады АН СССР. 1984, Т.275, №6, С.1302-1306

25. Джури Э. Инноры и устойчивость динамических систем. М.Наука,1979, 299 с.

26. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.Наука,1966, 664 с.

27. Дэвенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. М.Мир,1991, 350 с.

28. Зубов В.И. Устойчивость движения. М.Высшая школа, 1984, 232 с.

29. Иохвидов И.С. Ганкелевы и теплицевы матрицы и формы. М.Наука,1974, 263 с.

30. Каменков Г.В. Избранные труды. Т.2. М.Наука.1972, 214 с.

31. Компьютерная алгебра. Символьные и алгебраические вычисления. Под ред. Бухбергер Б.,Коллинз Дж., Лоос Р. М."Мир",1986, 392 с.

32. Красносельский М.А., Перов А.И., Поволоцкий А.И., Забрейко П.П. Векторные поля на плоскости. М.Физматгиз. 1963, 248 с.262

33. Красовский H.H. Об устойчивости по первому приближению.// Прикладная матем. и механика. 1955, Т. 19, №5, С. 516-530

34. Крейн М., Неймарк М. Метод симметрических и эрмитовых форм в теории отделения корней алгебраических уравнений.-Харьков, ГТ-ТИ, 1936, 39 с.

35. Ляпунов A.M. Общая задача об устойчивости движения.М.-Л.,ГИТТЛ,1950, 471 с.

36. Малкин И.Г. Теория устойчивости движения. М.Наука, 1966, 530 с.

37. Новиков М.А. О знакоопределенности аналитических функций.// В сб. "Метод функций Ляпунова в анализе динамики систем". Новосибирск.Наука, 1987, С. 256-261

38. Новиков М.А. Об устойчивости перманентных вращений твердого тела вокруг неподвижной точки в задаче Бруна.// Прикладная матем. и механика. 1994, Т.58, №5,С. 161-165

39. Программирование. 1992, №5; 1994, №1; 1997, №3

40. Постон Т., Стюарт И. Теория катастроф и ее приложения. М.Мир.1980, 680 с.

41. Постников М.М. Устойчивые многочлены. М.Наука,1981, 176 с.

42. Пуанкаре А. О кривых, определяемых дифференциальными уравнениями. М.-Л.,ГИТТЛ, 1947, 392 с.

43. Розенвассер E.H., Юсупов P.M. Чувствительность систем управления. М.Наука,1981, 464 с.

44. Сальвадоре Л. Об устойчивости равновесия в критических случаях.// Механика. 1969. Т. 117. №5, С.3-28- 263

45. Сенчакова H.B. О вычислении индекса Пуанкаре векторных полей с однородными компонентами.// Вестник Ярославского университета. №12. 1975. С. 103-124

46. Серре И.А. Курс высшей алгебры. М.-СПб., Вольф, Б.г., 573 с.

47. Сушкевич А.К. Основы высшей алгебры.- М.-Л.ОНТИ, 1937, 475 с.

48. Схрейвер А. Теория линейного и целочисленного программирования. М.Мир. 1991

49. Тарханов H.H. О вычислении индекса Пуанкаре.// Изв.вузов. Математика. 1984. №9. С.47-50

50. Уилкинсон Д.Х. Алгебраическая проблема собственных значений.970. М.Наука. 564 с.

51. Утешев А.Ю. Использование однородных форм в качестве функций Ляпунова.// Депон. в ВИНИТИ М2942-В87 Деп.24.04.87, "Вестник ЛГУ, сер.мат." 13 с.

52. Утешев А.Ю., Шуляк С.Г. Критерий асимптотической устойчивости системы двух дифференциальных уравнений с однородными правыми частями.// Дифференц. уравнения. 1987. Т.23. №6. С.1009-1014

53. Утешев А.Ю. Однородные полиномы:знакоопределенность и использование в качестве функций Ляпунова.// Тезисы 5-й всесоюзной Четаевской конференции по теории устойчивости, 1987, Казань, С.98

54. Утешев А.Ю. Критерий положительной определенности однородных форм.// Вестник ЛГУ,сер.1. 1988. №1. С.110-112- 264

55. Утешев А.Ю. Необходимые и достаточные условия положительной определенноти однородных форм.// В сб. "Вопросы механики и процессов управления", Л.ЛГУ. 1989. №11. С.87-90

56. Утешев А.Ю., Шуляк С.Г. Метод Эрмита отделения решений систем алгебраических уравнений и его применения.// Депон. в ВИНИТИ №6319-В89 Деп.18.10.89,"Вестник ЛГУ,сер. 1" — 42 с.

57. Утешев А.Ю. К вопросу существования полиномиальной функции Ляпунова.// Дифференц.у равнения. 1989. Т.25. №11. С.2010-2013

58. Утешев А.Ю. Вычисление индекса Кронекера-Пуанкаре алгебраических кривых относительно алгебраических полей на плоскости.// Дифференц.уравнения. 1991. Т.27. №12. С.2181-2183

59. Утешев А.Ю., Черкасов Т.М. Локализация решений систем алгебраических уравнений и неравенств. Метод Эрмита.// Доклады АН России. 1996. Т.347, №4, С. 451-453

60. Утешев А.Ю., Черкасов Т.М. К задаче полиномиальной оптимизации.// Доклады АН России. 1998. Т. 361. №2. С.168-170

61. Фаддеев Д.К. Лекции по алгебре. -М.Наука, 1984, 416 с.

62. Фаддеев Д.К.,Фаддеева В.Н. Вычислительные методы линейной алгебры. М. ГИФМЛ, 1960, 656 с.

63. Хартман Ф. Обыкновенные дифференциальные уравнения. 1970, М. Мир, 720 с.

64. Харди Г.Г., Литтльвуд Д.Е., Полиа Г. Неравенства. М. ИЛ.1948, 456 с.

65. Хассе Г. Лекции по теории чисел. М. ИЛ. 1953, 528 с.- 265

66. Хованский А.Г. Индекс полиномиального векторного поля. // Функц. анализ и его приложения. 1979, Т.13, №1, С.49-58

67. Хованский А.Г. Малочлены. М.Факториал. 1996.

68. Ходж В., Пидо Д. Методы алгебраической геометрии. М. ИЛ. 1954, Т.1, 461 с.

69. Хорн Р., Джонсон Ч. Матричный анализ. 1989, М.Мир, 655 с.

70. Чезаро Э. Элементарный учебник алгебраического анализа и исчисления бесконечно малых. 1936, М.-Л., ОНТИ, 592 с.

71. Чернятин В.А. О знакоопределенности произвольных форм четного порядка. // Доклады АН БССР, 1966, Т. 10, №11, С. 821-823

72. Четаев Н.Г. Характеристики Кронекера. //В кн. Устойчивость движения. Работы по аналитической механике. 1962, М., АН СССР, С. 273-322

73. Чистов А.Л. Алгоритм полиномиальной сложности для разложения многочленов и нахождение компонент многообразия в субэкспоненциальное время. // Зап. научн. семин. ЛОМИ, 1984, Т.137, С.124-188

74. Ackermann J., Muench R. Robustness analysis in a plant parameter plane. // Automatic Control. Proc. of the 10th Triential World Congress of IFAC, 1988, 8: 205-209

75. Bank В., Heintz J., Krick T., Mandel R., Solerno P. Computability and complexity of polynomial optimization problems.// Modern Methods of Optimization. (Krabs W., Zowe J. eds.) Springer. 1992. P. 1-23

76. Barnett S. Greatest common divisor of two polynomials.// Linear Algebra Appl, 1970, 3:7-9

77. Barnett S. Polynomials and Linear Control Systems. 1983. New-York, Dekker

78. Becker E., Wôrmann T. On the trace formula for quadratic forms.// Contemp. Math. 1994. 155:271-291

79. Becker T., Weispfenning V. Grôbner Bases A Computational Approach to Commutative Algebra. 1993. New-York, Springer

80. Ben-Or M., Kozen D., Reif J. The complexity of elementary algebra and geometry.// J. of Сотр. and Sys.Sciences 1986. 32:251-264

81. Berenstein C.A., Struppa D.C. Small degree solutions for the polynomial Bézout equation.// Linear Algebra Appl. 1988. 98: 41-56

82. Berenstein C.A., Yger A. Analytic Bézout identities.// Advances in Applied Mathematics 1989. 10(l):51-74

83. Bézout É. Théorie générale des Équations Algébriques. 1779. Paris, P.-D. Pierres

84. Bikker P. On Bézout's method for computing the resultant. 1995. RISCLinz Report Series No. 95-36.

85. Bikker P., Uteshev A.Yu. Elimination à la Bézout. // Extended abstracts of the Int. Conf. Computer Algebra in Scientific Computing. St.-Petersburg, 1998. C.20-21

86. Bini D., Pan V. Polynomial and Matrix Computations. V. 1 , 1994. Birkhäuser, Boston

87. Brill A. Vorlesungen über ebene algebraischen Kurven und algebraische Funktionen. 1925. Braunschweig.

88. Brioschi F. Sur les séries qui donnent le nombre de racines réelles des équations algébriques à une ou â plusieurs inconnues. //In Opere Mathematiche. Milano, Ulrico Hoepli, 1909. V. 5, P. 127-143,

89. Bose N.K. Applied Multidimensional Systems Theory. 1982. Van Nostrand Reinhold,

90. Buchberger B. Gröbner bases: an algorithmic method in polynomial ideal theory.// Multidimensional Systems Theory (Bose N.K. ed.). 1985. P. 184-232, Dordrecht, Reidel

91. Byrnes C.I. On a theorem of Hermite and Hurwitz.// Linear Algebra Appl. 1983. 50: 61-101

92. Cayley A. On the theory of elimination.// Collected Mathematical Papers. 1889. V. 1. P.370-374

93. Coleman C. Asymptotic stability in 3-space.// Ann. Math. Studies, Contrib. Nonl. Oscillations. 1960. 45:257-268

94. Collins G.E. The calculation of multivariate polynomial resultants.// J. of the ACM. 1971. 18(4):515-532.

95. Collins G.E. Quantifier elimination for real closed fields by cylindrical algebraic decomposition.// Led. Notes Comput. Sei. 1975,33:134-183

96. Computer Algebra in Industry. Problem Solving in Practice. (Cohen A.M. ed.) 1993. Chichester, Wiley- 268

97. Cox D. , Little J., O'Shea D. Ideals, Varieties and Algorithms. 1993. Undergraduate Texts in Mathematics, Springer

98. Dixon A.L. The eliminant of three quantics in two independent variables.// Proc. London Math. Society. 1908. 6:468-478

99. Faugere J.C., Gianni P., Lazard D., Mora T. Efficient computation of zero-dimensional Gröbner bases by change of ordering.// J.Symbolic Computation. 1993. V. 16. P. 329-344

100. Fuller A.T. Aperiodicity determinants expressed in terms of roots.// Int.J. Control. 1988. V.47 №6. P.1571-1593

101. Gelfand I.M., Kapranov M.M., Zelevinsky A.V. Discriminants, resultants and multidimensional determinants. 1994. Boston, Birkhäuser

102. Gerdt V.P., Blinkov Yu.A. Involutive bases of polynomial ideals. // Mathematics and Computers in Simulation. 1998. 45(4): 519-542

103. Gerdt V.P., Blinkov Yu.A. Minimal involutive bases.// Mathematics and Computers in Simulation. 1998. 45(4): 543-560

104. Gianni P., Trager B., Zacharias G. Gröbner bases and primary decomposition of polynomial ideals.// J.Symbolic Computation. 1988. 6:149-167

105. González-Vega L., Lombardi H., Recio T., Roy M.-F. Specialisation de la suite de Sturm et sous-resultants.// Inform. Theor. et Applic. 1990. 24(6):561—588

106. González-Vega L. Determinantal formulae for the solution set of zero-dimensional ideals.// J. Pure Appl. Algebra. 1991. 76:57-80

107. González-Vega L., Pardo L.M. The computation of the radical for a zero dimensional ideal in a polynomial ring through the determination of the trace for its quotient algebra.//Preprint of the University of Cantabria. 1992. P.l-12

108. González-Vega L. An elementary proof of Barnett's theorem about the greatest common divisor of several univariate polynomials.// Linear Algebra Appl 1996. 247: 185-202

109. Gray J. Algebraic geometry between Noether and Noether — a forgotten chapter in the history of algebraic geometry.// Revue d'Histoire des Mathématiques. 1997. 3:1-48

110. Gutman S. Root Clustering in Parameter Space. 1990. Berlin, Springer

111. Henrici P. Applied and Computational Complex Analysis. Vol. 1. 1974. N.-Y., Wiley

112. Hermite Ch. Sur l'extension du théorème de M.Sturm a un système d'équations simultannées.// Oeuvres 1905.1:280-283, Paris, Gauthier-Villars

113. Hermite Ch. Remarques sur le théorème de M.Sturm.// Oeuvres. 1905. 1:284-287, Paris, Gauthier-Villars

114. Hermite Ch. Sur le nombre des racines d'une équation algébrique comprises entre des limités données.// Oeuvres. 1905. 1:397-414, Paris, Gauthier-Villars- 270

115. Hermite Ch. Sur l'extension du théorème de M.Sturm a un système d'équations simultannées.// Oeuvres. 1912. 3: 1-34, Paris, Gauthier-Villars

116. Hess E. Uber die Darstellung der einförmigen symmetrischen Functionen der Simultanwurzeln zweier algebraischer Gleichungen.// Z. Math. u. Phys. 1870. 15:325-360

117. Hilbert D. Uber die vollen Invariantensysteme.// Math. Annalen. 1893. 42:313-373

118. Hsu C.S., Gutallu R.S. Index evaluation for dynamical systems and its application to locating all the zeros of a vector function.// J.Applied Mechanics. 1983. 50(4 a):858-862

119. Jacobi C.G.J. Theoremata nova algebraica circa systema duarum aequationum inter duas variabiles propositarum.// Gesammelte Werke. 1884. 3:287-294, Berlin, Reimer

120. Jacobi C.G.J. De relationibus, quae locum haber debeunt inter puncta intersectionis duarum curvarum vel trium superficierum algebraicarum dati ordinis, simul cum enodatione paradoxi algebraici.// Gesammelte Werke. 1884. 3:331-354, Berlin, Reimer

121. Jacobson N. Lectures in Abstract Algebra. 1964. V. 3, Van Nostrand, NY

122. Kalinina E.A., Uteshev,A.Yu. Determination of the number of roots of a polynomial lying in a given algebraic domain.// Linear Algebra Appl. 1993. 185:61-81

123. Kalkbrenner M. On the stability of Gröbner basis under specializations.// J.Symbolic Computation. 1997. 24: 51-58

124. Kapur D., Lakshman Y.N. Elimination methods: an introduction.// Symbolic and Numerical Computation for Artificial Intelligence, (B. Donald et. al. eds.) 1992. Academic Press.

125. Kapur D., Saxena T. Comparison of various multivariate resultant formulations.// Proceedings ISSAC'95. Montreal, Canada, 1995. P. 187-194

126. Katsura S., Fukuda W., Inawashiro S., Fujiki N.M., Gebauer R. Distribution of effective field in the Ising spin glass of the ± J model at T = 0.// Cell Biophysics. 1987. 11: 309-319.

127. Kearfott B. An efficient degree-computation method for a generalized method of bisection.// Numerische Mathematik. 1979. 32: 109-127

128. Kobayashi H., Fujise T., Furukawa A. Solving systems of algebraic equations by a general elimination method.// J.Symbolic Computation. 1988. 5: 303-320

129. Kronecker L. Uber einige Interpolationsformeln für ganze Functionen mehrer Variabein.// Werke. 1895. 1:135-141, Leipzig, Teubner

130. Kronecker L. Zur Theorie der Elimination einer Variabein aus zwei algebraischen Gleichungen.// Werke. 1897. 2:113-192, Leipzig, Teubner

131. Lazard D. Résolution des systèmes d'équations algébriques.// Theor. Comput. Sei. 1981. 15:77-110

132. Lazard D. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations.// Lecture Notes in Computer Science, Springer. 1983. 162:146-156

133. Lazard D. Solving zero-dimensional algebraic systems.// J.Symbolic Computation, 1992. 13:117-131- 272

134. Pedersen P., Roy M.-F., Szpirglas A. Counting real zeros in the multivariate case. // Progress Math. 1993. 109: 203-223

135. Perron O. Algebra. 1932. Vol.1. Berlin-Leipzig, de Gruyter

136. Petrowsky I. On the topology of real plane algebraic curves.// Ann.Math. 1938. 39(l):189-209

137. Saito T. An extension of Sturm's theorem to two dimensions.// Proc. Japan Acad. Ser. A Math. Sei. 1997. 73(1): 18-19

138. Scheja G., Storch U. Lehrbuch der Algebra. 1988. Teil 2. Stuttgart, Teubner

139. Schläfli L. Uber die Resultante eines Systemes mehrerer algebraischer Gleichungen.// Gesammelte Math. Abhandlungen 1953. 2:9-112, Basel, Birkhäuser

140. Schur I. Vorlesungen über Invariantentheorie. 1968. Berlin, Springer

141. Stickelberger L. Uber eine neue Eigenschaft der Diskriminante algebraishcer Zahlkörper.// Verband, der I internat. Math. Kongresse. 1897. Zürich. 1898. 182-193. Leipzig, Teubner

142. Stickelberger L. Verzeichnis der Schriften von Ludwig Stickelberger. // Jahresbericht der Deutschen Mathematiker Vereinigung. 1937. 47(5-8): 79-86

143. Uteshev A.Yu., Shulyak S.G. Conditions for sign-definiteness of homogeneous forms and Possibility of using polynomials as Lyapunov Functions.// Abstracts of the Second Colloquium on Differential Equations, Plovdiv, Bulgaria. 1991. P. 298

144. Uteshev A.Yu., Shulyak S.G. Determination of Kronecker-Poincare index of algebraic curve relative to algebraic field on the plane.//- 274

145. Abstracts of the Second Colloquium on Differential Equations, Plovdiv, Bulgaria. 1991. P. 299

146. Uteshev A.Yu., Shulyak S.G. Hermite's method of separation of solutions of systems of algebraic equations and its applications.// Linear Algebra and its Applications. 1992. 177:49-88

147. Uteshev A.Yu. On the existence of a polynomial Lyapunov function. // Proceedings of the Int. Conf. on Differential Equations, Equadiff'91, Barcelona 1991, (C.Perello, C.Simo, J.Sola-Morales , eds.), 1993. Vol.2 :943-946 Singapore, World Scientific

148. Uteshev A.Yu., Cherkasov T.M. The search for the maximum of a polynomial.// J.Symbolic Computation. 1998. 25: 587-618

149. Uteshev A.Yu., Cherkasov T.M. Symbolic algorithms for polynomial optimization problems.// Abstracts of the Int. Conf. Dedicated to the 90th Anniversary of L.S.Pontryagin. Optimal Control. Москва 1998. P. 197-198

150. Weber H. Lehrbuch der Algebra. 1898, Bd.I. Braunschweig, Vieweg