Mam problem z rozwiązaniem następującej rekurencji metodą przewidywań
\(\displaystyle{ a_{n}=a_{n-1}+2 \cdot a_{n-2}-\bigl((-1)^{n}+2 \cdot (-2)^{n}\bigl)-n}\)
dla: \(\displaystyle{ n \ge 2,\quad a_{0}=3,\quad a_{1}=5}\)
W moim rozwiązaniu wyszło
\(\displaystyle{ a_{n}=\frac{(-1)^{n}}{10}+ \frac{41\cdot 2^{n}}{20} -(-1)^{n}+ \frac{8 \cdot (-2)^{n}}{5} -\frac{3n}{4} + \frac{1}{4}}\)
natomiast po wrzuceniu danych do programu Maxima dostałem taki wynik
\(\displaystyle{ a_{n}=\frac{2^{n+3}}{9} +(-2)^{n+1}- \frac{n(-1)^{n}}{3} + \frac{103 \cdot (-1)^{n}}{36} + - \frac{n}{2} + \frac{5}{4}}\)
Gdzieś ewidentnie popełniłem błąd, ale siedzę nad tym kolejny dzień i nic nie mogę znaleźć. Bardzo bym prosił o pomoc w tym zagadnieniu.
Niejednorodne równanie rekurencyjne - metoda przewidywań
-
Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Niejednorodne równanie rekurencyjne - metoda przewidywań
W sumie wolałbym zastosować metodę funkcji tworzących, ale niech tam…
Równanie jednorodne:
\(\displaystyle{ a_n=a_{n-1}+2a_{n-2}}\)
ma równanie charakterystyczne
\(\displaystyle{ t^2-t-2=0\\ (t+1)(t-2)=0}\),
stąd rozwiązanie ogólne rekurencji jednorodnej jest postaci
\(\displaystyle{ A\cdot (-1)^n+B\cdot 2^n}\)
gdzie \(\displaystyle{ A, \ B}\) to pewne stałe.
Kluczowe jest przewidzenie rozwiązania szczególnego rekurencji niejednorodnej.
Dla fragmentu \(\displaystyle{ -(-1)^n}\) przewidujemy \(\displaystyle{ c_1 n(-1)^n}\), a to ze względu na fakt, że \(\displaystyle{ -1}\) jest jednokrotnym pierwiastkiem równania charakterystycznego dla rekurencji jednorodnej.
Dla fragmentu \(\displaystyle{ -2\cdot (-2)^n}\) przewidujemy po prostu \(\displaystyle{ c_2\cdot (-2)^n}\), ponieważ \(\displaystyle{ -2}\) nie jest pierwiastkiem równania charakterystycznego.
Dla fragmentu \(\displaystyle{ -n}\) przewidujemy \(\displaystyle{ c_3\cdot n+c_4}\).
No i teraz wyliczamy te stałe, podstawiając:
zaczniemy może od \(\displaystyle{ c_3}\) i \(\displaystyle{ c_4}\), tj. ten fragment od \(\displaystyle{ -n}\).
\(\displaystyle{ c_3 \cdot n+c_4 =c_3\cdot (n-1)+c_4+2c_3\cdot (n-2)+2c_4-n}\)
Traktujemy to jak równość wielomianów i mamy po prostych obliczeniach:
\(\displaystyle{ c_3=\frac 1 2, \ c_4=\frac 5 4}\)
To teraz ten fragment z \(\displaystyle{ (-2)^n}\):
\(\displaystyle{ c_2\cdot (-2)^n=c_2(-2)^{n-1}+2c_2(-2)^{n-2}-2\cdot (-2)^n\\ c_2=-2}\)
Wreszcie pozostaje fragment z \(\displaystyle{ c_1n(-1)^n}\):
\(\displaystyle{ c_1n(-1)^n=c_1(n-1)(-1)^{n-1}+2c_1(n-2)(-1)^{n-2}-(-1)^n\\c_1=-\frac 1 3}\)
Czyli sumując to, widzimy, że
\(\displaystyle{ -\frac 1 3 n(-1)^n+(-2)^{n+1}+\frac 1 2 n+\frac 5 4}\)
jest rozwiązaniem szczególnym naszej rekurencji niejednorodnej.
Natomiast trudno oczekiwać, żebyśmy wskazali, gdzie popełniłeś błąd, skoro nie pokazujesz obliczeń, a jedynie wynik
Ostatecznie wyszedł mi taki pyton (rozwiązanie rekurencji niejednorodnej z uwzględnieniem warunków początkowych):
\(\displaystyle{ a_n=\frac{103}{36}\cdot (-1)^n+\frac{2^{n+3}}{9}+(-2)^{n+1}-\frac 1 3 n(-1)^n{\red +\frac n 2}+\frac 5 4}\)
Fragment zaznaczony na czerwono mam inaczej niż podałeś z Maximy i za nic nie wychodzi inaczej.
Równanie jednorodne:
\(\displaystyle{ a_n=a_{n-1}+2a_{n-2}}\)
ma równanie charakterystyczne
\(\displaystyle{ t^2-t-2=0\\ (t+1)(t-2)=0}\),
stąd rozwiązanie ogólne rekurencji jednorodnej jest postaci
\(\displaystyle{ A\cdot (-1)^n+B\cdot 2^n}\)
gdzie \(\displaystyle{ A, \ B}\) to pewne stałe.
Kluczowe jest przewidzenie rozwiązania szczególnego rekurencji niejednorodnej.
Dla fragmentu \(\displaystyle{ -(-1)^n}\) przewidujemy \(\displaystyle{ c_1 n(-1)^n}\), a to ze względu na fakt, że \(\displaystyle{ -1}\) jest jednokrotnym pierwiastkiem równania charakterystycznego dla rekurencji jednorodnej.
Dla fragmentu \(\displaystyle{ -2\cdot (-2)^n}\) przewidujemy po prostu \(\displaystyle{ c_2\cdot (-2)^n}\), ponieważ \(\displaystyle{ -2}\) nie jest pierwiastkiem równania charakterystycznego.
Dla fragmentu \(\displaystyle{ -n}\) przewidujemy \(\displaystyle{ c_3\cdot n+c_4}\).
No i teraz wyliczamy te stałe, podstawiając:
zaczniemy może od \(\displaystyle{ c_3}\) i \(\displaystyle{ c_4}\), tj. ten fragment od \(\displaystyle{ -n}\).
\(\displaystyle{ c_3 \cdot n+c_4 =c_3\cdot (n-1)+c_4+2c_3\cdot (n-2)+2c_4-n}\)
Traktujemy to jak równość wielomianów i mamy po prostych obliczeniach:
\(\displaystyle{ c_3=\frac 1 2, \ c_4=\frac 5 4}\)
To teraz ten fragment z \(\displaystyle{ (-2)^n}\):
\(\displaystyle{ c_2\cdot (-2)^n=c_2(-2)^{n-1}+2c_2(-2)^{n-2}-2\cdot (-2)^n\\ c_2=-2}\)
Wreszcie pozostaje fragment z \(\displaystyle{ c_1n(-1)^n}\):
\(\displaystyle{ c_1n(-1)^n=c_1(n-1)(-1)^{n-1}+2c_1(n-2)(-1)^{n-2}-(-1)^n\\c_1=-\frac 1 3}\)
Czyli sumując to, widzimy, że
\(\displaystyle{ -\frac 1 3 n(-1)^n+(-2)^{n+1}+\frac 1 2 n+\frac 5 4}\)
jest rozwiązaniem szczególnym naszej rekurencji niejednorodnej.
Natomiast trudno oczekiwać, żebyśmy wskazali, gdzie popełniłeś błąd, skoro nie pokazujesz obliczeń, a jedynie wynik
Ostatecznie wyszedł mi taki pyton (rozwiązanie rekurencji niejednorodnej z uwzględnieniem warunków początkowych):
\(\displaystyle{ a_n=\frac{103}{36}\cdot (-1)^n+\frac{2^{n+3}}{9}+(-2)^{n+1}-\frac 1 3 n(-1)^n{\red +\frac n 2}+\frac 5 4}\)
Fragment zaznaczony na czerwono mam inaczej niż podałeś z Maximy i za nic nie wychodzi inaczej.
Re: Niejednorodne równanie rekurencyjne - metoda przewidywań
Znalazłem błąd. Źle przewidziałem rozwiązanie dla \(\displaystyle{ -(-1)^{n}}\). Do tego doszły "uciekające" minusy i ostatecznie wynik mi się kompletnie rozjechał. Bardzo dziękuję za pomoc.