ВУЗ:
Составители:
Рубрика:
Рекуррентные соотношения
48
() () () ()
1
1
11
1
2
3
1
12
1
11
−−−−−
====
ns
s
nnn
rnnf,,rnnf,nrnf,rnf
Κ
рассматриваемого рекуррентного соотношения. В общем решении этому
корню соответствует часть
[
]
12
321
1
1
−−
++++
s
s
n
nCnCnCCr
Κ
.
Составляя такие выражения для всех корней и складывая их, получаем общее
решение.
Например, решим рекуррентное соотношение
()()()()()
nfnfnfnfnf
81426354
++−+−+=+
.
Характеристическое уравнение имеет здесь вид
08465
234
=−++−
rrrr
.
Решая его, получаем корни
.r,r,r,r
1222
4321
−====
Значит, общее решение нашего соотношения имеет следующий вид:
()
[
]
()
1
4
2
321
1
12
−
−
−+++=
n
n
CnCnCCnf
.
Задачи для самостоятельного решения
1. Написать первые пять членов решения рекуррентного соотношения
()()()
nfnfnf
3122
−+=+
, удовлетворяющего заданным начальным ус-
ловиям:
a)
()
()
=
=
12
01
f
f
b)
()
()
=
−=
12
11
f
f
c)
()
()
=
=
02
31
f
f
d)
()
()
=
=
12
21
f
f
e)
()
()
=
=
82
21
f
f
2. Проверить, являются ли данные функции решениями данных рекуррент-
ных соотношений:
a)
()()()
() () ()
.n,nn,n
;nfnfnf
n
31225
122
321
=+=⋅=
−+=+
ϕϕϕ
b)
()()()
() () ()
71352
3142
321
=−⋅==
−+=+
n,n,nn
;nfnfnf
n
ϕϕϕ
3. Найти общее решение рекуррентных соотношений:
a)
012172
=
==
=+
++
++
++
+−
−−
−+
++
+
)n(f)n(f)n(f
;
b)
010132
=
==
=−
−−
−+
++
++
++
++
++
+
)n(f)n(f)n(f
;
c)
013142
=
==
=+
++
++
++
+−
−−
−+
++
+
)n(f)n(f)n(f
;
d)
092
=
==
=+
++
++
++
+
)n(f)n(f
;
e)
;)n(f)n(f)n(f
04142
=++++
f)
()() () ()
;nfnfnfnf
024126293
=−+++−+
48
Рекуррентные соотношения
f 1 (n ) =r1n −1 , f 2 (n ) =nr1n −1 , f 3 (n ) =n 2 r1n −1 ,Κ , f s (n ) =n s −1 r1n −1
рассматриваемого рекуррентного соотношения. В общем решении этому
корню соответствует часть
[
r1n −1 C1 +C 2 n +C 3 n 2 +Κ +C s n s −1 .]
Составляя такие выражения для всех корней и складывая их, получаем общее
решение.
Например, решим рекуррентное соотношение
f (n +4 ) =5 f (n +3) −6 f (n +2 ) −4 f (n +1) +8 f (n ).
Характеристическое уравнение имеет здесь вид
r 4 −5r 3 +6r 2 +4r −8 =0 .
Решая его, получаем корни
r1 =2 , r2 =2 , r3 =2 , r4 =−1.
Значит, общее решение нашего соотношения имеет следующий вид:
[ ]
f (n ) =2 n −1 C1 +C 2 n +C 3 n 2 +C 4 (−1) .
n −1
Задачи для самостоятельного решения
1. Написать первые пять членов решения рекуррентного соотношения
f (n +2 ) =2 f (n +1) −3 f (n ), удовлетворяющего заданным начальным ус-
ловиям:
f (1) =0 f (1) =−1 f (1) =3 f (1) =2 f (1) =2
a) b) c) d) e)
f (2 ) =1 f (2 ) =1 f (2) =0 f (2 ) =1 f (2 ) =8
2. Проверить, являются ли данные функции решениями данных рекуррент-
ных соотношений:
f (n +2 ) =2 f (n +1) − f (n );
a)
ϕ1 (n ) =5 ⋅ 2 n , ϕ 2 (n ) =2n +1, ϕ 3 (n ) =3.
f (n +2 ) =4 f (n +1) −3 f (n );
b)
ϕ1 (n ) =2n , ϕ 2 (n ) =5 ⋅ 3 n −1, ϕ 3 (n ) =7
3. Найти общее решение рекуррентных соотношений:
a) f ( n +2 ) −7 f ( n +1) +12 f ( n ) =0 ;
b) f ( n +2 ) +3 f ( n +1) −10 f ( n ) =0 ;
c) f ( n +2 ) −4 f ( n +1) +13 f ( n ) =0 ;
d) f ( n +2 ) +9 f ( n ) =0 ;
e) f ( n +2 ) +4 f ( n +1 ) +4 f ( n ) =0;
f) f (n +3) −9 f (n +2 ) +26 f (n +1) −24 f (n ) =0;
