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

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Рекуррентные соотношения
47
§ 3. Случай равных корней характеристического уравнения
Остановимся теперь на случае, когда оба корня характеристического
уравнения совпадают:
21
rr
=
. В этом случае выражение
1
22
1
11
−−
+
nn
rCrC
уже
не будет общим решением. Ведь из-за того, что
21
rr
=
, это решение можно
записать в виде
() ( )
.CrrCCnf
nn
1
1
1
121
=−
=+=
У нас остается только одно произвольное постоянное
C
, и выбрать его так,
чтобы удовлетворить двум начальным условиям
() ( )
bf,af
==
21
, вообще
говоря, невозможно.
Поэтому надо найти какое-нибудь второе решение отличное от
()
1
11
−
=
n
rnf
. Оказывается, таким решением является
()
1
12
−
=
n
nrnf
. В самом
деле, если квадратное уравнение
21
2
arar
+=
имеет два совпадающих корня
21
rr
=
, то по теореме Виета
2
1211
2
ra,ra
−==
. Поэтому наше уравнение запи-
сывается так:
2
11
2
2
rrrr
−=
.
Тогда рекуррентное соотношение имеет такой вид:
() () ()
nfrnfrnf
2
11
122
−+=+
. (4)
Проверим, что
()
1
12
−
=
n
nrnf
действительно является его решением. Имеем
()()
1
12
22
+
+=+
n
rnnf
, а
()()
n
rnnf
12
11
+=+
. Подставляя эти значения в соот-
ношение (4), получаем очевидное тождество
() ()
1
1
1
1
1
1
122
+++
−+=+
nnn
nrrnrn
.
Значит,
1
1
−
n
nr
— решение нашего соотношения.
Теперь уже знаем два решения
()
1
11
−
=
n
rnf
и
()
1
12
−
=
n
nrnf
заданного
соотношения. Его общее решение пишется так:
() ( )
nCCrnrCrCnf
n
r
nn
21
11
12
1
11
+=+=
−−−
.
Путем подбора
1
C
и
2
C
можно удовлетворить любым начальным условиям.
Линейные рекуррентные соотношения с постоянными коэффициента-
ми, порядок которых больше двух, решаются таким же способом. Пусть со-
отношение имеет вид
() ( ) ()
nfaknfaknf
k
++−+=+
Κ
1
1
.
Составляем характеристическое уравнение
k
kk
arar
++=
−
Κ
1
1
.
Если все корни
k
r,,r
Κ
1
этого алгебраического уравнение
k
-й степени раз-
личны, то общее решение имеет вид
()
11
22
1
11
−−−
+++=
n
kk
nn
rCrCrCnf
Κ
.
Если же, например,
s
rrr
===
Κ
21
, то этому корню соответствуют решения 
                                          47
Рекуррентные соотношения
        § 3. Случай равных корней характеристического уравнения

          Остановимся теперь на случае, когда оба корня характеристического
уравнения совпадают: r1 =r2 . В этом случае выражение C1 r1n −1 +C 2 r2n −1 уже
не будет общим решением. Ведь из-за того, что r1 =r2 , это решение можно
записать в виде
                               f (n ) =(C1 +C 2 )r1n −1 =Cr1n =1 .
У нас остается только одно произвольное постоянное C , и выбрать его так,
чтобы удовлетворить двум начальным условиям f (1) =a , f (2 ) =b , вообще
говоря, невозможно.
          Поэтому надо найти какое-нибудь второе решение отличное от
 f 1 (n ) =r1n −1 . Оказывается, таким решением является f 2 (n ) =nr1n −1 . В самом
деле, если квадратное уравнение r 2 =a1 r +a 2 имеет два совпадающих корня
r1 =r2 , то по теореме Виета a1 =2r1 , a 2 =−r12 . Поэтому наше уравнение запи-
сывается так:
                                  r 2 =2r1 r −r12 .
Тогда рекуррентное соотношение имеет такой вид:
                       f (n +2 ) =2r1 f (n +1) −r12 f (n ).                 (4)
Проверим, что f 2 (n ) =nr1n −1 действительно является его решением. Имеем
 f 2 (n +2 ) =(n +2 )r1n +1 , а f 2 (n +1) =(n +1)r1n . Подставляя эти значения в соот-
ношение (4), получаем очевидное тождество
                               (n +2 )r1n+1 =2(n +1)r1n +1 −nr1n+1 .
Значит, nr1n −1 — решение нашего соотношения.
      Теперь уже знаем два решения f 1 (n ) =r1n −1 и f 2 (n ) =nr1n −1 заданного
соотношения. Его общее решение пишется так:
                   f (n ) =C1 r1n −1 +C 2 nr1n −1 =rrn −1 (C1 +C 2 n ).
 Путем подбора C1 и C 2 можно удовлетворить любым начальным условиям.
      Линейные рекуррентные соотношения с постоянными коэффициента-
ми, порядок которых больше двух, решаются таким же способом. Пусть со-
отношение имеет вид
                     f (n +k ) =a1 f (n +k −1) +Κ +a k f (n ).
Составляем характеристическое уравнение
                                r k =a1 r k −1 +Κ +a k .
Если все корни r1 ,Κ , rk этого алгебраического уравнение k -й степени раз-
личны, то общее решение имеет вид
                       f (n ) =C1 r1n −1 +C 2 r2n −1 +Κ +C k rkn −1 .
Если же, например, r1 =r2 =Κ =rs , то этому корню соответствуют решения

Страницы