УказательРазделыОбозначенияАвторО проекте


§

Вспомогательный раздел к разделу ПОЛИНОМ


Локализация корней полинома

Задача. Пусть задан полином f(z)=a_0z^n+a_1z^{n-1}+\dots + a_n с комплексными коэффициентами от комплексной переменной z=x+{\mathbf i} y и заданы полиномы g_1(x,y), \dots, g_K(x,y) с вещественными коэффициентами. Требуется определить число корней полинома f_{}(z) в области комплексной плоскости, описываемой системой неравенств

g_1(x,y)>0, \dots, g_K(x,y)>0 \ .

Такая задача имеет теоретическое и практическое значение. Так, например, в теории управления требуется определить критерии того, чтобы все корни полинома f_{}(z) лежали в области y < 0, т.е. в левой полуплоскости комплексной плоскости. Проблема исследования сходимости итерационной процедуры в численных методах требует проверки другого свойства для корней: они должны лежать в круге x^2+y^2 < 1.

Оказывается, что многие подобные задачи могут быть решены без привлечения каких-либо явных способов решения алгебраического уравнения f(z)=0. Именно, существуют процедуры, позволяющие за конечное число элементарных алгебраических операций ( + , -,\times, \div ) над коэффициентами полиномов f,g_1,\dots,g_K однозначно установить искомое число корней.

Вещественные корни

Задача. Для полинома f(x)\in \mathbb R[x] установить точное число его вещественных корней на заданном интервале1) ]a,b_{}[:

\operatorname{nrr} \{f(x)=0 \ | \ a<x<b \} \ .

Чувствительность корней

Если мы хотим найти приближенное значение корня полинома применением какого-либо численного метода, то мы должны предварительно дать оценку точности вычислений: сколько значащих цифр мы должны сохранять в промежуточных выкладках, чтобы гарантировать достоверность получаемых результатов?

Это порождает более общую задачу оценки чувствительности корней, т.е. оценки их изменения при некотором возмущении коэффициентов полинома. Принципиальным результатом здесь является теорема о непрерывной зависимости корней полинома от его коэффициентов. Выясним на примере, насколько малым может быть возмущение коэффициентов полинома f(x)=x^n+a_{1}x^{n-1}+\dots+a_n с вещественными коэффициентами, чтобы сохранилось неизменным хотя бы число его вещественных корней. Для определенности, рассмотрим случай, когда полином f_{}(x) не имеет кратных корней (т.е. его дискриминант отличен от нуля). Тогда число вещественных корней не изменится при малых (вещественных) вариациях его коэффициентов. В самом деле, вещественный корень полинома с вещественными коэффициентами не может «сойти» с вещественной оси пока не столкнется с другим вещественным корнем, т.е. не станет кратным (см. ЗДЕСЬ ). Осталось только оценить малость допустимого возмущения.

П

Пример [Уилкинсон]. Вычислить корни полинома

\begin{matrix} f(x) &=&x^{20}+210\,x^{19}+20615\,x^{18}+1256850\, x^{17} +53327946\, x^{16}+1672280820\, x^{15}+ \\ & &+40171771630\, x^{14}+756111184500\, x^{13}+11310276995381\, x^{12} +135585182899530\, x^{11} + \\ & &+1307535010540395\, x^{10}+10142299865511450\, x^9 +63030812099294896\, x^8 + \\ & & +311333643161390640\, x^7+1206647803780373360\, x^6 +3599979517947607200\, x^5+ \\ & & +8037811822645051776\, x^4+12870931245150988800\, x^3 +13803759753640704000\, x^2+ \\ & & +8752948036761600000\,x +2432902008176640000 \end{matrix}

по методу Ньютона.

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

f(x)=\prod_{j=1}^{20}(x+j) \ ,

и таким образом его корнями являются числа -1,-2,\dots,-20, достаточно хорошо разнесенные. Пусть, однако же, эта информация нам изначально недоступна, и мы для поиска корней применяем метод Ньютона, задав точность вычислений в 10^{-5}. Является ли эта точность достаточной для нахождения приближенных значений корней? Оказывается, нет. Рассмотрим полином

{\tilde f}_{\varepsilon}(x)= f(x)+\varepsilon\,x^{19} \quad npu \ \varepsilon=2^{-23}\approx 1.192092896\times 10^{-7} \ .

Уже при таком малом возмущении в одном-единственном коэффициенте происходит потеря десяти вещественных корней! Корнями {\tilde f}_{\varepsilon}(x) являются

\lambda_1=-1.000000, \ \lambda_2=-2.000000, \ \lambda_3=-3.000000, \ \lambda_4=-4.000000,
\lambda_5=-4.999999,\ \lambda_6=-6.000007,\ \lambda_7=-6.999697,\ \lambda_8=-8.007268,\ \lambda_9=-8.917250
\lambda_{10,11}=-10.095266 \pm 0.643501 \, {\mathbf i}, \ \lambda_{12,13}=-11.793634 \pm 1.652330 \, {\mathbf i},
\lambda_{14,15}=-13.992358\pm 2.518830 \, {\mathbf i},\ \lambda_{16,17}=-16.730737\pm 2.812625\, {\mathbf i},
\lambda_{18,19}=-19.502439\pm 1.940330\, {\mathbf i},
\lambda_{20}=-20.846908 \ .

В данном примере допустимые возмущения для \varepsilon, т.е. такие, при которых сохранится свойство вещественности всех корней {\tilde f}_{\varepsilon}(x), находятся в пределах [7]

-1.3508\times 10^{-10}\ < \ \varepsilon \ < +1.4213\times 10^{-10} \ .

Правило знаков Декарта

Т

Теорема [Декарт]. Число положительных корней полинома

f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n, \quad (a_0> 0,a_n \ne 0)

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

\operatorname{nrr} \{ f(x)=0 \mid x>0 \} = {\mathcal V}(a_0,a_1,\dots,a_n)-2 k , \quad k\in \{0,1,2, \dots \} \ .

С помощью преобразования корней полинома (см. пункт 1 ЗДЕСЬ ) можно доказать следствие:

=>

Число отрицательных корней полинома

f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n, \quad (a_0> 0,a_n \ne 0)

с учетом их кратностей можно оценить по формуле

\operatorname{nrr} \{ f(x)=0 \mid x<0 \} = {\mathcal V}(a_0,-a_1,a_2,\dots,(-1)^na_n)-2 k' \ ,

а если среди коэффициентов a_j нет нулевых, то — по формуле

\operatorname{nrr} \{ f(x)=0 \mid x<0 \} = {\mathcal P}(a_0,a_1,a_2,\dots,a_n)-2 k' \ ,

где k'\in \{0,1,2, \dots \} и {\mathcal P} обозначает число знакопостоянств.

П

Пример. Оценить число положительных и число отрицательных корней полинома

f(x)=x^5-2\, x^4-8\,x^3-x^2-9\, x+1 \ .

Решение.

{\mathcal V}(1,-2,-8,-1,-9,1)=2 \ \Rightarrow \ \operatorname{nrr} \{ f(x)=0 \mid x>0 \} =2-2k \ge 0 \ ,

следовательно f(x) имеет либо два, либо ни одного положительного корня. Далее, по следствию:

\operatorname{nrr} \{ f(x)=0 \mid x<0 \} = {\mathcal P}(1,-2,-8,-1,-9,1)=3-2k'\ge 0 \ ,

следовательно f(x) имеет либо три, либо один отрицательный корень.

П

Пример. Оценить число положительных и число отрицательных корней полинома f(x)=x^5-x^3-1.

Решение. Здесь {\mathcal V}(1,0,-1,0,0,-1)={\mathcal V}(1,-1,-1)=1.

\operatorname{nrr} \{ f(x)=0 \mid x>0 \} =1-2k \ge 0 \ \Longrightarrow \ = 1

Далее, на основании первой формулы из следствия имеем

\operatorname{nrr} \{ f(x)=0 \mid x<0 \} ={\mathcal V}(1,0,-1,0,0,1)-2k'=2-2k' = \left\{ \begin{array}{cc} 2 & npu \ k'=0; \\ 0 & npu \ k'=1. \end{array} \right.

Ответ. Полином имеет один положительный и либо два, либо ни одного отрицательного корня.

§

Заметим, что формальное применение для решения последнего примера второй формулы из следствия дало бы неправильную оценку для \operatorname{nrr} \{ f(x)=0 \mid x<0 \}.

=>

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

\operatorname{nrr} \{ f(x)=0 \mid x>0 \} = {\mathcal V}(a_0,a_1,\dots,a_n) \ .

§

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

Система полиномов Штурма

Для полинома f(x_{}) система полиномов

f_0(x)\equiv f(x), f_1(x),\dots, f_K(x)

называется системой полиномов Штурма (или рядом Штурма) на заданном интервале ]a,b_{}[ если на этом интервале
1. cоседние полиномы f_{j}(x) и f_{j+1}(x) не имеют общих корней;
2. f_K(x)\ne 0;
3. если f_j(x_0)=0 при x_0 \in ]a,b[ и j\in \{1,\dots,k-1\}, то числа f_{j-1}(x_0) и f_{j+1}(x_0) имеют разные знаки: f_{j-1}(x_0)f_{j+1}(x_0)<0;
4. произведение f_{0}(x)f_{1}(x) меняет знак с отрицательного на положительный когда x_{}, возрастая, проходит корень \lambda\in ]a,b[ полинома f_0(x)\equiv f(x).

Число знакоперемен

{\mathcal V}_x= {\mathcal V}(f_0(x), f_1(x),\dots, f_K(x))

при x_{} возрастающем от a_{} к b_{}, будет меняться когда x_{} проходит через корень какого-либо полинома системы. Доказывается, что это число может разве лишь уменьшаться, и уменьшается на единицу тогда и только тогда, когда x_{} проходит через корень начального полинома системы, т.е. через корень f(x_{}).

Т

Теорема [Штурм]. Если f(a)\ne 0, \ f(b)\ne 0, и система f_0(x), f_1(x),\dots, f_K(x) является системой полиномов Штурма для f(x_{}), то

\operatorname{nrr} \{f(x)=0 \mid a<x<b \}= {\mathcal V}_a - {\mathcal V}_b=
={\mathcal V}(f_0(a), f_1(a),\dots, f_K(a))- {\mathcal V}(f_0(b), f_1(b),\dots, f_K(b)) \ .

Самый распространненный способ построение системы полиномов Штурма основан на алгоритме Евклида нахождения наибольшего общего делителя полинома f(x_{}) и его производной f'(x_{}). Предположим, что f(x_{}) не имеет кратных корней. Это равносильно тому, что \operatorname{HOD} (f(x),f'(x))= const \ne 0 (см. ЗДЕСЬ ). Установить этот факт можно по алгоритму Евклида нахождения \operatorname{HOD}. Оказывается, что в качестве полиномов системы Штурма можно взять последовательность остатков из алгоритма Евклида, если только домножить некоторые из них на (-1). Именно, возьмем

f_1(x) \equiv f'(x) \ .

Поделим f_0(x) \equiv f(x) на f_{1}(x) и обозначим через f_{2}(x) остаток, домноженный на (-1):

f_0(x)\equiv q_1(x) f_1(x)-f_2(x), \quad \deg f_2 < n-1 \ .

Поделим f_1(x) на f_2(x) и обозначим через f_3(x) остаток, домноженный на -1:

f_1(x)\equiv q_2(x) f_2(x)-f_3(x), \quad \deg f_3 < \deg f_2 \ .

Продолжаем алгоритм далее, в конце концов дойдем до последнего ненулевого остатка f_K(x), который совпадает с \operatorname{HOD} (f(x),f'(x)). По предположению, этот последний f_K(x)\equiv const \ne 0.

§

Если на интервале ]a,b_{}[ полином f(x_{}) имеет корень четной кратности, то построение системы полиномов Штурма невозможно.

П

Пример. Отделить корни полинома f (x)=x^4-x-1.

Решение. f_1=f'(x)=4\, x^3-1.

\begin{array}{rrrrrr|l} x^4+ &{}0x^3 +&{}0x^2 &-x &-1 &&\,4\, x^3-1\\ x^{4}+& & & - \frac{\scriptstyle 1}{\scriptstyle 4} x & &&\, \overline{\quad \frac{\scriptstyle 1}{\scriptstyle 4}\, x \quad } \\ \hline & & &- \frac{\scriptstyle 3}{\scriptstyle 4} \, x &-1 \\ \end{array}

Полагаем f_2(x)= \frac{\scriptstyle 3}{\scriptstyle 4} \, x+1.

\begin{array}{rrrrr|l} 4x^3 +&{}0x^2 &+0x &-{}1 &&\frac{\scriptstyle 3}{\scriptstyle 4}\, x+1\\ 4x^3 +&\frac{\scriptstyle 16}{\scriptstyle 3}\, x^2 & & & & \overline{ \frac{\scriptstyle 16}{\scriptstyle 3}\,x^{2}-\frac{\scriptstyle 64}{\scriptstyle 9}\, x+ \frac{\scriptstyle 256}{\scriptstyle 27}} \\ \hline &-\frac{\scriptstyle 16}{\scriptstyle 3}\, x^{2} & &{}-1 \\ &-\frac{\scriptstyle 16}{\scriptstyle 3}\, x^2 &-\frac{\scriptstyle 64}{\scriptstyle 9}\, x & \\ \hline & & \frac{\scriptstyle 64}{\scriptstyle 9}\, x & -1 \\ & & \frac{\scriptstyle 64}{\scriptstyle 9}\, x & +\frac{\scriptstyle 256}{\scriptstyle 27} \\ \hline & & & - \frac{\scriptstyle 283}{\scriptstyle 27} \end{array}

Полагаем f_3(x)=\frac{\scriptstyle 283}{\scriptstyle 27}.

x f(x) f_1(x) f_2(x) f_3(x) {\mathcal V}_x Комментарии
-\infty + - - + 2 сначала устанавливаем
+\infty + + + + 0 число вещественных корней,
0 - - + + 1 затем положительных и отрицательных,
-1 + - + + 2 затем просто дробим
1 - + + + 1 промежутки, отыскивая такие,
2 + + + + 0 чтобы на каждом {\mathcal V}_a-{\mathcal V}_b=1

Ответ. Полином f(x_{}) имеет два различных вещественных корня, один на интервале ]-1,0_{}[, другой — на ]1,2_{}[.

Упрощающие соображения

Иногда построение системы полиномов Штурма упрощается различными соображениями.

П

Пример. Полиномы Лежандра

P_0(x)=1,\ P_1(x)= x,\ P_2(x)=\frac{1}{2}(3\,x^2-1),\ P_3(x)= \frac{1}{2}( 5\,x^3-3\, x),\ P_4(x)= \frac{1}{8}(35\,x^4-30\, x^2+3),\dots
P_n(x)=\frac{1}{2^n} \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{(-1)^k(2n-2k)!}{k!(n-k)!(n-2k)!} x^{n-2k}

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

kP_{k}(x)-(2k-1)\,xP_{k-1}(x)+(k-1)\,P_{k-2}(x) \equiv 0 \quad npu \quad k\ge 2

позволяет сделать вывод, что для полинома P_{n}(x) системой полиномов Штурма может быть взята P_{n-1}(x),P_{n-2}(x),\dots,P_0(x). Оказывается, что все n_{} корней полинома P_{n}(x) вещественны, различны и расположены на интервале ]-1,1[.

Обобщенная система полиномов Штурма

Ганкелевы матрицы в теории локализации корней

§

Раздел «Ганкелевы матрицы, определители и полиномы» ЗДЕСЬ

Для полинома f(x)_{} его k_{}суммой Ньютона называется сумма k_{}-х степеней его корней

s_k=\sum_{j=1}^n\lambda_j^k \ .

Суммы Ньютона выражаются рационально через коэффициенты полинома f_{}(x) посредством следующих рекуррентных формул Ньютона:

s_0=n,\ s_1=-a_1/a_0,
s_k=\left\{\begin{array}{lr} -(a_1s_{k-1}+a_2s_{k-2}+\dots+a_{k-1}s_1+a_kk)/a_0, &npu \ k\le n ;\\ -(a_1s_{k-1}+a_2s_{k-2}+\dots+a_ns_{k-n})/a_0, &npu \ k > n \end{array} \right.

Явное выражение сумм Ньютона через a_0, \dots, a_{n} дается формулой Варинга; однако она неудобна при реальных расчетах.

Вычислим суммы Ньютона s_0,s_{1},\dots,s_{2n-2} полинома f_{}(x) и составим из них ганкелеву матрицу

S=\left[s_{j+k} \right]_{j,k=0}^{n-1} = \left[\begin{array}{llllll} s_0 &s_1&s_2&\dots&s_{n-2}& s_{n-1}\\ s_1 &s_2&s_3&\dots&s_{n-1}& s_{n}\\ s_2 &s_3&s_4&\dots&s_{n}& s_{n+1}\\ \dots& & &&& \dots\\ s_{n-1} &s_n&s_{n+1}&\dots &s_{2n-3}&s_{2n-2} \end{array}\right]_{n\times n} \ .

Обозначим S_1,\dots, S_{n} ее главные миноры.

Т

Теорема [Якоби].3) Число различных корней полинома f_{}(x) равно рангу, а число различных вещественных корней f_{}(x) сигнатуре матрицы S_{}.

Конструктивное вычисление ранга и сигнатуры симметричной (точнее, ганкелевой) матрицы S_{} возможно посредством определения знаков ее главных миноров S_{1},\dots,S_n.

=>

Пусть

S_n=0,\dots,S_{{\mathfrak r}+1}=0,S_{\mathfrak r}\ne 0, \dots, S_1 \ne 0 \ .

Тогда \operatorname{rank} (S)={\mathfrak r} и число различных вещественных корней f(x) равно

{\mathcal P}(1,S_1,\dots,S_{\mathfrak r}) -{\mathcal V}(1,S_1,\dots,S_{\mathfrak r}) \ ,

где {\mathcal P}_{}число знакопостоянств и {\mathcal V}_{}число знакоперемен.

=>

Определитель матрицы S_{} фактически совпадает с дискриминантом полинома f_{}(x):

S_n=\det S = {\mathcal D}(f)/a_0^{2n-2} \ .

П

Пример. Определить число вещественных корней полинома x^5-3\,x^3-x-1.

Решение. Суммы Ньютона:

\{s_j \}_{j=0}^8=\{5,\, 0,\, 6,\, 0,\, 22,\, 5,\, 72,\, 21,\,238 \} \ .
S= \left[ \begin{array}{rrrrr} 5 & 0 & 6 & 0 & 22 \\ 0 & 6 & 0 & 22 & 5 \\ 6 & 0 & 22 & 5 & 72 \\ 0 & 22 & 5 & 72 & 21 \\ 22 & 5 & 72 & 21 & 238 \end{array} \right] \ .

Главные миноры:

S_1=5,\, S_2=30,\, S_3=444,\, S_4=-4598,\, S_5=-56\,123 \ .

Поскольку S_5\ne 0, все корни f_{}(x) различны.

{\mathcal P}(1,\,5,\,30,\,444,\,-4598,\,-56\,123)=4,\ {\mathcal V}(1,\,5,\,30,\,444,\,-4598,\,-56\,123)=1 .

Ответ. Три вещественных корня.

Идею, использованную при доказательстве теоремы Якоби можно развить и для задачи отделения корней f_{}(x). Для этого вычислим дополнительно еще одну сумму Ньютона s_{2n-1} и составим следующую ганкелеву матрицу, зависящую от параметра t_{}:

H(t)=\left[ s_{j+k}t-s_{j+k+1} \right]_{j,k=0}^{n-1} =\left[ \begin{array}{llll} s_0t-s_1&s_1t-s_2&\dots& s_{n-1}t-s_{n} \\ s_1t-s_2&s_2t-s_3&\dots& s_{n}t-s_{n+1} \\ \dots & & & \dots \\ s_{n-1}t-s_{n} & s_{n}t-s_{n+1} & \dots & s_{2n-2}t-s_{2n-1} \end{array} \right]_{n\times n} \ .

Легко видеть, что матрица, составленная из коэффициентов при t_{} совпадает с матрицей S_{} из теоремы Якоби. Обозначим \ell_{}-й главный минор матрицы H(t) через H_{\ell}(t):

H_{\ell}(t)=\det \left[s_{j+k}t-s_{j+k+1} \right]_{j,k=0}^{{\ell}-1} \ .

Можно получить (см. прием ЗДЕСЬ ) иное детерминантное представление для H_{\ell}(t) — в виде определителя порядка \ell+1, в котором параметр t_{} оказывается «выметенным» в последнюю строку:

H_{\ell}(t)\equiv \left| \begin{array}{lllll} s_0&s_1&\dots&s_{{\ell}-1}& s_{\ell} \\ s_1&s_2&\dots&s_{\ell}& s_{\ell+1} \\ \vdots & && \vdots & \vdots \\ s_{\ell-1}&s_{\ell}&\dots&s_{2\ell-2}&s_{2\ell-1} \\ 1 & t & \dots & t^{\ell-1} & t^{\ell} \end{array} \right| \ .

Разложение по этому столбцу позволит получить каноническую форму полинома \mathcal H_{\ell}(t). Заметим, что

\mathcal H_{n}(t)=\det H(t) \equiv S_n f(t)/a_0 \ .
Т

Теорема [Йоахимшталь].4) Пусть \operatorname{rank} (S)={\mathfrak r}. Тогда

\operatorname{nrr} \{ f(x)=0 \mid a <x < b \} ={\mathcal V}(1,\mathcal H_1(a),\dots,\mathcal H_{\mathfrak r}(a))- {\mathcal V}(1,\mathcal H_1(b),\dots,\mathcal H_{\mathfrak r}(b)),

при условии, что в ряду

1,\mathcal H_1(t),\dots,\mathcal H_{\mathfrak r}(t)

нет двух последовательных нулей при t=a и t=b.

§

В случае, когда в ряду встречаются несколько подряд идущих нулей (например, f(x)=x^4-1, a=0), то можно воспользоваться правилом Кронекера-Хатендорфа:

\operatorname{nrr} \{ f(x)=0 \mid a <x < b \} =\frac{1}{2}\sum_{k=1}^{\mathfrak r} \{\operatorname{sign} ( \mathcal H_{k-1}(b)\mathcal H_{k}(b))- \operatorname{sign} (\mathcal H_{k-1}(a)\mathcal H_{k}(a)) \}.

Таким образом система полиномов \{\mathcal H_{\ell}(t)\}_{{\ell}=1}^{\mathfrak r} играет роль системы полиномов Штурма для полинома f(x)_{}. В отличие от классической системы полиномов Штурма, построенной с помощью алгоритма Евклида, здесь степени полиномов \mathcal H_{\ell}(t) возрастают при возрастании \ell_{}.

П

Пример. Локализовать вещественные корни полинома

f(x)=x^4-x^3-9\,x^2+14\,x-4 \ .

Решение. Вычисляем суммы Ньютона:

\{s_k\}_{k=0}^{7}=\{4,\ 1,\ 19,\ -14,\ 159,\ -229,\ 1474,\ -2869\}

и строим последовательность миноров из теоремы:

\mathcal H_1(t)=4\,t-1,\ \mathcal H_2(t)=75(t^2+t-5),\ \mathcal H_3(t)= 1250(3\,t^3-26\,t+17),\ \mathcal H_4(t)=62500\, f(t) \ .

Вычисляем числа знакоперемен в нескольких узлах:

t 1 \mathcal H_1(t) \mathcal H_2(t) \mathcal H_3(t) \mathcal H_4(t) {\mathcal V}_t
-\infty + - + - + 4
+\infty + + + + + 0
0 + - - + - 3
-4 + - + - + 4
-3 + - + + - 3
1 + + - - + 2
2 + + + - - 1
3 + + + + + 0

Ответ. Полином f_{}(x) имеет 4_{} различных вещественных корня, лежащие на интервалах ]-4,-3[,\ ]0,1[,\ ]1,2[, \ ]2,3[.

Проверка. \lambda_1 \approx -3.2360,\ \lambda_2 \approx 0.3819,\ \lambda_3 \approx 1.2360,\ \lambda_4 \approx 2.6180.

$

Как последняя теорема связана с $ ? ;-)

§

Фактическое построение ганкелевых полиномов из теоремы производится не непосредственным вычислением соответствующих определителей, зависящих от параметра (эта процедура весьма затратна), а посредством применения рекурсивной формулы — тождества Якоби-Йоахимшталя (JJ-тождества), приведенного ЗДЕСЬ.

=>

Матрицу из теоремы Йоахимшталя можно представить в виде комбинации двух ганкелевых матриц: H(t)=t\cdot S - \tilde S, где матрица S_{} — из теоремы Якоби, а

\tilde S = \left[s_{j+k+1} \right]_{j,k=0}^{n-1} = \left[\begin{array}{llllll} s_1 &s_2&s_3&\dots&s_{n-1}& s_{n}\\ s_2 &s_3&s_4&\dots&s_{n}& s_{n+1}\\ s_3 &s_4&s_5&\dots&s_{n+1}& s_{n+2}\\ \dots& & &&& \dots\\ s_{n} &s_{n+1}&s_{n}&\dots &s_{2n-2}&s_{2n-1} \end{array}\right]_{n\times n} \ .

Если обозначить главные миноры матрицы \tilde S через \tilde S_1, \tilde S_2,\dots, \tilde S_n, то число различных положительных корней полинома f_{}(x) вычисляется по формуле

\operatorname{nrr} \{ f(x)=0 \mid x > 0 \} = {\mathcal P}(1,\tilde S_1,\dots, \tilde S_{\mathfrak r}) -{\mathcal V}(1,S_1,\dots,S_{\mathfrak r}) \ ,

где {\mathfrak r}= \operatorname{rank} (S), и дополнительно предполагается, что все числа в рядах — ненулевые. В частности, для того, чтобы все корни полинома f_{}(x) были различными и положительными необходимо и достаточно, чтобы все главные миноры матриц S_{} и \tilde S были положительными.

!

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

Рассмотрим произвольный полином g(x)=b_0 x^m+ \dots + b_m, b_0\ne 0 с вещественными коэффициентами. Вычислим величины

h_k=\sum_{j=1}^ng(\lambda_j)\lambda_j^k=b_0s_{k+m}+b_1s_{k+m-1}+\dots+b_ms_{k} , \ npu \ k\in \{ 0,\dots,2n-2\} \ ;

здесь, по-прежнему, s_{\ell} означает сумму Ньютона полинома f_{}(x). По аналогии с построенной выше матрицей S_{}, cоставим из этих величин ганкелеву матрицу

H=\left[h_{j+k} \right]_{j,k=0}^{n-1} = \left[\begin{array}{llllll} h_0 &h_1&h_2&\dots&h_{n-2}& h_{n-1}\\ h_1 &h_2&h_3&\dots&h_{n-1}& h_{n}\\ h_2 &h_3&h_4&\dots&h_{n}& h_{n+1}\\ \dots& & &&& \dots\\ h_{n-1} &h_n&h_{n+1}&\dots &h_{2n-3}&h_{2n-2} \end{array}\right]_{n\times n} \ .

Обозначим H_1,\dots, H_n ее главные миноры.

Т

Теорема [Эрмит, Сильвестр]. Пусть полиномы f_{}(x) и g_{}(x) не имеют общих корней, т.е. их результант {\mathcal R}(f,g)\ne 0. Тогда число различных вещественных корней f_{}(x), удовлетворяющих условию g_{}(x) > 0 определяется по формуле

\operatorname{nrr} \{ f(x)=0 \mid g(x) > 0 \}=n_+(H)-n_{-}(S) \ .

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

=>

Имеет место соотношение

H_n=\det\, H =S_n \prod_{1\leq j \leq n}g(\lambda_j)={\mathcal R}(f,g)S_n/a_0^m

и f_{}(x) не имеет кратных корней тогда и только тогда, когда S_n \ne 0. При выполнении последнего условия, {\mathcal R}(f,g)\ne 0 тогда и только тогда, когда H_n \ne 0, что и дает возможность проверить условие предположения теоремы Эрмита-Сильвестра без предварительных вычислений.

П

Пример. Определить число вещественных корней полинома f(x)= x^5+4\,x^4-2\,x -2, удовлетворяющих неравенству g(x)=x^3-x^2+1 > 0.

Решение. Вычисляем суммы Ньютона полинома f_{}(x) (в количестве 2\deg f+\deg g -1):

\{s_k\}_{k=0}^{11}=\{5,\ -4,\ 16,\ -64,\ 264,\ -1054,\ 4240,\ -17056,\, 68624,\ -276076,\, 1110676,\ - 4468336 \} \ .

Составляем ганкелеву матрицу S=\left[s_{j+k} \right]_{j,k=0}^4 и вычисляем ее главные миноры:

\{S_j\}_{j=1}^5=\{5,\, 64,\, 512,\, -60160,\, -2375600 \} \ .

Отрицательный индекс инерции матрицы S_{} вычисляется как число знакоперемен:

n_{-}(S)=\mathcal V (1,S_1,S_2,S_3,S_4,S_5) = 1 \ .

Далее вычисляем величины h_{k} (в количестве 2\deg f -1):

\{h_k\}_{k=0}^{8}=\{-75,\ 324,\ -1302,\ 5230,\ -21032,\ 84626,\ -340460,\ 1369696,\, -5510388 \} \ .

Составляем ганкелеву матрицу H=\left[h_{j+k} \right]_{j,k=0}^4 и вычисляем ее главные миноры:

\{H_j\}_{j=1}^5=\{-75,\, -7326,\, 173460,\, 23423800,\, 201926000 \} \ .

Поскольку H_5 \ne 0, полиномы f_{}(x) и g_{}(x) не имеют общих корней. Вычисляем положительный индекс инерции матрицы H_{} как число знакопостоянств:

n_{+}(H)=\mathcal P (1,H_1,H_2,H_3,H_4,H_5) = 3 \ .

По теореме Эрмита-Сильвестра, имеем

\operatorname{nrr} \{ f(x)=0 \mid g(x) > 0 \}=3-1=2 \ .

Ответ. 2

Проверка. Вещественные корни полинома f_{}(x):

\lambda_1 \approx -4.0230 \ (g<0), \ \lambda_2 \approx 0.9415 \ (g>0),\ \lambda_3 \approx -0.6680 \ (g>0) \ .

Формула Маркова

Результат теоремы Эрмита-Сильвестра можно распространить на случай когда требуется определить число вещественных корней f_{}(x), удовлетворяющих системе неравенств g_1(x)>0,g_2(x)>0,\ldots,g_K(x)>0, где все полиномы имеют вещественные коэффициенты.

Т

Теорема [Марков,[6]].5) Если ни один из полиномов g_j(x) не имеет общих корней с f_{}(x) (т.е. результант {\mathcal R}(f,g_j)\ne 0), то справедлива следующая формула:

\operatorname{nrr}\{ f=0 \mid g_1>0,\dots ,g_K>0\}=
=\frac{1}{2^{K-1}}\Big[(1-2^{K-1})\operatorname{nrr}\{ f=0\}+ \sum_{1\le j_1\le K} \operatorname{nrr}\{ f=0\mid g_{j_1}>0\} +\sum_{1\le j_1<j_2\le K} \operatorname{nrr}\{f=0 \mid g_{j_1}g_{j_2}>0\}+
+\sum_{1\le j_1<j_2<j_3\le K} \operatorname{nrr}\{ f=0 \mid g_{j_1}g_{j_2}g_{j_3}>0\} +\dots +\operatorname{nrr}\{ f=0 \mid g_1g_2\times\ldots \times g_K>0\} \Big] \ .

§

Каждое слагаемое в правой части формулы Маркова можно вычислить, используя теорему Эрмита-Сильвестра. Можно упростить вычисления, используя различные соображения. Если, к примеру, какое-то из слагаемых в правой части формулы обращается в нуль, то и искомое число вещественных корней также равно нулю — независимо от величины оставшихся слагаемых.

Корни в области |z| <1

Устойчивость

Локализация собственных чисел матрицы

Для квадратной матрицы A определитель

\det (A- \lambda E)

называется характеристическим полиномом этой матрицы; его корни называются собственными числами этой матрицы, а полный их набор (с учетом кратностей) — спектром матрицы.

Задача. Найти собственные числа матрицы A.

§

Подробнее о характеристическом полиноме, собственных числах и их приложениях ЗДЕСЬ.

Для матрицы порядка n_{} ее характеристический полином имеет степень n_{} относительно6) \lambda

(-1)^n \lambda^n +a_1\lambda^{n-1} + \dots +a_n \ ;

а его коэффициенты полиномиально зависят от элементов матрицы. Можно выписать явное представление a_1,\dots a_n с помощью миноров матрицы (см. ЗДЕСЬ ). Так, к примеру, для A =\left[a_{jk} \right]_{j,k=1}^n имеем:

a_1=(-1)^{n-1} (a_{11}+a_{22}+\dots+a_{nn}), a_n = \det A \ ,

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

Теорема Гершгорина

Т

Теорема [Гершгорин]. Обозначим \mathbb D_j круг на комплексной плоскости \mathbb C с центром в точке a_{jj} и радиуса

r_j=\sum_{\ell\ne j} \left|a_{j \ell}\right| \ .

Тогда собственные числа матрицы A лежат внутри объединения этих кругов:

\{\lambda_1,\dots, \lambda_n \} \subset \bigcup_{j=1}^n \mathbb D_j .

П

Пример. Построить круги Гершгорина для матрицы

A=\left( \begin{array}{crr} -1+3\,{\mathbf i} & 2- {\mathbf i} & 3+2\, {\mathbf i} \\ -1+{\mathbf i} & 4+ {\mathbf i} & 3\, {\mathbf i} \\ -1& 2-2\,{\mathbf i}& -2-3\, {\mathbf i} \end{array} \right) .

Решение.

|\lambda + 1 - 3\,{\mathbf i} |\le | 2-{\mathbf i} |+| 3+2\,{\mathbf i} |=\sqrt{5}+\sqrt{13},\ |\lambda - 4 - {\mathbf i} |\le 3+\sqrt{2},\ |\lambda + 2+ 3\, {\mathbf i} |\le 1 + 2\sqrt{2} \ .

Проверка. Собственные числа матрицы A (на рисунке обозначены красными крестиками):

\{ -2.509081750-3.442241533\,{\mathbf i} ,\ -1.041999986+2.655757676\,{\mathbf i} ,\ 4.551081736+1.786483857\, {\mathbf i} \} .

Симметричные матрицы

Т

Теорема. Собственные числа вещественной симметричной матрицы A_{} все вещественны.

Доказательство ЗДЕСЬ.

Т

Теорема [Коши]. Для вещественной симметричной матрицы A_{} число ее собственных чисел, лежащих на интервале ]a,b_{}[, определяется по формуле:

\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ a< \lambda<b \}= {\mathcal P}(1, H_1(a), H_2(a),\dots, H_n(a))- {\mathcal P}(1, H_1(b), H_2(b),\dots, H_n(b)) \ .

Здесь H_1(\lambda), H_2(\lambda),\dots, H_n(\lambda)главные миноры матрицы A-\lambda\, E, а {\mathcal P}_{}число знакопостоянств.

Согласно этой теореме, главные миноры матрицы A-\lambda\, E играют роль системы полиномов Штурма для характеристического полинома симметричной матрицы A_{}.

=>

Если все главные миноры A_1,A_2,\dots,A_{n} симметричной матрицы A_{} отличны от нуля, то число положительных собственных чисел матрицы A_{} равно числу знакопостоянств, а число отрицательных собственных чисел — числу знакоперемен в ряду 1,A_1,\dots,A_n:

\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ \lambda>0 \} = {\mathcal P}(1,A_1,\dots,A_n), \quad \operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ \lambda<0 \}={\mathcal V}(1,A_1,\dots,A_n) \ .

П

Пример. Локализовать собственные числа матрицы

\left( \begin{array}{rrr} 11 & 2 & -8 \\ 2 & 2 & 10 \\ -8 & 10 & 5 \end{array} \right)

Решение.

H_1(\lambda)=11- \lambda, \ H_2(\lambda)=\lambda^2-13\, \lambda+18, \ f(\lambda)= H_3(\lambda)=-\lambda^3+18\, \lambda^2 +81\, \lambda -1458 \ .
\lambda 1_{} H_1(\lambda) H_2(\lambda) H_3(\lambda) {\mathcal P} Комментарии
0_{} + + + - 2 число положительных =2
-10 + + + + 3 собственное число
-5 + + + - 2 лежит на ]-10,-5[
5 + + - - 2 собственное число
10 + + - + 1 лежит на ]5,10[
15 + - - + 1 собственное число
20 + - + - 0 лежит на ]15,20[

Проверка. Спектр матрицы: \{-9,9,18 \}.

П

Пример. Локализовать собственные числа матрицы

\left( \begin{array}{rrr} 1 & -2 & 2 \\ -2 & -2 & 4 \\ 2 & 4 & -2 \end{array} \right) \ .

Решение.

H_1(\lambda)=1- \lambda, \ H_2(\lambda)=\lambda^2+\, \lambda-6, \ f(\lambda)=H_3(\lambda)=-\lambda^3-3\, \lambda^2 +24\, \lambda -28 \ .
\lambda_{} 1_{} H_1(\lambda) H_2(\lambda) H_3(\lambda) {\mathcal P} Комментарии
0_{} + + - - 2 число положительных =2
-8 + + + + 3 собственное число
-6 + + + - 2 лежит на ]-8,-6[
1.5 + - - - 2 два собственных числа
3_{} + - + - 0 лежат на ]1.5,3[

Никаким дроблением интервала ]1.5\, , \, 3[ не удается отделить два вещественных собственных числа. Вывод: имеется кратное собственное число.

Проверка. Спектр матрицы: \{-7,2,2 \}.

Решение системы неравенств

Идея

П

Пример. Решить неравенство f(x)= x^4-x^3-3\,x^2-4\,x-2>0.

Решение. Полином удается разложить на множители

f(x)\equiv (x-(1-\sqrt{3}))(x-(1+\sqrt{3}))(x^2+x+1) \ ,

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

Ответ. x \in ]-\infty, 1-\sqrt{3}[ \ \bigcup \ ]1+\sqrt{3},+\infty [.

Вспомним, что обычным школьным методом решения неравенства вида

(x-\lambda_1)\times \dots \times (x-\lambda_s) > 0

при различных вещественных \lambda_1, \dots, \lambda_s является метод интервалов. Этот метод естественным образом распространяется и на вещественные полиномы, имеющие мнимые корни: если

f(x) \equiv (x-\lambda_1)\times \dots \times (x-\lambda_s)f_1(x)

при \{\lambda_1, \dots, \lambda_s \} \subset \mathbb R и полиноме f_1(x) не имеющем вещественных корней, то f_1(x) будет иметь один и тот же знак при всех значениях x \in \mathbb R и, следовательно границами интервалов, составляющих множество решений неравенства f(x)>0 будут только вещественные корни полинома f(x).

Исключение представляет случай наличия кратных корней у полинома f(x).

Рассмотрим систему

g_1(x)>0, g_2(x)>0,\ldots ,g_K(x)>0.

вещественных полиномиальных неравенств. Если ее множество решений \mathbb S \subset \mathbb R непусто, то оно состоит из конечного числа составляющих интервалов одного из следующий типов

]-\infty ,+\infty [,\ ]-\infty ,\alpha [, ]\beta ,+\infty [,\ ]\gamma ,\delta [\ .

В граничных точках \alpha ,\beta ,\gamma и \delta некоторые из этих неравенств обращаются в равенства, а остальные неравенства продолжают оставаться справедливыми. Это свойство граничной точки послужит основой алгоритма проверки совместности системы, который мы разовьем в последующих пунктах; а также позволит определить структуру множества решений \mathbb S.

Совместность

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

Предположение 1. Пусть полиномы g_1,\ldots ,g_K не имеют общих корней, т.е. \mathcal R(g_j,g_k)\ne 0 для всех 1\le j<k \le K. Здесь \mathcal R означает результант рассматриваемых полиномов.

Предположение 2. Пусть полиномы g_1,\ldots ,g_K не имеют кратных корней, т.е. \mathcal D(g_j)\ne 0 для всех 1\le j \le K. Здесь \mathcal D означает дискриминант рассматриваемого полинома.

Т

Теорема. При выполнении условий предположений 1 и 2 система неравенств будет совместна тогда и только тогда, когда выполнено хотя бы одно из следующих условий:

a) g_1(0)>0,\ldots ,g_K(0)>0;

b) существует хотя бы один индекс j\in \{ 1,\dots,K \} такой, что уравнение g_j(x)=0 имеет вещественный корень, удовлетворяющий системе неравенств g_1(x)>0,\ldots ,g_{j-1}(x)>0, g_{j+1}(x)>0, \ldots , g_K(x)>0, т.е.

\operatorname{nrr} \{ g_j=0\mid g_1>0,\ldots ,g_{j-1}>0,g_{j+1}>0,\ldots ,g_K>0\}>0.

Условие пункта b) теоремы можно проверить по теореме Эрмита-Сильвестра с использованием формулы Маркова.

П

Пример. Исследовать на совместность систему

\begin{array}{ccl} g_1(x) &=& x^5+4x^4-2x-2>0, \\ g_2(x) &=& x^4+4\,x^3-4\,x^2-16\,x-8>0, \\ g_3(x) &=& -x^5+4\,x^4-2\,x^3+6\,x-5>0, \\ g_4(x) &=& x^4+5\,x^3+11\,x^2+12\,x+6>0. \end{array}

Решение. Мы приведем подробные (и избыточные) вычисления, имея в виду их использование в следующем пункте. Условие a) теоремы не выполнено. Проверим условие b). Определим сначала число различных вещественных корней полиномов системы по теореме Якоби. Найдем суммы Ньютона. Для g_1(x) получаем7):

\{ s_k\}_{k=0}^{12} = \{5; \, -4;\, 16; \dots ; -4\,468\, 336;17\, 976\, 480\} \ .

Рекомендация 1. В общем случае, для полинома g_j(x) достаточно найти 3(\deg g_j(x)-1) сумм Ньютона (см. далее рекомендацию 5).

Главные миноры матрицы S: ( S_0 полагаем равным 1):

\{ S_k\}_{k=0}^5=\{ 1;5;64;512;-60\, 160;-2\, 375\, 600\}.

Аналогичную процедуру проделываем с остальными полиномами системы. Для g_2(x):

\{ s_k\}_{k=0}^9= \{ 4;-4;24;-64;320;-1184;5184;-20\, 864;87\ 808;-361\, 216\},
\{ S_k\}_{k=0}^4=\{ 1;4;80;7680;147\, 456\};

для g_3(x):

\{ s_k\} _{k=0}^{12}= \{5;4;12;40;160;\dots; 1\, 088\, 300;3\, 850\, 696\},
\{ S_k\} _{k=0}^5=\{ 1;5;44;1152;-265\ 388;-14\ 940\ 251\};

для g_4(x):

\{ s_k\}_{k=0}^9=\{ 4;-5;3;4;-17;35;-54;65;-49;-32\},
\{ S_k\}_{k=0}^4=\{ 1;4;-13;10;12\}.

По теореме Якоби полиномы системы не имеют кратных корней и

\operatorname{nrr} \{ g_1=0\} =3,\ \operatorname{nrr} \{ g_2=0\} =4,\ \operatorname{nrr} \{ g_3=0\} =3,\ \operatorname{nrr} \{ g_4=0\} =0\ .

Поскольку g_4(x) не имеет вещественных корней и g_4(0)>0, то неравенство g_4(x)>0 выполняется для всех x\in \mathbb R и, значит, не влияет на совместность системы неравенств.

Рекомендация 2. Если полином g_j(x) не имеет вещественных корней, (т.e. \operatorname{nrr} \{ g_j=0\} =0), то система неравенств несовместна при g_j(0)<0. Если же g_j(0)>0, то неравенство g_j(x)>0 может быть удалено из исходной системы.

В дальнейшем рассматриваем систему примера без неравенства g_4(x)>0. Условие

\operatorname{nrr} \{ g_j=0\mid g_1>0,\ldots ,g_{j-1}>0,g_{j+1}>0,\ldots ,g_K>0\}>0

проверяем с помощью формулы Маркова и теоремы Эрмита-Сильвестра. Возьмем в этой формуле j=1.

\operatorname{nrr} \{ g_1=0\mid g_2>0,g_3>0\}=
={1\over 2}[- \operatorname{nrr} \{ g_1=0\} +\operatorname{nrr} \{ g_1=0\mid g_2>0\} + \operatorname{nrr} \{ g_1=0\mid g_3>0\}+ \operatorname{nrr} \{ g_1=0\mid g_2g_3>0\} ].

Ранее установлено, что \operatorname{nrr} \{g_1=0\} =3, определим теперь число \operatorname{nrr} \{ g_1=0\mid g_2>0\}. Вычислим элементы матрицы H из теоремы Эрмита-Сильвестра по формуле: h_k=s_{k+4}+4s_{k+3}-4s_{k+2}-16s_{k+1}-8s_k, где значения s_k вычислены выше.

\{ h_k\}_{k=0}^8=\{ -32;34;-136;408;-1808;7236;-29\, 148;117\, 136; -471\, 344\}

Главные миноры матрицы H ( H_0=1):

\{ H_k\}_{k=0}^5=\{ 1;-32;3196;-1\, 709\ 248;-2\, 646\, 578\, 880;7\, 867\ 987\, 200\}.

По формуле теоремы Эрмита-Сильвестра имеем: \operatorname{nrr} \{ g_1=0\mid g_2>0\} =0. Значит, полином g_1(x) не имеет вещественных корней, удовлетворяющих g_2(x)>0, следовательно, он не имеет вещественных корней, удовлетворяющих системе неравенств g_2(x)>0, g_3(x)>0, т.e. \operatorname{nrr} \{ g_1=0\mid g_2>0,g_3>0\} =0.

Рекомендация 3. Если для индекса j найдется хотя бы один индекс k\ne j (1\le j,k \le K) такой, что \operatorname{nrr} \{ g_j=0\mid g_k>0\} =0, то для такого j условие b) теоремы выполнено не будет.

Эту рекомендацию можно обобщить.

Рекомендация 4. Если для какого-то индекса j\in \{ 1,\dots,K \} найдется набор из k различных индексов \{ j_1,j_2,\ldots ,j_k\} \in \{ 1,\dots,K \} \setminus \{ j\} такой, что

\operatorname{nrr} \{ g_j=0\mid g_{j_1}g_{j_2}\ldots g_{j_k}>0\} =0,

то для такого j условие b) теоремы выполнено не будет.

Пусть теперь j=2.

\operatorname{nrr} \{g_2=0\mid g_1>0,g_3>0\} ={1\over 2} [-4+ \operatorname{nrr} \{ g_2=0\mid g_1>0\}+ \operatorname{nrr} \{ g_2=0\mid g_3>0\} + \operatorname{nrr} \{ g_2=0\mid g_1g_3>0\} ] \ .

Имеем \deg g_1>\deg g_2; поделим g_1 на g_2.

Рекомендация 5. При вычислении \operatorname{nrr} \{ g_j=0\mid g_k>0\} в случае \deg g_k \geq \deg g_j можно разделить сначала g_k на g_j, так как

\operatorname{nrr} \{ g_j=0\mid g_k>0\} =\operatorname{nrr} \{ g_j=0\mid \tilde{g}_{kj} >0\}

где \tilde{g}_{kj} — остаток от деления g_k на g_j. Возможно также сохранять эти остатки для дальнейших вычислений:

\operatorname{nrr} \{ g_j=0\mid g_kg_{\ell}>0\} = \operatorname{nrr} \{ g_j=0 \mid \tilde{g}_ {k\ell} \tilde{g}_{\ell j} >0\}= \operatorname{nrr} \{ g_j=0\mid \tilde{g}_{(k \ell)j}>0\}

Здесь \tilde{g}_{(k \ell )j} — остаток от деления g_kg_{\ell} на g_j — совпадает с остатком от деления \tilde{g}_{kj}\tilde{g}_{\ell j} на g_j.

На основании последней рекомендации имеем:

\operatorname{nrr} \{ g_2=0\mid g_1>0\} = \operatorname{nrr} \{ g_2=0\mid \tilde{g}_{12}\equiv 4x^3+ 16x^2+6x-2>0 \} = \operatorname{nrr} \{ g_2=0\mid 2x^3+8x^2+3x-1>0\}

Для этого числа матрица H из теоремы Эрмита-Сильвестра имеет элементы:

\{ h_k\}_{k=0}^6=\{48;204;-24;1920;-4128;25\, 440;-87\, 744\}

и ее главные миноры равны:

\{ H_k\}_{k=0}^4=\{ 1;48;-42\,768;-19\,187\,712;-30\, 523\, 392\} \ .

По формуле из теоремы Эрмита-Сильвестра : \operatorname{nrr} \{ g_2=0\mid g_1>0\} =3. Аналогично, используя рекомендацию 5, можем найти что

\operatorname{nrr} \{ g_2=0\mid g_3>0\} = \operatorname{nrr} \{ g_2=0\mid -38x^3+16x^2+126x+59>0\} =3

и, тем же приемом

\operatorname{nrr} \{ g_2=0\mid g_1g_3>0\} = \operatorname{nrr} \{ g_2=0\mid (4x^3+16x^2+6x-2)(-38x^3+16x^2+126x+59)>0\}=
= \operatorname{nrr} \{ g_2=0\mid 1576x^3+148x^2-4698x-2774>0\} =2.

Итак, \operatorname{nrr} \{ g_2=0\mid g_1>0,g_3>0\} =2 и, согласно теореме, система неравенств совместна.

Рекомендация 6. Предварительная проверка предположений 1 и 2 для полиномов системы неравенств не обязательна, так как ее можно произвести в ходе проверки условия теоремы. Действительно, по следствию к теореме Якоби предположение 2 будет выполнено если определитель соответствующей матрицы S из теоремы Якоби отличен от нуля; если же, вдобавок, отличен от нуля определитель матрицы H из теоремы Эрмита-Сильвестра (при f=g_j,g=g_k), то — согласно следствию к этой теореме — будет выполнено и предположение 1 .




Статья не закончена!







Определение структуры множества решений

Проблему, поставленную в заглавие, разделим на три.

Задача. Для множества решений \mathbb S системы неравенств

  1. установить число составляющих его интервалов;
  2. установить число составляющих интервалов, лежащих внутри заданного интервала ]a,b[;
  3. установить принадлежит ли заданный интервал ]a,b[ множеству \mathbb S или нет.

Мы будем решать эти задачи в предположениях 1 и 2 . Начнем с третьей.

Т

Теорема 1. При выполнении предположений 1 и 2 , заданный интервал ]a,b[ будет принадлежать \mathbb S тогда и только тогда, когда для любого j\in \{ 1,\dots,K \} будут выполнены оба условия

a) g_j(a)>0, g_j(b)>0;

b) \operatorname{nrr} \{ g_j=0 \mid a<x<b \}=0.

Для решения второй подзадачи рассмотрим число

\operatorname{nrr}_j=\operatorname{nrr} \{ g_j=0 \mid g_1>0, \ldots , g_{j-1}>0, g_{j+1}>0, \ldots, g_K>0 \},

в то время как для первой найдем

\operatorname{nrr}_{j,]a,b[}=\operatorname{nrr} \{ g_j=0 \mid g_1>0, \ldots , g_{j-1}>0, g_{j+ 1}>0, \ldots , g_K>0, a<x<b \}
Т

Теорема 2. При выполнении предположений 1 и 2 , общее число интервалов, составляющих \mathbb S, равно

\frac{1}{2}\left( \sum_{j=1}^K \operatorname{nrr}_j+I \right)

где

I=\left\{ \begin{array}{cl} 0 & npu +\infty \not\in \mathbb S, -\infty \not\in \mathbb S, \\ 1 & npu +\infty \in \mathbb S, -\infty \not\in \mathbb S , u\ npu \ +\infty \not\in \mathbb S, -\infty \in \mathbb S, \\ 2 & npu +\infty \in \mathbb S, -\infty \in \mathbb S. \end{array} \right.

Число составляющих интервалов, лежащих внутри заданного интервала ]a,b[\ (a\not\in \mathbb S,b\not\in \mathbb S,a\ne -\infty,b \ne +\infty ) равно

\frac{1}{2} \sum_{j=1}^K \operatorname{nrr}_{j,]a,b[}.

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

\operatorname{nrr}_j=\operatorname{nrr} \{ g_j=0\mid g_1>0,\ldots ,g_{j-1}>0,g_{j+1}>0,\ldots ,g_K>0\}>0,

и, обратно, любая такая точка служит концом какого-либо составляющего интервала.

Условия теорем можно проверить опять-таки применением теоремы Эрмита-Сильвестра. Проиллюстрируем это, имея целью построение системы полиномов относительно параметра t, которая позволит нам установить число составляющих интервалов в заданном интервале ]a,b[, (т.е., фактически, аналога системы полиномов Штурма). Для этого обратимся к теореме Йоахимшталя и формуле Маркова. Так, имеем:

\operatorname{nrr} \{ f(x)=0 \mid g(x)>0,a<x<b \}= \operatorname{nrr} \{ f(x)=0 \mid g>0,x<b \} - \operatorname{nrr} \{ f(x)=0 \mid g>0,a<x \} =
= {1\over 2} \biggl[ \operatorname{nrr} \{ f=0 \mid a<x<b \} + \operatorname{nrr} \{ f=0 \mid (a-x)g<0 \} - \operatorname{nrr} \{ f=0 \mid (b-x)g<0 \} \biggr] \ .

для произвольных a и b. Первое из чисел в квадратных скобках может быть определено по теореме Йоахимшталя, т.е. с помощью системы полиномов, построенной на основании сумм Ньютона полинома f(x). По аналогии с той теоремой может быть найдена и оставшаяся разность.

Т

Теорема 3. Пусть все корни полинома f(x) простые, отличны от корней g(x) и отличны от a и b. Тогда

\operatorname{nrr} \{ f=0 \mid (a-x)g<0 \} - \operatorname{nrr} \{ f=0 \mid (b-x)g<0 \} ={\mathcal V}(1, \tilde \Delta_1(a),\ldots ,\tilde \Delta_n(a))-{\mathcal V}(1, \tilde \Delta_1(b),\ldots ,\tilde \Delta_n(b))

где {\mathcal V}число знакоперемен,

\tilde \Delta_p(t)=\det [t\,h_{j+k}-h_{j+k+1}]_{j,k=0}^{p-1}= \left| \begin{array}{ccccc} h_0&h_1&\dots&h_{p-1}&1 \\ h_1&h_2&\dots&h_{p}& t \\ \vdots & && & \vdots \\ h_{p}&h_{p+1}&\dots&h_{2p-1}&t^p \end{array} \right| \ ,

и дополнительно предполагается, что в ряду 1,\tilde \Delta_1(t),\tilde \Delta_2(t),\ldots ,\tilde \Delta_n(t) нет двух последовательных нулей при t=a и t=b.

П

Пример. Локализовать множество решений системы

\begin{array}{ccl} g_1(x) &=& x^5+4x^4-2x-2>0, \\ g_2(x) &=& x^4+4\,x^3-4\,x^2-16\,x-8>0, \\ g_3(x) &=& -x^5+4\,x^4-2\,x^3+6\,x-5>0, \\ g_4(x) &=& x^4+5\,x^3+11\,x^2+12\,x+6>0 \end{array}

примера из предыдущего пункта.

Решение. Мы уже установили ВЫШЕ, что для данного примера

\operatorname{nrr}_2=\operatorname{nrr} \{ g_2=0\mid g_1>0,g_3>0\} =2 \ .

Аналогично можно установить, что \operatorname{nrr}_3=2. По теореме 2 множество решений \mathbb S системы неравенств состоит из двух интервалов. Построим теперь набор систем полиномов относительно параметра t, который позволит нам установить число составляющих интервалов внутри произвольного интервала ]a,b[. По формуле Маркова получаем

\operatorname{nrr}_{2,]a,b[}= \operatorname{nrr} \{ g_2=0\mid g_1>0,g_3>0,a<x<b\}=
= {1\over 4} \bigl[\operatorname{nrr} \{ g_2=0\mid a<x<b\}+(\operatorname{nrr} \{ g_2=0\mid (a-x)g_1<0\} - \operatorname{nrr} \{ g_2=0\mid (b-x)g_1<0\} )+
+(\operatorname{nrr} \{ g_2=0\mid (a-x)g_3<0\} -\operatorname{nrr} \{ g_2=0\mid (b-x)g_3<0\} )+
+(\operatorname{nrr} \{ g_2=0\mid (a-x)g_1g_3<0\} -\operatorname{nrr} \{ g_2=0\mid (b-x)g_1g_3<0\}) \bigr]\ .

Для вычисления \operatorname{nrr} \{ g_2=0\mid a<x<b\} построим полиномиальную систему из теоремы Йоахимшталя. Необходимые для этого значения сумм Ньютона s_0,\ldots,s_6,s_7 уже подсчитаны выше. С точностью до положительных констант, получаем следующие полиномы

\Delta_1(t)=t+1, \ \Delta_2(t)=t^2+2t-4, \ \Delta_3(t)=5t^3+15t^2-34t-44, \ \Delta_4(t)\equiv g_2(t).

Для нахождения оставшихся чисел в правой части формулы для \operatorname{nrr}_{2,]a,b[} воспользуемся теоремой 3. Разность

\operatorname{nrr} \{ g_2=0\mid (a-x)g_1<0\} - \operatorname{nrr} \{ g_2=0\mid (b-x)g_1<0\}

на основании рекомендации 5 из предыдущего пункта может быть заменена на

\operatorname{nrr} \{ g_2=0\mid (a-x)\tilde g_{12}<0\} - \operatorname{nrr} \{ g_2=0\mid (b-x) \tilde g_{12}<0\}

где \tilde g_{12}(x)=2x^3+8x^2+3x-1 (остаток от деления g_1 на g_2, деленный на 2). Необходимые для вычислений по теореме 3 значения h_0,\ldots ,h_6 уже найдены выше, а h_7=-53\, 088\, 896.

\tilde \Delta_1(t)=4t-17,\ \tilde \Delta_2(t)=-(297t^2+674t-2716), \tilde \Delta_3(t)=-(1388t^3+4597t^2-8710t-16\, 204),\ \tilde \Delta_4(t)\equiv -g_2(t).

Для следующей разности в формуле для \operatorname{nrr}_{2,]a,b[} имеем:

\tilde \Delta_1(t)=637t+2599,\ \tilde \Delta_2(t)=166\, 841t^2+327\, 442t-1\, 510\, 004,
\tilde \Delta_3(t)=41\, 717t^3+938\, 073t^2+1\, 301\, 858t-7\, 752\, 980, \tilde \Delta_4(t)\equiv -g_2(t).

И, наконец, для последней:

\begin{array}{l} \tilde \Delta_1(t)=-({\scriptstyle 3734}\, t+{\scriptstyle 16383}),\ \tilde \Delta_2(t)=-({\scriptstyle 21876541}\,t^2+ {\scriptstyle 44064378}\,t-{\scriptstyle 193472492}),\\ \tilde \Delta_3(t)=-({\scriptstyle 31580730}\,t^3 +{\scriptstyle 104965181}t^2-{\scriptstyle 197429382}\,t -{\scriptstyle 372012892}),\ \tilde \Delta_4(t)\equiv g_2(t). \end{array}

Число \operatorname{nrr}_{2,]a,b[} может быть найдено теперь подстановкой значений t=a и t=b в найденные системы, и нахождением разностей их знакоперемен из теоремы 3. Так, получаем:

\operatorname{nrr}_{2,]-2,-1[}={1\over 4}\bigl[ \left\{ \mathcal V(1,-1,-4,44,-8)- \mathcal V(1,0,-5,0,1)\right\} +\left\{4-3 \right\}+\left\{2-1 \right\}+\left\{3-2\right\} \bigr]=1,

и \operatorname{nrr}_{2,]2,3[}=1.

Совершенно аналогично строится система полиномов по t для определения \operatorname{nrr}_{3,]a,b[}, и устанавливается, что \operatorname{nrr}_{3,]-2,-1[}=\operatorname{nrr}_{3,]3,4[}=1. Поскольку \{ -2;-1;2;4\}\not\subset \mathbb S, то один из составляющих интервалов лежит внутри ]-2,-1[, а другой — внутри ]2,4[.

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

\mathbb S \subset ]-1.3179;\ -1.1457[ \ \cup \ ]2.1462;\ 3.5384[.
§

При реальных расчетах не имеет смысла стремиться получить разложение определителей \tilde \Delta_j(t) по степеням параметра. После получения ганкелевой матрицы следует подставлять в нее числовые значения этого параметра и вычислять ее числовые миноры.

Задачи

ЗДЕСЬ.

Источники

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

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

[3]. Утешев А.Ю. Использование символьных методов локализации решений для анализа полиномиальных систем. Диссертация на соискание ученой степени доктора физ.-мат.наук. - СПб. 1998. 275 с.

[4]. Утешев А.Ю., Калинина Е.А. Лекции по высшей алгебре. Часть II. Учеб. пособие. СПб. «СОЛО». 2007. 279 c.

[5]. Kalinina E.A., Uteshev A.Yu. Determination of the Number of Roots of a Polynominal Lying in a Given Algebraic Domain. Linear Algebra Appl. 1993. V.185, P.61-81.

[6]. Markoff A. On the determination of the number of roots of an algebraic equation situated in a given domain. Мат. сборник. 1940. Т. 7(49), N 1, c. 3–6. Текст в формате pdf выложен ☞ЗДЕСЬ

[7]. Uteshev A.Yu. Localization of roots of a polynomial not represented in canonical form. Proc. of the Second Workshop on Computer Algebra in Scientific Computing. Münich 1999, Springer, c.431-440

.

1) number of real roots (англ.)— мое «изобретение», поскольку лучшего не нашел.
2) Полином с большим количеством нулевых коэффициентов называется разреженным.
3) Якóби Карл Густав Якоб (Jacobi Carl Gustav Jacob, 1804-1851) — выдающийся немецкий математик, брат российского физика Бориса Семёновича Якоби. Замечательные результаты в теории чисел, алгебре, анализе и механике.
4) Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) — немецкий математик, ученик Якоби. Биография ЗДЕСЬ.
5) Марков А.А. (1903-1979), сын Маркова А.А. ("Маркова-старшего", 1856-1922) биография ЗДЕСЬ.
6) По исторической традиции переменную в характеристическом полиноме обозначают \lambda
7) Имея в виду теорему Эрмита-Сильвестра, мы вычислили бóльшее число сумм, чем нужно для теоремы Якоби.

2017/03/06 21:40 редактировал au