recurr:vspom2 [VF]

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

§

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

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

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