!!§!! Вспомогательная страница к пункту ((:recurr#метод_матричной_степени АНАЛИТИКА: МЕТОД МАТРИЧНОЙ СТЕПЕНИ)) раздела "Разностное уравнение и рекуррентная последовательность"
----
Для разностного уравнения
$$
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)
$$
((:mapping:operator#диагонализуемость_матрицы_оператора диагонализуема)):
$$ 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.** //Если характеристический полином имеет следующее ((:polynomial#основная_теорема_высшей_алгебры разложение на линейные множители))://
$$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) $-го порядка, стоящий в
правом верхнем углу отличен от нуля), то согласно
((:mapping:operator:jordan#алгоритм_построения_базиса_корневого_подпространства алгоритму построения ЖНФ))
имеется единственная клетка Жордана, соответствующая $ \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} $ означает ((:algebra2:notations#биномиальный_коэффициент биномиальный коэффициент)). Таким образом, в $ 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_{} $.
♦