Równania rekurencyjne-metoda przewidywań

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
pumbosza
Użytkownik
Użytkownik
Posty: 97
Rejestracja: 19 lut 2008, o 21:36
Płeć: Mężczyzna
Lokalizacja: kielce
Podziękował: 29 razy

Równania rekurencyjne-metoda przewidywań

Post autor: pumbosza »

Witam, nie za bardzo wiem czy w dobrym dziale umieściłem ten temat, w razie czego proszę o przeniesienie.
Mam pytanie ,bo nie bardzo mogę znaleźć to w internecie, mianowicie chodzi i o to jakie rozwiązanie przewidujemy w zależności od prawej strony równania rekurencyjnego, czysta teoria. Prosiłbym o odpowiedź ew. jakieś linki.
Pzdr
abc666

Równania rekurencyjne-metoda przewidywań

Post autor: abc666 »

Równanie niejednorodne rozwiązuje się w dwóch etapach.
Etap I. Poszukujemy rozwiązania ogólnego \(\displaystyle{ a_o}\) jednorodnego liniowego równania rekurencyjnego.
Etap II. Poszukujemy rozwiązania szczególnego \(\displaystyle{ a_s}\) niejednorodnego liniowego równania rekurencyjnego. Najczęściej stosuje się tzw, metodę przewidywań
• jeżeli \(\displaystyle{ f (n)}\) jest wielomianem stopnia n i rozwiązanie ogólne nie jest wielomianem, to rozwiązanie szczególne
jest wielomianem tego samego stopnia co \(\displaystyle{ f (n)}\),
• jeżeli \(\displaystyle{ f (n)}\) jest wielomianem stopnia n i rozwiązanie ogólne jest wielomianem stopnia k, to rozwiązanie
szczególne ma postać
\(\displaystyle{ a_n^s = n^{k+1} (A_k n^k + A_{k−1} n^{k−1} +...+ A_0 )}\),
• jeżeli \(\displaystyle{ f (n)}\) jest funkcją wykładniczą postaci \(\displaystyle{ f (n) = C\beta ^n}\) i \(\displaystyle{ \beta}\) nie jest pierwiastkiem równania charaktery-
stycznego, to rozwiązanie szczególne jest postaci \(\displaystyle{ a_n^s = A\beta^n}\) ,
• jeżeli \(\displaystyle{ f (n)}\) jest funkcją wykładniczą postaci \(\displaystyle{ f (n) = C\beta ^n}\) i \(\displaystyle{ \beta}\) jest k-krotnym pierwiastkiem równania
charakterystycznego, to rozwiązanie szczególne jest postaci \(\displaystyle{ a_n^s = n^kA\beta^n}\) .
n
Stałe \(\displaystyle{ A_1 , A_2 , . . . , A_0}\) i \(\displaystyle{ A}\) występujące w rozwiązaniach szczególnych należy wyznaczyć wykorzystując fakt, że
mamy otrzymać rozwiązanie równania niejednorodnego.
Jeżeli funkcja \(\displaystyle{ f (n)}\) jest sumą funkcji rozważanych powyżej, to przewidywanie rozwiazanie jest suma prze-
widywanych rozwiazań odpowiadajacych tym funkcjom.
Rozwiązanie jest wtedy postaci \(\displaystyle{ a_n=a_n^o+a_n^s}\)
pumbosza
Użytkownik
Użytkownik
Posty: 97
Rejestracja: 19 lut 2008, o 21:36
Płeć: Mężczyzna
Lokalizacja: kielce
Podziękował: 29 razy

Równania rekurencyjne-metoda przewidywań

Post autor: pumbosza »

Dziękuję bardzo za odpowiedź, bardzo mi to pomoże. Pozdrawiam-- 17 stycznia 2010, 21:43 --Jeszcze dwa pytanka co do tego tematu: Co przewidujemy gdy f(n) jest funkcją trygonometryczną. Co do tej wersji wielomianowej ,nie bardzo rozumiem kiedy dodajemy to \(\displaystyle{ n^{k+1}}\) przed rozwiązaniem, bo przecież rozwiązanie ogólne może mieć tylko dwie postacie, w zależności od pierwiastków równania charakterystycznego.
Linka87
Użytkownik
Użytkownik
Posty: 78
Rejestracja: 18 lut 2007, o 17:22
Płeć: Kobieta
Lokalizacja: Warszawa
Podziękował: 15 razy
Pomógł: 4 razy

Równania rekurencyjne-metoda przewidywań

Post autor: Linka87 »

abc666 pisze:
• jeżeli \(\displaystyle{ f (n)}\) jest wielomianem stopnia n i rozwiązanie ogólne nie jest wielomianem, to rozwiązanie szczególne
jest wielomianem tego samego stopnia co \(\displaystyle{ f (n)}\),
• jeżeli \(\displaystyle{ f (n)}\) jest wielomianem stopnia n i rozwiązanie ogólne jest wielomianem stopnia k, to rozwiązanie
szczególne ma postać
\(\displaystyle{ a_n^s = n^{k+1} (A_k n^k + A_{k−1} n^{k−1} +...+ A_0 )}\)
Nie za bardzo rozumiem tą część.
Np. mam powiedzmy taki przykład :
\(\displaystyle{ y_{n+2} + y_{n+1} - 2y_{n} = 12}\)
jeśli miałabym przewidywać to rozwiązanie szczególne zapisałabym
\(\displaystyle{ y^{s}_{n} = a}\)
ale jak podstawimy to wyjdzie sprzeczność, czyli wiadomo, że trzeba jednak przewidzieć
\(\displaystyle{ y^{s}_{n} = na}\)
równanie ogólne wygląda tak:
\(\displaystyle{ y^{o}_{n} = C_{1} \cdot 1^{n} + C_{2} \cdot (-2)^{n}}\)
abc666

Równania rekurencyjne-metoda przewidywań

Post autor: abc666 »

Linka87, mylisz się. Twoje równanie ma postać
\(\displaystyle{ y_{n+2}=-y_{n+1} - 2y_{n}+12}\)
podstawiając
\(\displaystyle{ a_n=y_n+3}\) dostajemy
\(\displaystyle{ a_{n+2}=-a_{n+1}-2a_n}\)
którego rozwiązanie ma postać
\(\displaystyle{ a_n=C_1x_1^n+C_2x_2^n}\)
a więc
\(\displaystyle{ y_n=C_1x_1^n+C_2x_2^n-3}\)

Dowód ogólny przeprowadzić można analogicznie.

-- 22 stycznia 2010, 18:37 --

pumbosza, ale to co ja podałem odnosi się do rekurencji dowolnego rzędu a nie tylko rzędu 2. Zauważ, że te dwie postaci które znasz są szczególnym przypadkiem tego wzoru.

pumbosza, pokaż proszę przykład takiej rekurencji z f. tryg.. Szczerze wątpię w istnienie tak prostej zależności, w końcu sumujemy funkcje trygonometryczne. Takie przykłady raczej trzeba rozważać indywidualnie, poza paroma szczególnymi przypadkami, które i tak dadzą się sprowadzić do tych wymienionych wyżej.
ODPOWIEDZ