Niechpolskimisiek pisze:Wszystko w swoim czasie. Moim następnym tematem do kompendium bedzie rozwiązywanie wszystkich rekurencji nieliniowych postaci \(\displaystyle{ x_{n+1}=\frac{ax_{n}+c}{bx_{n}+d}}\).
\(\displaystyle{ f(x)=\frac{ax+c}{bx+d}}\)
Jesli oznaczymy
\(\displaystyle{ M=\begin{pmatrix}a&b\\c&d\end{pmatrix}}\)
oraz jakos wyznaczymy liczby \(\displaystyle{ a_n,b_n,c_n,d_n}\) takie, ze
\(\displaystyle{ M^n=\begin{pmatrix}a_n&b_n\\c_n&d_n\end{pmatrix}}\),
to nietrudno sie przekonac, ze:
\(\displaystyle{ x_n=f^{(n)}(x_0)=\frac{a_nx_{0}+c_n}{b_nx_{0}+d_n}}\)
Liczby \(\displaystyle{ a_n,b_n,c_n,d_n}\) czasami daja sie calkiem latwo wyznaczyc. Istnieje bowiem macierz \(\displaystyle{ T}\), ktorej kolumnami sa (uogolnione) wektory wlasne *) macierzy \(\displaystyle{ M}\) (co latwo sie wyznacza w przypadku diagonalizowalnym) taka, ze macierz
\(\displaystyle{ TMT^{-1}}\)
jest (prawie) diagonalna. W ogolnosci jest to macierz postaci
\(\displaystyle{ \begin{pmatrix}\lambda_1&\varepsilon\\0&\lambda_2 \end{pmatrix}}\)
gdzie \(\displaystyle{ \lambda_1,\lambda_2}\) sa wartosciami wlasnymi macierzy \(\displaystyle{ M}\), czyli pierwiastkami wielomianu charakterystycznego \(\displaystyle{ \chi(x)=(a-x)(d-x)-bc}\),
zas \(\displaystyle{ \varepsilon\in\{0,1\}}\).
Jesli mamy szczescie i wyszla macierz diagonalna:
\(\displaystyle{ TMT^{-1}=\begin{pmatrix}\lambda_1&0\\0&\lambda_2 \end{pmatrix}}\),
to mamy juz z gorki:
\(\displaystyle{ M^n=T^{-1}(TMT^{-1})^nT=T^{-1}\begin{pmatrix}\lambda_1&0\\0&\lambda_2 \end{pmatrix}^nT=T^{-1}\begin{pmatrix}\lambda_1^n&0\\0&\lambda_2^n \end{pmatrix}T}\)
skad szybciutko wyznaczamy \(\displaystyle{ a_n,b_n,c_n,d_n}\).
Jesli natomiast
\(\displaystyle{ TMT^{-1}=\begin{pmatrix}\lambda_1&1\\0&\lambda_2 \end{pmatrix}}\),
wowczas wiadomo *), ze \(\displaystyle{ \lambda_1=\lambda_2=\lambda}\) i mamy
\(\displaystyle{ \begin{pmatrix}\lambda&1\\0&\lambda \end{pmatrix}^n=\begin{pmatrix}\lambda^n&n\lambda^{n-1}\\0&\lambda^n \end{pmatrix}}\)
co tak samo jak w przypadku diagonalnym umozliwia szybkie wyznaczenie \(\displaystyle{ a_n,b_n,c_n,d_n}\).
Wyglada to moze paskudnie, ale stosunkowo latwo sie wszystko liczy. Wyznaczanie wartosci i wektorow wlasnych to kwestia rozwiazania ukladu dwoch rownan z dwoma niewiadomymi.
Przyklad:
\(\displaystyle{ x_{n+1}=\frac{x_n-2}{-2x_n+1}}\)
\(\displaystyle{ x_0=0}\)
Macierz:
\(\displaystyle{ M=\begin{pmatrix}1&-2\\-2&1\end{pmatrix}}\)
Wartosci wlasne:
\(\displaystyle{ \det\begin{pmatrix}1-\lambda&-2\\-2&1-\lambda\end{pmatrix}=(1-\lambda)^2-4}\)
skad
\(\displaystyle{ \lambda_1=3,\;\;\lambda_2=-1}\)
Wekrory wlasne:
dla \(\displaystyle{ \lambda_1=3}\), czyli dowolne rozwiazanie rownania \(\displaystyle{ M\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}3x\\3y\end{pmatrix}}\):
\(\displaystyle{ w_1=\begin{pmatrix}1\\-1\end{pmatrix}}\)
dla \(\displaystyle{ \lambda_1=-1}\), czyli dowolne rozwiazanie rownania \(\displaystyle{ M\cdot\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}-x\\-y\end{pmatrix}}\):
\(\displaystyle{ w_2=\begin{pmatrix}1\\1\end{pmatrix}}\)
Macierz przejscia:
\(\displaystyle{ T=(w_1,w_2)=\begin{pmatrix}1&1\\-1&1\end{pmatrix}}\)
\(\displaystyle{ T^{-1}=\begin{pmatrix}1/2&-1/2\\1/2&1/2\end{pmatrix}}\)
Diagonalizacja:
\(\displaystyle{ TMT^{-1}=\begin{pmatrix}-1&0\\0&3\end{pmatrix}}\)
Potegowanie:
\(\displaystyle{ M^n=T^{-1}(TMT^{-1})^nT=T^{-1}\begin{pmatrix}(-1)^n&0\\0&3^n\end{pmatrix}T=}\)
\(\displaystyle{ =\begin{pmatrix}1/2&-1/2\\1/2&1/2\end{pmatrix}\begin{pmatrix}(-1)^n&0\\0&3^n\end{pmatrix}\begin{pmatrix}1&1\\-1&1\end{pmatrix}=\frac 12\begin{pmatrix}(-1)^n+3^n&(-1)^n-3^n\\(-1)^n-3^n&(-1)^n+3^n\end{pmatrix}}\)
Wspolczynniki:
Mamy wiec:
\(\displaystyle{ a_n=d_n=\frac{(-1)^n+3^n}{2}}\)
\(\displaystyle{ b_n=c_n=\frac{(-1)^n-3^n}{2}}\)
Wynik:
Stad:
\(\displaystyle{ x_n=\frac{\frac{(-1)^n+3^n}{2}x_0+\frac{(-1)^n-3^n}{2}}{\frac{(-1)^n-3^n}{2}x_0+\frac{(-1)^n+3^n}{2}}=\frac{((-1)^n+3^n)x_0+(-1)^n-3^n}{((-1)^n-3^n)x_0+(-1)^n+3^n}}\).
Zatem dla \(\displaystyle{ x_0=0}\) otrzymujemy:
\(\displaystyle{ x_n=\frac{(-1)^n-3^n}{(-1)^n+3^n}}\)
*) Uwaga nt. wektorow wlasnych i diagonalizacji:
Wektory wlasne otrzymujemy z rownan:
\(\displaystyle{ Mv=\lambda_iv}\)
lub rownowaznie
\(\displaystyle{ (M-\lambda_i I)v=0}\),
gdzie \(\displaystyle{ I}\) oznacza macierz jednostkowa.
Jesli wektorow wlasnych jest wystarczajaco wiele, to znaczy, jesli rozpinaja cala przestrzen (w naszym przypadku 2D), to macierz jest \(\displaystyle{ M}\) diagonalizowalna, zas macierz przejscia \(\displaystyle{ T}\) ma w kolumnach wektory wlasne. Taka sytuacja zachodzi miedzy innymi, gdy wartosci wlasne sa rozne.
Jesli wartosci wlasne nie sa parami rozne, w naszym przypadku \(\displaystyle{ \lambda_1=\lambda_2=\lambda}\), to moze sie okazac, ze jest tylko jeden wektor wlasny dla danej wartosci wlasnej. W naszym przypadku oznacza to, ze rozwiazaniem rownania
\(\displaystyle{ (M-\lambda I)v=0}\)
jest przestrzen jednowymiarowa rozpieta na wektorze \(\displaystyle{ w}\). W takiej sytuacji konstruujemy tzw. uogolniony wektor wlasny, ktory jest rozwiazaniem rownania
\(\displaystyle{ (M-\lambda I)v=w}\)
i dalej postepujemy standardowo: majac te dwa wektory diagonalizujemy macierz do postaci \(\displaystyle{ \begin{pmatrix}\lambda&1\\0&\lambda \end{pmatrix}}\) i podnosimy do potegi ze wzoru w tekscie powyzej.
I jeszcze taka uwaga dotyczca praktycznego rozwiazywania rekurencji
\(\displaystyle{ x_{n+1}=\frac{ax_n+b}{cx_n+d}}\)
Tak naprawde nie trzeba przechodzic przez aparat wartosci wlasnych, diagonalizacji etc.
Wystarczy znajomosc wartosci wlasnych, czyli po prostu pierwiastkow wielomianu:
\(\displaystyle{ \chi(\lambda)=(a-\lambda)(d-\lambda)-bc}\)
Gdy pierwiastki tego wielomianu sa rozne \(\displaystyle{ \lambda_1,\lambda_2}\) wowczas \(\displaystyle{ x_n}\) jest postaci:
\(\displaystyle{ x_n=\frac{\alpha \lambda_1^n+\beta \lambda_2^n}{\gamma \lambda_1^n+\delta \lambda_2^n}}\)
Stale \(\displaystyle{ \alpha,\beta,\gamma,\delta}\) wyznaczamy poprzez reczne wyznaczenie pierwszych wyrazow ciagu i porownanie ze wzorem.
Jesli natomiast \(\displaystyle{ \lambda_1=\lambda_2=\lambda}\), to rozwiazanie ma postac:
\(\displaystyle{ x_n=\frac{\alpha+n\beta}{\gamma+n\delta}}\)
i podobnie jak poprzednio.
Oczywiscie konstruktywniej jest znac sie na macierzach, bo problemow podobnego typy jest wiele i szkoda sobie glowe zasmiecac metodami dzialajacymi w szczegolnych przypadkach.