ВУЗ:
Составители:
Рубрика:
57
Пусть дано рекуррентное соотношение
12
(2)(1)().
fnafnafn
+=++
Составим квадратное уравнение
21
2
arar += , (4)
которое называется характеристическим для данного соотношения.
Если это уравнение имеет два различных корня
1
r и
2
r , то общее реше-
ние рекуррентного соотношения имеет вид
2
22
1
11
--
+=
nn
rCrC)n(f .
Действительно, по утверждению 2)
1
11
-
=
n
r)n(f и
1
22
-
=
n
r)n(f явля-
ются решениями нашего соотношения. По утверждению 1) и
2
22
1
11
--
+=
nn
rCrC)n(f является его решением. Надо показать, что любое
решение соотношения можно записать в этом виде. Но любое решение ли-
нейного рекуррентного соотношения второго порядка определяется значе-
ниями )(f 1 и )(f 2 . Поэтому достаточно показать, что система уравнений
î
í
ì
=+
=+
brCrC
aCC
2211
21
имеет решение при любых
a
и
b
. Этими решениями являются
.
rr
bar
C,
rr
arb
C
21
1
2
21
2
1
-
-
=
-
-
=
Случай, когда оба корня уравнения
21
2
arar += совпадают друг с
другом, мы разберем несколько позже. Рассмотрим пример.
При изучении чисел Фибоначчи мы пришли к рекуррентному соот-
ношению
)n(f)n(f)n(f 21
-
+
-
=
.
Для него характеристическое уравнение имеет вид
1
2
+
=
r
r
.
Корнями этого квадратного уравнения являются числа
.r,r
2
51
2
51
11
-
=
+
=
Поэтому общее решение соотношения Фибоначчи имеет вид
nn
CC)n(f
÷
÷
ø
ö
ç
ç
è
æ
-
+
÷
÷
ø
ö
ç
ç
è
æ
+
=
2
51
2
51
21
.
Пусть дано рекуррентное соотношение f (n � 2) � a1 f (n � 1) � a2 f (n). Составим квадратное уравнение r 2 � a1r � a2 , (4) которое называется характеристическим для данного соотношения. Если это уравнение имеет два различных корня r1 и r2 , то общее реше- ние рекуррентного соотношения имеет вид f ( n ) � C1 r1n �1 � C 2 r2n � 2 . Действительно, по утверждению 2) f 1( n ) � r1n �1 и f 2 ( n ) � r2n �1 явля- ются решениями нашего соотношения. По утверждению 1) и f ( n ) � C1 r1n �1 � C 2 r2n � 2 является его решением. Надо показать, что любое решение соотношения можно записать в этом виде. Но любое решение ли- нейного рекуррентного соотношения второго порядка определяется значе- ниями f ( 1) и f ( 2 ) . Поэтому достаточно показать, что система уравнений �C1 � C 2 � a � �C1 r1 � C 2 r2 � b имеет решение при любых a и b . Этими решениями являются b � ar2 ar � b C1 � , C2 � 1 . r1 � r2 r1 � r2 Случай, когда оба корня уравнения r 2 � a1r � a2 совпадают друг с другом, мы разберем несколько позже. Рассмотрим пример. При изучении чисел Фибоначчи мы пришли к рекуррентному соот- ношению f ( n ) � f ( n � 1) � f ( n � 2 ) . Для него характеристическое уравнение имеет вид r 2 � r � 1. Корнями этого квадратного уравнения являются числа 1� 5 1� 5 r1 � , r1 � . 2 2 Поэтому общее решение соотношения Фибоначчи имеет вид n n �1 � 5 � �1 � 5 � f ( n ) � C 1 �� � � C2 � � � � . � � 2 � � 2 � 57
Страницы
- « первая
- ‹ предыдущая
- …
- 55
- 56
- 57
- 58
- 59
- …
- следующая ›
- последняя »