!!§!! Вспомогательная страница к разделу ((:algebra2/hankel ГАНКЕЛЕВЫ МАТРИЦЫ, ОПРЕДЕЛИТЕЛИ И ПОЛИНОМЫ))
----
==Рекурсивная формула для ганкелевых полиномов==
~~TOC~~
Обозначения. Ганкелев полином $ k $-го порядка по переменной $ x $, порожденный числовой последовательностью $ \{c\} =\{c_0,c_1,\dots \} $:
$$
\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)}
$$
Коэффициенты будем обозначать $ h_{kj} $; таким образом
$$
\mathcal H_k(x; \{c\})\equiv h_{k0} x^k +h_{k1} x^{k-1} +\dots + h_{kk} \ ;
$$
Коэффициент при $ x^k $ является ганкелевым определителем
$$ h_{k0} = H_k(\{c\}):=
\left|
\begin{array}{llll}
c_0 & c_1 & c_2 & \ldots & c_{k-1} \\
c_1 & c_2 & c_3 &\ldots & c_{k} \\
\vdots & & & \ddots& \vdots \\
c_{k-1} & c_{k} & c_{k+1} & \ldots & c_{2k-2}
\end{array} \right|_{k \times k} \, .
$$
Он может обращаться в нуль, так что степень ганкелевого полинома $ k_{} $-го порядка может оказаться меньшей $ k_{} $.
В дальнейшем будем часто использовать сокращенные обозначения ганкелевых полиномов и определителей $ \mathcal H_л(x) $ и $ 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 \ .
$$
♦
!!Т!! **Теорема [Якоби, Йоахимшталь].** //Любые три ганкелевых полинома// $ \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**-**тождеством**.
**Доказательство** совпадает с оригинальным доказательством Йоахимшталя[[В современных обозначениях и с небольшим дополнением.]]
**Лемма.** //Пусть ганкелев полином// $ \mathcal H_k(x) $ //порожден последовательностью//
$$
\left\{ c_j=\sum_{\ell=1}^m \lambda_{\ell}^j \right\}_{j=0}^{2k-1}
$$
//при произвольных различных// $ \lambda_1,\dots,\lambda_m $ //при// $ m > k $ (т.е. $ c_0=m $).
//Тогда справедливы следующие равенства//
$$
\sum_{\ell=1}^m \lambda_{\ell}^j \mathcal H_k(\lambda_{\ell}) =
\left\{ \begin{array}{ll}
0 & \mbox{при} \ j \in \{0,\dots, k-1\}, \\
H_{k+1} & \mbox{при} \ j = k \, .
\end{array} \right.
$$
**Доказательство леммы.**
$$ \lambda_1^j \mathcal H_k(\lambda_1) + \lambda_2^j \mathcal H_k(\lambda_2) + \dots + \lambda_m^j \mathcal H_k(\lambda_m)=
$$
$$
=\lambda_1^j\left|
\begin{array}{llll}
c_0 & c_1 & \ldots & c_{k} \\
c_1 & c_2 & \ldots & c_{k+1} \\
\vdots & \vdots & & \vdots \\
c_{k-1} & c_{k} & \ldots & c_{2k-1} \\
1 & \lambda_1 & \ldots & \lambda_1^{k}
\end{array}
\right|+
\dots+
\lambda_m^j\left|
\begin{array}{llll}
c_0 & c_1 & \ldots & c_{k} \\
c_1 & c_2 & \ldots & c_{k+1} \\
\vdots & \vdots & & \vdots \\
c_{k-1} & c_{k} & \ldots & c_{2k-1} \\
1 & \lambda_m & \ldots & \lambda_m^{k}
\end{array}
\right| \, .
$$
Используя линейное свойство определителя, преобразуем линейную комбинацию определителей в один:
$$
\left|
\begin{array}{llll}
c_0 & c_1 & \ldots & c_{k} \\
c_1 & c_2 & \ldots & c_{k+1} \\
\vdots & \vdots & & \vdots \\
c_{k-1} & c_{k} & \ldots & c_{2k-1} \\
c_j & c_{j+1} & \ldots & c_{j+k}
\end{array}
\right| \, .
$$
При $ j < k $ последний определитель имеет две одинаковые строки. Следовательно, в этом случае он равен $ 0 $. При $ j=k $ полученный определитель совпадает с $ H_{k+1} $.
----
**Доказательство теоремы.** Рассмотрим сначала случай когда последовательность, порождающая полиномы
$ \mathcal H_{k-2}(x), \mathcal H_{k-1}(x), \mathcal H_{k}(x) $ задается формулами из леммы:
$$
\left\{ c_j=\sum_{\ell=1}^m \lambda_{\ell}^j \right\}_{j=0}^{2k-1}
$$
при произвольных различных $ \lambda_1,\dots,\lambda_m $ при $ m > k $ (т.е. $ c_0=m $).
В предположении $ H_{k-1}\ne 0 $ (т.е. $ \deg \mathcal H_{k-1}(x)= k-1 $) разделим $ \mathcal H_k(x) $ на $ \mathcal H_{k-1}(x) $:
\begin{equation}
\mathcal H_k(x) \equiv Q(x) \mathcal H_{k-1}(x) +R(x) \, .
\end{equation}
Неопределенные коэффициенты частного $ Q(x) $ могут быть выражены через коэффициенты
$ \mathcal H_k(x) $ и $ \mathcal H_{k-1}(x) $ приравниванием коэффициентов при соответствующих степенях
$ x $ в обеих частях этого тождества:
\begin{equation}
Q(x)=Q_0+Q_1x \quad \mbox{ где } \ Q_1=\frac{H_k}{H_{k-1}}\, ,\ Q_0=\frac{H_{k-1}h_{k1}-H_kh_{k-1,1}}{H_{k-1}^2} \, ,
\end{equation}
или, ((:polynomial:remquo эквивалентно)),
\begin{equation}
Q(x) \equiv \frac{1}{H_{k-1}^2}\left|\begin{array}{ccc} 0 & H_{k-1} & H_k \\ H_{k-1} & h_{k-1,1} & h_{k1} \\ 1 & x & 0 \end{array} \right|
\enspace .
\end{equation}
Для определения коэффициентов остатка
\begin{equation}
R(x) = R_0+R_1x+\dots+ R_{k-2}x^{k-2}
\end{equation}
подставляем $ x = \lambda_1,\dots,x=\lambda_m $ в
$$
\mathcal H_k(x) \equiv Q(x) \mathcal H_{k-1}(x) +R(x) \, ,
$$
и получаем
\begin{equation}
\left\{\mathcal H_k(\lambda_{\ell}) = \left(Q_1\lambda_{\ell}+Q_0 \right) \mathcal H_{k-1}(\lambda_{\ell})
+ \left( R_0+R_1\lambda_{\ell}+\dots+ R_{k-2}\lambda_{\ell}^{k-2}\right)\right\}_{\ell=1}^m \, .
\end{equation}
Суммируем эти равенства:
$$
\sum_{\ell=1}^m \mathcal H_k(\lambda_{\ell})
=Q_0\sum_{\ell=1}^m \mathcal H_{k-1}(\lambda_{\ell})+Q_1 \sum_{\ell=1}^m \lambda_{\ell}\mathcal H_{k-1}(\lambda_{\ell})
+ (c_0R_0+c_1R_1+\dots+c_{k-2}R_{k-2}) \, .
$$
На основании леммы, имеем:
$$
0=c_0R_0+c_1R_1+\dots+c_{k-2}R_{k-2} \, .
$$
Далее, умножаем каждое равенство
\begin{equation}
\left\{\mathcal H_k(\lambda_{\ell}) = \left(Q_1\lambda_{\ell}+Q_0 \right) \mathcal H_{k-1}(\lambda_{\ell})
+ \left( R_0+R_1\lambda_{\ell}+\dots+ R_{k-2}\lambda_{\ell}^{k-2}\right)\right\}_{\ell=1}^m \, .
\end{equation}
на соответствующее $ \lambda_{\ell}^j $ и суммируем полученное по $ \ell $. Для $ j\in \{1,\dots, k-3\} $ получающиеся равенства подобны выведенному выше:
$$
0=c_jR_0+c_{j+1}R_1+\dots+c_{j+k-2}R_{k-2} \, .
$$
Домножение равенств
\begin{equation}
\left\{\mathcal H_k(\lambda_{\ell}) = \left(Q_1\lambda_{\ell}+Q_0 \right) \mathcal H_{k-1}(\lambda_{\ell})
+ \left( R_0+R_1\lambda_{\ell}+\dots+ R_{k-2}\lambda_{\ell}^{k-2}\right)\right\}_{\ell=1}^m \, .
\end{equation}
на $ \lambda_{\ell}^{k-2} $ приводит к несколько иному соотношению
$$
0=H_k Q_1+ c_{k-2}R_0+c_{k-1}R_1+\dots+c_{2k-4}R_{k-2} \, .
$$
Объединяя все полученные уравнения для $ R_0,\dots,R_{k-2} $ с равенством
$$
R(x)=R_0+R_1x+\dots+ R_{k-2}x^{k-2}
$$
получаем систему уравнений
$$
\left\{\begin{array}{rrrrrr}
c_0R_0 &+c_1R_1 &+\dots & +c_{k-2}R_{k-2} & & =0, \\
c_1R_0 &+c_2R_1 &+\dots & +c_{k-1}R_{k-2} & & =0, \\
\dots & & & & & \dots \\
c_{k-3}R_0 & +c_{k-2}R_1 & +\dots &+c_{2k-5}R_{k-2} & & =0, \\
c_{k-2}R_0 & +c_{k-1}R_1 & +\dots &+c_{2k-4}R_{k-2} &+H_kQ_1 & =0,\\
R_0& +xR_1 &+\dots &+ x^{k-2}R_{k-2} & -R(x) & =0.
\end{array}
\right.
$$
Рассмотрим ее как систему однородных уравнений относительно $ R_0,R_1,\dots,R_{k-2}$ и $ 1 $.
Поскольку она обладает нетривиальным решением, ее определитель должен равняться нулю:
$$
\left|
\begin{array}{llllc}
c_0 & c_1 & \dots & c_{k-2} & 0 \\
c_1 & c_2 & \dots & c_{k-1} & 0 \\
\vdots & \vdots & & \vdots & \vdots \\
c_{k-3} & c_{k-2} & \dots & c_{2k-5} & 0 \\
c_{k-2} & c_{k-1} & \dots & c_{2k-4} & H_kQ_1 \\
1 & x & \dots & x^{k-2} & -R(x)
\end{array}
\right|=0 \, .
$$
Раскладываем определитель по последнему столбцу:
$$
H_{k-1}R(x) + H_kQ_1 \mathcal H_{k-2}(x) \equiv 0 \, .
$$
Вместе с уже полученным выше выражением для $ Q_1 $, это подтверждает справедливость тождества из формулировки теоремы
по крайней мере для частного случая выбора генерирующей последовательности
$$
\left\{ c_j=\sum_{\ell=1}^m \lambda_{\ell}^j \right\}_{j=0}^{2k-1} \, .
$$
Рассмотрим теперь случай произвольной генерирующей последовательности. Для любой последовательности комплексных чисел
$ c_1,\dots,c_{2k-1} $ можно найти комплексные числа $ \lambda_1,\dots, \lambda_{m} $ при $ m > 2k-1 $ такие, что будут справедливыми равенства
$$
\left\{ c_j=\sum_{\ell=1}^m \lambda_{\ell}^j \right\}_{j=0}^{2k-1} \, .
$$
Эти числа могут быть взяты как корни полинома степени $ m $, первые $ 2k-1 $ ((:dets/discrim/waring сумм Ньютона)) которого совпадают с
$ \{ c_j \}_{j=1}^{2k-1} $.
Требуется ликвидировать единственный пробел в рассуждениях предыдущего абзаца. В то время как числа
$ c_1,\dots,c_{2k-1} $ могут выбираться произвольными, число $ c_0 $ может быть только натуральным: $ c_0=m $.
Таким образом справедливость **JJ**-тождества доказана только для натуральных $ c_0 $. Однако, поскольку это тождество является алгебраическим относительно $ c_0 $ и выполняется для бесконечного набора натуральных чисел, то оно должно выполняться и при всех $ c_0 \in \mathbb C $.
Йоахимшталь не доказывал **JJ**-тождество для случая $ H_{k-1} = 0$. Но этот случай покрывается ((:polynomialm/weyl теоремой Вейля)) (принципом несущественности алгебраических неравенств). Левая часть доказываемого тождества и $ H_{k-1} $ являются полиномами относительно $ c_0,\dots,c_{2k-1} $.
♦
**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}
$$
при
$$
h_{k-1,0}=H_{k-1}\ne 0 \, .
$$
Тогда в **JJ**-тождестве, представленном в виде
$$
\mathcal H_{k}(x) \equiv\left( \frac{H_k}{H_{k-1}}x+\frac{h_{k,1}}{H_{k-1}} - \frac{H_kh_{k-1,1}}{H_{k-1}^2} \right) \mathcal H_{k-1}(x) - \frac{H_k^2}{H_{k-1}^2} \mathcal H_{k-2}(x) \, ,
$$
известны значения всех констант, за исключением $ 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|
$$
только своими последними столбцами. ((:algebra2/dets#minory_i_algebraicheskie_dopolnenija Разложения определителей)) по элементам этих последних столбцов имеют одинаковые значения для соответствующих алгебраических дополнений,
и поэтому следующие формулы
$$
\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 $. Существует модификация алгоритма и для этого случая.
!!Т!! **Теорема. ((#источники [3]))** //Пусть// $ H_{k-2} \ne 0, H_{k-1}=0 $. //Если// $ h_{k-1,1}=0 $, //то//
$$
\mathcal H_{k-1}(x) \equiv 0
$$
//и//
$$
\mathcal H_k(x) \equiv \frac{h_{k2}}{H_{k-2}} \mathcal H_{k-2}(x) \, .
$$
//В противном случае//
$$
\mathcal H_{k-1}(x) \equiv \frac{h_{k-1,1}}{H_{k-2}}\mathcal H_{k-2}(x)
$$
//и//
$$
\mathcal H_k(x) \equiv \frac{1}{H_{k-2}^3} \left(H_kH_{k-2}h_{k-1,1}\mathcal H_{k-3}(x)- \left|\begin{array}{cccc} H_{k-2} & 0 & 0 & H_k \\ h_{k-2,1} & H_{k-2} & 0 & h_{k1} \\
h_{k-2,2} & h_{k-2,1} & H_{k-2} & h_{k2} \\
x^2 & x & 1 & 0 \end{array} \right| \mathcal H_{k-2}(x) \right) \, .
$$
Последняя формула позволяет организовать рекурсивное вычисление
$ \mathcal H_k(x) $ на основе уже вычисленных полиномов $ \mathcal H_{k-2}(x) $ и
$ \mathcal H_{k-3}(x) $. Все содержащиеся в правой части константы, такие как $ h_{k-2,1} $, $ h_{k-2,2} $, $ h_{k-1,1} $ и $ h_{k1} $, либо уже определены как коэффициенты $ \mathcal H_{k-2}(x), \mathcal H_{k-3}(x) $, либо могут быть вычислены по формулам предыдущего пункта. Единственным исключением является $ h_{k2} $. Для определения этой величины
используется следующий результат.
!!Т!! **Теорема ((#источники [3])).** //Если// $H_{k-2} \ne 0, H_{k-1} = 0 $, //то//:
$$
h_{k2}=
-\frac{1}{H_{k-2}} \left|
\begin{array}{llll}
c_0 & c_1 & \dots & c_{k-2} \\
c_1 & c_2 & \dots & c_{k-1} \\
\vdots & \vdots & & \vdots \\
c_{k-3} & c_{k-2} & \dots & c_{2k-5} \\
c_{k} & c_{k+1} & \dots & c_{2k-2}
\end{array}
\right|^2 -
\left|
\begin{array}{llll}
c_0 & c_1 & \dots & c_{k-1} \\
c_1 & c_2 & \dots & c_{k} \\
\vdots & \vdots & & \vdots \\
c_{k-2} & c_{k-1} & \dots & c_{2k-3} \\
c_{k+1} & c_{k+2} & \dots & c_{2k}
\end{array}
\right|=
$$
$$
=-\frac{1}{H_{k-2}}\left(\sum_{j=0}^{k-2} h_{k-2,j} c_{2k-j-2} \right)^2- \sum_{j=1}^{k-1}h_{k-1,j}c_{2k-j} \, .
$$
==Ортогональные полиномы==
Рассмотрим линейное пространство $ \mathbb P_{n} $ ((:polynomial полиномов одной переменной)) степеней $ \le n_{} $ с вещественными коэффициентами.
В этом пространстве ((:euclid_space#opredelenija скалярное произведение)) можно вводить разными способами. Так, если
полиномы представлены в канонической форме[[Здесь допустимо $ \deg p(x) < n, \deg q(x) < n $]]
$$ p(x)=a_{0}x^n+a_1x^{n-1}+\dots + a_n \quad \mbox{ и } \quad
q(x)=b_{0}x^n+b_1x^{n-1}+\dots + b_n \ , $$
то их скалярное произведение можно ввести
1.
формулой
$$
\langle p(x), q(x) \rangle = \sum_{j=0}^n a_j b_j \, .
$$
С другой стороны, можно взять за определение и
2.
формулу
$$
\langle p(x), q(x) \rangle = \int_{a}^b p(t)q(t) d\,t
$$
при некоторых фиксированных вещественных константах $ a_{} $ и $ b_{} $, $ a_{}
3.