Комбинаторные алгоритмы для программистов


Случай равных корней характеристического уравнения


Рассмотрим случай, когда оба корня характеристического уравнения совпадают:

r_1 = r_2
. В этом случае выражение
C_1 r_1^{n - 1}+ C_2 r_2^{n - 1}
уже не будет общим решением. Ведь из-за того, что
r_1 = r_2
, это решение можно записать в виде
f(n) = (C_1 + C_2 )r_1^{n - 1} = Cr_1^{n - 1}.

Остается только одно произвольное постоянное ; и выбрать его так, чтобы удовлетворить двум начальным условиям

f(1) = a,f(2) = b
, вообще говоря, невозможно.Поэтому надо найти какое-нибудь второе решение, отличное от
f_1 (n) = r_1^{n - 1}
. Таким решением является
f_2 (n) = nr_1^{n - 1}
. В самом деле, если квадратное уравнение
r^2 = a_1 r + a_2
имеет два совпадающих корня
r_1 = r_2
, то по теореме Виета
a_1 = 2r_1,a_2 = - r_1^2
. Поэтому уравнение записывается так:
r^2 = 2r_1 r - r_1^2.

А тогда рекуррентное соотношение имеет такой вид:

f(n + 2) = 2r_1 f(n + 1) - r_1^2 f(n).

(8.10)

Проверим, что

f_2 (n) = nr_1^{n - 1}
действительно являются его решением. Имеем
f_2 (n + 2) = (n + 2)r_1^{n + 1}
, а
f_2 (n + 1) = (n + 1)r_1^n
. Подставляя эти значения в соотношение (8.10), получаем очевидное тождество
(n + 2)r_1^{n + 1} = 2(n + 1)r_1^{n + 1} - nr_1^{n + 1}.

Значит,

nr_1^{n - 1}
- решение рассматриваемого соотношения.

Итак, имеются два решения

f_1 (n) = r_1^{n - 1}
и
f_2 (n) = nr_1^{n - 1}
заданного соотношения. Его общее решение запишется так:
f(n) = C_1 r_1^{n - 1} + C_2 nr_1^{n - 1} = r_1^{n - 1} (C_1 + C_2 n).
Теперь уже путем подбора
C_1, C_2
можно удовлетворить любым начальным условиям.

Линейные рекуррентные соотношения с постоянными коэффициентами, порядок которых больше двух, решаются таким же способом. Пусть соотношение имеет вид

f(n + k) = a_1 f(n + k - 1) + \ldots + a_n f(n).

(8.11)

Составим характеристическое уравнение

r^k = a_1 r^{k - 1} + \ldots + a_k.

Если все корни

r_1,r_2,\ldots,r_k
этого алгебраического уравнения
k
-й степени различны, то общее решение соотношения (8.3) имеет вид
 f(n) = C_1 r_1^{n - 1} + C_2 r_2^{n - 1} + \ldots + C_k r_k^{n - 1}.

Если же, например,

r_1 = r_2 = \ldots = r_s
, то этому корню соответствуют решения
f_1 (n) = r_1^{n - 1},f_2 (n) = nr_1^{n - 1},

f_3 (n) = n^2 r_1^{n - 1},\ldots,f_s (n) = n^{s - 1} r_1^{n - 1}

рекуррентного соотношения (8.11). В общем решении этому корню соответствует часть

 r_1^{n - 1} [C_1 + C_2 n + C_3 n^2 + \ldots + C_s n^{s - 1} ]

Составляя такое выражение для всех корней и складывая их, получаем общее решение соотношения (8.3).

Например, решим рекуррентное соотношение

f(n + 4) = 5f(n + 3) - 6f(n + 2) - 4f(n + 1) + 8f(n).

Характеристическое уравнение в этом случае имеет вид

r^4 - 5r^3 + 6r^2 + 4r - 8 = 0.

Решая его, получим корни

r_1 = 2,r_2 = 2,r_3 = 2,r_4 = - 1.

Значит, общее решение нашего соотношения имеет следующий вид:

f(n) = 2^{n - 1} [C_1 + C_2 n + C_3 n^2 ] + C_4 ( - 1)^{n - 1}.




Начало  Назад  Вперед



Книжный магазин