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

О связи линейных рекуррентных соотношений с матричным возведением в степень.

Источник вдохновения

В учебниках по алгоритмам и структурам данных иногда указывают интересный факт:

\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix} \]

где \(F_{n}\)\(n\)-ное число Фибоначчи.

этот факт позволяет:

  • получить некоторые неочевидные свойства чисел Фибоначчи, например, соотношение \((-1)^n = F_{n+1} F_{n-1} - F_n^2\) с помощью подсчёта определителей матриц.
  • получить алгоритм получения чисел Фибоначчи за \(O(log(n))\) операций, пользуясь алгоритмом бинарного возведения в степень1.
  • вывести формулу Бине (т.е. нерекуррентную формулу \(F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}\), дающую \(n\)-ное число Фибоначчи):

    • пользуясь выражением функции от матрицы \(f(A) = A^n\) с помощью интерполяционного многочлена Лагранжа-Сильвестра 2.
    • переводя матрицу в ЖНФ (жорданову нормальную форму) и выводя формулу для \(f(A) = A^n\), пользуясь большей простотой вывыдения формул для степени матриц у матрицы специального вида, чем у матриц в общем случае.

      эти вещи нужно изложить отдельно, но идея тут в том, что \(f(A) = A^n\) можно выразить, не проводя \(n\) (или даже \(O(log(n))\)) умножений, а получив \(g(n)\), свою для каждой матрицы.

К чему это

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

Я распишу некоторые из обобщений и их приложения.

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

\(a_{n+2} = c_{1} \cdot a_{n+1} + c_{2} \cdot a_{n}\), а \(a_0\) и \(a_1\) – начальные состояния.

\(A\) – матрица итерации, \[A = \begin{bmatrix} c_{1} & c_{2} \\ 1 & 0 \end{bmatrix}\]

\(x_{n}\) – вектор состояния. \[x_{n} = \begin{bmatrix} a_{n} \\ a_{n-1} \end{bmatrix}\]

составляем уравнение \[A \cdot x_{n} = x_{n+1}\]

т.е. переход на следующую итерацию для “вектора состояния” записывается в виде умножения на матрицу итерации.

Уравнение \(A^{n} \cdot x_{1} = x_{n+1}\) означает выражение состояния \((x_{n+1}, x_{n})\) через начальные состояния \((x_{1}, x_{0})\), т.е. по сути это и есть задание линейного рекуррентного соотношения второго порядка (если взять первый компонент вектора справа, т.е. \(x_{n+1}\)).

Если нам нужно получить формулу для вычисления решения уравнения \(a_{n}\) в замкнутом виде, т.е. без зависимости от предыдущих условий, мы можем выразить \(n\)-ую степень матрицы \(A\) пользуясь техникой из теории матриц 3, либо переведя матрицу \(A\) сначала в жорданову нормальную форму, \(A = S^{-1} \cdot J \cdot S\), \(A^{n} = S^{-1} \cdot J^n \cdot S\), затем выражая \(n\)-ную степень жордановой нормальной формы (это сделать проще, чем в общем случае) и производя матричное умножение.

Этот метод получения замкнутой формы существенно сложнее способа, доступного и школьнику4, тем не менее, такой взгляд на эти соотношения позволяет проще выявлять некоторые их свойства, а также решать более широкий класс уравнений.

С другой стороны, можно видеть, что, наоборот, выражение \(n\)-ной степени некоторых матриц специального вида (например, указанного выше) можно свести к решению линейного рекуррентного уравнения (этот метод существенно проще, чем указанные выше).

Алгоритм получения \(a_{n}\) за \(O(log n)\) выводится так же, как и в случае чисел Фибоначчи, если пользоваться алгоритмом бинарного возведения в степень5.

Можно обобщать алгоритмы и дальше, пользуясь, например, тем, что умножение матриц проще распараллеливать. Этим можно пользоваться для того, чтобы затратить меньшее время на вычисление значений этих линейных рекуррентных уравнений.


  1. https://e-maxx.ru/algo/binary_pow

  2. Гантмахер Ф.Р. Теория матриц (Глава 5 “Функции матрицы”, с. 98). Физматлит, 2004.

  3. https://e-maxx.ru/algo/binary_pow

  4. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. - Комбинаторика (2006, ФИМА, МЦНМО), Глава VII Рекуррентные соотношения, п.101.

  5. https://e-maxx.ru/algo/binary_pow