Линейные рекуррентные последовательности

Последовательность { x_i }, i =0,1,… над полем действительных чисел называется линейной рекуррентной последовательностью (ЛРП) порядка п >0, если для некоторых действительных чисел a ₁,…, a_n, a при любом i ³0

x_i ₊ _п + a ₁ x_i ₊ _п _-1+…+ a_n x_i = a. (2.21)

ЛРП называется однородной (ОЛРП), если a =0, и неоднородной (НЛРП), если a ¹0. Равенство называют законом линейной рекурсии или линейным рекуррентным соотношением порядка п >0, а вектор (x ₀,…, x_п _-1) – начальным вектором ЛРП. Последовательность { x_i } есть решение линейного рекуррентного соотношения порядка п >0, если любые ее п +1 членов удовлетворяют закону рекурсии. Характеристическим многочленом ОЛРП называют связанный с законом линейной рекурсии многочлен F (x)= xⁿ - a ₁ xⁿ ^-1-...- a_n _-1 x - a_n.

Утверждение 2.1. Множество всех ОЛРП над полем действительных чисел, удовлетворяющих (2.21) при a =0, образует векторное пространство.

t Достаточно проверить, что множество указанных ОЛРП замкнуто относительно сложения и умножения на константу поля. u

Обозначим это пространство L. Далее потребуется понятие определителя матрицы M (обозначается det M), известное из курса линейной алгебры.

Теорема 2.8. Последовательности { a_i ⁽¹⁾},…,{ a_i ⁽ ⁿ ⁾} образуют базис в L Û det M ¹0, где

M= . w

Решение линейного рекуррентного соотношения при a =0 может быть общим, т.е. записано как линейная комбинация базисных последовательностей с некоторыми коэффициентами b₁,…,b _n, и частным, т.е. последовательностью с заданными начальными условиями b =(a ₀,…, a_п _-1). Во втором случае набор коэффициентов b=(b₁,…,b _n) определяется из решения системы линейных уравнений

M b= b.

Таким образом, основная задача – нахождение базиса пространства L.

Построение базисных последовательностей выполняется с помощью корней характеристического многочлена.

Лемма 2.3. Пусть l - ненулевой корень характеристического многочлена F (x). Тогда последовательность {l ⁱ }={1,l,l²,…} – решение однородного линейного рекуррентного соотношения (2.21).

t Подставим члены последовательности {l ⁱ } в однородное линейное рекуррентное соотношение (2.21). Так как l¹0, то получаем:

l ⁱ - a ₁l ⁱ ^-1-...-l ⁱ ^{- n +1} a_n _-1-l ⁱ ^{- n} a_n =l ⁱ ^{- n}(l ⁿ - a ₁l ⁿ ^-1-...-l a_n _-1- a_n)= F (l)=0. u

Теорема 2.9. Пусть характеристический многочлен F (x) имеет n различных корней l₁,…,l _n, тогда последовательности { },…,{ } образуют базис в L.

t По лемме 2.3 все последовательности { },…,{ } принадлежат пространству L. Определитель, образованный первыми n элементами этих последовательностей, называемый определителем Вандермонда, равен:

= .

Определитель не равен 0, так как все корни различны, значит, то теореме 2.8 последовательности { },…,{ } образуют базис в L. u

Итак, если характеристический многочлен имеет n различных корней l₁,…,l _n, то общее решение однородного рекуррентного соотношения имеет вид:

{ x_i }=b₁{ }+…+b _n { }.

Если корни l₁,…,l _n – действительные, то все базисные последовательности также действительные. Если не все корни действительные, то комплексным корням соответствуют комплексные базисные последовательности. Вместе с тем, применяя определенное невырожденное преобразование к системе базисных векторов, можно получить новый базис действительных последовательностей (переход от базиса к базису рассмотрен в разделе 6.5).

Из теории полей известно, что комплексные корни действительного многочлена образуют пары сопряженных корней. Пусть пара сопряженных корней характеристического многочлена F (x) имеет вид: l₁=r(cosj+ i sinj), l₂=r(cosj- i sinj). Применим к базисным последовательностям невырожденное линейное преобразование

Тогда паре базисных комплексных последовательностей { }={r ^j (cos j j+ i sin j j)} и { }={r ^j (cos j j- i sin j j)} после преобразования соответствует пара базисных действительных последовательностей {r ^j cos j j} и {r ^j sin j j}. Следовательно, базис можно выбрать состоящим только из действительных последовательностей.

Теорема 2.10 [22]. Общее решение неоднородного рекуррентного соотношения есть сумма некоторого его частного решения и общего решения соответствующего однородного рекуррентного соотношения. w

Конечные автоматы