Analysis of fixed sign property of even degree forms

Abstract

The article investigates the algorithm for analyzing the property of having fixed sign of polynomials of even degree by reducing them to quadratic forms. The formalization of the algorithm is described, as well as the simplest complexity analysis in the worst case is provided.

Full Text

Введение. В теории устойчивости движения по Ляпунову активно применяются два метода, предложенные самим А. М. Ляпуновым [1]. Первый метод основывается на анализе линейного приближения и использует алгебраический аппарат. Второй метод основан на применении специальных функций (так называемых «функций Ляпунова»), удовлетворяющих условиям теоремы Ляпунова об асимптотической устойчивости. В контексте второго метода очень важными становятся свойства знакопостоянности и знакоопределенности, которыми должны обладать как сама функция Ляпунова, так и ее производная на решениях исследуемой системы дифференциальных уравнений.

Приведем необходимые определения. Пусть 𝐷 ⊂ 𝑅^𝑛 n-мерная область, содержащая начало координат, 𝑥 = (𝑥₁, … , 𝑥_𝑛) - вектор из 𝐷.

Определение 1. [1] Непрерывная на 𝐷 функция 𝑓(𝑥) называется знако- постоянной положительной, если 𝑓(0) = 0 и 𝑓(𝑥) ≥ 0 при 𝑥 ∈ 𝐷 (𝑓(𝑥) ≤ 0 для знакопостоянных отрицательных функций).

Определение 2. [1] Непрерывная на 𝐷 функция 𝑓(𝑥) называется знакоопределенной положительной (или просто положительно определенной), если 𝑓(0) = 0 и 𝑓(𝑥)> 0 при 𝑥 ∈ 𝐷, 𝑥 ≠ 0, (𝑓(𝑥)<0 для знакоопределенных отрицательных функций).

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

$f(x_1,\dots ,x_n)={\sum }_{i,j=1}^n{a}_{ij}{x}_i{x}_j,$

где 𝑎_𝑖𝑗 ∈ 𝑅 — постоянные коэффициенты, причем 𝑎_𝑖𝑗 = 𝑎_𝑗𝑖 (принято для удобства). Очевидно, что квадратичная форма однозначно задается своей матрицей $A={\left\{a_{ij}\right\}}_{i,j=1}^n$, которая, как указано выше, симметрична. Для однозначного определения, является ли квадратичная форма знакоопределенной, служит следующий критерий.

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

${\Delta }_1=a_{11}>\mathrm{0,}{\Delta }_2=\left|\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right|>\mathrm{0,}\dots$

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

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

Постановка задачи. Рассмотрим упорядоченный набор 𝛼 = (𝛼_1,…𝛼_𝑛), состоящий из целых неотрицательных компонентов . Обозначим через Будем использовать подобные наборы для укороченной записи слагаемых в сложных выражениях по следующим правилам:

• Записьозначает покомпонентную сумму .
• Запись 𝑎_𝛼 означает, что переменная 𝑎 имеет 𝑛 целочисленных неотрицательных индексов, т.е..
• Запись 𝑥^𝛼 для вектора $x=(x_{\mathrm{1,}}\dots ,x_n)$ означает моном вида $x_1^{a_1}{x}_2^{a_2}\dots x_n^{a_n}$.

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

$f\left(x\right)={\sum }_{\left|a\right|=2m}{a}_a{x}^a,\left(\text{1}\right)$

где $x=(x_{\mathrm{1,}}\dots ,x_n)$, 𝑎_𝛼 — вещественные коэффициенты, суммирование проводится по всем возможным различным 𝛼, таким, что. Целью данной работы является построение алгоритма, который позволил бы определить, является ли полином вида (1) знакоопределенной функцией. Для этого, согласно методу, предложенному в работе [3], преобразуем полином 𝑓(𝑥) в квадратичную форму. Введем новые переменные

$y_1=x_1^m,y_2=x_1^{m-1}{x}_2\mathrm{,...,}{y}_{N-1}=x_{n-1}{x}_n^{m-1},y_N=x_n^m,\left(\text{2}\right)$

так, что 𝑦_𝑖 пробегают все возможные мономы при  В результате, полином 𝑓(𝑥) преобразуется в квадратичную форму

$q\left(y\right)={\sum }_{i,j=1}^N{q}_{ij}{y}_i{y}_j,\left(\text{3}\right)$

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

1. Как сказано выше, преобразование полинома в квадратичную форму является неоднозначным, т.к. некоторые мономы x^α нельзя однозначно разбить на произведение двух мономов вида x^β. Однако, число таких вариантов конечно.
2. Сложность алгоритма оценивается как, что при большой размерности вектора 𝑥 требует огромного количества вычислительных операций.

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

Формализация алгоритма. Пусть a = (a₁,…a_n), a_i – целые неотрицательные числа, $i=\overline{\mathrm{1,}n}$.

Определение 3. Будем говорить, что набор 𝛼 старше набора a′, если существует номер $k\in \left\{\mathrm{1,...,}n\right\}$, такой, что $a_k>{a^{\text{'}}}_k$ и $a_i={a^{\text{'}}}_i$ при 𝑖 < 𝑘.

Рассмотрим множество ${\Omega }_{2m}=\left\{a:\left|a\right|=2m\right\}$ и множество натуральных чисел ${\Xi }_{2m}=\left\{\mathrm{1,...}\left|{\Omega }_{2m}\right|\right\}$. Очевидно, что $\left|{\Omega }_{2m}\right|=\left|{\Xi }_{2m}\right|=C_{2m+n-1}^{2m}$. Пусть $p:{\Xi }_{2m}\to {\Omega }_{2m}$ есть взаимно однозначное отображение, такое, что 𝑝(𝑖) старше 𝑝(𝑗) при 𝑖 < 𝑗. Будем говорить, что такое отображение 𝑝 упорядочивает множество ${\Omega }_{2m}$ в лексикографическом порядке. Теперь полином (1) можно записать в строго упорядоченном виде

$f\left(x\right)={\sum }_{s=1}^{\left|{\Omega }_{2m}\right|}{a}_{p\left(s\right)}{x}^{p\left(s\right)}\left(\text{4}\right)$

Рассмотрим множества ${\Omega }_m=\left\{a:\left|a\right|=m\right\}$, ${\Xi }_m=\left\{\mathrm{1,...,}\left|{\Omega }_m\right|\right\}$ и отображение $q:{\Xi }_m\to {\Omega }_m$, которое упорядочивает множество ${\mathrm{\Omega }}_m$ в лексикографическом порядке. Заметим, что $\left|{\Omega }_m\right|=\left|{\Xi }_m\right|=C_{m+n-1}^m$.Теперь замену (2) тоже можно записать в строго упорядоченном виде

$y_1=x^{q\left(i\right)},i\in {\Xi }_m.\left(\text{5}\right)$

Обозначим ${\Xi }_m^2$через множество, состоящее из всевозможных неупорядоченных пар элементов множества Ξ_m. Очевидно,  что $\left|{\Xi }_m^2\right|=C_{\left|{\Omega }_m\right|}^2$. Рассмотрим отображение $Ф:{\Xi }_m^2\to {\Xi }_{2m}$ действующее по следующему правилу:

$\left(i,j\right)\stackrel{\overrightarrow{Ф}}{\to }{p}^{-1}\left(q\left(i\right)+q\left(j\right)\right),\left(i,j\right)\in {\Xi }_m^2.\left(\text{6}\right)$

Отображение Φ является сюръективным, но не инъективным, потому что некоторые наборы $a\in {\Omega }_{2m}$ неоднозначно раскладываются в сумму $\beta +{\beta }^{\text{'}},\beta ,{\beta }^{\text{'}}\in {\Omega }_m$. Применяя замену (5) и отображение Φ, каждое слагаемое вида $a_{p\left(s\right)}{x}^{p\left(s\right)}$ из полинома (4) можно представить в виде

$a_{p\left(s\right)}{x}^{p\left(s\right)}=a_{q\left(i\right)+q\left(j\right)}{y}_i{y}_j\left(\text{7}\right)$

где (𝑖, 𝑗) ∈ Φ⁻¹(𝑠), . В результате получаем семейство квадратичных форм, соответствующих записи (3),

В выражении (8) пара индексов (𝑖, 𝑗) выбирается из множества Φ⁻¹(𝑠) для каждого значения 𝑠. Матрица 𝐺 соответствующей квадратичной формы строится по правилу

$q_{ij}=\left\{\begin{array}{c}\frac{1}{2}{a}_{q\left(i\right)+q\left(j\right)},i\ne j,\\ a_{q\left(i\right)+q\left(j\right)},i=j.\end{array}\right.$

После того, как матрица 𝐺 построена, необходимо определить, не пропадают ли в соответствующей квадратичной форме некоторые переменные 𝑦_𝑖 , и какие из переменных 𝑦_𝑖 в ней остаются. Для того, чтобы наглядно пояснить ситуацию, рассмотрим пример. Пусть дана положительно определенная форма четвертого порядка  $f(x_1,x_2)=x_1^4+x_2^4.$

После замены

$y_1=x_1^2,y_2=x_1{x}_2,y_3=x_2^2\left(\text{9}\right)$

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

$q(y_1,y_2,y_3)=y_1^2+y_3^2.$

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

$G=\left(\begin{array}{ccc}1& 0& 1\\ 0& 0& 0\\ 0& 0& 1\end{array}\right)$

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

Рассмотрим другой пример. Пусть дана знакопостоянная форма $f(x_1,x_2)=x_1^4+x_1^2{x}_2^2.$

Замена (9) приводит к квадратичной форме $q(y_1,y_2,y_3)=y_1^2+y_2^2.$

с матрицей

$G=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}\right)$

После удаления третьей строки и третьего столбца получаем положительно определенную матрицу, хотя исходная форма f =(x₁,x₂) = является лишь знакопостоянной. Такой эффект получается в силу того, что замены y₁ = x²₁ и y₂ = x₁x₂ содержат общий множитель 𝑥₁. Следовательно, исследовать матрицу 𝐺 после удаления нулевых строк и столбцов следует только тогда, когда оставшиеся переменные 𝑦_𝑖 не имеют общего множителя.

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

1. Исходные данные: числа 𝑛, 2𝑚, массив коэффициентов a_a, упорядоченный по 𝛼. Если коэффициент в полиноме отсутствует, то соответствующий элемент массива равен нулю.
2. По числам n, m строятся упорядоченные массивы ${\Omega }_{2m}, {\Omega }_m$.
3. Строится массив Φ длины $\left|{\Omega }_{2m}\right|$, состоящий из списков. В списке с номером 𝑠 содержатся пары (𝑖, 𝑗), такие, что ${\Omega }_m\left[i\right]+{\Omega }_m\left[j\right]={\Omega }_{2m}\left[s\right]$.
4. Строится матрица 𝐺 квадратичной формы 𝑔(𝑦) размености $\left|{\Omega }_m\right|\times \left|{\Omega }_m\right|$. Для этого необходимо пройти по массиву списков Φ и из каждого списка Φ[𝑠] выбрать одну пару (𝑖, 𝑗). Тогда
   $G\left[i\right]\left[j\right]=q\left[j\right]\left[i\right]=\left\{\begin{array}{c}\frac{1}{2}{a}_{{\Omega }_{2m}\left[s\right]},i\ne j,\\ a_{{\Omega }_{2m}\left[s\right]},i=j.\end{array}\right.$
5. Пусть $s_1,s_2\mathrm{,...,}{s}_k$ – номера ненулевых строк в матрице G. Если ${\Omega }_m\left[s_1\right]\mathrm{,...,}{\Omega }_m\left[s_k\right]$ не имеют общей компоненты, отличной от нуля, то матрица 𝐺 после удаления нулевых строк и столбцов исследуется на критерий Сильвестра, иначе данная матрица пропускается.
6. Этапы 4, 5 повторяются до тех пор, пока не будут перебраны все возможные матрицы 𝐺 либо пока какая-либо из этих матриц не будет удовлетворять критерию Сильвестра.

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

Общее количество получаемых квадратичных форм (т.е. матриц 𝐺) вычисляется по формуле

$N_q={\prod }_{s=1}^{\left|{\Xi }_m^2\right|}\left|{Ф}^{-1}\left(S\right)\right|.\left(\text{10}\right)$

Для нахождения верхней оценки правой части выражения (10) решим следующую задачу оптимизации:

$\begin{array}{l}h\left(z_1\mathrm{,...,}{z}_{{}_{\left|{\Xi }_{2m}\right|}}\right)=\prod _{s=1}^{{}_{\left|{\Xi }_{2m}\right|}}{z}_s\to \max ,\\ z_1+\mathrm{...}+z_{{}_{\left|{\Xi }_{2m}\right|}}=\left|{\Xi }_m^2\right|,\left(\text{11}\right)\\ z_1>\mathrm{0,...,}\left.z_{{}_{\left|{\Xi }_{2m}\right|}}\right|>0.\end{array}$

Методами математического анализа несложно установить, что решение задачи (11) достигается при значениях $z_1=\mathrm{...}=z_{{}_{\left|{\Xi }_{2m}\right|}}=\left|{\Xi }_m^2\right|/\left|{\Xi }_{2m}\right|$ и равно $h_{\max }={(\left|{\Xi }_m^2\right|/\left|{\Xi }_{2m}\right|)}^{\left|{\Xi }_{2m}\right|}$. Следовательно, величина 𝑁_𝑞 должна удовлетворять неравенству

$N_q\le {\left(\frac{\left|{\Xi }_m^2\right|}{\left|{\Xi }_{2m}\right|}\right)}^{\left|{\Xi }_{2m}\right|}={\left(\frac{{\left|{\Xi }_m\right|}^2+\left|{\Xi }_m\right|}{2\left|{\Xi }_{2m}\right|}\right)}^{\left|{\Xi }_{2m}\right|}.\left(\text{12}\right)$

Для продолжения оценки (12) воспользуемся соотношением

$\frac{\left|{\Xi }_m\right|}{\left|{\Xi }_{2m}\right|}=\frac{C_{m+n-1}^m}{C_{2m+n-1}^{2m}}={\prod }_{k=1}^{n-1}\frac{m+k}{2m+k}\le \frac{2}{3}.$

Действительно, каждый множитель вида $(m+k)/(2m+k)$ строго меньше единицы и убывает при возрастании 𝑚, поэтому наибольшее свое значение произведение ${\prod }_{k=1}^{n-1}\frac{m+k}{2m+k}$ принимает при 𝑛 = 2 и 𝑚 = 1. Теперь, учитывая неравенство (12) и $\left|{\Xi }_m\right|\le 2/3\left|{\Xi }_{2m}\right|$, получаем

$N_q\le {(\frac{2}{9}\left|{\Xi }_{2m}\right|+\frac{1}{3})}^{\left|{\Xi }_{2m}\right|},\left(\text{13}\right)$

где  $\left|{\Xi }_{2m}\right|=C_{2m+n-1}^{2m}.$

Пример.

Рассмотрим полином четвертой степени $f(x_1,x_2)=2x_1^4+x_1^2{x}_2^2-3x_1{x}_2^3+3x_2^4.$

Опишем работу алгоритма по этапам.

1. Исходные данные: $n=\mathrm{2,2}m=4\Rightarrow m=2$, упорядоченный массив коэффициентов [2, 0, 1, −3, 1].
2. Ω₄= [(4, 0), (3, 1), (2, 2), (1, 3), (0, 4)], Ω₂ = [(2, 0), (1, 1), (0, 2)].
3. Φ = [[(1, 1)], [(1, 2)], [(1, 3), (2, 2)], [(2, 3)], [(3, 3)]].
4. В данном случае имеем две матрицы

$G_1=\left(\begin{array}{ccc}2& 0& 1/2\\ 0& 0& -3/2\\ 1/2& -3/2& 3\end{array}\right),$

$G_2=\left(\begin{array}{ccc}2& 0& 0\\ 0& 1& -3/2\\ 0& -3/2& 3\end{array}\right).$

Нетрудно убедиться, что матрица $G_2$ удовлетворяет критерию Сильвестра о положительной определенности (все ее главные диагональные миноры строго положительны).