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

         

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


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

. В этом случае выражение
уже не будет общим решением. Ведь из-за того, что
, это решение можно записать в виде

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

, вообще говоря, невозможно.Поэтому надо найти какое-нибудь второе решение, отличное от
. Таким решением является
. В самом деле, если квадратное уравнение
имеет два совпадающих корня
, то по теореме Виета
. Поэтому уравнение записывается так:

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

(8.10)

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

действительно являются его решением. Имеем
, а
. Подставляя эти значения в соотношение (8.10), получаем очевидное тождество

Значит,

- решение рассматриваемого соотношения.

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

и
заданного соотношения. Его общее решение запишется так:
Теперь уже путем подбора
можно удовлетворить любым начальным условиям.

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

(8.11)

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

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

этого алгебраического уравнения
-й степени различны, то общее решение соотношения (8.3) имеет вид

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

, то этому корню соответствуют решения

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

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

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

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

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

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



Содержание раздела