!!§!! Вспомогательная результат к разделу ☞ ((:recurr РАЗНОСТНОЕ УРАВНЕНИЕ И РЕКУРРЕНТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ)). Существенно используются материалы раздела ((:algebra2:hankel Ганкелевы матрицы, определители и полиномы)). !!⊗!! Страница --- в разработке. Начало работ --- 20.04.2016, окончание --- ??.??.????. ---- ==Генерация характеристического полинома рекуррентной последовательности== !!?!! Известны первые члены линейной рекуррентной последовательности: $$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,... $$ Чему равен следующий? !!Т!! **Теорема.** //Пусть имеется последовательность// $ \{x_j\}_{j=0}^{\infty} $. //Если эта последовательность является решением линейного однородного разностного уравнения порядка// $ \le n_{} $ //, то все ((:algebra2/dets#теорема_лапласа главные миноры))// $ S_0,S_1,S_2,\dots $ //бесконечной ((:algebra2#ганкелева ганкелевой матрицы))// $$ S=\left( \begin{array}{lllll} x_0 & x_1 & x_2 & x_3 & \dots \\ x_1 & x_2 & x_3 & x_4 & \dots \\ x_2 & x_3 & x_4 & x_5 & \dots \\ \dots & & & & \end{array} \right) $$ //начиная с порядка// $ n+1 $ //будут равны// $ 0_{} $. //В этом случае разностное уравнение должно иметь вид// $$ \left| \begin{array}{llllll} x_0 & x_1 & x_2 & x_3 & \dots & x_n \\ x_1 & x_2 & x_3 & x_4 & \dots & x_{n+1} \\ x_2 & x_3 & x_4 & x_5 & \dots & x_{n+2}\\ \dots & & & & & \dots \\ x_{n-1} & x_n & x_{n+1} & & \dots & x_{2n-1} \\ {\color{RubineRed} x_K} & {\color{RubineRed} x_{K+1}} & {\color{RubineRed} x_{K+2}} & & \dots & {\color{RubineRed} x_{K+n}} \end{array} \right|_{n+1}=0 \ . $$ //При дополнительных условиях// $$ S_n \ne 0, \tilde S_n = \left| \begin{array}{lllll} x_1 & x_2 & \dots & x_{n-1} & x_n \\ x_2 & x_3 & \dots & x_n & x_{n+1}\\ x_3 & x_4 & & x_{n+1} & x_{n+2} \\ \dots & & & & \dots \\ x_{n} & x_{n+1} & \dots & x_{2n-2} & x_{2n-1} \end{array} \right| \ne 0 $$ //это уравнение будет уравнением в точности// $ n_{} $-//го порядка.// **Доказательство.** Если элементы последовательности удовлетворяют некоторому уравнению вида $$ a_0x_{n+K}+a_1 x_{n+K-1}+ \dots+ a_n x_K = 0 \quad npu \ K\in \{0,1,2,\dots \} $$ при хотя бы одном коэффициенте из $ a_0,a_1,\dots,a_n $ отличном от нуля, то справедливы равенства $$ \begin{array}{lllll} a_n x_0&+ a_{n-1}x_1& + \dots &+a_0x_n & =0, \\ a_n x_1&+ a_{n-1}x_2& + \dots &+a_0x_{n+1} & =0, \\ \dots & & & & \dots \\ a_n x_n&+ a_{n-1}x_{n+1}& + \dots &+a_0x_{2n} & =0. \end{array} $$ Эти равенства составляют систему линейных однородных уравнений относительно коэффициентов. По предположению, система совместна и имеет нетривиальное решение. Но тогда (см. ☞ ((:algebra2:linearsystems#система_однородных_уравнений ЗДЕСЬ))) ее определитель $$ \left| \begin{array}{llllll} x_0 & x_1 & x_2 & x_3 & \dots & x_n \\ x_1 & x_2 & x_3 & x_4 & \dots & x_{n+1} \\ x_2 & x_3 & x_4 & x_5 & \dots & x_{n+2}\\ \dots & & & & & \dots \\ x_{n-1} & x_n & x_{n+1} & & \dots & x_{2n-1} \\ x_{n} & x_{n+1} & x_{n+2} & & \dots & x_{2n} \end{array} \right|_{n+1} $$ должен быть равен нулю. Этот определитель совпадает с $ S_{n+1} $ из условия теоремы. Равенство нулю $ S_{n+2}, S_{n+3}, \dots $ доказывается аналогично: если последовательность удовлетворяет уравнению $$ a_0x_{n+K}+a_1 x_{n+K-1}+ \dots+ a_n x_K = 0 \ , $$ то она удовлетворяет и уравнению $$ a_0x_{n+K+1}+a_1 x_{n+K}+ \dots+ a_n x_{K+1}+a_{n+1}x_K = 0 \quad npu \ a_{n+1}=0 \, . $$ Далее, при равенстве нулю определителя матрицы системы уравнений $$ \left(\begin{array}{lllll} x_0 & x_1 & x_2 & \dots & x_n \\ x_1 & x_2 & x_3 & \dots & x_{n+1} \\ \vdots & & & & \vdots \\ x_{n-1} & x_n & x_{n+1} & \dots & x_{2n-1} \\ x_{n} & x_{n+1} & x_{n+2} & \dots & x_{2n} \end{array} \right) \left( \begin{array}{l} a_n \\ a_{n-1} \\ a_{n-2} \\ \vdots \\ a_0 \end{array} \right)= \mathbb O $$ ее фундаментальная система решений будет состоять из единственного набора значений если $ S_n \ne 0 $. Этот набор решений ((:algebra2:linearsystems#система_однородных_уравнений может быть построен)) с помощью алгебраических дополнений к элементам последней строки матрицы: $$ a_n= (-1)^n\left|\begin{array}{llll} x_1 & x_2 & \dots & x_n \\ x_2 & x_3 & \dots & x_{n+1} \\ \vdots & & & \vdots \\ x_n & x_{n+1} & \dots & x_{2n-1} \end{array} \right| , a_{n-1}= (-1)^{n-1}\left|\begin{array}{llll} x_0 & x_2 & \dots & x_n \\ x_1 & x_3 & \dots & x_{n+1} \\ \vdots & & & \vdots \\ x_{n-1} & x_{n+1} & \dots & x_{2n-1} \end{array} \right|, \dots, a_0= S_n \ . $$ Но это и означает, что разностное уравнение имеет то представление в виде определителя, что указано в теореме. ♦ !!П!! **Пример 1.** Известны первые члены линейной рекуррентной последовательности: $$ 0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,... $$ Чему равен следующий? **Решение.** Имеем: $$ S= \left( \begin{array}{rrrrrrrr} 0 & 1 & 2 &2 &0 & -9 & -38 & \dots \\ 1 & 2 & 2 & 0 & -9 & -38 & -123 & \dots \\ 2 & 2 & 0 & -9 & -38 & -123 & -360 & \dots \\ 2 & 0 & -9 & -38 & -123 & -360 & -1004 & \dots \\ 0 & -9 & -38 & -123 & -360 & -1004 & -2728 & \dots \\ -9 & -38 & -123 & -360 & -1004 & -2728 & -7303 & \dots \\ \dots & & & & & & \end{array} \right) $$ Вычисляем главные миноры: $$ S_1=0,S_2=2,S_3=0,S_4=25,S_5=0,S_6=0,\dots $$ Больше главных миноров вычислить невозможно поскольку последовательность обрывается. Выдвинем в качестве __рабочей гипотезы__, что наша последовательность "разворачивается в бесконечность" как линейная рекуррентная последовательность порядка $ \le 4 $. Тогда, в соответствии с теоремой эта последовательность является решением разностного уравнения $$ \left| \begin{array}{rrrrr} 0 & 1 & 2 &2 &0 \\ 1 & 2 & 2 & 0 & -9 \\ 2 & 2 & 0 & -9 & -38 \\ 2 & 0 & -9 & -38 & -123 \\ x_K & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right|=0 $$ Раскладываем определитель по последней строке: $$ 25\,x_{K+4}-100\,x_{K+3}+75\,x_{K+2}+50\,x_{K+1}-25\,x_K=0 \iff x_{K+4}=4\,x_{K+3}-3\,x_{K+2}-2\,x_{K+1}+\,x_K \ . $$ По имеющейся у нас информации нельзя гарантировать абсолютную истинность полученного ответа: любую последовательность можно так "испортить" в одном-единственном элементе, чтобы после обращения в нуль любого подряд идущего набора главных миноров матрицы $ S_{} $, очередной главный минор стал бы отличным от нуля. Так что ответ в задаче приходится формулировать так: **Ответ.** Если автор задачи не задумал особенную подлость, то очередной элемент последовательности равен $ (-19380) $. Справедлив и более общий результат, который основан на понятии ранга бесконечной матрицы. По аналогии с ((:algebra2:rank#ранг_матрицы конечными матрицами)), будем считать ранг бесконечной матрицы равным $ \mathfrak r \in \mathbb N $ если все ее миноры порядка $ \mathfrak r+1 $ равны нулю, и существует хотя бы один минор порядка $ \mathfrak r $ отличный от нуля. !!Т!! **Теорема.** //Бесконечная ганкелева матрица// $$ H=\left[h_{i+j-2}\right]_{i,j=1}^{\infty} $$ //имеет конечный ранг// $ n_{} $ //тогда и только тогда, когда существуют числа// $ a_0,a_1,\dots,a_{n-1} $ //такие, что// $$ h_{n+K}=a_0h_{n+K-1}+a_1h_{n+K-2}+\dots+a_{n-1}h_{K} \quad npu \quad K\in \{0,1,\dots \} \, , $$ //т.е. последовательность// $ \{ h_j\}_{j=0}^{\infty} $ //является линейной рекуррентной последовательностью порядка// $ \le n $. !!П!! **Пример 2.** Найти линейное разностное уравнение задающее последовательность $$ x_0=-2,\ x_1=-3,\ x_2=-1,\ x_3=2,\ x_4=4,\ x_5=-4,\ $$ $$ x_6=-5,\ x_7=26,\ x_8=11,\ x_9=-85,\ x_{10}=44,\ x_{11}=308,\dots $$ **Решение.** В отсутствие гипотезы о порядке линейного разностного уравнения, имеет смысл организовать процедуру вычисления кандидата последовательно, начиная с минимально возможного. Так, в рассмотренном примере мы могли бы выдвинуть сначала гипотезу о том, что этот порядок равен $ 1 $: $$ \left| \begin{array}{rr} -2 & -3 \\ x_{K} & x_{K+1} \end{array} \right|=0 \quad \iff \quad -2\, x_{K+1}+3\,x_K=0 \, . $$ Это уравнение правильно определяет элемент последовательности $ x_{1} $ по значению $ x_{0} $. Но величина $ x_2 $ определяется с ошибкой. Рассмотрим следующий по порядку определитель: $$ \left| \begin{array}{rrr} -2 & -3 & -1 \\ -3 & -1 & 2 \\ x_{K} & x_{K+1} & x_{K+2} \end{array} \right|=0 \quad \iff \quad -7\,x_{K+2}+7\,x_{K+1}-7\, x_K =0 \quad \iff \quad x_{K+2}=x_{K+1}-x_K \, . $$ Элементы последовательности $ x_2, x_3 $ определяются из этого уравнения (и из данных значений $ x_0,x_1 $) правильно, но $ x_4 $ определяется неверно. $$ \left| \begin{array}{rrrr} -2 & -3 & -1 & 2 \\ -3 & -1 & 2 & 4 \\ -1 & 2 & 4 & -4 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} \end{array} \right|=0 \quad \iff \quad -7\,x_{K+3}-42\,x_{K+2}+44\,x_{K+1}-52\, x_K =0 $$ $$ \iff \quad x_{K+3}=-6\,x_{K+2}+44/7\,x_{K+1}-52/7x_K \, . $$ Снова два значения $ x_{4} $ и $ x_5 $ определятся правильно, а $ x_6 $ --- нет. $$ \left| \begin{array}{rrrrr} -2 & -3 & -1 & 2 & 4 \\ -3 & -1 & 2 & 4 & -4 \\ -1 & 2 & 4 & -4 & -5 \\ 2 & 4 & -4 & -5 & 26 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} \end{array} \right|=0 $$ $$ \iff 275\,x_{K+4}+356\,x_{K+3}+1311\,x_{K+2}-627\,x_{K+1}+1191\, x_K =0 $$ Теперь $ x_6 $ и $ x_7 $ находятся верно, но $ x_8 $ --- нет: $ -9973/275 \ne 11 $. $$ \left| \begin{array}{rrrrrr} -2 & -3 & -1 & 2 & 4 & -4 \\ -3 & -1 & 2 & 4 & -4 & -5\\ -1 & 2 & 4 & -4 & -5 & 26 \\ 2 & 4 & -4 & -5 & 26 & 11 \\ 4 & -4 & -5 & 26 & 11 & -85 \\ x_{K} & x_{K+1} & x_{K+2} & x_{K+3} & x_{K+4} & x_{K+5} \end{array} \right|=0 $$ $$ \iff \ 12998\, x_{K+5}-12998\, x_{K+4}+38994\, x_{K+3}-77988\, x_{K+2}+25996\, x_{K+1}-12998\, x_{K}=0 \, . $$ $$ \iff x_{K+5}=x_{K+4}-3\, x_{K+3}+6\, x_{K+2}-2\, x_{K+1}+ x_{K} \, . $$ Этот вариант дает верные значения элементов последовательности для всех доступных значений $ K_{} $. Имеется ли закономерность в формировании последовательноcти этих уравнений? Для ответа на этот вопрос выпишем их ((:recurr#аналитика характеристические полиномы)): $$ \mathcal H_1(x)=-2\, x+ 3 \ , $$ $$ \mathcal H_2(x)=-7\,x^2+7\,x-7 \ , $$ $$ \mathcal H_3(x)=-7\,x^3-42\,x^2+44\,x-52 \ , $$ $$ \mathcal H_4(x)= 275\,x^4+356\,x^3+1311\,x^2-627\,x+1191 \ , $$ $$ \mathcal H_5(x)=12998\,x^5-12998\,x^4+38994\,x^3-77988\,x^2+25996\,x-12998 \ . $$ Теперь разделим каждый полином, начиная c $ \mathcal H_3 $, на предыдущий (с остатком): $$ \mathcal H_3(x)\equiv (x+7) \mathcal H_2(x) + (2\,x-3) \equiv (x+7) \mathcal H_2(x)- \mathcal H_1(x) \ ; $$ $$ \mathcal H_4(x)\equiv \frac{1}{7}(-275\,x+1294) \mathcal H_3(x)-\frac{75625}{49} \mathcal H_2(x) \ ; $$ $$ \mathcal H_5(x)\equiv \left(\frac{12998}{275}\,x-\frac{8201738}{75625} \right) \mathcal H_4(x)-\frac{168948004}{75625} \mathcal H_3(x) \ . $$ Итак, с точностью до числового сомножителя, остаток от деления $ \mathcal H_{k}(x) $ на $ \mathcal H_{k-1}(x) $ совпадает с $ \mathcal H_{k-2}(x) $. Наблюдение имеет под собой теоретическое обоснование. ==Рекурсивное вычисление последовательности ганкелевых полиномов== Для произвольной числовой последовательности $ \{c\}=\{c_0,c_1,c_2,\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)} $$ является полиномом по $ 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_{} $. !!Т!! **Теорема [Якоби, Йоахимшталь].**[[Йоахимшталь Фердинанд (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 \, . $$ В литературе после 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 $. Именно эта ситуация встречается в примере $ 1 $ предыдущего пункта. !!§!! Доказательство **JJ**-формулы для ганкелевых полиномов и ее обобщения ☞ ((:algebra2/hankel/jjidentity#rekursivnaja_formula_dlja_gankelevyx_polinomov ЗДЕСЬ)). ==Источники== [1]. **Иохвидов И.С.** //Ганкелевы и теплицевы матрицы и формы.// М. Наука. 1974. [2]. **Jacobi C.G.J.** //De eliminatione variabilis e duabus aequationibus algebraicis//. J.reine angew. Math. 1836. Bd. 15, S. 101-124 [3]. **Joachimsthal F.** //Bemerkungen über den Sturm'schen Satz.// J.reine angew. Math. 1854. Bd. 48, S. 386-416 [4]. **Uteshev A., Baravy I., Kalinina E.** //Rational Interpolation: Jacobi's Approach Reminiscence.// Symmetry, 2021, **13** (8), 1401 Текст --- в открытом доступе ☞ {{:references:symmetry-13-01401.pdf}}