!!§!! Вспомогательный раздел к разделу ((:polynomial ПОЛИНОМ)) ---- == Локализация корней полинома == ~~TOC~~ **Задача.** Пусть задан полином $ f(z)=a_0z^n+a_1z^{n-1}+\dots + a_n $ с комплексными коэффициентами от комплексной переменной $ z=x+{\mathbf i} y $ и заданы ((:polynomialm полиномы)) $ 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] $ установить точное число его вещественных корней на заданном интервале[[number of real roots (//англ.//)--- мое "изобретение", поскольку лучшего не нашел.]] $ ]a,b_{}[ $: $$ \operatorname{nrr} \{f(x)=0 \ | \ a ☞ ((:polynomial:geometry ЗДЕСЬ)) ). Осталось только оценить малость допустимого возмущения. !!П!! **Пример [Уилкинсон].** Вычислить корни полинома $$ 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 $$ по ((:polynomial:newton методу Ньютона)). **Решение.** Забегая вперед, укажем ответ: данный полином имеет каноническое разложение $$f(x)=\prod_{j=1}^{20}(x+j) \ ,$$ и таким образом его корнями являются числа $ -1,-2,\dots,-20 $, достаточно хорошо разнесенные. Пусть, однако же, эта информация нам изначально недоступна, и мы для поиска корней применяем ((:polynomial:newton метод Ньютона)), задав точность вычислений в $ 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)$$ //с учетом их кратностей равно или меньше на четное число ((algebra2:notations#число_знакопостоянств_знакоперемен числа знакоперемен)) в ряду его коэффициентов:// $$ \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 \} \ . $$ **Доказательство** ☞ ((:polynomial:descartes ЗДЕСЬ)). С помощью преобразования корней полинома (см. пункт 1 ☞ ((:polynomial#преобразования_корней ЗДЕСЬ)) ) можно доказать следствие: !!=>!! //Число отрицательных корней полинома// $$f(x)=a_0x^n+a_1x^{n-1}+\dots+a_{n-1}x+a_n, \quad (a_0> 0,a_n \ne 0)$$ //с учетом их ((:polynomial#основная_теорема_высшей_алгебры кратностей)) можно оценить по формуле// $$ \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} $ обозначает ((algebra2:notations#число_знакопостоянств_знакоперемен число знакопостоянств)). !!П!! **Пример.** Оценить число положительных и число отрицательных корней полинома $$ 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) $ обращается в нуль[[Полином с большим количеством нулевых коэффициентов называется **разреженным**.]], тем меньше у него потенциальных возможностей иметь вещественные корни! ==== Система полиномов Штурма== Для полинома $ 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) $. ((algebra2:notations#число_знакопостоянств_знакоперемен Число знакоперемен)) $$ {\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 ☞ ((#производные_от_полинома ЗДЕСЬ)) ). Установить этот факт можно по алгоритму Евклида нахождения $ \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_{}[ $. ==== Упрощающие соображения == Иногда построение системы полиномов Штурма упрощается различными соображениями. !!П!! **Пример.** ((:euclid_space#ортогонализация Полиномы Лежандра)) $$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[ $. ♦ ==== Обобщенная система полиномов Штурма == ==== Ганкелевы матрицы в теории локализации корней == Раздел "Ганкелевы матрицы, определители и полиномы" ☞ ((:algebra2:hankel ЗДЕСЬ)) Для полинома $ 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} $ дается ((dets:discrim:waring#формула_варинга формулой Варинга)); однако она неудобна при реальных расчетах. Вычислим суммы Ньютона $ s_0,s_{1},\dots,s_{2n-2} $ полинома $ f_{}(x) $ и составим из них ((:algebra2:hankel#определения ганкелеву)) матрицу $$ 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} $ ее ((:algebra2:dets#теорема_лапласа главные миноры)). !!Т!! **Теорема [Якоби].**[[Якóби Карл Густав Якоб (Jacobi Carl Gustav Jacob, 1804-1851) --- выдающийся немецкий математик, брат российского физика Бориса Семёновича Якоби. Замечательные результаты в теории чисел, алгебре, анализе и механике.]] //Число различных корней полинома// $ f_{}(x) $ //равно ((algebra2:rank рангу)), а число различных вещественных корней// $ f_{}(x) $ //--- ((:2form#закон_инерции сигнатуре матрицы))// $ S_{} $. Конструктивное вычисление ранга и сигнатуры симметричной (точнее, ганкелевой) матрицы $ S_{} $ возможно посредством ((:2form#закон_инерции определения знаков ее главных миноров)) $ 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}_{} $ --- ((algebra2:notations#число_знакопостоянств_знакоперемен число знакопостоянств)) и $ {\mathcal V}_{} $ --- ((algebra2:notations#число_знакопостоянств_знакоперемен число знакоперемен)). !!=>!! Определитель матрицы $ S_{} $ фактически совпадает с ((dets:discrim#представление_дискриминанта_посредством_ганкелевой_матрицы дискриминантом)) полинома $ 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} \ . $$ Можно получить (см. прием ☞ ((:algebra2:dets:special_cases#увеличение_порядка_определителя ЗДЕСЬ)) ) иное детерминантное представление для $ 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| \ . $$ Разложение по этому столбцу позволит получить ((:polynomial#общая_информация каноническую форму)) полинома $ \mathcal H_{\ell}(t) $. Заметим, что $$ \mathcal H_{n}(t)=\det H(t) \equiv S_n f(t)/a_0 \ .$$ !!Т!! **Теорема [Йоахимшталь].**[[Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) --- немецкий математик, ученик Якоби. Биография ☞ ((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Joachimsthal.html ЗДЕСЬ)).]] //Пусть// $ \operatorname{rank} (S)={\mathfrak r} $. //Тогда// $$ \operatorname{nrr} \{ f(x)=0 \mid a В случае, когда в ряду встречаются несколько подряд идущих нулей (например, $ f(x)=x^4-1, a=0 $), то можно воспользоваться правилом Кронекера-Хатендорфа: $$ \operatorname{nrr} \{ f(x)=0 \mid 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**-тождества), приведенного ☞ ((:algebra2/hankel/jjidentity ЗДЕСЬ)). !!=>!! Матрицу из теоремы Йоахимшталя можно представить в виде комбинации двух ганкелевых матриц: $ 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оставим из этих величин ((:algebra2:dets#ганкеля ганкелеву)) матрицу $$ 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 $ ее ((:algebra2:dets#теорема_лапласа главные миноры)). !!Т!! **Теорема [Эрмит, Сильвестр].** //Пусть полиномы// $ f_{}(x) $ //и// $ g_{}(x) $ //не имеют общих корней, т.е. их ((:dets:resultant#результант_в_форме_сильвестра результант))// $ {\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_{} $ вычисляется как ((algebra2:notations#число_знакопостоянств_знакоперемен число знакоперемен)): $$ 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_{} $ как ((algebra2:notations#число_знакопостоянств_знакоперемен число знакопостоянств)): $$ 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) \ . $$ ====Критерии вещественности (мнимости) всех корней полинома== ((:polynomial/zero_local/reality .)) ==== Формула Маркова == Результат теоремы Эрмита-Сильвестра можно распространить на случай когда требуется определить число вещественных корней $ f_{}(x) $, удовлетворяющих системе неравенств $ g_1(x)>0,g_2(x)>0,\ldots,g_K(x)>0 $, где все полиномы имеют вещественные коэффициенты. !!Т!! **Теорема [Марков]((#источники [6])).[[Марков А.А. (1903-1979), сын ((:biogr#марков Маркова А.А. ("Маркова-старшего", 1856-1922) )) биография ☞ ((http://logic.pdmi.ras.ru/Markov/Markov.html ЗДЕСЬ)).]]** //Если ни один из полиномов// $ g_j(x) $ //не имеет общих корней с// $ f_{}(x) $ (т.е. ((:dets:resultant результант)) $ {\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_10\}+ $$ $$ +\sum_{1\le j_10\} +\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 $. Полином с таким свойством корней иногда называют **дискретно устойчивым** или **устойчивым по Шуру**. !!Т!! **Теорема [Шур, Кон].**[[Шур Исай (Schur Issai, 1875-1941) --- немецкий математик, ученик Фробениуса. Родился в Могилёве. Биография ☞ ((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Schur.html ЗДЕСЬ)).]] //Полином// $ 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 $ условие теоремы выполнено[[В дальнейшем для упрощения вычислений каждый полином $ f_j(x) $ делим на положительный $ \operatorname{HOD} $ его коэффициентов.]]. $$ \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 $. Подробнее о характеристическом полиноме, собственных числах и их приложениях ☞ ((algebra2:charpoly ЗДЕСЬ)). Для матрицы порядка $ n_{} $ ее характеристический полином имеет степень $ n_{} $ относительно[[По исторической традиции переменную в характеристическом полиноме обозначают $ \lambda $]] $ \lambda $ $$ (-1)^n \lambda^n +a_1\lambda^{n-1} + \dots +a_n \ ; $$ а его коэффициенты полиномиально зависят от элементов матрицы. Можно выписать явное представление $ a_1,\dots a_n $ с помощью миноров матрицы (см. ☞ ((algebra2:charpoly ЗДЕСЬ)) ). Так, к примеру, для $ 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 \ , $$ но, вообще говоря, задача вычисления характеристического полинома (т.е. нахождения его ((:polynomial#общая_информация канонической формы)) ) считается сложной и поэтому интерес представляют методы, позволяющие определить или, хотя бы, локализовать собственные числа матрицы $ 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} \ . $$ {{ polynomial:gershgorin2.gif |}} **Проверка.** Собственные числа матрицы $ A $ (на рисунке обозначены красными крестиками): $$ \{ -2.509081750-3.442241533\,{\mathbf i} ,\ -1.041999986+2.655757676\,{\mathbf i} ,\ 4.551081736+1.786483857\, {\mathbf i} \} .$$ === Симметричные матрицы== !!Т!! **Теорема.** //Собственные числа вещественной симметричной матрицы// $ A_{} $ // все вещественны.// **Доказательство** ☞ ((:algebra2:charpoly:symm ЗДЕСЬ)). !!Т!! **Теорема [Коши].** //Для вещественной симметричной матрицы// $ A_{} $ //число ее собственных чисел, лежащих на интервале// $ ]a,b_{}[ $, //определяется по формуле:// $$\operatorname{nrr} \{ \det (A-\lambda E) =0 \ | \ a< \lambda ☞ ((:algebra2/symmetric/cauchy ЗДЕСЬ)). Согласно этой теореме, главные миноры матрицы $ A-\lambda\, E $ играют роль системы полиномов Штурма для характеристического полинома симметричной матрицы $ A_{} $. !!=>!! Если все ((:algebra2/dets#minory_i_algebraicheskie_dopolnenija главные миноры)) $$ 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 [ $. Вспомним, что обычным школьным методом решения неравенства вида {{ polynomial:ineq_interval.gif|}} $$ (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 Предположение 2. Пусть полиномы $ g_1,\ldots ,g_K $ не имеют кратных корней, т.е. $ \mathcal D(g_j)\ne 0 $ для всех $ 1\le j \le K $. Здесь $ \mathcal D $ означает ((dets:discrim#дискриминант дискриминант)) рассматриваемого полинома. !!Т!! **Теорема.** //При выполнении условий// предположений 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) $ получаем[[Имея в виду теорему Эрмита-Сильвестра, мы вычислили бóльшее число сумм, чем нужно для теоремы Якоби.]]: $$ \{ 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 . {{users:au:scriber.jpg |}} \\ \\ \\ Статья не закончена! === Определение структуры множества решений == Проблему, поставленную в заглавие, разделим на три. **Задача.** Для множества решений $ \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 a0, \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 предположений 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,a0,x0,a0, \\ 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 рекомендации 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) $ по степеням параметра. После получения ганкелевой матрицы следует подставлять в нее числовые значения этого параметра и вычислять ее **числовые** миноры. ==Задачи== ☞ ((:polynomial:zero_local:problems ЗДЕСЬ)). == Источники== [1]. **Джури Э.** //((:references#джури Инноры и устойчивость динамических систем.))// М.Наука.1979.\\ [2]. **Крейн М., Наймарк М.** //((:references#крейн_наймарк Метод симметрических и эрмитовых форм в теории отделения корней алгебраических уравнений))//.-Харьков. ГТТИ. 1936. 39 с. [3]. **Утешев А.Ю.** //Использование символьных методов локализации решений для анализа полиномиальных систем//. Диссертация на соискание ученой степени доктора физ.-мат.наук. - СПб. 1998. 275 с. \\ [4]. **Утешев А.Ю., Калинина Е.А.** //Лекции по высшей алгебре. Часть II.// Учеб. пособие. СПб. "СОЛО". 2007. 279 c. [5]. **Kalinina E.A., Uteshev A.Yu.** //((:references#утешев_со_товарищи 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. Текст ☞ ((http://www.mathnet.ru/php/journal.phtml?wshow=paper&jrnid=sm&paperid=5932&year=1940&volume=49&issue=1&fpage=3&lpage=6&option_lang=eng ЗДЕСЬ)) (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 ((:polynomial:zero_local:vspom1 .)) [8]. **Joachimsthal F.** //Bemerkungen über den Sturm'schen Satz.// J.reine angew. Math. 1854. Vol. 48, P. 386-416