\(\displaystyle{ a _{0}=3,a _{1}=10, a_{2}=11 , a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3}\)
Obliczam równanie charakterystyczne, wyliczam pierwiastki \(\displaystyle{ r_{1}=1,r_{2}=2,r_{3}=-2}\)
Ale jak wygląda ogólna postać ciągu? Po prostu \(\displaystyle{ a_{n}=A+B2 ^{n}+C(-2)^{n}}\)?
Ta -3 w rekurencji przysparza mi problemów. Bo w końcu \(\displaystyle{ -3=-3 \cdot (1)^{n}}\), czyli podstawa potęgi jest równa jednemu pierwiastkowi charakterystycznemu... Co dalej?
Rekurencja III rzędu
-
- Użytkownik
- Posty: 67
- Rejestracja: 5 gru 2015, o 12:39
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 21 razy
Rekurencja III rzędu
Ostatnio zmieniony 22 cze 2017, o 21:28 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Rekurencja III rzędu
Ta rekurencja nie jest liniowa, właśnie przez to \(\displaystyle{ -3}\), więc postać rozwiązania ogólnego nie będzie dokładnie taka jak napisałeś. Można to rozwiązać z użyciem funkcji tworzących lub metody przewidywania, za którą nie przepadam, ale która często się pojawia, a tu akurat jest łatwa do zastosowania. Metodą przewidywania znajdujesz rozwiązanie szczególne tej rekurencji, a rozwiązanie ogólne to będzie suma tego rozwiązania szczególnego i rozwiązania rekurencji jednorodnej
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
Tutaj można przewidzieć rozwiązanie szczególne w postaci \(\displaystyle{ x_n=c\cdot n}\) gdzie \(\displaystyle{ c}\) to stała. Po podstawieniu do zależności
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3}\) za \(\displaystyle{ a_n=x_n}\) mamy:
\(\displaystyle{ c n=c(n-1)+4c(n-2)-4c(n-3)-3}\)
czyli
\(\displaystyle{ 3c-3=0}\),
a więc \(\displaystyle{ c=1}\), czyli rozwiązanie szczególne rekurencji niejednorodnej jest postaci
\(\displaystyle{ x_n=n}\)
Natomiast rozwiązanie ogólne rekurencji jednorodnej
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
ma postać
\(\displaystyle{ A+B\cdot 2^n+C\cdot (-2)^n}\)
Zatem rozwiązanie ogólne rekurencji niejednorodnej:
\(\displaystyle{ a_n=A+B\cdot 2^n+C\cdot (-2)^n+x_n=A+B\cdot 2^n+C\cdot (-2)^n+n}\)
Teraz podstawiasz dane warunki początkowe i masz układ równań:
\(\displaystyle{ \begin{cases} a_0=A+B\cdot 2^0+C\cdot (-2)^0+0\\a_1=A+B\cdot 2^1+C\cdot (-2)^1+1 \\ a_2=A+B\cdot 2^2+C\cdot (-2)^2+2\end{cases}}\)
rozwiązujesz ten układ równań ze względu na \(\displaystyle{ A, B, C}\)
i koniec.
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
Tutaj można przewidzieć rozwiązanie szczególne w postaci \(\displaystyle{ x_n=c\cdot n}\) gdzie \(\displaystyle{ c}\) to stała. Po podstawieniu do zależności
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3}\) za \(\displaystyle{ a_n=x_n}\) mamy:
\(\displaystyle{ c n=c(n-1)+4c(n-2)-4c(n-3)-3}\)
czyli
\(\displaystyle{ 3c-3=0}\),
a więc \(\displaystyle{ c=1}\), czyli rozwiązanie szczególne rekurencji niejednorodnej jest postaci
\(\displaystyle{ x_n=n}\)
Natomiast rozwiązanie ogólne rekurencji jednorodnej
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}}\)
ma postać
\(\displaystyle{ A+B\cdot 2^n+C\cdot (-2)^n}\)
Zatem rozwiązanie ogólne rekurencji niejednorodnej:
\(\displaystyle{ a_n=A+B\cdot 2^n+C\cdot (-2)^n+x_n=A+B\cdot 2^n+C\cdot (-2)^n+n}\)
Teraz podstawiasz dane warunki początkowe i masz układ równań:
\(\displaystyle{ \begin{cases} a_0=A+B\cdot 2^0+C\cdot (-2)^0+0\\a_1=A+B\cdot 2^1+C\cdot (-2)^1+1 \\ a_2=A+B\cdot 2^2+C\cdot (-2)^2+2\end{cases}}\)
rozwiązujesz ten układ równań ze względu na \(\displaystyle{ A, B, C}\)
i koniec.
-
- Użytkownik
- Posty: 67
- Rejestracja: 5 gru 2015, o 12:39
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 21 razy
Rekurencja III rzędu
Ciekawe rozwiązanie, aczkolwiek metoda funkcji tworzących jest tu odgórnie narzucona...
Mógłbyś mi przybliżyc rozwiązanie za jej pomocą?
Mógłbyś mi przybliżyc rozwiązanie za jej pomocą?
- Premislav
- Użytkownik
- Posty: 15685
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 195 razy
- Pomógł: 5219 razy
Rekurencja III rzędu
Z użyciem funkcji tworzących to byłoby tak:
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3\a_{n+3}=a_{n+2}+4a_{n+1}-4a_n-3\ sum_{n=0}^{ infty }a_{n+3} z^n= sum_{n=0}^{ infty }left( a_{n+2}+4a_{n+1}-4a_n-3
ight) z^n\ frac{1}{z^3} sum_{n=0}^{ infty }a_{n+3}z^{n+3}= frac{1}{z^2} sum_{n=0}^{ infty }a_{n+2}z^{n+2}+ frac{4}{z} sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 sum_{n=0}^{ infty }a_n z^n -3 sum_{n=0}^{ infty }z^n\ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=z sum_{n=0}^{ infty }a_{n+2}z^{n+2}+4z^2 sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 z^3sum_{n=0}^{ infty }a_n z^n -3z^3 sum_{n=0}^{ infty }z^n}\)
Niech teraz \(\displaystyle{ G(z)=sum_{n=0}^{ infty }a_n z^n}\)
Wówczas mamy
\(\displaystyle{ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=G(z)-a_0-a_1 z-a_2 z^2\sum_{n=0}^{ infty }a_{n+2}z^{n+2}=G(z)-a_0-a_1 z\sum_{n=0}^{ infty }a_{n+1}z^{n+1}=G(z)-a_0}\)
Ponadto oczywiście mamy
\(\displaystyle{ sum_{n=0}^{ infty }z^n=frac{1}{1-z}}\)
Zatem:
\(\displaystyle{ G(z)-a_0-a_1 z-a_2 z^2=zleft(G(z)-a_0-a_1 z
ight) +4z^2left( G(z)-a_0
ight)-4z^3G(z) - frac{3z^3}{1-z}}\)
Wyliczasz z tego \(\displaystyle{ G(z)}\), traktując to jak równanie z niewiadomą \(\displaystyle{ G(z)}\), podstawiasz z danych
\(\displaystyle{ a _{0}=3,a _{1}=10, a_{2}=11}\)
no a potem wykonujesz rozkład na ułamki proste: 298450.htm
i rozwijasz te ułamki w szeregi potęgowe.
\(\displaystyle{ a _{n}=a_{n-1}+4a_{n-2}-4a_{n-3}-3\a_{n+3}=a_{n+2}+4a_{n+1}-4a_n-3\ sum_{n=0}^{ infty }a_{n+3} z^n= sum_{n=0}^{ infty }left( a_{n+2}+4a_{n+1}-4a_n-3
ight) z^n\ frac{1}{z^3} sum_{n=0}^{ infty }a_{n+3}z^{n+3}= frac{1}{z^2} sum_{n=0}^{ infty }a_{n+2}z^{n+2}+ frac{4}{z} sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 sum_{n=0}^{ infty }a_n z^n -3 sum_{n=0}^{ infty }z^n\ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=z sum_{n=0}^{ infty }a_{n+2}z^{n+2}+4z^2 sum_{n=0}^{ infty }a_{n+1}z^{n+1}-4 z^3sum_{n=0}^{ infty }a_n z^n -3z^3 sum_{n=0}^{ infty }z^n}\)
Niech teraz \(\displaystyle{ G(z)=sum_{n=0}^{ infty }a_n z^n}\)
Wówczas mamy
\(\displaystyle{ sum_{n=0}^{ infty }a_{n+3}z^{n+3}=G(z)-a_0-a_1 z-a_2 z^2\sum_{n=0}^{ infty }a_{n+2}z^{n+2}=G(z)-a_0-a_1 z\sum_{n=0}^{ infty }a_{n+1}z^{n+1}=G(z)-a_0}\)
Ponadto oczywiście mamy
\(\displaystyle{ sum_{n=0}^{ infty }z^n=frac{1}{1-z}}\)
Zatem:
\(\displaystyle{ G(z)-a_0-a_1 z-a_2 z^2=zleft(G(z)-a_0-a_1 z
ight) +4z^2left( G(z)-a_0
ight)-4z^3G(z) - frac{3z^3}{1-z}}\)
Wyliczasz z tego \(\displaystyle{ G(z)}\), traktując to jak równanie z niewiadomą \(\displaystyle{ G(z)}\), podstawiasz z danych
\(\displaystyle{ a _{0}=3,a _{1}=10, a_{2}=11}\)
no a potem wykonujesz rozkład na ułamki proste: 298450.htm
i rozwijasz te ułamki w szeregi potęgowe.
Re: Rekurencja III rzędu
Jest dużo prostszy sposób. Od wyrazu \(\displaystyle{ a _{n+1}}\) odejmujesz wyraz \(\displaystyle{ a _{n}}\).
\(\displaystyle{ -3}\) się redukuje i masz normalną liniową rekurencję, którą możesz rozwiązać poprzez zwykłe podstawienie \(\displaystyle{ a _{n} = r ^{n}}\).
\(\displaystyle{ -3}\) się redukuje i masz normalną liniową rekurencję, którą możesz rozwiązać poprzez zwykłe podstawienie \(\displaystyle{ a _{n} = r ^{n}}\).