szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 31 mar 2018, o 17:46 
Użytkownik

Posty: 11
Lokalizacja: Polska
Mam równanie rekurencyjne
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
x^2=7x-6
a następnie podstawić je pod wzór
a_{n}=Ax^{n}_1 + Bx^n_1
Niestety w przypadku gdy równanie dotyczy c_{n+3} zamiast 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ą?
Góra
Mężczyzna
PostNapisane: 31 mar 2018, o 17:57 
Użytkownik
Avatar użytkownika

Posty: 14100
Lokalizacja: Wrocław
Równanie charakterystyczne:
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
c_n=A_1 +A_2 \cdot (-3)^n+A_3\cdot 2^n
gdzie 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.
Cytuj:
Ponadto mam obliczyć równanie ogóle i szczególne. Czym one się różnią?

W tym kontekście nie wiem.
Góra
Mężczyzna
PostNapisane: 31 mar 2018, o 19:17 
Użytkownik

Posty: 11
Lokalizacja: Polska
Premislav napisał(a):
Jeśli nie chcesz równania charakterystycznego, to można zastosować metodę funkcji tworzących, polecam.

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:
C(n)=\sum_{n=1}^{\infty} c_n x^n
Co daje:
C(n)=2x+3x^2+5x^3+\sum_{n=4}^{\infty} c_n x^n
C(n)=2x+3x^2+5x^3+\sum_{n=4}^{\infty} (7c_{n-2}-6c_{n-3}) x^n
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:
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ę a_k na x^k. Skąd to się wzięło? Dlaczego jest to równoważne?
Góra
Mężczyzna
PostNapisane: 31 mar 2018, o 22:37 
Użytkownik
Avatar użytkownika

Posty: 14100
Lokalizacja: Wrocław
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):
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 C(x) to funkcja tworząca pewnego naszego ciągu (c_n) spełniającego równanie rekurencyjne z zadania, to
\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:
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 c_1, c_2, c_3 (i jakieś tam wstawiłeś, tj. 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ąć):
c_{n+3}=7c_{n+1}-6c_n
Można na to popatrzeć od strony macierzy:
\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
\begin{bmatrix}0 & 7 & -6\\ 1 & 0 & 0 \\ 0& 1 &0\end{bmatrix}
nad ciałem \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
\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:
\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
PDP^{-1},
gdzie macierz D wymiaru 3\times 3 ma na głównej przekątnej (niezerowe) wartości własne naszej macierzy 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 P to po prostu jakaś tam macierz odwracalna 3\times 3 o współczynnikach zespolonych (tak naprawdę nie do końca jakaś tam, ponieważ jej kolumny tworzą wektory własne macierzy A odpowiadające kolejno odpowiednim wartościom własnym).
Wtedy
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
\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 \lambda_1, \ \lambda_2, \ \lambda_3 to wspomniane niezerowe wartości własne macierzy A) dostaniemy w szczególności
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 A_1, \ A_2, \ A_3
(na te stałe będą miały wpływ wartości współczynników macierzy P i P^{-1} oraz 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):
\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
-x^3-(-7x+6)=0, czyli równoważnie
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ą 1, \ -3, \
 2.
Czyli rozwiązanie ogólne będzie postaci
c_n=A_1'\cdot 1^n +A_2'(-3)^n+A_3' \cdot 2^n
(ponieważ nasza formuła opisywała c_{n+3}, dodałem primy, żeby coś takiego zaszło; tutaj byłoby A_i'= \frac{A_i}{\lambda_i^3} ),
a gdybyś miał dane c_1, \ c_2, \ c_3, to mógłbyś wyliczyć też 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" a_n przez 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.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 dwumian newtona, losowanie dwóch elementów obok siebie  plosaczek  2
 3 zadania: szachownica, graf, rekurencja  jraven  3
 Rekurencja z liczbami zespolonymi  MenosGrandes  7
 Liczba elementów - zadanie 3  together  0
 rekurencja-funkcja tworzaca  duze_jablko2  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl