Równanie rekurencyjne – Wikipedia, wolna encyklopedia
Równanie rekurencyjne – równanie, które definiuje ciąg w sposób rekurencyjny.
Rozwiązanie rekurencji
[edytuj | edytuj kod]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 | edytuj kod]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
i 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 | edytuj kod]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: