Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Применение многочленов от матриц для решения систем рекуррентных уравнений

Применение многочленов от матриц для решения систем рекуррентных уравнений


Рассмотрим систему линейных рекуррентных уравнений


\begin{pmatrix}x_1(k+1)= a_{11}x_1(k)+ a_{12}x_2(k)+ \ldots+ a_{1n}x_n(k)+ f_1(k),\\ \cdots\cdots\cdots\cdots\cdots\\ x_n(k+1)= a_{n1}x_1(k)+ a_{n2}x_2(k)+ \ldots+ a_{nn}x_n(k)+f_n(k). \end{pmatrix}
(7.47)

где a_{ij}коэффициенты системы, f_i(k) — заданные, а x_i(k) — неизвестные функции дискретного аргумента k, k=k_0,k_0+ 1,k_0+2,\ldots. При описании дискретных динамических систем аргумент k в (7.47) называют дискретным временем.


Систему (7.47) можно записать в матричном виде:


x(k+1)=A\cdot x(k)+f(k),
(7.48)

где A — квадратная матрица (n-го порядка) коэффициентов системы рекуррентных уравнений, f(k)=\begin{pmatrix}f_1(k)&\cdots&f_n(k)\end{pmatrix}^T — столбец заданных функций, a x(k)=\begin{pmatrix} x_1(k)&\cdots& x_n(k)\end{pmatrix}^T — столбец неизвестных.


Решением системы (7.48) называется последовательность столбцов \Bigl\{x(k)\Bigr\}_{k=k_0}^{\infty}, при подстановке которых в (7.48) получаются верные равенства для всех k=k_0,k_0+1,k_0+2,\ldots.


Поставим задачу нахождения решения системы (7.48), удовлетворяющего начальным условиям


x(k_0)=x_0,
(7.49)

где x_0=\begin{pmatrix} x_{10}&\cdots&x_{n0} \end{pmatrix}^T — заданный столбец.


Рассмотрим сначала однородную систему (f(k)\equiv0) с постоянными коэффициентами


x(k+1)=Ax(k),\quad k=k_0,k_0+1,k_0+2,\ldots
(7.50)

Записывая (7.50) для k=k_0,k_0+1,k_0+2,\ldots, последовательно получаем


x(k_0+1)=Ax(k_0),\quad x(k_0+2)= Ax(k_0+1)=A^2x(k_0) и т.д.

Следовательно, решение однородной системы (7.50), удовлетворяющее начальным условиям (7.49), имеет вид:


x(k)= A^{k-k_0}\cdot x_0,\quad k=k_0,k_0+1,k_0+2,\ldots
(7.51)

Получим теперь решение системы (7.48). Учитывая (7.49), запишем (7.48) для k=k_0,k_0+1,k_0+2,\ldots:


\begin{gathered}x(k_0+1)=Ax(k_0)+f(k_0)=Ax_0+f(k_0),\\[5pt] x(k_0+2)= Ax(k_0+1)+f(k_0+1)= A\Bigl[Ax_0+f(k_0)\Bigr]+f(k_0+1)= A^2x_0+ Af(k_0)+f(k_0+1),\\ \vdots\\  x(k)=Ax(k-1)+f(k-1)= A^{k-k_0}x_0+f(k-1)+ Af(k-2)+\ldots+ A^{k-k_0-1}f(k_0) \end{gathered}

и т.д. Следовательно, решение системы (7.48) имеет вид


x(k)=A^{k-k_0}x_0+ \sum_{j=k_0}^{k-1}A^{k-j-1}f(j).
(7.52)

Первое слагаемое в (7.52) — решение однородной системы (7.50) с начальными условиями (7.49), второе слагаемое — решение системы (7.48) с нулевыми начальными условиями (т.е. при x(k_0)=o).




Алгоритм решения системы рекуррентных уравнений


Для нахождения решения системы (7.48) с начальными условиями (7.49) требуется выполнить следующие действия.


1. Найти выражение для степени матрицы A^k одним из способов, рассмотренных ранее.


2. Записать по формуле (7.52) искомое решение.




Замечания 7.9


1. Линейное рекуррентное уравнение с постоянными коэффициентами:


a_n\cdot x(k+n)+ a_{n-1}\cdot x(k+n-1)+\ldots+a_0\cdot x(k)=f_0(k)

может быть сведено к эквивалентной системе рекуррентных уравнений вида (7.47). Действительно, используя обозначения


x_1(k)=x(k),\quad x_2(k)=x(k+1),\quad \ldots,\quad x_n(k)=x(k+n-1),
получаем
\begin{cases} x_1(k+1)=x_2(k),\\ \phantom{aaaa}\vdots\\ x_{n-1}(k+1)=x_n(k),\\ x_n(k+1)=-\dfrac{a_0}{a_n}\,x_n(k)-\ldots- \dfrac{a_0}{a_n}\,x_1(k)+\dfrac{f_0(k)}{a_n} \end{cases}

или в матричной форме (7.48): x(k+1)=Ax(k)+f(k) с матрицами A и f(k):


A=\begin{pmatrix}0&1&0&\cdots&0\\ 0&0&1&\cdots&0\\ \vdots&\vdots& \vdots& \ddots&\vdots\\ 0&0&0&\cdots&1\\ -\dfrac{a_0}{a_n}&-\dfrac{a_1}{a_n}&-\dfrac{a_2}{a_n} &\cdots& -\dfrac{a_{n-1}}{a_n} \end{pmatrix}\!,\quad f(k)=\begin{pmatrix}0\\\vdots\\0\\ \dfrac{f_0(k)}{a_n} \end{pmatrix}\!.



Пример 7.19. Найти решение рекуррентного уравнения с начальными условиями x(1)=3,~x(2)=13:


x(k+2)-3x(k+1)-4x(k)=0.

Решение. В соответствии с пункту 1 замечаний 7.11 составим систему уравнений


\begin{cases}x_1(k+1)= x_2(k),\\ x_2(k+1)= 4x_1(k)+3x_2(k),\end{cases}

где x_1(k)=x(k),~x_2(k)=x(k+1). Требуется найти решение этой системы, удовлетворяющее начальным условиям: x_1(1)= 3,~x_2(1)=13.


1. Составим матрицу системы A=\begin{pmatrix} 0&1\\4&3 \end{pmatrix} и найдем ее степень A^k, используя второй способ. Характеристический многочлен \Delta_A(\lambda)= \begin{vmatrix}-\lambda&1\\ 4&3-\lambda\end{vmatrix}= \lambda^2-3 \lambda-4 имеет вторую степень и два простых корня: \lambda_1=-1, \lambda_2=4. Поэтому многочлен (7.44) — линейный: r(\lambda)=r_1 \lambda+r_0. Для его коэффициентов записываем систему (7.46):


\begin{cases}f(-1)=r(-1),\\ f(4)=r(4)\end{cases}\Rightarrow\quad \begin{cases}(-1)^k=r_1\cdot(-1)+r_0,\\ 4^k=r_1\cdot4+r_0.\end{cases}

Отсюда r_1= \frac{1}{5}\Bigl[4^k-(-1)^k\Bigr],~ r_0= \frac{1}{5}\Bigl[4^k+4(-1)^k\Bigr]. Таким образом,


A^k=r(A)=r_1A+r_0E= \frac{A}{5}\Bigl[4^k-(-1)^k\Bigr]+ \frac{E}{5}\Bigl[4^k+4(-1)^k\Bigr]= \frac{1}{5}\!\begin{pmatrix} 4^k+4(-1)^k&4^k-(-1)^k\\ 4^{k+1}-4(-1)^k& 4^{k+1}+(-1)^k \end{pmatrix}\!.

2. По формуле (7.52) записываем решение системы (учитывая, что k_0=1,~f(j)\equiv0):


\begin{pmatrix}x_1(k)\\x_2(k)\end{pmatrix}= \frac{1}{5}\! \begin{pmatrix}4^k+4(-1)^k&4^k-(-1)^k\\ 4^{k+1}-4(-1)^k& 4^{k+1}+(-1)^k \end{pmatrix}\!\cdot\! \begin{pmatrix}3\\13 \end{pmatrix}\!.

Нас интересует только первый элемент этого столбца:


x(k)=x_1(k)=\frac{1}{5}\Bigl[16\cdot4^{k-1}-(-1)^{k-1}\Bigr]= \frac{1}{5}\Bigl[4^{k+1}+(-1)^k\Bigr].

Решение совпадает с найденным в примере 2.15.




Пример 7.20. Найти решение системы рекуррентных уравнений с начальными условиями x_1(0)=1,~ x_2(0)=2,~x_3(0)=1:


\begin{cases}x_1(k+1)=-2x_1(k)+5x_2(k)-3x_3(k)+k,\\[2pt] x_2(k+1)=-2x_1(k)+ 5x_2(k)-3x_3(k)+3^k,\\[2pt] x_3(k+1)=x_1(k)-x_2(k)-k. \end{cases}
(7.53)

Решение. Запишем систему в матричной форме (7.48) и начальные условия x(0)=x_0= \begin{pmatrix} 1&2&1 \end{pmatrix}^T


x(k+1)=D\cdot x(k)+f(k), где D=\begin{pmatrix} -2&5&-3\\ -2&5&-3\\ 1&-1&0 \end{pmatrix}\!,~~f(k)=\begin{pmatrix}k\\3^k\\-k\end{pmatrix}.

1. Выражение для степени матрицы D найдено в примерах 7.17 и 7.18:


D^k=3^k\cdot\! \begin{pmatrix} -1&2&-1\\ -1&2&-1\\ 0&0&0\end{pmatrix} при k=2,\,3,\,\ldots\,.

2. Выражение, полученное для D^k, справедливо только при k>1 (см. пример 7.18). Поэтому для k=0,~k=1 формулу (7.52) нельзя использовать. Найдем x(1),~x(2) непосредственно из системы (7.53)


\begin{aligned} x(1)&=D\cdot x(0)+f(0)= \begin{pmatrix}-2&5&-3\\ -2&5&-3\\ 1&-1&0 \end{pmatrix}\!\cdot\! \begin{pmatrix}1\\2\\1\end{pmatrix}+ \begin{pmatrix}0\\3^0\\0\end{pmatrix}= \begin{pmatrix}5\\6\\-1\end{pmatrix}\!;\\[5pt] x(2)&=D\cdot x(1)+f(1)= \begin{pmatrix} -2&5&-3\\ -2&5&-3\\ 1&-1&0\end{pmatrix}\!\cdot\! \begin{pmatrix}5\\6\\-1\end{pmatrix}+ \begin{pmatrix}1\\3^1\\-1\end{pmatrix}= \begin{pmatrix}24\\26\\-2\end{pmatrix}\!. \end{aligned}

Далее записываем искомое решение для k=3,4,\ldots, выделяя в формуле (7.52) слагаемые с D^0=E и D^1=D:


\begin{gathered} x(k)=D^k\cdot x_0+E\cdot f(k-1)+D\cdot f(k-2)+ \sum_{j=0}^{k-3}D^{k-j-1}f(j)=\\[2pt] =3^k\cdot\! \begin{pmatrix}-1&2&-1\\ -1&2&-1\\ 0&0&0\end{pmatrix}\!\cdot\! \begin{pmatrix}1\\2\\1 \end{pmatrix}+ \begin{pmatrix}k-1\\3^{k-1}\\-k+1\end{pmatrix}+ \begin{pmatrix}-2&5&-3\\ -2&5&-3\\ 1&-1&0\end{pmatrix}\!\cdot\! \begin{pmatrix}k-2\\3^{k-2}\\-k+2\end{pmatrix}+\\[2pt] +\,\sum_{j=0}^{k-3}3^{k-j-1}\! \begin{pmatrix}-1&2&-1\\ -1&2&-1\\ 0&0&0\end{pmatrix}\!\cdot\! \begin{pmatrix}j\\3^j\\-j\end{pmatrix}= \begin{pmatrix} 2\cdot3^k+2k-3+5\cdot3^{k-2}\\ 2\cdot3^k+3^{k-1}+k-2+5\cdot3^{k-2}\\ -3^{k-2}-1 \end{pmatrix}+ \sum_{j=0}^{k-3}3^{k-1}\! \begin{pmatrix}2\\2\\0\end{pmatrix}\!.\end{gathered}

В последней сумме слагаемые не зависят от индекса суммирования, т.е. это сумма (k-2) одинаковых слагаемых. Поэтому, приводя подобные члены, получаем


x(k)= \begin{pmatrix}2k-3+23\cdot3^{k-2}\\ k-2+26\cdot3^{k-2}\\-1-3^{k-2} \end{pmatrix}+ \begin{pmatrix}2(k-2)\cdot3^{k-1}\\ 2(k-2)\cdot3^{k-1}\\0\end{pmatrix}= \begin{pmatrix}2k-3+(6k+11)\cdot 3^{k-2}\\ k-2+(6k+14)\cdot3^{k-2}\\ -1-3^{k-2} \end{pmatrix}\!.

Таким образом, решением заданной системы является последовательность столбцов:


x(0)=\begin{pmatrix}1\\2\\1\end{pmatrix}\!,~~ x(1)=\begin{pmatrix}5\\6\\-1 \end{pmatrix}\!,~~ x(2)=\begin{pmatrix}24\\26\\-2\end{pmatrix}\!,~~ x(k)=\begin{pmatrix}2k-3+(6k+11)\cdot 3^{k-2}\\ k-2+(6k+14)\cdot3^{k-2}\\ -1-3^{k-2}\end{pmatrix}\!, где k\geqslant3.
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2021 MathHelpPlanet.com. All rights reserved