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


§

Вспомогательный раздел к разделу МАТРИЦА

Страница — в разработке. Начало работ — 06.05.2016, окончание — ??.??.????


Ганкелевы матрицы, определители и полиномы

Определения

Ганкелева матрица порядка k_{} — это квадратная матрица вида

\left(\begin{array}{llllll} \color{Brown}c_0 & \color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & \dots & c_{k-1} \\ \color{Blue}c_1 & \color{Green}c_2 & \color{Violet}c_3 & c_4 & \dots & c_k \\ \color{Green}c_2 & \color{Violet}c_3 & c_4 & &\dots & c_{k+1} \\ \color{Violet}c_3 & c_4 & & & & \\ \vdots & & & \ddots & \vdots \\ c_{k-1} & c_{k} & c_{k+1} & &\dots & c_{2k-2} \end{array} \right)_{k\times k}= \left[ c_{j+k}\right]_{j,k=0}^{k-1} \ .

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

c_0,c_1,\dots, c_{2k-2}

— они называются образующими ганкелевой матрицы.

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

Определитель ганкелевой матрицы порядка k_{} будем обозначать H_{k}(\{c\}) или просто H_{k}.

Если в ганкелевой матрице порядка k+1 заменить последнюю строку на \left[ 1,x,x^2,\dots,x^{k} \right], то определитель полученной матрицы

\mathcal H_k(x; \{c\}) = \left| \begin{array}{lllll} c_0 & c_1 & c_2 & \ldots & c_{k} \\ c_1 & c_2 & c_3 &\ldots & c_{k+1} \\ \vdots & & & \ddots& \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-1} \\ 1 & x & x^2 & \ldots & x^{k} \end{array} \right|_{(k+1) \times (k+1)}

будет полиномом по x_{}; он называется ганкелевым полиномом k-го порядка (порожденным последовательностью \{c\}). Его каноническое представление имеет коэффициентами числовые определители k_{}-го порядка:

\mathcal H_k(x; \{c\})\equiv x^{k} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-2} \end{array} \right|- x^{k-1} \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & c_{k} \\ c_1 & c_2 & \ldots & c_{k-1} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & c_{2k-1} \end{array} \right|+
+ \dots +(-1)^k \left| \begin{array}{lllll} c_1 & c_2 & \ldots & c_{k-1} & c_{k} \\ c_2 & c_3 & \ldots & c_{k} & c_{k+1} \\ \vdots & & \ddots& & \vdots \\ c_{k} & c_{k+1} & \ldots & c_{2k-2} & c_{2k-1} \end{array} \right| \ .

Коэффициенты будем обозначать h_{kj}; таким образом

\mathcal H_k(x; \{c\})\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad npu \quad h_{k0}= H_k \ ;

Коэффициент h_{k0} может обращаться в нуль, так что степень ганкелевого полинома k_{}-го порядка может оказаться меньшей k_{}.

Т

Теорема. Ганкелев полином k-го порядка можно представить в виде ганкелевого определителя k-го порядка:

\mathcal H_k(x; \{c\}) = (-1)^k \left| \begin{array}{lllll} c_1 -c_0x & c_2-c_1x & \ldots & c_{k}-c_{k-1}x \\ c_2-c_1x & c_3-c_2x &\ldots & c_{k+1}-c_kx \\ \vdots & & \ddots& \vdots \\ c_{k}-c_{k-1}x & c_{k+1}-c_kx & \ldots & c_{2k-1}-c_{2k-2}x \end{array} \right|_{k \times k}=(-1)^k H_k (\{c_{j+1}-c_jx\}_{j=0}^{2\, k-1}) \ .

Доказательство. Для простоты рассмотрим случай k=4:

\left| \begin{array}{lllll} c_0 & c_1 & c_2 & c_3 & c_{4} \\ c_1 & c_2 & c_3 & c_4 & c_{5} \\ c_2 & c_3 & c_4 & c_5 & c_{6} \\ c_{3} & c_{4} & c_{5} & c_6 & c_{7} \\ 1 & x & x^2 & x^3 & x^{4} \end{array} \right|=

С помощью элементарных преобразований столбцов исключим x_{} из последней строки. С этой целью вычтем из 5_{}-го столбца 4-й, домноженный на x_{}, потом из 4_{}-го столбца 3_{}-й, домноженный на x_{}, и т.д. В результате получим

= \left| \begin{array}{ccccc} c_0 & c_1 -c_0x & c_2-c_1x & c_3-c_2x & c_{4}-c_{3}x \\ c_1 & c_2-c_1x & c_3-c_2x & c_4-c_3x & c_{5}-c_4x \\ c_2 & c_3-c_2x & c_4-c_3x & c_5-c_4x & c_{6}-c_5x \\ c_3 & c_4-c_3x & c_5-c_4x & c_6-c_5x & c_{7}-c_6x \\ 1 & 0 & 0 & 0 & 0 \end{array} \right|= + \left| \begin{array}{llll} c_1 -c_0x & c_2-c_1x & c_3-c_2x & c_{4}-c_{3}x \\ c_2-c_1x & c_3-c_2x & c_4-c_3x & c_{5}-c_4x \\ c_3-c_2x & c_4-c_3x & c_5-c_4x & c_{6}-c_5x \\ c_4-c_3x & c_5-c_4x & c_6-c_5x & c_{7}-c_6x \end{array} \right|\ .

Тождество Якоби

Т

Теорема. Справедливо следующее равенство (тождество) Якоби:

H_k \left| \begin{array}{llll} c_2 & c_3 & \ldots & c_{k-1} \\ c_3 & c_4 & \ldots & c_{k} \\ \vdots & & \ddots & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-4} \end{array} \right|_{(k-2)\times (k-2)} =
=H_{k-1} \left|\begin{array}{llll} c_2 & c_3 & \dots & c_{k} \\ c_3 & c_4 & \dots & c_{k+1} \\ \vdots & & \ddots & \vdots \\ c_{k} & c_{k+1} & \dots & c_{2k-2} \end{array} \right|_{(k-1)\times (k-1)} - \left|\begin{array}{llll} c_1 & c_2 & \dots & c_{k-1} \\ c_2 & c_3 & \dots & c_{k} \\ \vdots & & \ddots & \vdots \\ c_{k-1} & c_{k} & \dots & c_{2k-3} \end{array} \right|_{(k-1)\times (k-1)}^2 \ .

Это равенство связывает ганкелев определитель k_{}-го порядка с тремя ганкелевыми определителями порядка k-1 и одним ганкелевым определителем порядка k-2. Оно является частным случаем тождества Сильвестра.

Обращение ганкелевой матрицы

Рекурсивная формула для ганкелевых полиномов

Рассмотрим последовательность ганкелевых полиномов \mathcal H_1(x), \mathcal H_2(x) ,\dots,, порожденных последовательностью \{ \mathbf c \}. Коэффициенты канонического разложения полинома \mathcal H_k(x) будем обозначать \{h_{kj}\}:

\mathcal H_k(x)\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \quad npu \quad h_{k0}= H_k \ .
П

Пример. Вычислить ганкелевы полиномы \{\mathcal H_k(x)\}_{k=1}^5, порожденные последовательностью

\{1,1,2,-1,-9,-142,-2051,-29709,-430018,-6224467,\dots \} \, .

Решение. Имеем:

\mathcal H_1(x)=x-1,\ \mathcal H_2(x)=x^2+3\,x-5,\ \mathcal H_3(x)=-22\,x^3+164\,x^2+316\,x-666,
\mathcal H_4(x)=19656\,x^4-278356\,x^3-97864\,x^2+93808\,x+468,
\mathcal H_5(x)=4638712(x^5-14\,x^4-7\,x^3+2\,x^2-3\,x+8) \ .

Легко проверить, что вычисленные полиномы удовлетворяют тождествам:

-22\, \mathcal H_1(x)+\left(\frac{115}{11}-x\right)\mathcal H_2(x) -\frac{1}{22} \mathcal H_3(x) \equiv 0,
-\frac{9828}{11}\, \mathcal H_2(x) +\left( \frac{27887}{4158}-x \right) \mathcal H_3(x)-\frac{11}{9828} \mathcal H_4(x) \equiv 0,
\frac{44603}{189} \mathcal H_3(x)+ \left( -\frac{61}{378}-x \right) \mathcal H_4(x)+\frac{189}{44603} \mathcal H_5(x) \equiv 0 \ .

Т

Теорема [Якоби, Йоахимшталь].2) Любые три ганкелевых полинома \mathcal H_{k-2}(x), \mathcal H_{k-1}(x), \mathcal H_{k}(x) связаны тождеством

H_k^2\mathcal H_{k-2}(x) + \left(H_kh_{k-1,1}-H_{k-1}h_{k1}-H_kH_{k-1}x\right)\mathcal H_{k-1}(x) + H_{k-1}^2 \mathcal H_{k}(x) \equiv 0 \, .

§

В литературе после 1910 г. упоминаний этого тождества (и ссылок на него) не нашел. В дальнейшем буду называть его JJ-тождеством.

=>

Если H_{k} \ne 0, H_{k-1} \ne 0 то JJ-тождество может быть переписано в «более симметричном» виде

\frac{H_k}{H_{k-1}}\mathcal H_{k-2}(x)- \left(x-\frac{h_{k-1,1}}{H_{k-1}}+\frac{h_{k1}}{H_{k}} \right)\mathcal H_{k-1}(x)+\frac{H_{k-1}}{H_{k}}\mathcal H_{k}(x) \equiv 0 \, .

JJ-тождество позволяет организовать рекурсивную процедуру вычисления ганкелевых полиномов. Предположим, что канонические представления полиномов \mathcal H_{k-2}(x) и \mathcal H_{k-1}(x) уже известны:

\mathcal H_{k-1}(x) \equiv h_{k-1,0} x^{k-1}+h_{k-1,1}x^{k-2}+\dots+ h_{k-1,k-1} \quad npu \ h_{k-1,0}=H_{k-1} \, .

Тогда в JJ-тождестве известны значения всех констант, за исключением H_k и h_{k1}. Для последних имеются лишь детерминантные представления:

H_k = \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k-1} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-3} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-2} \end{array} \right| \ , \ h_{k1} = - \left| \begin{array}{lllll} c_0 & c_1 & \dots & c_{k-2} & c_{k} \\ c_1 & c_2 & \dots & c_{k-1} & c_{k+1} \\ \vdots & \vdots & & \vdots & \vdots \\ c_{k-2} & c_{k-1} & \dots & c_{2k-4} & c_{2k-2} \\ c_{k-1} & c_{k} & \dots & c_{2k-3} & c_{2k-1} \end{array} \right| \, .

Эти определители отличаются от детерминантного представления \mathcal H_{k-1}(x) (транспонированного)

\left[\mathcal H_{k-1}(x) \right]^{\top} = \left| \begin{array}{llllll} c_0 & c_1 & c_2 & \ldots & c_{k-2} & 1 \\ c_1 & c_2 & c_3 &\ldots & c_{k-1} & x \\ \vdots & & & \ddots & \vdots & \vdots \\ c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-3} & x^{k-1} \end{array} \right|

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

\left\{\begin{array}{rcl} h_{k0}=H_k&=&c_{k-1}h_{k-1,k-1}+c_{k}h_{k-1,k-2}+\dots+c_{2k-2}h_{k-1,0}, \\ h_{k1}&=&-(c_{k}h_{k-1,k-1}+c_{k+1}h_{k-1,k-2}+\dots+c_{2k-1}h_{k-1,0}) \end{array} \right.

позволяют вычислить h_{k0} и h_{k1} посредством уже известных коэффициентов полинома \mathcal H_{k-1}(x).

Частный случай тождества известен для ортогональных полиномов.

Предложенный алгоритм сведения вычисления \mathcal H_{k}(x) к вычислению двух ганкелевых полиномов меньших порядков не будет работать в случае H_{k-1}=0. Существует модификация алгоритма и для этого случая.

Применения

Линейные рекуррентные последовательности

Т

Теорема. Бесконечная ганкелева матрица H=\left[h_{j+k}\right]_{j,k=0}^{\infty} имеет конечный ранг \mathfrak r тогда и только тогда, когда последовательность \{h_{j}\}_{j=0}^{\infty} является линейной рекуррентной порядка \mathfrak r, т.е. существует \mathfrak r чисел a_1,a_2,\dots,a_{\mathfrak r} таких, что

h_{\ell}=a_1 h_{\ell-1}+a_2 h_{\ell-2}+\dots+a_{\mathfrak r} h_{\ell-\mathfrak r} \quad npu \quad \ell\in\{\mathfrak r,\mathfrak r+1,\dots\}

и \mathfrak r есть наименьшее число, обладающее этим свойством.

Т

Теорема. Бесконечная ганкелева матрица H=\left[h_{j+k}\right]_{j,k=0}^{\infty} имеет конечный ранг тогда и только тогда, когда сумма ряда Лорана

R(x)=\frac{h_0}{x}+\frac{h_1}{x^2}+\frac{h_2}{x^3}+\dots

является рациональной функцией от переменной x. В этом случае \operatorname{rank} (H) совпадает с числом полюсов функции R(x), с учетом кратности каждого полюса.

Аппроксимация

Результант и наибольший общий делитель полиномов

§

Раздел Результант.

Для полиномов

f(x)=a_0x^n+a_1x^{n-1}+\ldots+a_n\quad u \quad g(x)=b_0x^m+b_1x^{m-1}+\ldots+b_m

(a_{0}\ne 0) построим сначала формальное разложение дроби g_{}(x)/f(x) в ряд Лорана по отрицательным степеням x_{}. Для случая \deg g < \deg f выписываем разложение

\frac{g(x)}{f(x)}=\frac{c_0}{x}+\frac{c_1}{x^2}+\dots+\frac{c_j}{x^{j+1}}+\dots \ ,

домножаем обе части на f_{}(x) и приравниваем коэффициенты при одинаковых степенях x_{} в левой и правой частях получившегося равенства. В случае m=n-1 формулы, выражающие коэффициенты c_{j} через коэффициенты полиномов f_{}(x) и g_{}(x) следующие:

\begin{array}{ll} c_0&=b_{0}/a_0,\\ c_1& =(-c_{0}a_1+b_1)/a_0,\\ c_2& =(-c_{0}a_2-c_1a_1+b_2)/a_0, \\ \dots & \dots \\ c_{n-1}&=(-c_0a_{n-1}-c_1a_{n-2}-\dots-c_{n-2}a_1+b_{n-1})/a_0,\\ c_{K+n}&=(-c_{K}a_{n}-c_{K+1}a_{n-1}-\dots-c_{K+n-1}a_1)/a_0 \quad npu \quad \forall K \in \{0,1,2,\dots \} \ . \end{array}

В случае m<n-1 эти же формулы можно применять при дополнительном условии, что полином g_{}(x) считается записанным в виде

g(x) = b_0x^{n-1}+ b_1x^{n-2}+ \dots + b_{n-1} \ ,

где коэффициенты b_0,\dots, b_{n-m} считаются равными нулю. Для случая \deg f \le \deg g сначала вычисляется частное q_{}(x) и остаток g_{1}(x) от деления g_{}(x) на f_{}(x), а далее правильная дробь g_1(x)/f(x) раскладывается по отрицательным степеням x_{} с использованием приведенных выше правил:

\frac{g(x)}{f(x)}=q(x)+\frac{g_1(x)}{f(x)}=q(x)+\frac{c_0}{x}+\frac{c_1}{x^2}+\dots+\frac{c_j}{x^{j+1}}+\dots

Вычислив величины c_{0},\dots,c_{2n-2}, cоставим из них ганкелеву матрицу

C= [c_{j+k}]_{j,k=0}^{n-1}= \left(\begin{array}{lllll} c_0&c_1&c_2&\ldots&c_{n-1}\\ c_1&c_2&c_3&\ldots&c_{n}\\ c_2&c_3&c_4&\ldots&c_{n+1}\\ \dots&&&&\dots\\ c_{n-1}&c_{n}&c_{n+1}&\ldots&c_{2n-2} \end{array}\right)\ .

Обозначим C_{1},\dots,C_n ее главные миноры.

Т

Теорема [Кронекер][?].Имеет место формула

{\mathcal R}(f,g)=a_0^{n+m} \det C \ .

связывающая определитель матрицы C_{} с результантом полиномов f_{}(x) и g_{}(x). Для того чтобы эти полиномы имели наибольший общий делитель степени k>0, необходимо и достаточно, чтобы были выполнены условия

\underbrace{C_n=0,\ C_{n-1}= 0,\ \dots , C_{n-k+1}=0}_k, C_{n-k}\ne 0.

Дискриминант и локализация корней полинома

§

Раздел Дискриминант; раздел Локализация корней полинома.

Дискриминант полинома f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n, (n>1, a_0\ne 0) фактически совпадает с результантом этого полинома и его производной:

{\mathcal D}(f)=\frac{(-1)^{n(n-1)/2}}{a_0}{\mathcal R}(f(x),f^{\prime}(x)) \ .
Т

Теорема. {\mathcal D}(f_{}) = 0 тогда и только тогда, когда f_{}(x) имеет кратный корень.

Существует несколько способов представления дискриминанта в виде определителя матрицы, зависящей от коэффициентов полинома f_{}(x). Один из них основан на ганкелевой матрице.

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

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

Суммы Ньютона могут быть формально получены из разложения в ряд Лорана дроби

\frac{f^{\prime}(x)}{f(x)}=\frac{s_0}{x}+\frac{s_1}{x^2}+\dots+\frac{s_j}{x^{j+1}}+\dots \ ,

и выражаются рационально через коэффициенты полинома 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 ее главные миноры.

Т

Теорема. Имеет место формула

{\mathcal D}_{k}=n^{n-k-2}a_0^{2(n-k-1)}S_{n-k} \ ,

связывающая миноры матрицы S_{} с субдискриминантами. В частности,

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

Доказательство следует из теоремы Кронекера.

Матрицу S из предыдущей теоремы можно использовать и для локализации вещественных корней полинома f_{}(x), имеющего вещественные коэффициенты.

Т

Теорема [Якоби]. Число различных корней полинома f_{}(x)\in \mathbb R[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}_{}число знакоперемен.

Идею, использованную при доказательстве теоремы Якоби можно развить и для задачи отделения (локализации) корней полинома 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_{} из теоремы Якоби. Главный минор матрицы H(t) порядка \ell_{} является ганкелевым полиномом того же порядка

\mathcal H_{\ell}(t)=\det \left[s_{j+k}t-s_{j+k+1} \right]_{j,k=0}^{{\ell}-1} \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|_{(\ell+1)\times (\ell+1)} \ .

Заметим, что

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

Теорема [Йоахимшталь].[?] Пусть \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 были положительными.

Источники

[?]. Гантмахер Ф.Р. Теория матриц. 4-е изд. М.Наука. 1988.

[?]. Иохвидов И.С. Ганкелевы и теплицевы матрицы и формы. М. Наука. 1974.

[?]. Henrici P. Applied and Computational Complex Analysis. V. 1. 1974. NY. Wiley

[?]. Kronecker L. Zur Theorie der Elimination einer Variabeln aus zwei algebraischen Gleichungen. Werke. Bd. 2. 1897. 113-192, Teubner, Leipzig

[?]. Jacobi C.G.J. De eliminatione variabilis e duabus aequationibus algebraicis. J.reine angew. Math. 1836. Vol. 15, P. 101-124

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

[?]. Утешев А.Ю., Боровой И.И. Решение задачи рациональной интерполяции с использованием ганкелевых полиномов. Вестник СПбГУ. Серия 10. 2016. Вып. 4, С. 31-43.

1) Ганкель Герман (Hankel Hermann, 1839-1873) — немецкий математик. Биография ЗДЕСЬ
2) Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) — немецкий математик, ученик Якоби. Биография ЗДЕСЬ.

2018/04/27 10:08 редактировал au