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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


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

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


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


[math]\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}[/math]
(7.47)

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


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


[math]x(k+1)=A\cdot x(k)+f(k),[/math]
(7.48)

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


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


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


[math]x(k_0)=x_0,[/math]
(7.49)

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


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


[math]x(k+1)=Ax(k),\quad k=k_0,k_0+1,k_0+2,\ldots[/math]
(7.50)

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


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

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


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

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


[math]\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}[/math]

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

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

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




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


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


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


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




Замечания 7.9


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


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

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

[math]x_1(k)=x(k),\quad x_2(k)=x(k+1),\quad \ldots,\quad x_n(k)=x(k+n-1),[/math]
получаем
[math]\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}[/math]

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


[math]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}\!.[/math]



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


[math]x(k+2)-3x(k+1)-4x(k)=0.[/math]

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


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

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


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


[math]\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}[/math]

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


[math]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}\!.[/math]

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


[math]\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}\!.[/math]

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

[math]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].[/math]

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




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


[math]\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}[/math]
(7.53)

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


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

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


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

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


[math]\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}[/math]

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


[math]\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}[/math]

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


[math]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}\!.[/math]

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


[math]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}\!,[/math] где [math]k\geqslant3[/math].

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


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

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