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

Последовательность {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^n-1-...-a_n-1x-a_n.

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

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

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

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

M= . w

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

Mb=b.

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

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

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

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

lⁱ-a₁l^i-1-...-l^i-n+1a_n-1-l^i-na_n=l^i-n(lⁿ-a₁l^n-1-...-la_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+isinj), l₂=r(cosj-isinj). Применим к базисным последовательностям невырожденное линейное преобразование

.

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

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

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