Równanie rekurencyjne

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

Rozwiązanie rekurencjiEdytuj

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ładEdytuj

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