Równanie rekurencyjne

[Tomek_Z]

Znajdź wzór na wyrazy ciągu zadanego równaniem rekurencyjnym \(\displaystyle{ x_{n+2} = 2x_{n+1} - x_n}\) jeśli wyrazy początkowe wynoszą \(\displaystyle{ x_0 = 1, x_1 = 2}\).

Zapisuję równanie w postaci macierzy:

\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} =\begin{bmatrix} 2&-1\\0&1 \end{bmatrix} \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix}}\)

i zauważam, że \(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} = \begin{bmatrix} 2&-1\\0&1 \end{bmatrix} ^n \begin{bmatrix} 2\\1 \end{bmatrix}}\) (*)

Znajduję wartości i wektory własne macierzy ( dla \(\displaystyle{ t=2}\): \(\displaystyle{ X = (1,0)}\) zaś dla \(\displaystyle{ t=1}\): \(\displaystyle{ X=(1,1)}\) ) po czym zapisuję macierz przejścia i macierz do niej odwrotną, otrzymując ostatecznie:

\(\displaystyle{ \begin{bmatrix} 2&-1\\0&1 \end{bmatrix} ^n = \begin{bmatrix} 2^n&-2^n+1\\0&1 \end{bmatrix}}\)

Korzystając z (*) otrzymuję

\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} = \begin{bmatrix} 2^{n+1} - 2^n+1\\1 \end{bmatrix}}\)

Co jest trochę nielogiczne...Gdzie jest błąd?

[Qń]

Zapisuję równanie w postaci macierzy:
\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} =\begin{bmatrix} 2&-1\\0&1 \end{bmatrix} \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix}}\)
i zauważam, że \(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} = \begin{bmatrix} 2&-1\\0&1 \end{bmatrix} ^n \begin{bmatrix} 2\\1 \end{bmatrix}}\)

Błąd jest tutaj - to co zauważyłeś jest nieprawdą. Nie możesz w ten sposób rozwinąć poprzedniej równości, bo nie zgadzają się indeksy przy \(\displaystyle{ x_i}\) (po prawej stronie nie różnią się o dwa, tak jak po lewej).

Q.

[Tomek_Z]

Nie za bardzo rozumiem dlaczego to jest błąd, no i co zrobić, żeby było poprawnie?

[Qń]

Ok, skoro przedstawiona idea tego co jest źle jest niejasna, to przedstaw swoje rozumowanie. Jeśli spróbujesz je uściślić, to z pewnością sam zauważysz błąd.

A jak powinno być dobrze? Mamy:
\(\displaystyle{ x_{n+2}=2x_{n+1}-x_n=2 \cdot (2x_n-x_{n-1})-x_n = 3x_n- 2x_{n-1}}\)
oraz:
\(\displaystyle{ x_{n+1}=2x_{n}-x_{n-1}}\)

Tak więc:
\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_{n+1} \end{bmatrix} =\begin{bmatrix} 3&-2\\2&-1 \end{bmatrix} \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}}\)
skąd tym razem już prawidłowo można dojść do wniosku, że jeśli położymy \(\displaystyle{ n=2k-1}\), to dostaniemy:
\(\displaystyle{ \begin{bmatrix} x_{2k+1}\\ x_{2k} \end{bmatrix} =\begin{bmatrix} 3&-2\\2&-1 \end{bmatrix} \begin{bmatrix} x_{2k-1}\\ x_{2k-2} \end{bmatrix}}\)
i stąd wynika, że w takim razie:
\(\displaystyle{ \begin{bmatrix} x_{2k+1}\\ x_{2k} \end{bmatrix} =\begin{bmatrix} 3&-2\\2&-1 \end{bmatrix}^k \begin{bmatrix} 2\\ 1 \end{bmatrix}}\)

Tutaj co prawda jest cień problemu, bo macierz \(\displaystyle{ \begin{bmatrix} 3&-2\\2&-1 \end{bmatrix}}\) jest niediagonalizowalna, ale jej postać Jordana to \(\displaystyle{ \begin{bmatrix} 1&1\\0&1 \end{bmatrix}}\), a nietrudno pokazać indukcyjnie, że:
\(\displaystyle{ \begin{bmatrix} 1&1\\0&1 \end{bmatrix}^k=\begin{bmatrix} 1&k\\0&1 \end{bmatrix}}\)
skąd łatwo po rachunkach dojść do wniosku, że \(\displaystyle{ x_n=n+1}\).

Nawiasem mówiąc ciekawa metoda, chyba jej wcześniej nie widziałem. Chociaż w tym wypadku o wiele szybciej można rozwiązać tę rekurencję w inny sposób.

Q.

[Tomek_Z]

Ok, skoro przedstawiona idea tego co jest źle jest niejasna, to przedstaw swoje rozumowanie. Jeśli spróbujesz je uściślić, to z pewnością sam zauważysz błąd.

Ja brałem:

\(\displaystyle{ x_{n+2} = 2x_{n+1} - x_n \\ x_n = 0 \cdot x_{n+1} + x_n}\)

No i wydawało mi się to poprawne bo

\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} =\begin{bmatrix} 2&-1\\0&1 \end{bmatrix} \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix} = \begin{bmatrix} 2x_{n+1}-x_n\\ x_n \end{bmatrix}}\)

Zatem równość jest zachowana.

[Qń]

To jest poprawne. Ale przedstaw wnioskowanie, którego efektem była równość:
\(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_n \end{bmatrix} = \begin{bmatrix} 2&-1\\0&1 \end{bmatrix} ^n \begin{bmatrix} 2\\1 \end{bmatrix}}\)
a ja Ci wskażę błąd w tym rozumowaniu. Choć tak jak napisałem - jeśli zaczniesz je zapisywać, to zapewne sam dostrzeżesz lukę.

Q.

[Tomek_Z]

No faktycznie coś jest nie tak. Dostrzegam błąd, ale nie potrafię powiedzieć co jest jego źródłem

[Qń]

Ja też nie będę potrafił powiedzieć gdzie zrobiłeś błąd w dedukcji, jeśli tej dedukcji nie przedstawisz.

Q.

[Tomek_Z]

Szczerze mówiąc to poleciałem schematem, który był w pewnym skrypcie. Tam nie podano, żadnego uzasadnienia, ale działało, a tutaj nie działa i właśnie głowię się dlaczego...?

[Qń]

Jedno z dwojga: albo nie zrozumiałeś schematu i źle go zastosowałeś, albo też ten schemat nie ma zastosowania w omawianym przypadku.

Jeśli nie przytoczysz przykładu ze skryptu, to nic więcej powiedzieć się nie da. Za to rada ogólna: nigdy nie ucz się schematów bez zrozumienia zasady ich działania.

Q.

[xiikzodz]

Pewnie miało być tak:

\(\displaystyle{ \begin{pmatrix}x_{n+1\\x_n}\end{pmatrix}=A\begin{pmatrix}x_n\\x_{n-1}\end{pmatrix}=\begin{pmatrix}2&-1\\1&0\end{pmatrix}\begin{pmatrix}x_n\\x_{n-1}\end{pmatrix}}\).

Mamy:

\(\displaystyle{ A=\begin{pmatrix}2&-1\\1&0\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}1&1\\0&1\end{pmatrix}\begin{pmatrix}0&1\\1&-1\end{pmatrix}}\).

Macierz \(\displaystyle{ A}\) nie jest diagonalizowalna, więc najpierw znajdujemy wektor własny \(\displaystyle{ w_1=\begin{pmatrix}1\\1\end{pmatrix}}\) następnie uogólniony wektor własny z równania \(\displaystyle{ Ax=w_1}\), czyli \(\displaystyle{ \begin{pmatrix}1\\0\end{pmatrix}}\) i z tych wektorów składamy macierz przejścia.

Dalej łatwo:

\(\displaystyle{ \begin{pmatrix}x_{n+1}\\x_n\end{pmatrix}=A^n\begin{pmatrix}x_1\\x_0\end{pmatrix}=\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}1&1\\0&1\end{pmatrix}^n\begin{pmatrix}0&1\\1&-1\end{pmatrix}\begin{pmatrix}x_1\\x_0\end{pmatrix}=}\)

\(\displaystyle{ =\begin{pmatrix}1&1\\1&0\end{pmatrix}\begin{pmatrix}1&n\\0&1\end{pmatrix}\begin{pmatrix}0&1\\1&-1\end{pmatrix}\begin{pmatrix}x_1\\x_0\end{pmatrix}=\begin{pmatrix}(n+1)x_1-nx_0\\nx_1-(n-1)x_0\end{pmatrix}}\)

skąd \(\displaystyle{ x_n=nx_1-(n-1)x_0=n+1}\).

[Tomek_Z]

Jeśli nie przytoczysz przykładu ze skryptu, to nic więcej powiedzieć się nie da.

To ten przykład:

\(\displaystyle{ x_{n+1} = 2x_n + 3x_{n-1} \\ x_0 = x_1 = 1}\)

(...)Pomysł polega na tym, że wyrażamy parę \(\displaystyle{ \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix}}\) poprzez \(\displaystyle{ \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}}\) korzystając z równości \(\displaystyle{ x_{n+1} = 2x_n + 3x_{n-1} \\ x_n = x_n}\) z których mamy \(\displaystyle{ \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix} = \begin{bmatrix} 2&3\\1&0 \end{bmatrix} \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}}\). Możemy dalej w sposób analogiczny wyrażać kolejne pary, aż dojdziemy do pary
utworzonej z wyrazów początkowych \(\displaystyle{ \begin{bmatrix} x_1\\ x_0 \end{bmatrix}}\):
\(\displaystyle{ \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix} = \begin{bmatrix} 2&3\\1&0 \end{bmatrix} \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix} = \begin{bmatrix} 2&3\\1&0 \end{bmatrix} \begin{bmatrix} 2&3\\1&0 \end{bmatrix} \begin{bmatrix} x_{n-1}\\ x_{n-2} \end{bmatrix}=...= \begin{bmatrix} 2&3\\1&0 \end{bmatrix} ^n \begin{bmatrix} x_1\\ x_0 \end{bmatrix}}\)(...)

No i ja robiłem w ten sam sposób, ale coś zazgrzytało...

[Qń]

Zazgrzytało to, że w skrypcie dało się "dalej w sposób analogiczny wyrażać kolejne pary, aż dojdziemy do pary utworzonej z wyrazów początkowych", ponieważ tam zależność z macierzą wiązała nam \(\displaystyle{ \begin{bmatrix} x_{n+1}\\ x_n \end{bmatrix}}\) oraz \(\displaystyle{ \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}}\), czyli z tej samej zależności można skorzystać obliczając \(\displaystyle{ \begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}}\).
Tymczasem u Ciebie zależność z macierzą wiąże \(\displaystyle{ \begin{bmatrix} x_{n+2}\\ x_{n} \end{bmatrix}}\) z \(\displaystyle{ \begin{bmatrix} x_{n+1}\\ x_{n} \end{bmatrix}}\), więc już w pierwszej próbie operacja "wyrażania kolejnych par w analogiczny sposób" jest niewykonalna.

Ponadto: przyjrzyj się postowi xiikzodz, to najbardziej pomocny post w tym wątku.

Q.

[Tomek_Z]

No ok, ale w jaki sposób mam znaleźć zależność, która zwiąże mi odpowiednie macierze?

[Qń]

przyjrzyj się postowi xiikzodz, to najbardziej pomocny post w tym wątku.

Q.