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


§

Вспомогательная страница к разделу ГАНКЕЛЕВЫ МАТРИЦЫ, ОПРЕДЕЛИТЕЛИ И ПОЛИНОМЫ


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

Обозначения. Ганкелев полином $ 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-тождеством.

Доказательство совпадает с оригинальным доказательством Йоахимшталя1)

Лемма. Пусть ганкелев полином $ \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} или, эквивалентно, \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 $ сумм Ньютона которого совпадают с $ \{ 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$. Но этот случай покрывается теоремой Вейля (принципом несущественности алгебраических неравенств). Левая часть доказываемого тождества и $ 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} \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 $. Существует модификация алгоритма и для этого случая.

Т

Теорема. [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} \, . $$

Ортогональные полиномы

Источники

[1]. Jacobi C.G.J. De eliminatione variabilis e duabus aequationibus algebraicis. J. Reine Angew. Math. 1836, Bd. 15, S. 101-124.

[2]. Joachimsthal F. Bemerkungen über den Sturm'schen Satz. J.reine angew. Math. 1854. Bd. 48, S. 386-416

[3]. Uteshev A., Baravy I., Kalinina E. Rational Interpolation: Jacobi's Approach Reminiscence. Symmetry, 2021, 13 (8), 1401 Текст — в открытом доступе symmetry-13-01401.pdf

1)
В современных обозначениях и с небольшим дополнением.
algebra2/hankel/jjidentity.txt · Последние изменения: 2021/09/09 11:03 — au