szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 sie 2012, o 13:35 
Użytkownik
Avatar użytkownika

Posty: 705
Wstęp

Jak wiadomo za pomocą równań rekurencyjnych możemy definiować ciągi liczbowe. Niestety bywa tak że o zadanym w ten sposób ciągu chcemy wiedzieć jaką postać jawną ma konkretny jego wyraz a obliczanie jej za pomocą zadanej zależności rekurencyjnej bywa bardzo uciążliwe. Prezentowany tutaj zbiór metod rozwiązywania (znajdowania postaci jawnej ciągów) omawianych równań może być w wielu przypadkach bardzo pomocny. Zaznaczam jednak że prezentowane algorytmy mają charakter praktyczny i nie będziemy zajmować się dowodzeniem ich prawdziwości.


1. Liniowe równania rekurencyjne jednorodne o stałych współczynnikach rzędu k mają postać:

x_n=a_1x_{n-1}+a_2x_{n-2}+...+a_kx_{n-k} \ \ \ \ (1)

gdzie: n>k, \ \forall _{i \in \left\{1,2,..,k\right\}=I_k} \ a_i \in \CC są współczynnikami, a ciąg (x_i)_{i \in N_+} jest przez (1) i k początkowych wyrazów zdefiniowany. Umawiamy się też stosować od teraz utożsamienie \forall_{k \in N_+} \left\{1,2,...,k\right\}=I_k.

Aby je rozwiązać należy zauważyć że ciąg zadany w sposób: x_n= x^n, spełnia nasze równanie wtedy i tylko wtedy gdy x jest pierwiastkiem stowarzyszonego równania charakterystycznego równania (1) postaci:

x^k-a_1x^{k-1}-a_2x^{k-2}-...-a_{k-1}x-a_k=0 \ \ \ \ (2)

Na mocy zasadniczego twierdzenia algebry ma ono k pierwiastków, wielokrotnych lub nie. Jeżeli oznaczymy je przez \alpha_1, \ \alpha_2, \ ..., \ \alpha_l, l \le k, a ich krotności odpowiednio przez p_1, \ p_2, \ ..., \ p_l gdzie oczywiście \forall_{i \in I_l}p_i  \ge 1 oraz p_1 + p_2 + ... + p_l = k to rozwiązanie (1) ma postać:

x_n=\sum_{m=1}^{l}\left(\sum_{i=0}^{p_m-1}b^{(m)}_{i}n^i \right)\left(\alpha_m\right)^n \ \ \ \ (3)

gdzie: \forall_{m \in I_l} \forall_{i \in \left\{0,1,...,p_m-1 \right\}} b^{(m)}_{i} \in \CC są współczynnikami wyznaczanymi przez podstawienie wartości początkowych wyrazów do (3). W szczególności jeśli l=k tzn. jeśli wszystkie pierwiastki są pojedynczej krotności otrzymamy:

x_n=\sum^{k}_{m=1}b_m(\alpha_m)^n \ \ \ \ (4)

gdzie: \forall_{m \in I_k}b_m \in \CC i tym razem to one grają rolę współczynników.

Przykład 1.
x_n=2x_{n-1}, \ x_1=2, \ n>1


Rozwiązanie:    


Przykład 2.
F_n=F_{n-1}+F_{n-2}, \ F_1=1, \ F_2=1, \ n>2


Rozwiązanie:    


Przykład 3.

x_n=x_{n-1}-ix_{n-2}+ix_{n-3}, \ x_1=1, \ x_2=1-2i, \ x_3=1, \ n>3


Rozwiązanie:    


2.Liniowe równania rekurencyjne jednorodne o zmiennych współczynnikach rzędu k
są postaci:

x_n=a^{(1)}_nx_{n-1}+a^{(2)}_nx_{n-2}+...+a^{(k)}_{n}x_{n-k}

gdzie: n>k, \ ( a^{(1)}_n)^{\infty}_{n=k+1}, \ ( a^{(2)}_n)^{\infty}_{n=k+1}, \ ..., \ ( a^{(k)}_n)^{\infty}_{n=k+1} są zadanymi ciągami współczynników takich że \forall_{ i \in I_k} \forall_{n \in \left\{k+1,k+2,...\right\}}a^{(i)}_n \in \CC. Nie będziemy jednak zajmować się wszystkimi równaniami tego typu a jedynie szczególnym przypadkiem rzędu pierwszego tzn. iloczynem nieskończonym postaci:

x_n=a_nx_{n-1} \ \ \ \ (5)

postać jawna tego ciągu to:

x_n=x_1\prod^{n}_{i=2}a_1 \ \ \ \ (6)


Przykład 1.
x_n=nx_{n-1}, \ x_1=1, \ n>1

Rozwiązanie:    


Przykład 2.
x_n=\frac{n-1}{n}x_{n-1}, \ x_1=1, \ n>1

Rozwiązanie:    


Przykład 3.
x_n=\frac{5^n}{n}x_{n-1}, \ x_1=5, \ n>1

Rozwiązanie:    


3. Liniowym równaniem rekurencyjnym niejednorodnym o stałych współczynnikach rzędu k nazywamy równanie postaci:

x_n=a_1x_{n-1}+a_2x_{n-2}+...+a_kx_{n-k}+f(n) \ \ \ \ (7)

gdzie: n>k, \ \forall_{i \in I_k}a_i \in \CC są współczynnikami, a f(n) oznacza funkcję zmiennej n taką że f(n)\not\equiv 0.

Rozwiązując równanie (7) zajmujemy się najpierw równaniem powstałym przez odrzucenie z (7) wyrazu f(n) tzn. znalezieniem rozwiązania x^{(1)}_n równania postaci (1). Następnie poszukujemy tzw. szczególnego rozwiązania x^{(2)}_n równania (7). Rozwiązanie ogólne tego równania jest wtedy postaci:

x_n=x^{(1)}_n+x^{(2)}_n \ \ \ \ (8).

Niestety znalezienie rozwiązania szczególnego nie jest zwykle zadaniem prostym, toteż użyteczna jest tzw. metoda przewidywań która dla niektórych postaci f(n) mówi nam jaką postać man rozwiązanie szczególne. Oto te przypadki:
\star Jeżeli f(n)=a \neq 0 \ \wedge \ \sum_{i=1}^k a_i \neq 1 to x^{(2)}_n=\frac{a}{1- \sum_{i=1}^k a_i}

\star Jeżeli f(n)=a\neq 0 \  \wedge \ \sum_{i=1}^k a_i = 1 to x^{(2)}_n=n\frac{a}{\sum_{i=1}^k ia_i}

\star Jeżeli f(n)=A\alpha^n i \alpha nie jest pierwiastkiem równania charakterystycznego
równania (1) stowarzyszonego z równaniem (7) to x^{(2)}_n=B\alpha^n

\star Jeżeli f(n)=A\alpha^n i \alpha jest pierwiastkiem k \ge 1 krotnym równania charakterystycznego
równania (1) stowarzyszonego z równaniem (7) to x^{(2)}_n=Bn^k\alpha^n

\starJeżeli f(n)=w_d(n) (gdzie w_d(n) oznacza wielomian stopnia d zmiennej n) a x^{(1)}_n nie jest wielomianem zmiennej n to x^{(2)}_n=q_{max \ d}(n) (gdzie q_{max \ d}(n) oznacza wielomian stopnia co najwyżej d zmiennej n)

\starJeżeli f(n)=w_d(n) a x^{(1)}_n jest wielomianem stopnia k zmiennej n to x^{(2)}_n=n^{k+1}q_{max \ d}(n)


Jeżeli natomiast f(n) jest sumą/różnicą wspomnianych klas funkcji to rozwiązanie szczególne jest sumą/różnicą przewidywanych rozwiązań szczególnych. Warto także zatrzymać się na równaniu niejednorodnym:

x_n=x_{n-1}+f(n) \ \ \ \ (9)

nazywanym sumą nieskończoną (jest to po prostu suma częściowa pewnego szeregu). Mamy tutaj łatwy do wyznaczenia wzór jawny:

x_n=x_1 + \sum^{n}_{i=2}f(i) \ \ \ \ (10).

O ile jednak otrzymanie takiej postaci jest łatwe to jej przekształcenie na postać zwartą już nie zawsze takie jest. Zależy to oczywiście od postaci f(n), i jest raczej zagadnieniem bardziej charakterystycznym przy rozważaniu szeregów, godny wspomnienia tutaj przypadek ma miejsce gdy: f(n)=n^{\underline{m}}\alpha^{n-m} gdzie x^{\underline{m}}=n(n-1)...(n-m+1) to tzw. potęga ubywająca, można bowiem skorzystać wtedy z tożsamości: (\alpha^n)^{(m)}=n^{\underline{m}}\alpha^{n-m}.

Przykład 1.
x_n=2x_{n-1}+1, \ x_1=1, \ n>1

Rozwiązanie:    


Przykład 2.
x_n=x_{n-1}+\frac{1}{n(n-1)}, \ x_1=0, \ n>1

Rozwiązanie:    


Przykład 3.
x_n=-6x_{n-1}-9x_{x-2}+3^n, \ x_1=-3, \ x_2=36, \ n>2

Rozwiązanie:    


Przykład 4.
x_n=2ix_{n-1}+x_{n-2}+2n, \ x_1=1, \ x_2=i, \ n>2

Rozwiązanie:    


4. Nieliniowe równania rekurencyjne są dużo bardziej różnorodne toteż bardzo trudno wskazać uniwersalne metody ich rozwiązywania. Zajmiemy się jednak analizą wybranych równań tego typu.

(a) \ \ \ \ x_n=\alpha x_{n-1}^{\beta}

gdzie: \alpha,\beta >0, \ x_1>0, \ n>1. Równanie to sprowadza się przez obustronne zlogarytmowanie i podstawienie z_n=\ln x_n do liniowego:

(a') \ \ \ \ z_n= \beta z_{n-1}+ \ln \alpha.

(b) \ \ \ \ \alpha x_nx_{n+1}+\beta x_{n+1}+ \gamma=0

gdzie: n \ge 1, \ \alpha, \ \beta, \ \gamma \in \CC, równanie to także sprowadza się do liniowego tym razem podstawieniem x_n=\frac{z_n}{z_{n+1}} przy założeniu że \forall_{n \in N_+}z_n \neq 0. Otrzymamy:

(b') \ \ \ \ \alpha z_n+ \beta z_{n+1}+ \gamma z_{n+2}=0.

Przy pomocy tego równania w prosty sposób otrzymujemy zwartą postać n-tego reduktu ułamka łańcuchowego [0; \ a, \ a, \ ... ] gdyż redukt ten zadany jest równaniem:

x_n=\frac{1}{a+x_{n-1}}, \ x_1=0, \ a \in N_+, \ n>1.

(c) \ \ \ \ x_n^l=a_1x_{n-1}^l+a_2x_{n-2}^l+...+a_kx_{n-k} + f(n)

gdzie: n>k, l \in N_+ \ \forall_{i \in I_k}a_i \in \CC a f(n) jest funkcją zmiennej n. Stosuje się tutaj podstawienie x_n^k=z_n (jest ono uprawomocnione o ile: \forall_{n \in N_+}x_n \ge 0 albo k jest nieparzyste) aby otrzymać:

(c') \ \ \ \ z_n=a_1z_{n-1}+a_2z_{n-2}+...+a_kz_{n-k}+f(n).

(d) \ \ \ \ x_n^{l_n}=\alpha x_{n-1}^{l_{n-1}}x_{n-2}^{l_{n-2}}...x_{n-k}^{l_{n-k}}

gdzie: n>k, \ \alpha >0, \ \forall_{i \in \left\{0,1,...,k \right\}}l_{n-i} \in R_+, \ \forall_{n \in N_+}x_n>0. Na podstawie (a) można się domyślić że należy tutaj obustronnie zlogarytmować i zastosować podstawienie z_n=\ln x_n aby otrzymać:

(d') \ \ \ \ l_nz_n=l_{n-1}z_{n-1}+l_{n-2}z_{n-2}+...+l_{n-k}z_{n-k} + \ln \alpha.
Góra
Instytut Matematyczny, Uniwersytet Wrocławski
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 rownania rekurencyjne  doniczek  8
 Równania rekurencyjne  kamil.jack  0
 równania rekurencyjne - zadanie 2  Ja_89  4
 równania rekurencyjne - zadanie 3  Suzi86  3
 równania rekurencyjne - zadanie 4  rotka  3
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com