Równanie rekurencyjne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Równanie rekurencyjnerównanie, które definiuje ciąg w sposób rekurencyjny.

Rozwiązanie rekurencji[edytuj]

Jest to postać jawna (iteracyjna) równania rekurencyjnego opisującego daną rekursję.

W większości przypadków, przy zastosowaniu odpowiednio zaawansowanego aparatu algebraicznego można uzyskać dokładne rozwiązanie równania/nierówności rekurencyjnej, często są to jednak metody nieefektywne lub numerycznie niestabilne. Zazwyczaj zadowalające jest rozwiązanie asymptotyczne.

Przykład[edytuj]

Przykładem równania rekurencyjnego liniowego jednorodnego jest równanie postaci

gdzie dane jest .

Załóżmy, że ma ono rozwiązanie postaci . Podstawiając otrzymujemy:

Dzieląc przez ,

.

Równanie to nazywamy równaniem charakterystycznym równania rekurencyjnego. W tym przypadku jest to równanie kwadratowe.

Jeżeli nie ma ono pierwiastków podwójnych, wówczas

Jeżeli natomiast równanie charakterystyczne ma pierwiastek podwójny, to

C i D są dowolnymi stałymi a i są pierwiastkami równania charakterystycznego. Jeżeli dane jest i wówczas można łatwo ułożyć układ równań i otrzymać ich wartość.

Przykład (ciąg Fibonacciego)[edytuj]

Następujący przykład jest rozwiązaniem ciągu Fibonacciego:

Warunki początkowe:

Równanie charakterystyczne ma następującą postać:

.

Pierwiastki tego równania są następujące:

.

Pierwiastki są różne, zatem:

Korzystając z warunków początkowych układamy układ równań:

Z rozwiązania tego układu wynika:

.

Co po podstawieniu i do wzoru na otrzymujemy tzw. wzór Bineta:

Zobacz też[edytuj]