Równanie rekurencyjne


Równanie rekurencyjne w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

Spis treści

Rozwiązanie rekurencji | 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 kod

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

a n = A a n 1 + B a n 2 , {\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2},}

gdzie dane jest A , B . {\displaystyle A,B.}

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

r n = A r n 1 + B r n 2 . {\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}.}

Dzieląc przez r n 2 {\displaystyle r^{n-2}} :

r 2 = A r + B , {\displaystyle r^{2}=Ar+B,} r 2 A r B = 0. {\displaystyle 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 = C r 1 n + D r 2 n . {\displaystyle a_{n}=Cr_{1}^{n}+Dr_{2}^{n}.}

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

a n = ( C + D n ) r 1 n . {\displaystyle a_{n}=(C+Dn)r_{1}^{n}.}

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

Przykład (ciąg Fibonacciego) | edytuj kod

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

a n = a n 1 + a n 2 . {\displaystyle a_{n}=a_{n-1}+a_{n-2}.}

Warunki początkowe:

a 0 = 0 , a 1 = 1. {\displaystyle a_{0}=0,\quad a_{1}=1.}

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

r 2 r 1 = 0. {\displaystyle r^{2}-r-1=0.}

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

r 1 = 1 + 5 2 ; r 2 = 1 5 2 . {\displaystyle r_{1}={\frac {1+{\sqrt {5}}}{2}};\quad r_{2}={\frac {1-{\sqrt {5}}}{2}}.}

Pierwiastki są różne, zatem:

a n = A r 1 n + B r 2 n . {\displaystyle a_{n}=Ar_{1}^{n}+Br_{2}^{n}.}

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

{ a 0 = 0 : A + B = 0 , a 1 = 1 : A r 1 + B r 2 = 1. {\displaystyle {\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 5 ; B = 1 5 . {\displaystyle A={\frac {1}{\sqrt {5}}};\quad B=-{\frac {1}{\sqrt {5}}}.}

Co po podstawieniu A {\displaystyle A} i B {\displaystyle B} do wzoru na a n {\displaystyle a_{n}} otrzymujemy tzw. wzór Bineta:

a n = 1 5 ( 1 + 5 2 ) n 1 5 ( 1 5 2 ) n . {\displaystyle 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 kod

Na podstawie artykułu: "Równanie rekurencyjne" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy