Основное
Вспомогательная страница к пункту АНАЛИТИКА: МЕТОД МАТРИЧНОЙ СТЕПЕНИ раздела «Разностное уравнение и рекуррентная последовательность»
Для разностного уравнения $$ x_{n+K}=a_1 x_{n+K-1}+ \dots+ a_n x_K $$ составим его характеристический полином $$ f(\lambda)= \lambda^n - a_1 \lambda^{n-1} - \dots - a_n . $$
Теорема 1. Если все корни $ \lambda_1,\dots,\lambda_n $ характеристического полинома различны, то решение разностного уравнения получается в виде
$$ x_{K}= C_1\lambda_1^K + \dots+ C_n \lambda_n^K \ , $$ числа $ C_{1},\dots,C_n $ не зависят от $ K_{} $ и определяются с помощью начальных условий из системы линейных уравнений: $$ \left\{\begin{array}{rrrrcl} C_1 &+C_2 &+\dots &+ C_n &=& x_0 \\ \lambda_1 C_1 &+ \lambda_2C_2&+\dots & + \lambda_n C_n & = & x_1 \\ \lambda_1^2 C_1 &+ \lambda_2^2C_2&+\dots & + \lambda_n^2 C_n & = & x_2 \\ \dots &&&&& \dots \\ \lambda_1^{n-1}C_1 &+ \lambda_2^{n-1}C_2&+\dots & + \lambda_n^{n-1} C_n & = & x_{n-1}. \end{array} \right. $$
Доказательство. При условии теоремы матрица Фробениуса $$ \mathfrak F = \left( \begin{array}{lllllll} 0 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 1 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 & 0 \\ \vdots& &&&\ddots & & \vdots \\ 0 & 0 & 0 & 0 & \dots & 0 & 1 \\ a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1 \end{array} \right) $$ диагонализуема: $$ C^{-1} \mathfrak F C= \mathfrak F_{_{\mathfrak J}} $$ при $$ \mathfrak F_{_{\mathfrak J}} = \left( \begin{array}{llll} \lambda_1 & & &\mathbb O \\ & \lambda_2 & & \\ & & \ddots & \\ \mathbb O& & & \lambda_n \end{array} \right) \ , \qquad C= \left( \begin{array}{llll} 1 &1 & \dots & 1 \\ \lambda_1 & \lambda_2 & \dots & \lambda_n \\ \vdots & & & \vdots \\ \lambda_1^{n-1} &\lambda_2^{n-1} &\dots & \lambda_n^{n-1} \end{array} \right). $$ Действительно, пользуясь тем, что $ \lambda_j^n=a_1 \lambda_j^{n-1}+\dots+a_n $ получаем: $$ \mathfrak F \left( \begin{array}{l} 1 \\ \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{n-1} \end{array} \right) = \left( \begin{array}{c} \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{n-1} \\ a_n +a_{n-1}\lambda_j+\dots+ a_1 \lambda_j^{n-1} \end{array} \right) = \left( \begin{array}{l} \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{n-1} \\ \lambda_j^{n} \end{array} \right)= \lambda_j \left( \begin{array}{l} 1 \\ \lambda_j \\ \lambda_j^2 \\ \vdots \\ \lambda_j^{n-1} \end{array} \right), $$ т.е. столбцами матрицы Вандермонда $ C_{} $ являются собственные векторы матрицы $ \mathfrak F $.
По формуле $ {\mathfrak F}^{K}=C {\mathfrak F}_{\mathfrak J}^{K+1} C^{-1} $ имеем: $$ {\mathfrak F}^{K}=C \left( \begin{array}{llll} \lambda_1^{K} & & & \mathbb O\\ & \lambda_2^{K} & & \\ & & \ddots & \\ \mathbb O& & & \lambda_n^{K} \end{array} \right) C^{-1}= \left( \begin{array}{llll} \lambda_1^{K} &\lambda_2^{K} &\dots &\lambda_n^{K} \\ \lambda_1^{K} &\lambda_2^{K} &\dots &\lambda_n^{K} \\ \dots & & & \dots \\ \lambda_1^{K} &\lambda_2^{K} &\dots &\lambda_n^{K} \end{array} \right) C^{-1} \, . $$ Первый элемент столбца $ X_{K}={\mathfrak F}^{K}X_0 $, т.е. искомый элемент рекуррентной последовательности $ x_{K} $ получается по формуле: $$x_{K}=\left[ \lambda_1^{K}, \lambda_2^{K}, \dots, \lambda_n^{K} \right]C^{-1}X_0 \ .$$ Если теперь обозначить $$ \left( \begin{array}{l} C_1 \\ C_2 \\ \vdots \\ C_n \end{array} \right) = C^{-1} \left( \begin{array}{l} x_0 \\ x_1 \\ \vdots \\ x_{n-1} \end{array} \right) $$ то и получим представление представление решения из теоремы. ♦
Рассмотрим теперь случай наличия кратного корня у характеристического полинома.
Теорема 2. Если характеристический полином имеет следующее разложение на линейные множители:
$$f(\lambda)\equiv (\lambda-\lambda_1)^{{\mathfrak m}_1}\times \dots \times (\lambda-\lambda_{\mathfrak r})^{{\mathfrak m}_{\mathfrak r}}, \quad \lambda_k \ne \lambda_{\ell} \ \mbox{ при } \ k \ne \ell \ , {\mathfrak m}_1 + \dots + {\mathfrak m}_{\mathfrak r} =n, $$ то общее решение разностного уравнения имеет вид: $$ x_{K}=L_1(K)\lambda_1^{K} +\dots + L_{\mathfrak r}(K)\lambda_{\mathfrak r}^{K} , $$ где $ L_1(K),\dots,L_{\mathfrak r}(K) $ — полиномы по $ K_{} $ : $$ \{L_j(K)\}_{j=1}^{\mathfrak r} \subset \mathbb C[K],\ \{\deg L_j < {\mathfrak m}_j \}_{j=1}^{\mathfrak r} \, . $$
Доказательство. Если корень $ \lambda_1 $ характеристического полинома $ f(\lambda) $ имеет кратность $ {\mathfrak m}_1 $, то в жордановой нормальной форме матрицы $ \mathfrak F $ ему соответствует единственная клетка Жордана порядка $ {\mathfrak m}_1 $. Действительно, поскольку матрица $$ {\mathbf B}=\mathfrak F-\lambda_1 E = \left( \begin{array}{ccccccc} -\lambda_1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & -\lambda_1 & 1 & 0 & \dots & 0 & 0 \\ \vdots& && & \ddots && \vdots \\ 0 & 0 & 0 & 0 & \dots & -\lambda_1 & 1 \\ a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1-\lambda_1 \end{array} \right)_{n \times n} $$ имеет ранг равный $ n-1 $ ( $ \det {\mathbf B} = 0 $, а минор $ (n-1) $-го порядка, стоящий в правом верхнем углу отличен от нуля), то согласно алгоритму построения ЖНФ имеется единственная клетка Жордана, соответствующая $ \lambda_{1} $. Тогда ее порядок совпадает с алгебраической кратностью $ {\mathfrak m}_1 $. Этот же вывод справедлив и для остальных собственных чисел. Таким образом, имеем $$ {\mathfrak F}_{_{\mathfrak J}}=\left( \begin{array}{cccc} \mathbf F_1 & \mathbb O & \dots & \mathbb O \\ \mathbb O & \mathbf F_2 & \dots & \mathbb O \\ & & \ddots & \\ \mathbb O & \mathbb O & \dots & \mathbf F_{{\mathfrak r}} \end{array} \right) \quad \mbox{при} \ \mathbf F_j = \left( \begin{array}{cccccc} \lambda_j & 0 & 0 & \dots & 0 & 0 \\ 1 & \lambda_j & 0 & \dots & 0 & 0 \\ 0 & 1 & \lambda_j & \dots & 0 & 0 \\ \vdots & & \ddots & \ddots& & \vdots \\ 0 & 0 & 0 & \dots & 1 & \lambda_j \end{array} \right)_{{\mathfrak m}_j\times {\mathfrak m}_j} \ . $$ Теперь будем искать соответствующую матрицу $ C_{} $. Из доказательства теоремы 1 нам известно, что фундаментальная система решений системы $ {\mathbf B}X=\mathbb O $ должна включать в себя вектор $ X_1=\left[1,\lambda_1,\lambda_1^2,\dots,\lambda_1^{n-1} \right]^{\top} $. Будем искать теперь корневые векторы высоты $ 2_{} $. С этой целью рассмотрим систему $ {\mathbf B}^2X=\mathbb O $. Докажем, что ее решением будет вектор $$ X_2=\left[0,1,2\lambda_1,3\lambda_1^2,\dots,(n-1)\lambda_1^{n-2} \right]^{\top} \ ; $$ его можно рассматривать как полученный формальным дифференцированием вектора $ X_1 $: $$ X_2=d\, X_1/d\, \lambda_1 \, . $$ Вычислим сначала $ {\mathbf B}X_2 $: $$ \left( \begin{array}{ccccccc} -\lambda_1 & 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & -\lambda_1 & 1 & 0 & \dots & 0 & 0 \\ \vdots& && & \ddots && \vdots \\ 0 & 0 & 0 & 0 & \dots & -\lambda_1 & 1 \\ a_n & a_{n-1} & a_{n-2} & & \dots & a_2 & a_1-\lambda_1 \end{array} \right)\left(\begin{array}{c} 0\\ 1\\ 2\lambda_1\\ 3\lambda_1^2\\ \vdots \\ (n-1)\lambda_1^{n-2} \end{array} \right)= $$ $$ = \left(\begin{array}{c} 1\\ \lambda_1\\ \lambda_1^2\\ \lambda_1^3\\ \vdots \\ \lambda_1^{n-2} \\ a_{n-1}+2\,\lambda_1a_{n-2}+3\, \lambda_1^2 a_{n-3}+ \dots + (n-2)a_2 \lambda_1^{n-3} +(n-1)(a_1-\lambda_1)\lambda_1^{n-2} \end{array} \right) = \left(\begin{array}{c} 1\\ \lambda_1\\ \lambda_1^2\\ \lambda_1^3\\ \vdots \\ \lambda_1^{n-2} \\ f^{\prime}(\lambda_1) + \lambda_1^{n-1} \end{array} \right) \, . $$ Если, по предположению, корень $ \lambda_1 $ кратный, то $ f^{\prime}(\lambda_1)= 0 $. Тогда имеем: $$ {\mathbf B}X_2=X_1 \, , $$ и вектор $ X_2 $ является корневым высоты $ 2_{} $. Аналогично, в предположении, что алгебраическая кратность $ \mathfrak m_1 \ge 3 $, доказывается, что вектор $$ X_3=\frac{1}{2}\left[0,0,2,6\lambda_1,\dots,(n-1)(n-2)\lambda_1^{n-3} \right]^{\top} = \frac{1}{2 !} \frac{d^2 X_1}{d \lambda_1^2} $$ является корневым высоты $ 3_{} $ и при этом $$ {\mathbf B}X_3=X_2 \, . $$ И так далее. Окончательно, векторы $$ \frac{1}{(\mathfrak m_1-1)!} \frac{ d\,^{\mathfrak m_1-1} X_1}{d\, \lambda_1^{\mathfrak m_1-1}},\ \frac{1}{(\mathfrak m_1-2)!} \frac{ d\,^{\mathfrak m_1-2} X_1}{d\, \lambda_1^{\mathfrak m_1-2}}, \dots , \frac{1}{2!} \frac{d^2\, X_1}{d\, \lambda_1^2} , \ \frac{d\, X_1}{d\, \lambda_1},\ X_1 $$ составляют канонический базис корневого подпространства, принадлежащего $ \lambda_{1} $. Первые $ \mathfrak m_1 $ столбцов матрицы $ C_{} $ имеют вид $$ C= \left( \begin{array}{ccccccccccc} 0 & 0 & \dots & 0 & 0 & 0 & 1 & \ast & \ast & \dots & \ast \\ 0 & 0 & \dots & 0 & 0 & 1 & \lambda_1 & \ast & \ast & \dots & \ast \\ 0 & 0 & \dots & 0 & 1 & 2\lambda_1 & \lambda_1^2 & \ast & \ast & \dots & \ast \\ 0 & 0 & \dots & 1 & 3\lambda_1 & 3\lambda_1^2 & \lambda_1^3 & \ast & \ast & \dots & \ast \\ \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 1 & (\mathfrak m_1-1) \lambda_1 & \dots & C_{\mathfrak m_1-1}^{3} \lambda_1^{\mathfrak m_1-4} & C_{\mathfrak m_1-1}^{2} \lambda_1^{\mathfrak m_1-3} & (\mathfrak m_1-1) \lambda_1^{\mathfrak m_1-2} & \lambda_1^{\mathfrak m_1-1} & \ast & \ast & \dots & \ast \\ \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ C_{n-1}^{\mathfrak m_1-1} \lambda_1^{n-\mathfrak m_1} & C_{n-1}^{\mathfrak m_1-2} \lambda_1^{n-\mathfrak m_1+1} & \dots & C_{n-1}^3 \lambda_1^{n-4} & C_{n-1}^2 \lambda_1^{n-3} & (n-1)\lambda_1^{n-2} & \lambda_1^{n-1} & \ast & \ast & \dots & \ast \end{array} \right) \, . $$ Здесь $ C_{N}^{\ell} $ означает биномиальный коэффициент. Таким образом, в $ j_{} $-й строке матрицы $ C_{} $ стоят члены разложения бинома Ньютона $ ( 1+\lambda_1 )^{j-1} $.
Далее, по аналогии с теоремой 1, применяем формулу $ {\mathfrak F}^{K}=C {\mathfrak F}_{_{\mathfrak J}}^{K} C^{-1} $ при: $$ {\mathfrak F}_{_{\mathfrak J}}^{K}= \left( \begin{array}{cccccc|llll} \lambda_1^{K} & & & & & & & & & \\ C_{K}^1\lambda_1^{K-1} & \lambda_1^{K} & & & & & & \mathbb O & \\ C_{K}^2\lambda_1^{K-2} & C_{K}^1\lambda_1^{K-1} & \lambda_1^{K} & & \mathbb O & & \\ \vdots & \vdots & & & \ddots & & & & \\ C_{K}^{\mathfrak m_1-1}\lambda_1^{K-\mathfrak m_1+1} & C_{K}^{\mathfrak m_1-2}\lambda_1^{K-\mathfrak m_1+2} & & & \dots & \lambda_1^{K} & & & & \\ \hline & & & & & & \mathbf F_2^{K} & \dots & \mathbb O \\ & & \mathbb O & & & & & \ddots & \vdots \\ & & & & & & \mathbb O & \dots & \mathbf F_{\mathfrak r}^{K} \end{array} \right) $$ Первый элемент столбца $ X_{K}={\mathfrak F}^{K}X_0 $, т.е. искомый элемент рекуррентной последовательности $ x_{K} $ получается отсюда в виде: $$x_{K}=\left[ C_{K}^{\mathfrak m_1-1}\lambda_1^{K-\mathfrak m_1+1}, C_{K}^{\mathfrak m_1-2}\lambda_1^{K-\mathfrak m_1+2} , \dots , \lambda_1^{K},\dots \right]C^{-1}X_0 \ ;$$ (в векторе я указал только элементы, зависящие от $ \lambda_1 $). Элементы столбца $$ C^{-1}X_0 = \left[ D_1,D_2,\dots,D_n \right]^{\top} $$ от $ K_{} $ не зависят. Таким образом, $$ x_{K}=\left(D_1C_{K}^{\mathfrak m_1-1}\lambda_1^{-\mathfrak m_1+1}+ D_2 C_{K}^{\mathfrak m_1-2}\lambda_1^{-\mathfrak m_1+2} + \dots + D_{\mathfrak m_1} \right)\lambda_1^{K}+ \dots $$ В скобках стоит полином степени $ \le m_1-1 $ по $ K_{} $. ♦