Algorytmy rekurencyjne w połączeniu ze strukturami grafowymi doskonale nadają się do reprezentacji wielu
problemów, z którymi mo\
emy spotkać się na co dzień. Analiza efektywności i poprawności rekurencji wraz
umiejętnością prawidłowego jej wykorzystania jest elementem bardzo istotnym w dzisiejszej sztuce programowania.
Rekurencje liniowe
Rozwa\
my następujące równanie rekurencyjne
fn+k = G fn, fn-1,..., fn+k -1 (1)
( )
gdzie G jest daną funkcją fn, fn+1,& , fn+k-1, przy czym fn jest funkcją niewiadomą, określoną na zbiorze liczb
naturalnych. Liczbę k nazywamy rzędem równania rekurencyjnego.
W przypadku gdy G jest funkcją liniową swych argumentów, tj.
fn+k = a1fn+k -1 + a2 fn+l-2 + ... + ak fn + bn (2)
równanie jest liniowe, przy czym, gdy współczynniki rzeczywiste ai, bi (i=1, 2,& , k) nie zale\
Ä… od n, to
równanie (2) jest równaniem rekurencyjnym liniowym o stałych współczynnikach, w p.p. równaniem
rekurencyjnym liniowym o współczynnikach zmiennych.
Ponadto w zale\
ności od tego czy w równaniu (2) bn = 0 lub bn `" 0 równanie rekurencyjne (2) jest
jednorodne lub niejednorodne.
Dla jednoznacznego wyznaczenia funkcji fn, określonej przez równanie rekurencyjne, potrzebne są jej
wartości początkowe, przy czym tyle wartości początkowych, ile wynosi rząd równania rekurencyjnego.
Równanie rekurencyjne (1) jest rozwiązane wtedy, gdy dany jest wzór postaci:
fn = Õ n, f1, f2,..., fk (3)
( )
gdzie f1, f2,..., fk oznaczają warunki początkowe równania (1). Zauwa\
my, \
e rozwiązanie równania w
postaci (3) pozwala obliczyć fn dla dowolnego n, bez konieczności wyznaczania wszystkich fi dla i < n.
Równanie rekurencyjne ma nieskończenie wiele rozwiązań. Mo\
emy je zapisać w postaci ogólnej,
obejmującej wszystkie rozwiązania szczególne danego równania (w zale\
ności od warunków początkowych
f1, f2,..., fk).Wówczas takie rozwiązanie ogólne równania rekurencyjnego ma tyle stałych dowolnych, ile
wynosi jego rzÄ…d.
Podsumowując, rozwiązanie równania rekurencyjnego polega bądz
na znalezieniu rozwiązania ogólnego,
bÄ…dz
w przypadku gdy dane są wartości początkowe równania szukamy rozwiązania szczególnego.
Rozwiązywanie jednorodnych równań rekurencyjnych liniowych o stałych
współczynnikach
Niech będzie dane jednorodne równanie rekurencyjne liniowe rzędu k
fn+k = a1fn+k -1 + a2 fn+k -2 + ... + ak fn (4)
w którym a1,a2,...,ak są współczynnikami rzeczywistymi niezale\
nymi od n, przy czym ak `" 0. Jest to
równanie rzędu k, a więc dla jego jednoznacznego rozwiązania potrzeba, aby były dane wartości początkowe
f1, f2,..., fk.
Dla rozwiązania równania (4) wprowadza się pewną funkcję pomocniczą p(z) zwaną wielomianem
charakterystycznym równania. Funkcja p(z) zmiennej zespolonej z jest określona jako wielomian tego
samego stopnia k co dane równanie (4) jest rzędu, i którego współczynnikami są te same współczynniki ai,
występujące w równaniu (4). Zatem
p(z) = zk - a1zk -1 - a2zk -2 - ... - ak -1z - ak (5)
Równanie
p(z) = 0 (6)
z kolei nazywamy równaniem charakterystycznym, a jego pierwiastki (rzeczywiste lub zespolone, których
liczba wraz z ich krotnościami wynosi k)  pierwiastkami charakterystycznymi.
Niech z1, z2,..., zr, r d" k oznaczają ró\
ne pierwiastki charakterystyczne o krotnościach równych
r
odpowiednio v1,v2,...,vr tak, \
e = k. Wówczas
"v
i
i=1
r
p(z) = - zi vi (7)
"(z )
i=1
Ogólnym rozwiązaniem równania (4) o współczynnikach rzeczywistych a1,a2,...,ak niezale\
nych od n oraz
ak `" 0 jest
vi
r -1
n
fn = nm (8)
"zs "Csm
s=1 m=0
gdzie zs (s = 1, & ,r) jest pierwiastkiem charakterystycznym równania o krotności vi, Csm (s = 1,& ,r;
m = 0,1,& ,vi-1) jest dowolną stałą.
W przypadku gdy wszystkie pierwiastki charakterystyczne zi są pojedyncze, tj. równanie (6) ma k
pierwiastków zi o krotnościach vi = 1 (i = 1,& ,k), rozwiązanie (8) przyjmuje uproszczoną postać
k
n
fn = Cs (9)
"z
s
s=1
gdzie Cs (s = 1,& ,k) są dowolnymi stałymi wyznaczanymi z warunków początkowych.
Dla otrzymania rozwiązania szczególnego wzoru (4) o warunkach początkowych f1, f2,..., fk nale\
y
najpierw rozwiązać równanie charakterystyczne, zapisać postać ogólną rozwiązania (8) bądz
(9) zale\
nie od
pierwiastków, a następnie rozwiązać układ k równań liniowych względem k niewiadomych, którymi są C10,
C11, & , Cr,v-1
v1-1 v2-1 vr -1
z1 + z2 + ... + zr = f1
"C1m "C2m "C1m
m=0 m=0 m=0
v1-1 v2-1 vr -1
2 2 2
z1 2m + z2 2m + ... + zr 2m = f2
"C1m "C2m "Crm
(10)
m=0 m=0 m=0
.............................................................................
v1-1 v2-1 vr -1
k m k m k m
z1 k + z2 k + ... + zr k = fk
"C1m "C2m "Crm
m=0 m=0 m=0
Obliczone wartości wstawiamy do wzoru (8) uzyskując w ten sposób szukane rozwiązanie szczególne
danego równania.
UWAGA Je\
eli współczynniki równania charakterystycznego p(z) = 0 są liczbami rzeczywistymi, to
równanie, jeśli ma pierwiastki zespolone, to są one parami sprzę\
one.
Rozwiązywanie niejednorodnych równań rekurencyjnych liniowych o stałych
współczynnikach
Niech będzie dane niejednorodne równanie rekurencyjne liniowe rzędu k
fn+k = a1fn+k -1 + a2 fn+k -2 + ... + ak fn + b (11)
W którym a1,a2,...,ak,b są współczynnikami rzeczywistymi niezale\
nymi od n, przy czym ak `" 0 oraz b `" 0.
Jest to równanie rzędu k, a więc dla jego jednoznacznego rozwiązania potrzeba, aby były dane wartości
poczÄ…tkowe f1, f2,..., fk.
Równanie jednorodne, które otrzymujemy z danego równania (4) przez przyjęcie b = 0, nosi nazwę równania
uzupełniającego to równanie i ma postać
fn+k = a1fn+k -1 + a2 fn+k -2 + ... + ak fn (12)
Wielomianem charakterystycznym równania uzupełniającego jest
p(z) = zk - a1zk -1 - a2zk -2 - ... - ak -1z - ak (13)
Napiszmy teraz (12) zastępując n n+1
fn+k +1 = a1 fn+k + a2 fn+k -1 + ... + ak -1 fn+2 + ak fn+1 + b (14)
Odejmując stronami (11) i (14) otrzymamy równanie jednorodne rzędu k+1
fn+k +1 - ( ) ( - a2 fn+k -1 + ... + ak -1 - ak fn+1 + ak fn = 0 (15)
1+ a1 fn+k + a1 ( )
)
o równaniu charakterystycznym
zk +1 - ( ) ( - a2 zk -1 + ... + ak -1 - ak z + ak = 0 (16)
1+ a1 zk + a1 ( )
)
Ostatnie równanie mo\
na zapisać jako
p(z)(z -1) = 0 (17)
i
Z drugiej strony wydzielajÄ…c czynnik zwiÄ…zany z ewentualnym pierwiastkiem z = 1 wielomianu
charakterystycznego
(
p(z) = z -1)Ä… Õ(z) (18)
gdzie Õ(1) `" 0 otrzymujemy
(
p(z)(z -1) = z -1)Ä…+1Õ(z) (19)
Wówczas rozwiązanie ogólne równania (11) jest postaci
bnÄ…
fn = gn + (20)
Õ(1)Ä…!
Gdzie gn jest rozwiÄ…zaniem ogólnym równania uzupeÅ‚niajÄ…cego (12), Õ(z) zaÅ› oraz Ä… jak we wzorze (18).
i
Jeśli wielomian charakterystyczny p(z) ma pierwiastek z = 1, to a jest równe jego krotności.
ĆWICZENIA
1) Znalez
ć rozwiązanie równania rekurencyjnego
fn+3 - 6 fn+2 +11fn+1 - 6 fn = 0
przy warunkach poczÄ…tkowych f1 = 0, f2 =1, f3 = 0.
ROZWI
ZANIE
Równanie charakterystyczne jest postaci
z3 - 6z2 +11z - 6 = 0
Pierwiastki tego równania mo\
na znalez
ć korzystając z tw. Bezou ta zauwa\
ajÄ…c, \
e z - 2
dzieli bez reszty wielomian z3 - 6z2 +11z - 6. StÄ…d otrzymujemy, \
e
(
z -1)(z - 2)(z - 3) = 0
A zatem pierwiastkami charakterystycznymi sÄ… z = 1, z = 2, z = 3, wszystkie jednokrotne.
Wobec tego rozwiązaniem ogólnym danego równania rekurencyjnego według wzoru (9) jest
fn = C1 + C22n + C33n
Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba jeszcze
rozwiązać układ równań liniowych względem C1,C2,C3 odpowiadający układowi
C1 + 2C2 + 3C3 = 0
C1 + 4C2 + 9C3 = 1
C1 + 8C2 + 27C3 = 0
5 1
Stąd otrzymujemy C1 = - ,C2 = 2,C3 = - . Podstawiając te wartości do wzoru na
2 2
rozwiązanie ogólne uzyskujemy rozwiązanie szczególne postaci
5 1
fn = - + 2n+1 - Å"3n
2 2
2) Znalez
ć rozwiązanie równania rekurencyjnego
fn+3 = fn+2 + fn+1 - fn
przy warunkach poczÄ…tkowych f1 = 1, f2 = 2, f3 = 3.
ROZWI
ZANIE
Równanie charakterystyczne jest postaci
z3 - z2 - z +1 = 0
czyli
(
z -1)2(z +1) = 0
StÄ…d pierwiastkami charakterystycznymi sÄ…
z1 = 1 o krotności ą1 = 2
z2 = -1 o krotności ą2 = 1
Rozwiązanie ogólne równania rekurencyjnego ma więc postać
fn = C10 + C11n + C20 (-1)n
Współczynniki C10,C11,C20 wyznaczmy z układu równań
C10 + C11 - C20 = 1
C10 + 2C11 + C20 = 2
C10 + 3C11 - C20 = 3
Dostajemy
C10 = C20 = 0,C11 = 1,
co prowadzi di rozwiązania szczególnego
fn = n.
3) Znalez
ć rozwiązanie równania rekurencyjnego
 fn+2 + 4 fn+1 + 3 fn = 0
przy warunkach poczÄ…tkowych f1 = -1, f2 = 5
ROZWI
ZANIE
Równanie charakterystyczne jest postaci
z2 + 4z + 3 = 0
StÄ…d pierwiastkami charakterystycznymi sÄ…
z1 = -3 o krotności ą1 = 1
z2 = -1 o krotności ą2 = 1
Wobec tego rozwiązaniem ogólnym danego równania rekurencyjnego według wzoru (9) jest
( (
fn = -3)nC1 + -1)n C2
Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba jeszcze
rozwiązać układ równań liniowych względem C1 oraz C2 odpowiadający układowi
-3 C1 - C2 = -1
9 C1 + C2 = 5
2
Stąd otrzymujemy C1 = ,C2 = -1. Podstawiając te wartości do wzoru na rozwiązanie ogólne
3
uzyskujemy rozwiązanie szczególne postaci
(
fn = 2Å"(-3)n-1 + -1)n+1
4) Znalez
ć rozwiązanie równania rekurencyjnego niejednorodnego
fn+2 + 4 fn+1 + 3 fn = 5
przy warunkach poczÄ…tkowych f1 = -1, f2 = 5
ROZWI
ZANIE
Rozwiązanie równania uzupełnionego ju\
policzyliśmy
(
gn = 2Å"(-3)n-1 + -1)n+1
Pozostało zauwa\
yć, \
e wielomian charakterystyczny równania jednorodnego nie ma
pierwiastka z = 1 zatem Ä… = 0 oraz Õ(z) = p(z) i stÄ…d Õ(1) = 8 oraz b = 5. PodstawiajÄ…c do
wzoru (20)
5
(
fn = 2Å"(-3)n-1 + -1)n+1 +
8
5) Znalez
ć rozwiązanie równania rekurencyjnego niejednorodnego
fn+3 - 3 fn+2 + 3 fn+1 - fn = 5
przy warunkach poczÄ…tkowych f1 = 1, f2 = 0, f3 = -1.
ROZWI
ZANIE
Równanie charakterystyczne równania uzupełniającego jest
(
z -1)3 = 0
Stąd z1 = 1 o krotności ą1 = 3
Wobec tego rozwiązaniem ogólnym danego równania według wzoru (9) przy uwzględnieniu (2)
(
( )
Õ(z) = 1 bo p(z) = z -1)3 Å"1, b = 5 jest
5n3
fn = C1 + C2n + C3n2 +
3!
Dla spełnienia warunków początkowych musi być
1
C1 + C2 + C3 =
6
20
C1 + 2C2 + 4C3 = -
3
47
C1 + 3C2 + 9C3 = -
2
49
Rozwiązaniem tego układu są C1 = -3,C2 = ,C3 = -5. Zatem rozwiązaniem równania rekurencyjnego
6
niejednorodnego spełniającego podane warunki początkowe jest
49 5
fn = -3 + n - 5n2 + n3
6 6
ROZWI
ZAĆ
1) an = -6an-1 - 9an-2 z warunkami poczÄ…tkowymi a0 = 1, a1 = -9.
2) an+2 = an+1 + an z warunkami poczÄ…tkowymi a0 = 0, a1 = 1.
3) an+2 = 5an+1 + 6an z warunkami poczÄ…tkowymi a0 = 1, a1 = -4.
4) an = 3an-1 - 2an-2 z warunkami poczÄ…tkowymi a1 = 2, a2 = 3.
5) fn = fn-1 + 6 fn-2 z warunkami poczÄ…tkowymi f0 = 3, f1 = 4.
6) fn = 3 fn-1 + 4 fn-2 -12 fn-3 z warunkami poczÄ…tkowymi f0 = 1, f1 = 2, f2 = 3.
7) fn = 2 fn-2 - fn-4 z warunkami poczÄ…tkowymi f0 = 1, f1 = 1, f2 = 2, f3 = 2.
ODPOWIEDZI
(
1) an = -3)n (1+ 2n)
n n
îÅ‚ Å‚Å‚
1 1+ 5 1- 5
2) an = -
( ) ( )
ïÅ‚ śł
ðÅ‚ 2 2 ûÅ‚
5
3
(
3) an = -1)n Å"10 - Å"6n
7 7
4) an = 2n-1 +1
(
5) fn = -2)n + 2Å"3n
(
6) fn = 2nC1 + -2)n C2 + 3nC3
3 1 1
(
7) fn = C10 + C11n + -1)n C20 + C21n fn = + n + Å"(-1)n
( )
4 2 4