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


§

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

Страница — в разработке. Начало работ — 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


2016/11/07 08:54 редактировал au