double arrow

Линейное рекуррентное соотношение

Соотношение вида

an + k + p 1 an + k -1+…+ pkan = h (n) (2)

где h (n) – функция от числа , а , называется линейным рекуррентным соотношением.

Линейное рекуррентное соотношение называют однородным, если f (n)=0:

an + k + p 1 an + k -1+…+ pkan =0. (3)

Многочлен xk + p 1 xk -1+…+ pk -1 x + pk называется характеристическим для соотношения (2).

Корень a многочлена называется простым, если делится на , но не делится на .

Корень a многочлена называется кратным, если делится на , но не делится на , .

При этом число называется кратностью корня .

Основная теорема алгебры: многочлен степени с комплексными коэффициентами имеет комплексных корней с учетом их кратности.

Теорема 1. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет n простых корней a1, …, a n. Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

, (4)

где c 1,…, ck Î C.

Доказательство. Легко проверить следующие два утверждения.

(a) Последовательность cxn, где c Î C, является решением рекуррентного соотношения (3).

(b) Если последовательности an и bn являются решениями соотношения (3), то последовательность an + bn также является решением соотношения (3).

Из (a) и (b) следует, что любая последовательность вида (4) является решением соотношения (3).

Обратно, любое решение соотношения (3) имеет вид (4).

При n =0,1,…, k -1, из равенства (4) мы получим систему линейных уравнений относительно c 1,…, ck:

(5)

Определитель системы (5) есть известный в алгебре определитель Вандермонда:

.

Так как простые корни x 1,…, xk попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.

Теорема 2. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a1 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

, (6)

где .

Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: