Równanie rekurencyjne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Równanie rekurencyjneró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

a_{n}=Aa_{n-1}+Ba_{n-2} \,

gdzie dane jest A,B.

Załóżmy, że ma ono rozwiązanie postaci a_{n}=r^{n}\;. Podstawiając otrzymujemy:

r^n=Ar^{n-1}+Br^{n-2}.\,

Dzieląc przez r^{n-2}\;,

r^2=Ar+B\;
r^2-Ar-B=0\;.

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

a_n = Cr_1^n+Dr_2^n \,

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

a_n = (C+Dn)r_1^n \,

C i D są dowolnymi stałymi a r_1 i r_2 są pierwiastkami równania charakterystycznego. Jeżeli dane jest a_{1} i a_{2} 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:

a_{n}=a_{n-1}+a_{n-2} \,

Warunki początkowe:

a_{0}=0, a_{1}=1\,

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

r^2-r-1=0\;.

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

r_1={1+\sqrt{5}\over 2}; r_2={1-\sqrt{5}\over 2}.

Pierwiastki są różne, zatem:

a_n = Ar_1^n+Br_2^n \,

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

\begin{cases} a_{0} = 0: A + B = 0, \\ a_{1} = 1: Ar_1 + Br_2 = 1 \end{cases}

Z rozwiązania tego układu wynika:

A={1\over \sqrt{5}}; B=-{1\over \sqrt{5}}.

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

a_n = \frac{1}{\sqrt 5}\left(\frac{1 + \sqrt 5}{2}\right)^n - \frac{1}{\sqrt 5}\left(\frac{1 - \sqrt 5}{2}\right)^n

Zobacz też[edytuj | edytuj kod]