Анализ знакоопределённости форм четной степени

Приведем необходимые определения. Пусть De Rⁿ n-мерная область, содержащая начало координат,* = (х 1 , .^,х_п) - вектор из D.

Определение 1. [1] Непрерывная на D функция f(x) называется знако- постоянной положительной, если f(0) = 0 и f(x) > 0 при х Е D (f(x) < 0 для знакопостоянных отрицательных функций).

Определение 2. [1] Непрерывная на D функция f(x) называется знакоопределенной положительной (или просто положительно определенной), если f(0) = 0 и f(x) >  0 при х Е D, х ^ 0 (f(x) <  0 для знакоопределенных отрицательных функций).

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

f(x1,...,xn) = ^Ij^aijXiXj ,

где a ij ER — постоянные коэффициенты, причем a ij = a ji (принято для удобства). Очевидно, что квадратичная форма однозначно задается своей матрицей А = {а^}^^ , которая, как указано выше, симметрична. Для однозначного определения, является ли квадратичная форма знакоопределенной, служит следующий критерий.

Теорема 1 (Критерий Сильвестра). Квадратичная форма f(x) является положительно определенной тогда и только тогда, когда все угловые миноры ее матрицы положительны:

а^  а^

△1= а11>0    △= |а21 а22|>0'-

Для отрицательной определенности необходимо и достаточно, чтобы знаки угловых миноров чередовались : А , < 0, Д₂> 0, Д 3 < 0,...

Квадратичные формы применяются для исследования линейных дифференциальных систем, но для нелинейных систем они в общем случае не подходят. В теории выделен очень важный класс так называемых однородных систем, правая часть которых является однородным отображением [2]. Самым распространенным их примером являются системы с полиномиальной правой частью. Для таких систем функция Ляпунова может быть построена в виде однородного полинома четной степени. В настоящий момент критерий знакоопределенности четных полиномов отсутствует, поэтому их исследование проводится различными путями. Одним из таких является сведение полинома к квадратичной форме, предложенный в работе [3]. Данная работа посвящена построению и анализу описанного в этой работе алгоритма.

Постановка задачи. Рассмотрим упорядоченный набор а = (а 1 , ..., а_п}, состоящий из целых неотрицательных компонентов a i ,i = 1,п. Обозначим через |а| = Е П=1 a i . Будем использовать подобные наборы для укороченной записи слагаемых в сложных выражениях по следующим правилам:

• •    Запись а + а ' означает покомпонентную сумму а + а’ = (а 1 + а 1 ,..., а_п + а_п ' ).

• •    Запись а_а означает, что переменная а имеет п целочисленных неотрицательных индексов, т.е. а_а = а_а^_Мп .

• •    Запись х^а для вектора х = (х 1 , ..., х_п~) означает моном вида х^х^² ■■■ х ^^п .

Рассмотрим полином четной степени 2т

/(х) = 1\а\=2т и а х^а ,                                 (1)

где х = (х 1 ,..., х_п), а_а — вещественные коэффициенты, суммирование проводится по всем возможным различным а, таким, что \а\ = 2т. Целью данной работы является построение алгоритма, который позволил бы определить, является ли полином вида (1) знакоопределенной функцией. Для этого, согласно методу, предложенному в работе [3], преобразуем полином /(х) в квадратичную форму. Введем новые переменные

У 1 = *т,У2 = хт-1х2, :,yN-i = хп-1 х™-1^ = хП ,(2)

так, что у [ пробегают все возможные мономы х^в при \Р\ = т. В результате, полином /(х) преобразуется в квадратичную форму

д⁽у) = Z i,j=i9ij yiy j ,                                     ⁽³⁾

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

• 1.    Как сказано выше, преобразование полинома в квадратичную форму является неоднозначным, т.к. некоторые мономы х^а нельзя однозначно разбить на произведение двух мономов вида х^в. Однако, число таких вариантов конечно.

• 2.    Сложность алгоритма оценивается как, что при большой размерности вектора х требует огромного количества вычислительных операций.

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

Формализация алгоритма. Пусть а = (а₁,...,а_п), a i - целые неотрицательные числа, i = 1,п.

Определение 3 . Будем говорить, что набор а старше набора а', если существует номер к Е {1,.. .,п}, такой, что а_к > а'_к и a i = а ' при i < к.

/(х) = ЕяЧи' ’⁽” '                      (4)

y i = х^, i £ z_m.                                 (5)

Обозначим через ^ т множество, состоящее из всевозможных неупорядоченных пар элементов множества Е_т . Очевидно, что |^ т | = Сщ^. Рассмотрим отображение Ф : ^ т ^ 3_2т , действующее по следующему правилу: ф

^(i,j) ^ р ¹⁽q⁽ⁱ⁾ + qb)),^,]) ^G ^ т .                          ⁽⁶⁾

Отображение Φ является сюръективным, но не инъективным, потому что некоторые наборы а G ^2т неоднозначно раскладываются в сумму /? + /?',/?,/?' G ^т. Применяя замену (5) и отображение Ф, каждое слагаемое вида ap(S)XpsS) из полинома (4) можно представить в виде ap(s)XpS) = Uq^+q^yiyj                              (7)

где (i,j) £ Ф^-1(з'),а^ = a p( _s ) . В результате получаем семейство квадратичных форм, соответствующих записи (3),

g⁽y) = ? }?= l ^{l a} q(i)+qu№ .                           ⁽⁸⁾

В выражении (8) пара индексов (i,j) выбирается из множества Ф-1(s) для каждого значения s. Матрица G соответствующей квадратичной формы строится по правилу

9 ij =

faqV+qUyi * ^j, I ^a q(i)+q(j) , ⁱ = ^j.

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

f⁽X 1 ,X2^ = х 4 + X 4 .

После замены

y 1 = ^х^У 2 = ^X 1 ^X 2 ,y 3 = ^х 2

получаем квадратичную форму

3(У 1^, У 2^, У з⁾ = У^{2 +} У з -

Матрица данной квадратичной формы имеет вид

G =

(1 01\

(0 00)

0 01

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

Рассмотрим другой пример. Пусть дана знакопостоянная форма /(^ 1 ,^ 2 ) = Х 4 + х 2 х 2 .

Замена (9) приводит к квадратичной форме

5(У1,У2-Уз) = У12

с матрицей

G =

1 00

(0 10

0 00

После удаления третьей строки и третьего столбца получаем положительно определенную матрицу, хотя исходная форма /(х1, х2) = является лишь знакопостоянной. Такой эффект получается в силу того, что замены У1 = х2 и У2 = х1х2 содержат общий множитель х1. Следовательно, исследовать матрицу G после удаления нулевых строк и столбцов следует только тогда, когда оставшиеся переменные У[ не имеют общего множителя.

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

• 1.    Исходные данные: числа п, 2т, массив коэффициентов а_а , упорядоченный по а.

• 2.    По числам n, m строятся упорядоченные массивы П_2т , &_т .

• 3.    Строится массив Ф длины Щ_2т|, состоящий из списков. В списке с номером s содержатся пары (i, ]), такие, что O_m[i] + ^_m[j] = Q_2m[s].

• 4.    Строится матрица G квадратичной формы д(У') размености Щ_т|хЩ_т|. Для этого необходимо пройти по массиву списков Ф и из каждого списка Ф[s] выбрать одну пару (i, j).

• 5.    Пусть 5 1 , s₂,...,s_k - номера ненулевых строк в матрице G. Если H_m[s₁],...,H_m[s_fc] не имеют общей компоненты, отличной от нуля, то матрица G после удаления нулевых строк и столбцов исследуется на критерий Сильвестра, иначе данная матрица пропускается.

• 6.    Этапы 4, 5 повторяются до тех пор, пока не будут перебраны все возможные матрицы G либо пока какая-либо из этих матриц не будет удовлетворять критерию Сильвестра.

Если коэффициент в полиноме отсутствует, то соответствующий элемент массива равен нулю.

Тогда

G[i][j] = g[j-][i] =