Дискретная математика. Азарнова Т.В - 48 стр.

UptoLike

Рекуррентные соотношения
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
=++++