Анализ расположения корней полинома с помощью матрицы Безу

[Alex Krylov]

Дан полином $p(z)=a_n z^n+a_{n-1} z^{n-1}+...+a_0$ с вещественными коэффициентами, зависящими от вещественных параметров $\mu_k, k=1..m$. Требуется определить область значений параметров $\mu_k$, при которых все корни полинома $z=x+j y$ находятся в области, задаваемой алгебраическим неравенством $f(x,y)>0$.

Ну то есть это стандартная задача о D-стабильности корней полинома, т.е. принадлежности их заданной области D комплексной плоскости. Пусть кривая $f(x,y)=0$ - рациональная, т.е. для нее существует рациональная параметризация $x(t)=\frac{r_1(t)}{r_0(t)}, y(t)=\frac{r_2(t)}{r_0(t)}$. Далее, подставляя величины $z(t)=x(t)+j y(t)=\frac{r_1(t)}{r_0(t)}+j \frac{r_2(t)}{r_0(t)}$ в исходный полином, получаем два следующих полинома для анализа:

$\\g(t)=Numer(\operatorname{Re}[p(x(t)+j y(t))])\\ h(t)=Numer(\operatorname{Im}[p(x(t)+j y(t))])$

Здесь $Numer(...) -$ взятие числителя дробно-рационального выражения.

Далее используется то свойство, что если все корни полиномов $g(t), h(t)$ вещественные, различные и перемежающиеся, то матрица Безу (Безутианта) $Bez(g(t),h(t))$, построенная для данной пары полиномов, - положительно определенная. Это необходимое и достаточное условие положительной определенности матрицы Безу.

И для ряда простейших кривых $f(x,y)=0$ не выше 2-го порядка (прямая, парабола, круг, эллипс) полиномы $g(t), h(t)$ обладают нужными нам свойствами. Для кривых выше 2-го порядка у полиномов $g(t), h(t)$ помимо желанных вещественных корней появляются комплексные корни.

Итого: Для ряда простейших областей/кривых (прямая, парабола, круг, эллипс) искомая область значений параметров $\mu_k$ получается исходя из условия положительной определенности соотв. матрицы Безу. Понятно, что всё это элементарным образом обобщается на случай пересечения таких простейших областей: получаем систему неравенств для нескольких матриц Безу.

Вопрос: Известны ли кому обобщения или похожие методики на случай алгебраических областей более общего вида? Т.е. чтобы решение вопроса в итоге сводилось к матричному неравенству или (эквивалентно) к системе алгебраических неравенств относительно параметров $\mu_k$.

[Alex Krylov]

Удалось прояснить ситуацию благодаря следующему результату, приведенному в [1]:

Цитата:

Пусть $R(x)$ - вещественная функция. Тогда индексом $J_{a}^b R(x)$ функции $R(x)$ на интервале $(a,b)$ называется разность между числом разрывов данной функции от $-\infty$ до $+\infty$ и от $+\infty$ до $-\infty$ на интервале $(a,b)$ при движении от $a$ к $b$.

Теорема (Коши). Пусть $h(t), g(t)$ - полиномы с вещественными коэффициентами. Тогда сигнатура $\rho$ матрицы Безу $Bez(h,g)$ равна индексу функции $\frac{g(t)}{h(t)}$ на итервале $(-\infty, +\infty$), т.е. $\rho=J_{-\infty}^{+\infty} \frac{g(t)}{h(t)}$.

Пример: Если дан полином 3-й степени с корнями, лежащими внутри круга/эллипса (на комплексной плосткости), то сигнатура соотв. матрицы Безу равна 6 при размерности матрицы Безу также равной 6. Из-за равенства сигнатуры матрицы Безу ее размерности тут все вырождается в простое условие положительной определенности матрицы Безу, что эквивалентно системе алгебраических неравенств. Если теперь корни $z=x+j y$ этого же полинома лежат в области $-x^4-x^2 y^2-y^4+x^3+x y^2>0$, то сигнатура соотв. матрицы Безу по-прежнему равна 6, а вот размерность матрицы Безу увеличилась до 12. Тут уже надо задействовать теорему Якоби, где сигнатура матрицы определяется через числа знакопостоянств и знакоперемен в ряду миноров соотв. матрицы. Т.е. все вырождается в комбинаторную задачу, где искомая область стабильности в итоге получается как объединение (по "ИЛИ") нескольких областей, задаваемых системами алгебраических неравенств (ЕМНИП, для приведенного тут случая число таких комбинаций неравенств равно 100).

1) Крейн, М., Неймарк, М. Метод симметрических и эрмитовых форм в теории отделения корней алгебраических уравнений / М. Крейн // Х.: АНТ-ВУ, 1938. — 257 с.

[Alex Krylov]

Как известно, область устойчивости в общем случае невыпукла и может иметь весьма сложную структуру, которую (особенно в многомерном случае) невозможно проанализировать. В этом случае можно взять пробное множество более простой структуры (шар, гиперкуб, выпуклый многогранник итд) и проверить, принадлежит ли оно области устойчивости, задаваемой неравенством относительно матрицы Безу. Фишка тут состоит в том, что известная теорема Пойа о представлении положительных полиномов на симплексе обобщается на случай симметричных полиномиальных матриц (а матрицы Безу именно таковы!). Эти два ингредиента (матрица Безу и теорема Пойа) позволяют проверять на устойчивость области в виде выпуклых многогранников:

Цитата:

Теорема Пойа (о представлении положительных полиномов)
Если однородный полином $p(x)>0$ для всех $x\in\left\lbrace x\in R^n:\sum\limits_{i=1}^{n}x_i=1, x_i\geqslant0 \right\rbrace$, то найдется $d\geqslant0 $ такое, что все коэффициенты полинома $(\sum\limits_{i=1}^{n}x_i)^d p(x)$ - положительные числа.

Теорема Пойа (обобщение на случай полиномиальных матриц)
Если однородная полиномиальная матрица $F(x)>0$ для всех $x\in\left\lbrace x\in R^n:\sum\limits_{i=1}^{n}x_i=1, x_i\geqslant0 \right\rbrace$, то найдется $d\geqslant0 $ такое, что все коэффициенты $(\sum\limits_{i=1}^{n}x_i)^d F(x)$ - положительно определенные.

Любой неоднородный полином на симплексе может быть гомогенизирован, т.е. доведен до однородного вида (домножением в нужных местах на множители вида $(\sum\limits_{i=1}^{n}x_i)^q$, которые (по свойству симплекса) равны единице).

Игрушечный пример

$p(z)=z^3+k_1 z^2+(k_2-5k_1-13)z+k_2$ - исходный характеристический полином, $k_1, k_2$ - вещественные параметры. Матрица Безу, построенная для данного характеристического полинома (гурвицев случай) $M=\begin{bmatrix} k_2(k_2-5k_1-13)&0 &-k_2 \\ 0&k_1(k_2-5k_1-13)-k_2 &0 \\ -k_2&0 &k_1 \end{bmatrix}>0$. Умножая матрицу $M$ слева и справа на матрицу перестановки $P=\begin{bmatrix} 1&0 &0 \\ 0&0 &1 \\ 0&1 &0 \end{bmatrix}$ получим эквивалентное неравенство $\tilde{M}=P M P^T=\begin{bmatrix} k_2(k_2-5k_1-13)&-k_2 &0 \\ -k_2&k_1 &0 \\ 0&0 &k_1(k_2-5k_1-13)-k_2 \end{bmatrix}>0$. Для гурвицева случая такое преобразование всегда возможно (с распадением исходного матричного неравенства на два более простых относительно диагональных блоков) - это известный результат. Теперь с помощью теоремы Пойа хотим проверить, устойчива ли прямоугольная область $\left\lbrace 2\leqslant k_1 \leqslant 4, 60\leqslant k_2 \leqslant 80 \right\rbrace $ (это заведомо стабильная область). Любой выпуклый многогранник с числом вершин $n$ может быть представлен в виде симплекса той же размерности. В данном случае: $\begin{bmatrix} k_1 \\ k_2 \end{bmatrix}=\begin{bmatrix} 2 \\ 60 \end{bmatrix}t_1+\begin{bmatrix} 2 \\ 80 \end{bmatrix}t_2+\begin{bmatrix} 4 \\ 80 \end{bmatrix}t_3+\begin{bmatrix} 4 \\ 60 \end{bmatrix}t_4, \sum\limits_{i=1}^{4}t_i=1, t_i\geqslant 0$. Далее подставляем $k_1, k_2$, выраженные через переменные симплекса, в $\tilde{M}$, выполняя где надо гомогенизацию, в результате получим два неравенства (одно матричное, другое скалярное) относительно соответственно однородного матричного и скалярного полиномов. Вот на этом этапе можем применять теорему Пойа.