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
(
)
1
1
,
,...,
n k
n
n
n k
f
G f
f
f
+
−
+ −
=
(1)
gdzie
G jest daną funkcją f
n
, f
n+1
,…,
f
n+k-1
, przy czym
f
n
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.
1
1
2
2
...
n k
n k
n l
k
n
n
f
a f
a f
a f
b
+
+ −
+ −
=
+
+ +
+
(2)
równanie jest liniowe, przy czym, gdy współczynniki rzeczywiste a
i
, b
i
(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) b
n
= 0 lub b
n
≠
0 równanie rekurencyjne (2) jest
jednorodne lub niejednorodne.
Dla jednoznacznego wyznaczenia funkcji f
n
, 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:
(
)
1
2
,
,
,...,
n
k
f
n f
f
f
= ϕ
(3)
gdzie
1
2
,
,...,
k
f
f
f
oznaczają warunki początkowe równania (1). ZauwaŜmy, Ŝe rozwiązanie równania w
postaci (3) pozwala obliczyć f
n
dla dowolnego n, bez konieczności wyznaczania wszystkich f
i
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
1
2
,
,...,
).
k
f
f
f
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ądź na znalezieniu rozwiązania ogólnego,
bądź 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
1
1
2
2
...
n k
n k
n k
k
n
f
a f
a f
a f
+
+ −
+ −
=
+
+ +
(4)
w którym
1
2
,
,...,
k
a a
a są współczynnikami rzeczywistymi niezaleŜnymi od n, przy czym a
k
≠
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
1
2
,
,...,
.
k
f
f
f
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 a
i
,
występujące w równaniu (4). Zatem
( )
1
2
1
2
1
...
k
k
k
k
k
p z
z
a z
a z
a
z
a
−
−
−
=
−
−
− −
−
(5)
Równanie
( )
0
p z
=
(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
1
2
,
,..., ,
r
z z
z
r
k
≤
oznaczają róŜne pierwiastki charakterystyczne o krotnościach równych
odpowiednio
1
2
, ,...,
r
v v
v tak, Ŝe
1
.
r
i
i
v
k
=
=
∑
Wówczas
( )
(
)
1
i
r
v
i
i
p z
z
z
=
=
−
∏
(7)
Ogólnym rozwiązaniem równania (4) o współczynnikach rzeczywistych
1
2
,
,...,
k
a a
a niezaleŜnych od n oraz
a
k
≠
0 jest
1
1
0
i
v
r
n
m
n
s
sm
s
m
f
z
C n
−
=
=
=
∑ ∑
(8)
gdzie z
s
(s = 1,
…,r) jest pierwiastkiem charakterystycznym równania o krotności v
i
, C
sm
(s = 1,
…,r;
m
= 0,1,
…,v
i
-1) jest dowolną stałą.
W przypadku gdy wszystkie pierwiastki charakterystyczne z
i
są pojedyncze, tj. równanie (6) ma k
pierwiastków z
i
o krotnościach
v
i
= 1 (i = 1,
…,k), rozwiązanie (8) przyjmuje uproszczoną postać
1
k
n
n
s
s
s
f
z C
=
=
∑
(9)
gdzie C
s
(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
1
2
,
,...,
k
f f
f
naleŜy
najpierw rozwiązać równanie charakterystyczne, zapisać postać ogólną rozwiązania (8) bądź (9) zaleŜnie od
pierwiastków, a następnie rozwiązać układ k równań liniowych względem k niewiadomych, którymi są C
10
,
C
11
,
…, C
r,v
-1
1
2
1
2
1
1
1
1
1
1
2
2
1
1
0
0
0
1
1
1
2
2
2
1
1
2
2
2
0
0
0
1
1
1
0
...
2
2
...
2
.............................................................................
r
r
v
v
v
m
m
r
m
m
m
m
v
v
v
m
m
m
m
m
r
rm
m
m
m
v
k
m
m
m
z
C
z
C
z
C
f
z
C
z
C
z
C
f
z
C k
z
−
−
−
=
=
=
−
−
−
=
=
=
−
=
+
+ +
=
+
+ +
=
+
∑
∑
∑
∑
∑
∑
∑
2
1
1
2
2
0
0
...
r
v
v
k
m
k
m
m
r
rm
k
m
m
C k
z
C k
f
−
−
=
=
+ +
=
∑
∑
(10)
Obliczone wartości wstawiamy do wzoru (8) uzyskując w ten sposób szukane rozwiązanie szczególne
danego równania.
U
WAGA
JeŜeli współczynniki równania charakterystycznego
( )
0
p z
=
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
1
1
2
2
...
n k
n k
n k
k
n
f
a f
a f
a f
b
+
+ −
+ −
=
+
+ +
+
(11)
W którym
1
2
,
,...,
,
k
a a
a b są współczynnikami rzeczywistymi niezaleŜnymi od n, przy czym a
k
≠
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
1
2
,
,...,
.
k
f
f
f
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ć
1
1
2
2
...
n k
n k
n k
k
n
f
a f
a f
a f
+
+ −
+ −
=
+
+ +
(12)
Wielomianem charakterystycznym równania uzupełniającego jest
( )
1
2
1
2
1
...
k
k
k
k
k
p z
z
a z
a z
a
z
a
−
−
−
=
−
−
− −
−
(13)
Napiszmy teraz (12) zastępując n → n+1
1
1
2
1
1
2
1
...
n k
n k
n k
k
n
k
n
f
a f
a f
a
f
a f
b
+ +
+
+ −
−
+
+
=
+
+ +
+
+
(14)
Odejmując stronami (11) i (14) otrzymamy równanie jednorodne rzędu k+1
(
)
(
)
(
)
1
1
1
2
1
1
1
1
...
0
n k
n k
n k
k
k
n
k
n
f
a
f
a
a
f
a
a
f
a f
+ +
+
+ −
−
+
− +
+
−
+ +
−
+
=
(15)
o równaniu charakterystycznym
(
)
(
)
(
)
1
1
1
1
2
1
1
...
0
k
k
k
k
k
k
z
a z
a
a z
a
a
z
a
+
−
−
− +
+
−
+ +
−
+
=
(16)
Ostatnie równanie moŜna zapisać jako
( )(
)
1
0
p z z
− =
(17)
Z drugiej strony wydzielając czynnik związany z ewentualnym pierwiastkiem z = 1
i
wielomianu
charakterystycznego
( ) (
)
( )
1
p z
z
z
α
= −
ϕ
(18)
gdzie
( )
1
0
ϕ ≠
otrzymujemy
( )(
) (
)
( )
1
1
1
p z z
z
z
α+
− = −
ϕ
(19)
Wówczas rozwiązanie ogólne równania (11) jest postaci
( )
1
!
n
n
bn
f
g
α
=
+ ϕ α
(20)
Gdzie g
n
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)
Znaleźć rozwiązanie równania rekurencyjnego
3
2
1
6
11
6
0
n
n
n
n
f
f
f
f
+
+
+
−
+
−
=
przy warunkach początkowych
1
2
3
0,
1,
0.
f
f
f
=
=
=
R
OZWIĄZANIE
Równanie charakterystyczne jest postaci
3
2
6
11
6
0
z
z
z
−
+
− =
Pierwiastki tego równania moŜna znaleźć korzystając z tw. Bezou
’ta zauwaŜając, Ŝe
2
z
−
dzieli bez reszty wielomian
3
2
6
11
6.
z
z
z
−
+
−
Stąd otrzymujemy, Ŝe
(
)(
)
(
)
1
2
3
0
z
z
z
−
−
− =
A zatem pierwiastkami charakterystycznymi są
1,
2,
3, wszystkie jednokrotne.
z
z
z
=
=
=
Wobec tego rozwiązaniem ogólnym
danego równania rekurencyjnego według wzoru (9) jest
1
2
3
2
3
n
n
n
f
C
C
C
=
+
+
Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba
jeszcze
rozwiązać układ równań liniowych względem
1
2
3
,
,
C C C
odpowiadający układowi
1
2
3
1
2
3
1
2
3
2
3
0
4
9
1
8
27
0
C
C
C
C
C
C
C
C
C
+
+
=
+
+
=
+
+
=
Stąd otrzymujemy
1
2
3
5
1
,
2,
.
2
2
C
C
C
= −
=
= −
Podstawiając te wartości do wzoru na
rozwiązanie ogólne uzyskujemy rozwiązanie szczególne postaci
1
5
1
2
3
2
2
n
n
n
f
+
= − +
− ⋅
2)
Znaleźć rozwiązanie równania rekurencyjnego
3
2
1
n
n
n
n
f
f
f
f
+
+
+
=
+
−
przy warunkach początkowych
1
2
3
1,
2,
3.
f
f
f
=
=
=
R
OZWIĄZANIE
Równanie charakterystyczne jest postaci
3
2
1
0
z
z
z
− − + =
czyli
(
) (
)
2
1
1
0
z
z
−
+ =
Stąd pierwiastkami charakterystycznymi są
1
1
2
2
1 o krotności
2
1 o krotności
1
z
z
=
α =
= −
α =
Rozwiązanie ogólne równania rekurencyjnego ma więc postać
( )
10
11
20
1
n
n
f
C
C n C
=
+
+
−
Współczynniki
10
11
20
,
,
C
C C
wyznaczmy z układu równań
10
11
20
10
11
20
10
11
20
1
2
2
3
3
C
C
C
C
C
C
C
C
C
+
−
=
+
+
=
+
−
=
Dostajemy
10
20
11
0,
1,
C
C
C
=
=
=
co prowadzi di rozwiązania szczególnego
.
n
f
n
=
3)
Znaleźć rozwiązanie równania rekurencyjnego
2
1
4
3
0
n
n
n
f
f
f
+
+
+
+
=
przy warunkach początkowych
1
2
1,
5
f
f
= −
=
R
OZWIĄZANIE
Równanie charakterystyczne jest postaci
2
4
3
0
z
z
+ + =
Stąd pierwiastkami charakterystycznymi są
1
1
2
2
3 o krotności
1
1 o krotności
1
z
z
= −
α =
= −
α =
Wobec tego rozwiązaniem ogólnym danego równania rekurencyjnego według wzoru
(9) jest
( )
( )
1
2
3
1
n
n
n
f
C
C
= −
+ −
Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba
jeszcze
rozwiązać układ równań liniowych względem
1
2
oraz
C
C
odpowiadający
układowi
1
2
1
2
3
1
9
5
C
C
C
C
−
−
= −
+
=
Stąd otrzymujemy
1
2
2 ,
1.
3
C
C
=
= −
Podstawiając te wartości do wzoru na
rozwiązanie ogólne
uzyskujemy rozwiązanie szczególne postaci
( )
( )
1
1
2
3
1
n
n
n
f
+
−
= ⋅ −
+ −
4)
Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego
2
1
4
3
5
n
n
n
f
f
f
+
+
+
+
=
przy warunkach początkowych
1
2
1,
5
f
f
= −
=
R
OZWIĄZANIE
Rozwiązanie równania uzupełnionego juŜ policzyliśmy
( )
( )
1
1
2
3
1
n
n
n
g
+
−
= ⋅ −
+ −
Pozostało zauwaŜyć, Ŝe wielomian charakterystyczny równania jednorodnego nie ma
pierwiastka
1
z
=
zatem
0
α =
oraz
( )
( )
z
p z
ϕ
=
i stąd
( )
1
8
ϕ =
oraz
5.
b
=
Podstawiając
do
wzoru (20)
( )
( )
1
1
5
2
3
1
8
n
n
n
f
+
−
= ⋅ −
+ −
+
5)
Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego
3
2
1
3
3
5
n
n
n
n
f
f
f
f
+
+
+
−
+
−
=
przy warunkach początkowych
1
2
3
1,
0,
1.
f
f
f
=
=
= −
R
OZWIĄZANIE
Równanie charakterystyczne równania uzupełniającego jest
(
)
3
1
0
z
−
=
Stąd
1
1
z
=
o krotności
1
3
α =
Wobec tego rozwiązaniem ogólnym danego równania według wzoru (9) przy uwzględnieniu (2)
( )
( ) (
)
(
)
3
1 bo
1
1,
5
z
p z
z
b
ϕ
=
= −
⋅
=
jest
3
2
1
2
3
5
3!
n
n
f
C
C n C n
=
+
+
+
Dla spełnienia warunków początkowych musi być
1
2
3
1
2
3
1
2
3
1
6
20
2
4
3
47
3
9
2
C
C
C
C
C
C
C
C
C
+
+
=
+
+
= −
+
+
= −
Rozwiązaniem tego układu są
1
2
3
49
3,
,
5.
6
C
C
C
= −
=
= −
Zatem rozwiązaniem równania rekurencyjnego
niejednorodnego spełniającego podane warunki początkowe jest
2
3
49
5
3
5
6
6
n
f
n
n
n
= − +
−
+
R
OZWIĄZAĆ
1)
1
2
6
9
n
n
n
a
a
a
−
−
= −
−
z warunkami początkowymi
0
1
1,
9.
a
a
=
= −
2)
2
1
n
n
n
a
a
a
+
+
=
+
z warunkami początkowymi
0
1
0,
1.
a
a
=
=
3)
2
1
5
6
n
n
n
a
a
a
+
+
=
+
z warunkami początkowymi
0
1
1,
4.
a
a
=
= −
4)
1
2
3
2
n
n
n
a
a
a
−
−
=
−
z warunkami początkowymi
1
2
2,
3.
a
a
=
=
5)
1
2
6
n
n
n
f
f
f
−
−
=
+
z warunkami początkowymi
0
1
3,
4.
f
f
=
=
6)
1
2
3
3
4
12
n
n
n
n
f
f
f
f
−
−
−
=
+
−
z warunkami początkowymi
0
1
2
1,
2,
3.
f
f
f
=
=
=
7)
2
4
2
n
n
n
f
f
f
−
−
=
−
z warunkami początkowymi
0
1
2
3
1,
1,
2,
2.
f
f
f
f
=
=
=
=
O
DPOWIEDZI
1)
( ) (
)
3
1 2
n
n
a
n
= −
+
2)
( ) ( )
1
1
5
1
5
2
2
5
n
n
n
a
+
−
=
−
3)
( )
10
3
1
6
7
7
n
n
n
a
= −
⋅
− ⋅
4)
1
2
1
n
n
a
−
=
+
5)
( )
2
2 3
n
n
n
f
= −
+ ⋅
6)
( )
1
2
3
2
2
3
n
n
n
n
f
C
C
C
=
+ −
+
7)
( )
(
)
10
11
20
21
1
n
n
f
C
C n
C
C n
=
+
+ −
+
( )
3
1
1
1
4
2
4
n
n
f
n
= +
+ ⋅ −