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

f

= G

+

( f , f ,..., f

(1)

n k

n

n 1

−

n+ k − )

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.

f

= a f

+ a f

+ ... + a f + b

(2)

n+ k

1 n+ k 1

−

2 n+ l −2

k

n

n

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: f = ϕ( ,

n f , f ,..., f

(3)

n

1

2

k )

gdzie f , f ,..., f oznaczają warunki początkowe równania (1). ZauwaŜmy, Ŝe rozwiązanie równania w 1

2

k

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 f , f ,..., f ).Wówczas takie rozwiązanie ogólne równania rekurencyjnego ma tyle stałych dowolnych, ile 1

2

k

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 f

= a f

+ a f

+ ... + a f

(4)

n+ k

1 n+ k 1

−

2 n+ k −2

k

n

w którym a , a ,..., a są współczynnikami rzeczywistymi niezaleŜnymi od n, przy czym a 1

2

k

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 f , f ,..., f .

1

2

k

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)

k

k 1

−

k −2

= z − a z − a z

−... − a z − a

(5)

1

2

k 1

−

k

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 z , z ,..., z , r ≤ k oznaczają róŜne pierwiastki charakterystyczne o krotnościach równych 1

2

r

r

odpowiednio v , v ,..., v tak, Ŝe ∑ v = .

k Wówczas

1

2

r

i

i 1

=

r

p ( z) = ∏( z − z

(7)

i ) vi

i 1

=

Ogólnym rozwią zaniem równania (4) o współczynnikach rzeczywistych a , a ,..., a niezaleŜnych od n oraz 1

2

k

ak ≠ 0 jest

r

v 1

−

i

n

m

f = ∑ z ∑ C n

(8)

n

s

sm

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

f = ∑ z C

(9)

n

s

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 f , f ,..., f naleŜy 1

2

k

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

v 1

−

v

1

−

v

1

−

1

2

r

z ∑ C + z ∑ C + ... + z ∑ C = f 1

1 m

2

2 m

r

1 m

1

m=0

m=0

m=0

v 1

−

v

1

−

v

1

−

1

2

r

2

m

2

m

2

z ∑ C 2 + z ∑ C 2 + ... + z ∑ C 2 m = f 1

1 m

2

2 m

r

rm

2

(10)

m=0

m=0

m=0

.............................................................................

v 1

−

v

1

−

v

1

−

1

r

k

m

z ∑

2

C k + z k

m

∑ C k +... k

m

+ z ∑ C k = f

1

1 m

2

2 m

r

rm

k

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 f

= a f

+ a f

+ ...+ a f + b

(11)

n+ k

1 n+ k 1

−

2 n+ k −2

k

n

W którym a , a ,..., a , b są współczynnikami rzeczywistymi niezaleŜnymi od n, przy czym a 1

2

k

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 f , f ,..., f .

1

2

k

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ć

f

= a f

+ a f

+ ... + a f

(12)

n+ k

1 n+ k 1

−

2 n+ k −2

k

n

Wielomianem charakterystycznym równania uzupełniającego jest

p ( z)

k

k 1

−

k −2

= z − a z − a z

−... − a z − a

(13)

1

2

k 1

−

k

Napiszmy teraz (12) zastępując n → n+1

f

= a f

+ a f

+ ... + a f

+ a f + b

(14)

n+ k 1

+

1 n+ k

2 n+ k 1

−

k 1

− n+2

k

n 1

+

Odejmując stronami (11) i (14) otrzymamy równanie jednorodne rzędu k+1

f

− 1+ a f

+ a − a f

+ ... + a − a f + a f = 0

(15)

n+ k 1

+

(

1)

n+ k

( 1 2) n+ k 1−

( k 1− k) n 1+ k n

o równaniu charakterystycznym

k 1

z + − (1+ a ) k

z + ( a − a ) k 1

z − + ... + a

− a z + a = 0

(16)

1

1

2

( k 1− k)

k

Ostatnie równanie moŜna zapisać jako

p ( z)( z − )

1 = 0

(17)

Z drugiej strony wydzielając czynnik związany z ewentualnym pierwiastkiem z = 1 i wielomianu charakterystycznego

α

p ( z) = ( z − )

1 ϕ( z)

(18)

gdzie ϕ( )

1 ≠ 0 otrzymujemy

α+

p ( z)( z − ) = ( z − ) 1

1

1

ϕ( z)

(19)

Wówczas rozwiązanie ogólne równania (11) jest postaci

bnα

f = g +

n

n

ϕ( )

1 α

(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

f

− 6 f

+11 f − 6 f = 0

n+3

n+2

n 1

+

n

przy warunkach początkowych f = 0, f = 1, f = 0.

1

2

3

ROZWIĄZANIE

Równanie charakterystyczne jest postaci

3

2

z − 6 z +11 z − 6 = 0

Pierwiastki tego równania moŜna znaleźć korzystając z tw. Bezou’ta zauwaŜając, Ŝe z − 2

dzieli bez reszty wielomian 3

2

z − 6 z +11 z − 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

f = C + C 2 n + C 3 n

n

1

2

3

Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba jeszcze

rozwiązać układ równań liniowych względem C , C , C odpowiadający układowi 1

2

3

C + 2 C + 3 C = 0

1

2

3

C + 4 C + 9 C = 1

1

2

3

C + 8 C + 27 C = 0

1

2

3

St

5

1

ąd otrzymujemy C = − , C = 2, C = − . Podstawiając te wartości do wzoru na 1

2

3

2

2

rozwiązanie ogólne uzyskujemy rozwiązanie szczególne postaci

+

5

n 1

1

f = − + 2

− ⋅3 n

n

2

2

2)

Znaleźć rozwiązanie równania rekurencyjnego

f

= f

+ f − f

n+3

n+2

n 1

+

n

przy warunkach początkowych f = 1, f = 2, f = 3.

1

2

3

ROZWIĄZANIE

Równanie charakterystyczne jest postaci

3

2

z − z − z +1 = 0

czyli

2

( z − )

1 ( z + )

1 = 0

Stąd pierwiastkami charakterystycznymi są

z = 1 o krotności α = 2

1

1

z = −1 o krotności α =

1

2

2

Rozwiązanie ogólne równania rekurencyjnego ma więc postać

n

f = C + C n + C (− )

1

n

10

11

20

Współczynniki C , C , C

wyznaczmy z układu równań

10

11

20

C + C − C

=1

10

11

20

C + 2 C + C

= 2

10

11

20

C + 3 C − C

= 3

10

11

20

Dostajemy

C

= C = 0, C =1,

10

20

11

co prowadzi di rozwiązania szczególnego

f = .

n

n

3)

Znaleźć rozwiązanie równania rekurencyjnego

f

+ 4 f + 3 f = 0

n+2

n 1

+

n

przy warunkach początkowych f = −1, f = 5

1

2

ROZWIĄZANIE

Równanie charakterystyczne jest postaci

2

z + 4 z + 3 = 0

Stąd pierwiastkami charakterystycznymi są

z = −3 o krotności α = 1

1

1

z = −1 o krotności α =

1

2

2

Wobec tego rozwiązaniem ogólnym danego równania rekurencyjnego według wzoru (9) jest

n

n

f = (− )

3 C + (− )

1 C

n

1

2

Dla znalezienia rozwiązani szczególnego o danych warunkach początkowych trzeba jeszcze

rozwiązać układ równań liniowych względem C oraz C odpowiadający układowi

1

2

−3 C − C = −1

1

2

9 C + C =

5

1

2

St

2

ąd otrzymujemy C =

, C = −1. Podstawiając te wartości do wzoru na

rozwiązanie ogólne

1

2

3

uzyskujemy rozwiązanie szczególne postaci

n 1

−

n+

f = 2 ⋅ (− )

3

+ (− ) 1

1

n

4)

Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego

f

+ 4 f + 3 f = 5

n+2

n 1

+

n

przy warunkach początkowych f = −1, f = 5

1

2

ROZWIĄZANIE

Rozwiązanie równania uzupełnionego juŜ policzyliśmy

n 1

−

n+

g = 2 ⋅ (− )

3

+ (− ) 1

1

n

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)

n 1

−

n+

f = ⋅ (− )

+ (− ) 1 5

2

3

1

+

n

8

5)

Znaleźć rozwiązanie równania rekurencyjnego niejednorodnego

f

− 3 f

+ 3 f − f = 5

n+3

n+2

n 1

+

n

przy warunkach początkowych f = 1, f = 0, f = −1.

1

2

3

ROZWIĄZANIE

Równanie charakterystyczne równania uzupełniającego jest

( z − )3

1 = 0

Stąd z = 1 o krotności α = 3

1

1

Wobec tego rozwiązaniem ogólnym danego równania według wzoru (9) przy uwzględnieniu (2) (ϕ( z) =

p ( z) = ( z − )3

1 bo

1 ⋅1, b = )

5 jest

3

2

5 n

f = C + C n + C n +

n

1

2

3

3!

Dla spełnienia warunków początkowych musi być

1

C + C + C =

1

2

3

6

20

C + 2 C + 4 C = −

1

2

3

3

47

C + 3 C + 9 C = −

1

2

3

2

Rozwi

49

ązaniem tego układu są C = 3

− , C =

, C = −5. Zatem rozwiązaniem równania rekurencyjnego

1

2

3

6

niejednorodnego spełniającego podane warunki początkowe jest

49

2

5 3

f = −3 +

n − 5 n + n

n

6

6

ROZWIĄZAĆ

1)

a = −6 a

− 9 a z warunkami początkowymi a =1, a = 9

− .

n

n 1

−

n−2

0

1

2)

a

= a + a z warunkami początkowymi a = 0, a = 1.

n+2

n 1

+

n

0

1

3)

a

= 5 a + 6 a z warunkami początkowymi a =1, a = 4

− .

n+2

n 1

+

n

0

1

4)

a = 3 a

− 2 a z warunkami początkowymi a = 2, a = 3.

n

n 1

−

n−2

1

2

5)

f = f

+ 6 f

z warunkami początkowymi f = 3, f = 4.

n

n 1

−

n−2

0

1

6)

f = 3 f

+ 4 f

−12 f

z warunkami początkowymi f = 1, f = 2, f = 3.

n

n 1

−

n−2

n−3

0

1

2

7)

f = 2 f

− f

z warunkami początkowymi f = 1, f = 1, f = 2, f = 2.

n

n−2

n−4

0

1

2

3

ODPOWIEDZI

n

1)

a = (− )

3 (1+ 2 n)

n

n

n





+

−

2)

1

a =



−

n



5 (1

5



) (1 5

2

2

) 

n

3)

a = (− ) 10

3

1 ⋅

− ⋅6 n

n

7

7

−

4)

n 1

a = 2

+1

n

n

5)

f = ( 2

− ) + 2⋅3 n

n

n

6)

f = 2 nC + (−2) C + 3 nC

n

1

2

3

n

n

7)

f = C + C n + (− )

1

C

+ C n

3

1

1

f =

+ n + ⋅(− )

1

n

10

11

( 20

21 )

n

4

2

4