Rekurencja zależąca od elementów innych niż 2 poprzednie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
wpzd
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 lis 2017, o 11:43
Płeć: Mężczyzna
Lokalizacja: Polska

Rekurencja zależąca od elementów innych niż 2 poprzednie

Post autor: wpzd » 31 mar 2018, o 17:46

Mam równanie rekurencyjne
\(\displaystyle{ c_{n+3} = 7c_{n+1}-6{c_n}}\)
Wyznaczanie równania szczególnego takiej rekurencji polegałoby na tym, żeby obliczyć pierwiastki równania charakterystycznego
\(\displaystyle{ x^2=7x-6}\)
a następnie podstawić je pod wzór
\(\displaystyle{ a_{n}=Ax^{n}_1 + Bx^n_1}\)
Niestety w przypadku gdy równanie dotyczy \(\displaystyle{ c_{n+3}}\) zamiast \(\displaystyle{ c_{n+2}}\) sprawa się komplikuje, bo rekurencja zależy od innych elementów niż 2 poprzednie.

W jaki sposób zabrać się za coś takiego?

Ponadto mam obliczyć równanie ogóle i szczególne. Czym one się różnią?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14375
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 80 razy
Pomógł: 4726 razy

Re: Rekurencja zależąca od elementów innych niż 2 poprzednie

Post autor: Premislav » 31 mar 2018, o 17:57

Równanie charakterystyczne:
\(\displaystyle{ t^3-7t+6=0\\(t-1)\left( t^2+t-6\right)=0}\)
Stąd możemy wywnioskować (po rozłożeniu tego wielomianu np. z użyciem twierdzenia o pierwiastkach wymiernych), że rozwiązanie ogólne jest postaci
\(\displaystyle{ c_n=A_1 +A_2 \cdot (-3)^n+A_3\cdot 2^n}\)
gdzie \(\displaystyle{ A_1, A_2, A_3}\) to pewne stałe.

Jeśli nie chcesz równania charakterystycznego, to można zastosować metodę funkcji tworzących, polecam.
Ponadto mam obliczyć równanie ogóle i szczególne. Czym one się różnią?
W tym kontekście nie wiem.

wpzd
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 26 lis 2017, o 11:43
Płeć: Mężczyzna
Lokalizacja: Polska

Rekurencja zależąca od elementów innych niż 2 poprzednie

Post autor: wpzd » 31 mar 2018, o 19:17

[quote="Premislav"]
Jeśli nie chcesz równania charakterystycznego, to można zastosować metodę funkcji tworzących, polecam.
[/quote]
Jako że metoda którą chciałem zrobić to zadanie wymagała żmudnych obliczeń, postanowiłem spróbować tej z funkcjami tworzącymi. Niestety i tu sprawa się zagmatwała:
Z definicji:
\(\displaystyle{ C(n)=\sum_{n=1}^{\infty} c_n x^n}\)
Co daje:
\(\displaystyle{ C(n)=2x+3x^2+5x^3+\sum_{n=4}^{\infty} c_n x^n}\)
\(\displaystyle{ C(n)=2x+3x^2+5x^3+\sum_{n=4}^{\infty} (7c_{n-2}-6c_{n-3}) x^n}\)
\(\displaystyle{ C(n)=2x+3x^2+5x^3+7x^2(\sum_{n=1}^{\infty} c_nx^n-c_1x^1)-6x^3\sum_{n=1}^{\infty} c_nx^n}\)
Finalny wzór funkcji tworzącej:
\(\displaystyle{ C(x)=\frac{-9x^3+3x^2+2x}{6x^3-7x^2+1}}\)
Teraz możnaby to rozbić na ułamki proste, z tym że zapowiada się masa liczenia. Czy ja idę w ogóle w dobrą stronę? xD

-- 31 mar 2018, o 18:24 --

A z innej beczki:
czytam sobie uzasadnienie zastosowania równania charakterystycznego z tego pdf'u i w punkcie 4.2 zastosowano zamianę \(\displaystyle{ a_k}\) na \(\displaystyle{ x^k}\). Skąd to się wzięło? Dlaczego jest to równoważne?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14375
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 80 razy
Pomógł: 4726 razy

Re: Rekurencja zależąca od elementów innych niż 2 poprzednie

Post autor: Premislav » 31 mar 2018, o 22:37

Coś mi tu na pierwszy rzut (zmęczonego) oka nie do końca pasuje, mianowicie zaś funkcja tworząca w sposób jednoznaczny identyfikuje ciąg, natomiast tutaj tę rekurencję spełnia nieskończenie wiele ciągów, więc muszą być jakieś błędy w tym dojściu do postaci funkcji tworzącej. Miałeś tam podane jakieś warunki początkowe? Czwarty wyraz zależy od pierwszego i drugiego, zaś piąty od drugiego i trzeciego (no a dalej to już widać, że „poleci"), zatem do jednoznacznego wyznaczenia ciągu potrzebne byłoby określenie trzech pierwszych wyrazów.

Ja metodą funkcji tworzących otrzymałem coś takiego (przyjmując, jak u Ciebie, numerowanie od jedynki, a nie od zera):
\(\displaystyle{ c_{n+3}=7c_{n+1}-6c_n\\ \sum_{n=1}^{+\infty}c_{n+3}x^n=7 \sum_{n=1}^{+\infty}c_{n+1}x^n-6 \sum_{n=1}^{+\infty}c_n x^n \bigg| \cdot x^3\\ \sum_{ n=1}^{+\infty}c_{n+3}x^{n+3}=7x^2 \sum_{n=1}^{+\infty}c_{n+1}x^n-6x^3 \sum_{n=1}^{+\infty}c_n x^n}\)
Teraz jeżeli \(\displaystyle{ C(x)}\) to funkcja tworząca pewnego naszego ciągu \(\displaystyle{ (c_n)}\) spełniającego równanie rekurencyjne z zadania, to
\(\displaystyle{ \sum_{ n=1}^{+\infty}c_{n+3}x^{n+3}=C(x)-x^3 c_3-x^2 c_2-xc_1\\\sum_{n=1}^{+\infty}c_{n+1}x^n=C(x)-xc_1\\\sum_{n=1}^{+\infty}c_n x^n=C(x)}\),
tak więc otrzymujemy:
\(\displaystyle{ C(x)-x^3 c_3-x^2 c_2-xc_1=7x^2\left(C(x)-xc_1\right)-6x^3 C(x)\\C(x)\left( 1-7x^2+6x^3\right)=x^3 (c_3-7c_1)+x^2 c_2+xc_1\\ C(x)= \frac{x^3 (c_3-7c_1)+x^2 c_2+xc_1}{1-7x^2+6x^3}}\)
No i dalej najpierw dzielenie wielomianów z resztą (licznika przez mianownik oczywiście), a potem rozkład na ułamki proste. Tak, niestety to jest dość sporo liczenia.

-- 31 mar 2018, o 21:38 --

Wychodzi na to, że Twoje przekształcenia były z grubsza OK, z tymże zastrzeżeniem, iż potraktowałeś to zadanie tak, jakbyś miał dane \(\displaystyle{ c_1, c_2, c_3}\) (i jakieś tam wstawiłeś, tj. \(\displaystyle{ c_1=2, \ c_2=3, c_3=5}\)), wówczas otrzymasz pewne rozwiązanie szczególne wspomnianego równania rekurencyjnego (a nie postać ogólną).

-- 31 mar 2018, o 21:42 --

A gdyby rozkład na ułamki proste Ci nie szedł, to możesz przejrzeć przykłady stąd:
298450.htm

-- 1 kwi 2018, o 00:46 --

A, jeszcze ta sprawa z równaniem charakterystycznym. Spróbuję to wytłumaczyć na przykładzie tego równania rekurencyjnego z zadania (w ogólności byłoby tylko znacznie więcej pisania, przy czym idea ta sama, a tego wolałbym uniknąć):
\(\displaystyle{ c_{n+3}=7c_{n+1}-6c_n}\)
Można na to popatrzeć od strony macierzy:
\(\displaystyle{ \begin{bmatrix}c_{n+3}\\c_{n+2}\\c_{n+1} \end{bmatrix}=\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}\begin{bmatrix}c_{n+2}\\c_{n+1} \\ c_{n}\end{bmatrix}}\)
i gdybyśmy teraz zdiagonalizowali tę macierz
\(\displaystyle{ \begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}}\)
nad ciałem \(\displaystyle{ \CC}\),
to moglibyśmy ją łatwo podnieść do odpowiedniej potęgi.
No a to się przyda, ponieważ zapisując dalej rekurencje dla kolejnych wektorów z użyciem macierzy, otrzymamy
\(\displaystyle{ \begin{bmatrix}c_{n+2}\\c_{n+1}\\c_{n} \end{bmatrix}=\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}\begin{bmatrix}c_{n+1}\\c_{n} \\ c_{n-1}\end{bmatrix}}\)
i tak dalej (mnożenie macierzy jest łączne), co prowadzi do:
\(\displaystyle{ \begin{bmatrix}c_{n+3}\\c_{n+2}\\c_{n+1} \end{bmatrix}=\left(\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}\right)^n \begin{bmatrix}c_{3}\\c_{2} \\ c_{1}\end{bmatrix}}\)
Powiedzmy, że zdiagonalizowaliśmy tę macierz, tj. przedstawiliśmy ją w postaci
\(\displaystyle{ PDP^{-1}}\),
gdzie macierz \(\displaystyle{ D}\) wymiaru \(\displaystyle{ 3\times 3}\) ma na głównej przekątnej (niezerowe) wartości własne naszej macierzy \(\displaystyle{ A=\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}}\),
a poza główną przekątną same zera, no a macierz \(\displaystyle{ P}\) to po prostu jakaś tam macierz odwracalna \(\displaystyle{ 3\times 3}\) o współczynnikach zespolonych (tak naprawdę nie do końca jakaś tam, ponieważ jej kolumny tworzą wektory własne macierzy \(\displaystyle{ A}\) odpowiadające kolejno odpowiednim wartościom własnym).
Wtedy
\(\displaystyle{ A^n=PD^nP^{-1}}\)
(dowód: łatwa indukcja plus skorzystanie z łączności mnożenia macierzy)
i stąd po wymnożeniu z tej postaci
\(\displaystyle{ \begin{bmatrix}c_{n+3}\\c_{n+2}\\c_{n+1} \end{bmatrix}=\left(\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}\right)^n \begin{bmatrix}c_{3}\\c_{2} \\ c_{1}\end{bmatrix}}\)
(powiedzmy, że \(\displaystyle{ \lambda_1, \ \lambda_2, \ \lambda_3}\) to wspomniane niezerowe wartości własne macierzy \(\displaystyle{ A}\)) dostaniemy w szczególności
\(\displaystyle{ c_{n+3}=A_1 \cdot \lambda_1^n+A_2\cdot \lambda_2^n+A_3\cdot \lambda_3^n}\)
dla jakichś tam stałych zespolonych \(\displaystyle{ A_1, \ A_2, \ A_3}\)
(na te stałe będą miały wpływ wartości współczynników macierzy \(\displaystyle{ P}\) i \(\displaystyle{ P^{-1}}\) oraz \(\displaystyle{ c_1, \ c_2, \ c_3}\), które tu, bez warunku początkowego, pozostałyby jako parametry; sorry Gregory, nie będę tego bardziej drobiazgowo rozpisywał, se kurde wymnóż i zobacz, że to tak działa).
No to wartości własne to po prostu pierwiastki wielomianu charakterystycznego, czyli takiego wielomianu (w tym przypadku, po prostu odejmujemy iksy na przekątnej):
\(\displaystyle{ \det\begin{bmatrix}-x & 7 & -6\\ 1 & -x & 0 \\ 0& 1 &-x\end{bmatrix}}\)
No a ten wyznacznik można obliczyć ulubioną metodą (ja zwykle pamiętam tylko rozwinięcie Laplace'a):
wychodzi, że stajemy przed zadaniem znalezienia rozwiązań równania
\(\displaystyle{ -x^3-(-7x+6)=0}\), czyli równoważnie
\(\displaystyle{ x^3-7x+6=0}\),
jak wspomniałem. I to jest właśnie wspomniane równanie charakterystyczne.
Pierwiastkami tego (ja to zgadłem akurat) są \(\displaystyle{ 1, \ -3, \ 2}\).
Czyli rozwiązanie ogólne będzie postaci
\(\displaystyle{ c_n=A_1'\cdot 1^n +A_2'(-3)^n+A_3' \cdot 2^n}\)
(ponieważ nasza formuła opisywała \(\displaystyle{ c_{n+3}}\), dodałem primy, żeby coś takiego zaszło; tutaj byłoby \(\displaystyle{ A_i'= \frac{A_i}{\lambda_i^3}}\) ),
a gdybyś miał dane \(\displaystyle{ c_1, \ c_2, \ c_3}\), to mógłbyś wyliczyć też \(\displaystyle{ A_1', \ A_2', \ A_3'}\).

Pozostaje jeszcze taka kwestia, że czasem to się tak ładnie nie diagonalizuje (wyskakuje jakiś rozkład Jordana itd.).
A czemu oni sobie to tak po prostu „zastąpili" \(\displaystyle{ a_n}\) przez \(\displaystyle{ x^n}\) to nie wiem, to taka sztuczka mnemotechniczna, a skąd się bierze to równanie charakterystyczne to , mam nadzieję, powyżej wytłumaczyłem.

Pozdrawiam.

ODPOWIEDZ