!!⊗!! Страница --- в разработке. Начало работ --- 06.05.2016, окончание --- ??.??.????
==Ганкелевы матрицы, определители и полиномы==
~~TOC~~
===Определения==
{{ :hankel.gif|}}
**Ганкелева матрица** порядка $ 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} \ .
$$
Это ((#симметричная симметричная)) матрица, на каждой диагонали которой, перпендикулярной главной, стоят одинаковые элементы. Таким образом, ганкелева[[Ганкель Герман (Hankel Hermann, 1839-1873) --- немецкий математик. Биография
☞
((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Hankel.html ЗДЕСЬ))]] матрица полностью определяется заданием своих крайних элементов ---
$$ c_0,c_1,\dots, c_{2k-2} $$
--- они называются **образующими ганкелевой матрицы**.
!!П!! **Пример.** Матрица
$$\left(
\begin{array}{lllll}
1 & 1/2 & 1/3 & \dots & 1/n \\
1/2 & 1/3 & 1/4 & \dots & 1/(n+1) \\
1/3 & 1/4 & 1/5 & \dots & 1/(n+2) \\
\vdots & & & & \vdots \\
1/n & 1/(n+1) & 1/(n+2) & \dots & 1/(2n-1)
\end{array}
\right) =\left[ \frac{1}{j+k+1} \right]_{j,k=0}^{n-1}
$$
относится к типу ганкелевых. Она называется **матрицей Гильберта**.
Наряду с конечными ганкелевыми матрицами, рассматривают также и бесконечные, задаваемые бесконечной последовательностью образующих элементов.
Определитель ганкелевой матрицы порядка $ 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 \mbox{ при } \quad h_{k0}= H_k \ ;
$$
Коэффициент $ h_{k0} $ может обращаться в нуль, так что степень ганкелевого полинома $ k_{} $-го порядка может оказаться меньшей $ k_{} $.
!!Т!! **Теорема.** //Ганкелев полином// $ k $//-го порядка можно представить в виде ганкелевого определителя// $ k $//-го порядка//:
$$
\mathcal H_k(x; \{c\}) =
\left|
\begin{array}{lllll}
c_0x-c_1 & c_1x-c_2 & \ldots & c_{k-1}x - c_k \\
c_1x-c_2 & c_2x-c_3 &\ldots & c_kx -c_{k+1} \\
\vdots & & \ddots& \vdots \\
c_{k-1}x-c_k & c_kx -c_{k+1} & \ldots & c_{2k-2}x -c_{2k-1}
\end{array} \right|_{k \times k}=H_k (\{c_jx-c_{j+1}\}_{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 $. Оно является частным случаем ((:dets:sylvester тождества Сильвестра)).
===Обращение ганкелевой матрицы==
===Рекурсивная формула для ганкелевых полиномов==
Рассмотрим последовательность ганкелевых полиномов $ \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 \ .
$$
♦
!!Т!! **Теорема [Якоби, Йоахимшталь].**[[Йоахимшталь Фердинанд (Joachimsthal Ferdinand, 1818-1861) --- немецкий математик, ученик Якоби. Биография
☞
((http://www-history.mcs.st-andrews.ac.uk/history/Biographies/Joachimsthal.html ЗДЕСЬ)).]] //Любые три ганкелевых полинома// $ \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 \, .
$$
**Доказательство**
☞
((:algebra2/hankel/jjidentity ЗДЕСЬ))
В литературе после 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 $. Существует модификация алгоритма и для этого случая. См.
☞
((:algebra2/hankel/jjidentity#iskljuchitelnye_sluchai ЗДЕСЬ)).
==Применения==
===Линейные рекуррентные последовательности==
!!Т!! **Теорема.** //Бесконечная ганкелева матрица// $ 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
$$
//является ((:fraction#лорана рациональной функцией)) от переменной// $ x $. //В этом случае// $ \operatorname{rank} (H) $ //совпадает с числом полюсов функции// $ R(x) $, //с учетом кратности каждого полюса.//
===Аппроксимация: метод наименьших квадратов==
!!§!! Раздел
☞
((:interpolation:mnk МЕТОД НАИМЕНЬШИХ КВАДРАТОВ))
Пусть в заданной таблице экспериментальных значений
$$
\begin{array}{c|ccccc}
x & x_1 & x_2 & \dots & x_m \\ \hline
y & y_1 & y_2 &\dots & y_m
\end{array} \quad \{ x_j,y_j\}_{j=1}^m \subset \mathbb R
$$
величины $ x_{} $ нам известны без искажений, а вот измерения величины $ y_{} $ подвержены случайным погрешностям.
**Задача.** Построить полином $ f_{}(x) $ такой, чтобы величина
$$
\sum_{j=1}^m (f(x_j)-y_j)^2
$$
стала минимальной.
В случае $ \deg f_{} =m-1 $ получаем классическую задачу ((:interpolation#polinomialnaja_interpoljacija полиномиальной интерполяции)). Практический интерес, однако, представляет случай $ \deg f_{} < m-1 $: экспериментальных данных больше (обычно --- много больше) чем значений параметров (коэффициентов полинома $ f_{} $), которые требуется определить.
!!Т!! **Теорема.** //Если// $ m\ge n_{} $ и $ x_{1},\dots,x_m $ //все различны, то
существует единственный набор коэффициентов// $ a_{0},\dots,a_{n-1} $, //обеспечивающий
минимальное значение для//
$$
\sum_{j=1}^m (a_0+a_1x_j+\dots+a_{n-1}x_j^{n-1} -y_j)^2 \ .
$$
//Этот набор определяется как решение// **системы нормальных уравнений**
$$
\underbrace{
\left(\begin{array}{llllll}
s_0 &s_1&s_2&\ldots&s_{n-2}& s_{n-1}\\
s_1 &s_2&s_3&\ldots&s_{n-1}& s_{n}\\
s_2 &s_3&s_4&\ldots&s_{n}& s_{n+1}\\
\vdots& & & && \vdots\\
s_{n-1} &s_n&s_{n+1}&\ldots &s_{2n-3}&s_{2n-2}
\end{array}\right)}_{\displaystyle S_{n\times n}}
\left(\begin{array}{l}
a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_{n-1} \end{array} \right)=
\left(\begin{array}{l}
t_0 \\ t_1 \\ t_2 \\ \vdots \\ t_{n-1} \end{array} \right)
$$
//при// $ s_{k} = x_1^k+\dots+x_m^k, \ t_{k} = x_1^ky_1+\dots+x_m^k y_m $.
===Аппроксимация: функциональный метод наименьших квадратов==
**Задача.** Для функции $ f(x_{}) $, непрерывной на $ [0_{},1] $, построить полином $ f_{n-1}(x_{})=a_0+a_1x+\dots+a_{n-1}x^{n-1} $ такой, чтобы величина
$$ \int_0^1 \left[f_{n-1}(x)-f(x) \right]^2 d\, x $$
была наименьшей.
!!Т!! **Теорема.** //Коэффициенты полинома// $ f_{n-1}(x_{}) $ //находятся из системы уравнений//
$$
\left(
\begin{array}{lllll}
1 & \frac{1}{2} & \frac{1}{3} & \dots & \frac{1}{n} \\
&&&& \\
\frac{1}{2} & \frac{1}{3} & \frac{1}{4} & \dots & \frac{1}{n+1} \\
&&&& \\
\frac{1}{3} & \frac{1}{4} & \frac{1}{5} & \dots & \frac{1}{n+2} \\
&&&& \\
\dots & & & & \dots \\
&&&& \\
\frac{1}{n} & \frac{1}{n+1} & \frac{1}{n+2} & \dots & \frac{1}{2n-1}
\end{array}
\right)
\left(
\begin{array}{l}
a_0 \\
a_1 \\
a_2 \\
\vdots \\
a_{n-1}
\end{array}
\right)=
\left(
\begin{array}{l}
b_0 \\
b_1 \\
b_2 \\
\vdots \\
b_{n-1}
\end{array}
\right) \ .
$$
//Здесь//
$$
b_{j}=\int_0^1 f(x) x^{j} d\, x \quad npu \quad j\in \{0,\dots,n-1 \} .
$$
Матрица $ {\mathfrak H}_{n} $ системы называется **матрицей Гильберта**. Ее определитель ((:algebra2:dets:special_cases:vspom1 равен))
$$
\frac{[1!\,2!\, 3! \dots (n-1)!]^3}
{n!\, (n+1)!\, (n+2)!\, \dots (2n-1)!} \ ,
$$
т.е. отличен от нуля, и, ((algebra2:linearsystems#Формулы_Крамера следовательно)), система имеет единственное решение.
Матрица Гильберта ((:algebra2:condnumber плохо обусловлена)):
$$
\det {\mathfrak H}_3=\frac{1}{2160},\ \det {\mathfrak H}_4=\frac{1}{6\,048\,000},\
\det {\mathfrak H}_6=\frac{1}{186313420339200000}
$$
поэтому при решении линейной системы надо внимательно следить за ошибками округлений.
===Результант и наибольший общий делитель полиномов==
!!§!! Раздел
☞
((:dets:resultant Результант)).
Для полиномов
$$
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) $ в ((:fraction#лорана ряд Лорана)) по отрицательным степеням $ 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}
$$
В случае $ m0 $, //необходимо и достаточно, чтобы были выполнены условия//
$$\underbrace{C_n=0,\ C_{n-1}= 0,\ \dots , C_{n-k+1}=0}_k, C_{n-k}\ne 0.$$
===Дискриминант и локализация корней полинома==
!!§!! Раздел
☞
((:dets:discrim Дискриминант)); раздел
☞
((:polynomial:zero_local Локализация корней полинома)).
**Дискриминант** полинома $ f(x)=a_{0}x^n+a_1x^{n-1}+\dots+a_n, (n>1, a_0\ne 0) $ фактически совпадает с ((dets:resultant результантом)) этого полинома и его ((:polynomial#производные_от_полинома производной)):
$$
{\mathcal D}(f)=\frac{(-1)^{n(n-1)/2}}{a_0}{\mathcal R}(f(x),f^{\prime}(x)) \ .
$$
!!Т!! **Теорема.** $ {\mathcal D}(f_{}) = 0 $ //тогда и только тогда, когда// $ f_{}(x) $ //имеет
((:polynomial#основная_теорема_высшей_алгебры кратный корень))//.
Существует несколько способов представления дискриминанта в виде определителя матрицы, зависящей от коэффициентов полинома $ 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 $ дается ((dets:discrim:waring#формула_варинга формулой Варинга)).
Вычислим суммы Ньютона $ 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 $ ее ((:algebra2:dets#теорема_лапласа главные миноры)).
!!Т!! **Теорема.** //Имеет место формула//
$$
{\mathcal D}_{k}=n^{n-k-2}a_0^{2(n-k-1)}S_{n-k} \ ,
$$
//связывающая миноры матрицы// $ S_{} $ //с// ((:dets:discrim#субдискриминанты субдискриминантами)).// В частности,// $$
{\mathcal D}(f)=a_0^{2n-2}\det S \ .
$$
**Доказательство** следует из ((#результант_и_наибольший_общий_делитель_полиномов теоремы Кронекера)).
Матрицу $ S $ из предыдущей теоремы можно использовать и для локализации вещественных корней полинома $ f_{}(x) $, имеющего вещественные коэффициенты.
!!Т!! **Теорема [Якоби].** //Число различных корней полинома// $ f_{}(x)\in \mathbb R[x] $ //равно ((algebra2:rank рангу)), а число различных вещественных корней// $ f_{}(x) $ //--- ((:2form#закон_инерции сигнатуре матрицы))// $ 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}_{} $ --- ((algebra2:notations#число_знакопостоянств_знакоперемен число знакопостоянств)) и $ {\mathcal V}_{} $ --- ((algebra2:notations#число_знакопостоянств_знакоперемен число знакоперемен)).
Идею, использованную при доказательстве теоремы Якоби можно развить и для
((:polynomial:zero_local задачи отделения (локализации) корней полинома)) $ 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
В случае, когда в ряду встречаются несколько подряд идущих нулей (например, $ f(x)=x^4-1, a=0 $), то можно воспользоваться правилом Кронекера-Хатендорфа:
$$
\operatorname{nrr} \{ f(x)=0 \mid a
Таким образом система ганкелевых полиномов $ \{\mathcal H_{\ell}(t)\}_{{\ell}=1}^{\mathfrak r} $, порожденная последовательностью сумм Ньютона полинома $ f(x) $, играет роль системы полиномов
Штурма для этого полинома. В отличие от ((:polynomial:zero_local#система_полиномов_штурма традиционной системы полиномов Штурма)), построенной с помощью алгоритма Евклида, здесь степени полиномов $ \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 $.
!!$!! Как теоремы Йоахимшталя связаны с $ $ $ ? ;-)
Фактическое построение ганкелевых полиномов из теоремы производится не непосредственным вычислением соответствующих определителей, зависящих от параметра (эта процедура ((algebra2:dets:special_cases весьма затратна))), а посредством применения рекурсивной формулы --- **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
[?]. **Hilbert D.** //Ein Beitrag zur Theorie des Legendreschen Polynoms.// Acta Math. Bd.18, 1894, S.155-160
[?]. **Форсайт Дж., Молер К.** //Численное решение систем линейных алгебраических уравнений.// М. Мир. 1969
[?]. **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.
[?]. **Uteshev A., Baravy I., Kalinina E.** //Rational Interpolation: Jacobi's Approach Reminiscence.// Symmetry, 2021, **13** (8), 1401 Текст --- в открытом доступе
☞
{{:references:symmetry-13-01401.pdf}}