Инструменты сайта


§

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


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

Задача. Пусть задан полином $ 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) $ не имеет кратных корней (т.е. его дискриминант отличен от нуля). Тогда число вещественных корней не изменится при малых (вещественных) вариациях его коэффициентов. В самом деле, вещественный корень полинома с вещественными коэффициентами не может «сойти» с вещественной оси пока не столкнется с другим вещественным корнем, т.е. не станет кратным (см. ЗДЕСЬ ). Осталось только оценить малость допустимого возмущения.

П

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

$$ 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 $$ по методу Ньютона.

Решение. Забегая вперед, укажем ответ: данный полином имеет каноническое разложение $$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 \ \mbox{ удовлетворяющих неравенству } \ 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

Единичным кругом на комплексной плоскости назовем круг $ |z|\le 1 $.

Задача. Найти необходимые и достаточные условия на коэффициенты полинома $$ f(z)=a_0z^n+\dots+ a_n \in \mathbb C[z] \, , $$ при которых все его корни $ \lambda_1,\dots, \lambda_n $ находятся внутри единичного круга, т.е. удовлетворяют условию $ \{|\lambda_j|<1\}_{j=1}^n $.

Полином с таким свойством корней иногда называют дискретно устойчивым или устойчивым по Шуру.

Т

Теорема [Шур, Кон].6) Полином $ f(z)=a_0z^n+\dots+a_n $ с вещественными коэффициентами имеет все свои корни лежащими внутри единичного круга тогда и только тогда, когда

$$ |\mbox{ старший коэффициент } f(z) |>|\mbox{ свободный член } f(z)| \ , $$ т.е. $ |a_0| > |a_n| $, и полином $$ f_1(z) = \frac{a_0f(z)-a_nf^{*}(z)}{z} \quad npu \quad f^{*}(z) = z^nf(1/z) \equiv a_0+a_1z+\dots+a_nz^n $$ имеет все свои корни лежащими внутри единичного круга.

На первый взгляд, конструктивность этого результата не очень очевидна: исходная задача для полинома $ f(z) $ сводится к аналогичной задаче для полинома $ f_1(z) $. Обратим, однако, внимание на то, что полином $$ \begin{matrix} f_1(z)&=& \left[a_0(a_0z^n+\dots+a_n)-a_n (a_0+a_1z+\dots+a_nz^n) \right] \big/ z = \\ &=& \left[(a_0^2-a_n^2)z^n+(a_0a_1-a_{n-1}a_n)z^{n-1} + \dots + (a_0a_{n-1}-a_{1}a_n)z \right] \big/ z = \\ &=& (a_0^2-a_n^2)z^{n-1}+(a_0a_1-a_{n-1}a_n)z^{n-2} + \dots + (a_0a_{n-1}-a_{1}a_n) \end{matrix} $$ имеет степень меньшую, чем $ \deg f $. Таким образом, алгоритм конструктивен в том смысле, что он сводит исходную задачу к более простой — рекурсией по степени. Применяя к полиному $ f_1(z) $ снова критерий Шура-Кона, получим следующее необходимое условие $$ |\mbox{ старший коэффициент } f_1(z) | > | \mbox{ свободный член } f_1(z)| \ \iff \quad |a_0^2-a_n^2| > |a_0a_{n-1}-a_{1}a_n| \ , $$ при выполнении которого дальнейшему исследованию подлежит полином $$ f_2(z) = \frac{(a_0^2-a_n^2)f_1(z)-(a_0a_{n-1}-a_{1}a_n)f^{*}_1(z)}{z} \ . $$ Продолжая процедуру, за конечное число шагов мы дойдем до полинома первой степени. Окончательно, необходимые и достаточные условия нахождения всех корней полинома $ f(z) $ степени $ n_{} $ внутри единичного круга получаются объединением $ n_{} $ условий $$ |\mbox{ старший коэффициент } f(z) |>|\mbox{ свободный член } f(z)| , $$ $$ |\mbox{ старший коэффициент } f_1(z) | > |\mbox{ свободный член } f_1(z)| , $$ $$ \vdots \qquad \qquad \qquad \vdots $$ $$ |\mbox{ старший коэффициент } f_{n-1}(z) |>|\mbox{ свободный член } f_{n-1}(z)| \ . $$

П

Пример. Определить все вещественные значения параметра $ {\color{Red} \alpha } $, при которых полином

$$5\,z^4+4\,z^3+{\color{Red} \alpha }\,z^2+2\,z+1 $$ имеет все корни лежащими внутри единичного круга.

Решение. Первое из условий теоремы выполнено: $ 5 > 1 $. $$ \begin{array}{rcrrrrrr|r} f(z)&=&5\,z^4&+4\,z^3&+{\color{Red} \alpha }\,z^2&+2\,z&+1 && \times 5 \\ f^{*}(z)&=&z^4&+2\,z^3&+{\color{Red} \alpha }\,z^2&+4\,z&+5 && \times 1 \\ \hline & &24\,z^4&+18\,z^3&+4{\color{Red} \alpha }\,z^2&+6\,z \end{array} $$ Для $ f_1(z) = 24\,z^3+18\,z^2+4{\color{Red} \alpha }\,z+6 $ условие теоремы выполнено7). $$ \begin{array}{rcrrrrr|l} f_1(z)&=&12\,z^3&+9\,z^2&+2{\color{Red} \alpha }\,z&+3 && \times 12 \\ f_1^{*}(z)&=&3\,z^3&+2{\color{Red} \alpha }\,z^2&+9\,z&+12 && \times 3 \\ \hline & &135\,z^3&+(108-6{\color{Red} \alpha })\,z^2&+(24{\color{Red} \alpha }-27)\,z \end{array} $$ Для $ f_2(z) = 135\,z^2+(108-6{\color{Red} \alpha })\,z+(24{\color{Red} \alpha }-27) $ необходимое условие расположения всех его корней внутри единичного круга выполнено при $ |8{\color{Red} \alpha }-9|<45 $. $$ \begin{array}{rcrrrr|l} f_2(z)&=&45\,z^2&+(36-2{\color{Red} \alpha })\,z&+(8{\color{Red} \alpha }-9) && \times 45 \\ f_2^{*}(z)&=&(8{\color{Red} \alpha }-9)\,z^2&+(36-2{\color{Red} \alpha })\,z&+45 && \times (8{\color{Red} \alpha }-9) \\ \hline & &[45^2-(8{\color{Red} \alpha }-9)^2]\,z^2&+(36-2{\color{Red} \alpha })(45-(8{\color{Red} \alpha }-9))\,z \end{array} $$ Единственный корень полинома $$f_3(z)= [45^2-(8{\color{Red} \alpha }-9)^2]\,z+(36-2{\color{Red} \alpha })(45-(8{\color{Red} \alpha }-9))$$ удовлетворяет неравенству $ |z|<1 $ тогда и только тогда, когда $$|45-(8{\color{Red} \alpha }-9) |\cdot |45+(8{\color{Red} \alpha }-9) |>|45-(8{\color{Red} \alpha }-9) |\cdot |36-2{\color{Red} \alpha }| \ .$$ Собираем полученные условия на $ {\color{Red} \alpha } $ в систему неравенств: $$|8{\color{Red} \alpha }-9|<45, \quad 2\, |9+2 {\color{Red} \alpha }|>|18- {\color{Red} \alpha }| \ ,$$ и решаем ее: $ 0< {\color{Red} \alpha } <27/4 $. Это условие является необходимым и достаточным для того чтобы все корни $ f_{}(z) $ удовлетворяли условию $ |z|<1 $. На границах получившегося интервала лежат значения параметра, при которых полином $ f_{}(z) $ будет обладать корнями с модулями равными $ 1_{} $: $$ \begin{array}{rllr} npu & {\color{Red} \alpha }=0: & f(z)\equiv (z+1)(5\,z^3-z^2+z+1) & \Rightarrow \lambda=-1 \\ npu & {\color{Red} \alpha }=27/4: & f(z)\equiv 1/4 (2\,z^2+z+2)(10\,z^2+3\,z+2)& \Rightarrow \lambda=-1/4 \pm {\mathbf i} \sqrt{15}/4 . \end{array} $$

Ответ. $ 0< {\color{Red} \alpha } <27/4 $.

?

Показать, что если коэффициенты полинома $ f(z)=a_0z^n+\dots+a_n $ удовлетворяют условиям $ a_0>a_1>\dots > a_n>0 $, то все корни полинома $ f(z) $ лежат внутри единичного круга.

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

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

Для квадратной матрицы $ A $ определитель $$ \det (A- \lambda E) $$ называется характеристическим полиномом этой матрицы; его корни называются собственными числами этой матрицы, а полный их набор (с учетом кратностей) — спектром матрицы.

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

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

Для матрицы порядка $ n_{} $ ее характеристический полином имеет степень $ n_{} $ относительно8) $ \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), $$ $$ \operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ \lambda<0 \}={\mathcal V}(1,A_1,\dots,A_n) \ . $$

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

Идея

П

Пример. Решить неравенство

$$ 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) $ получаем9): $$ \{ 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 .

[8]. Joachimsthal F. Bemerkungen über den Sturm'schen Satz. J.reine angew. Math. 1854. Vol. 48, P. 386-416

1)
number of real roots (англ.)— мое «изобретение», поскольку лучшего не нашел.
2)
Полином с большим количеством нулевых коэффициентов называется разреженным.
3)
Якóби Карл Густав Якоб (Jacobi Carl Gustav Jacob, 1804-1851) — выдающийся немецкий математик, брат российского физика Бориса Семёновича Якоби. Замечательные результаты в теории чисел, алгебре, анализе и механике.
4)
Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) — немецкий математик, ученик Якоби. Биография ЗДЕСЬ.
5)
Марков А.А. (1903-1979), сын Маркова А.А. ("Маркова-старшего", 1856-1922) биография ЗДЕСЬ.
6)
Шур Исай (Schur Issai, 1875-1941) — немецкий математик, ученик Фробениуса. Родился в Могилёве. Биография ЗДЕСЬ.
7)
В дальнейшем для упрощения вычислений каждый полином $ f_j(x) $ делим на положительный $ \operatorname{HOD} $ его коэффициентов.
8)
По исторической традиции переменную в характеристическом полиноме обозначают $ \lambda $
9)
Имея в виду теорему Эрмита-Сильвестра, мы вычислили бóльшее число сумм, чем нужно для теоремы Якоби.
polynomial/zero_local.txt · Последние изменения: 2022/12/27 18:59 — au