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

§

Вспомогательная результат к разделу ☞ РАЗНОСТНОЕ УРАВНЕНИЕ И РЕКУРРЕНТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ.

⊗

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

?

Известны первые члены линейной рекуррентной последовательности:

$0,1,2,2,0,-9,-38,-123,-360,-1004,-2728,-7303,...$

Чему равен следующий?

Т

Теорема. Пусть имеется последовательность $\{x_j\}_{j=0}^{\infty}$ . Если эта последовательность является решением линейного однородного разностного уравнения порядка $\le n_{}$ , то все главные миноры $S_0,S_1,S_2,\dots$ бесконечной ганкелевой матрицы

$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}$

Эти равенства составляют систему линейных однородных уравнений относительно коэффициентов. По предположению, система совместна и имеет нетривиальное решение. Но тогда (см. ☞ ЗДЕСЬ) ее определитель

$\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$ . Этот набор решений может быть построен с помощью алгебраических дополнений к элементам последней строки матрицы:

$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)$ .

Справедлив и более общий результат, который основан на понятии ранга бесконечной матрицы. По аналогии с конечными матрицами, будем считать ранг бесконечной матрицы равным $\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ти этих уравнений?

Для ответа на этот вопрос выпишем их характеристические полиномы:

$\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_{}$ .

Т

Теорема [?]. Полиномы $\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 \, .$

=>

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

$\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 \, .$

Пусть мы хотим использовать это тождество для вычисления коэффициентов полинома $\mathcal H_{k}(x)$ на основании уже вычисленных коэффициентов полиномов $\mathcal H_{k-1}(x)$ и $\mathcal H_{k-2}(x)$ . Величины констант $H_{k-1}$ и $h_{k-1,1}$ , используемых в тождестве, нам известны — это коэффициенты полинома $\mathcal H_{k-1}(x)$ . Но оставшиеся константы, именно $h_{k1}$ и $H_{k}$ , нам пока неизвестны, поскольку они являются коэффициентами полинома $\mathcal H_{k} (x)$ , который мы хотим найти. Как разорвать порочный круг? — Посмотрим на детерминантные представления этих коэффициентов:

$H_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|, \ h_{k-1,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| \ .$

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

$\left(\mathcal H_{k-1}(x)\right)^{\top} = \left| \begin{array}{lllll} c_0 & c_1 & \ldots & c_{k-2} & 1 \\ c_1 & c_2 & \ldots & c_{k-1} & x \\ \vdots & & \ddots& & \vdots \\ c_{k-1} & c_{k} & \ldots & c_{2k-3} & x^{k-1} \end{array} \right| \ .$

Но выражение для $\mathcal H_{k-1}(x)$ , т.е. разложение определителя по последнему столбцу, считается нам известным:

$\mathcal H_{k-1}(x)\equiv h_{k-1,0} x^k +h_{k-1,1} x^{k-1} +\dots + h_{k-1,k-1} \ .$

Тогда оба определителя $h_{k1}$ и $H_{k}$ могут быть вычислены по формулам

$\begin{array}{ll} H_k&= h_{k-1,0} c_{2k-2} +h_{k-1,1} c_{2k-3} +\dots + h_{k-1,k-1}c_{k-1} \ , \\ h_{k1}&=-(h_{k-1,0} c_{2k-1} +h_{k-1,1} c_{2k-2} +\dots + h_{k-1,k-1}c_{k}) \ , \end{array}$

и, тем самым, мы «замыкаем» рекурсивную формулу вычисления ганкелевого полинома $k_{}$ -го порядка.

Формула из теоремы применима для рекурсивного вычисления $\mathcal H_k(x)$ . Однако она не работает в случае $H_{k-1}=0$ . Именно эта ситуация встречается в примере 1 предыдущего пункта.

Т

Теорема [?]. Пусть $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{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)}{H_{k-2}^3} \, .$

Источники

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

[?]. Uteshev A.Yu., Baravy I. Solution of Interpolation Problems via the Hankel Polynomial Construction. 2016. arXiv:1603.08752