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


§

Вспомогательная страница к пункту АНАЛИТИКА: МЕТОД МАТРИЧНОЙ СТЕПЕНИ раздела «Разностное уравнение и рекуррентная последовательность»


Для разностного уравнения

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} при \ 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 , \quad npu \ \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_{}.


2016/09/05 17:01 редактировал au