Companion matrix complex

Question

Я знаю, что это вопрос теории сложности, а не вопрос программирования, надеюсь, что я не ошибаюсь, пишу здесь, извини меня, если это не то место, но я надеюсь, что у кого-то из вас есть ответ. И это даже когда-то связано с программированием, поскольку это теория сложности.

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

Я не могу дать пример кодирования, но я постараюсь, чтобы получить вам больше объяснение:

Однородная линейная рекуррентная последовательность к-й (n + k-1) + a (k-2) s (n + k-2) + ... + a (0)
(n + k) = a (k-1) s для n = 0,1, где s (i) - i-е значение секвенса e, а a (i) - коэффициенты в алгебраическом поле.

А спутница матрица выше последовательности, если это:
(0 0 0 0 ... 0 (0))
(1 0 0 0 ... 0 а (1))
(0 1 0 0 ... 0 a (2))
(.. .. .. .. .. .. .. ..)
(0 0 0 0 ... 1 a (k -1))
Кроме того Теория гласит, что для векторов состояния последовательности мы имеем:
s (N) = s (0) А^при п = 0,1, ..
Вот это, спасибо помощь.

Answer 1

Обычная стратегия для нахождения силы матрицы быстро, чтобы она диагонализация (выполнить собственный вектор, разложение):

А = Р ^-1 D P

, где D представляет собой диагональную матрицу. Вы можете поднять к мощности п вычисляя

^п = P ^-1 D ^п P

где D ^п быстро вычислить, потому что это диагональная матрица, так вы просто берете полномочия каждого элемента отдельно.

Однако не все матрицы диагонализуемы - я не знаю, будет ли ваша сопутствующая матрица или нет. В любом случае вы можете найти this Wikipedia article.

Answer 2

Вы можете вычислить n ю степень матрицы M использованием O(log n) матричных продуктов:

• если n=0, возвращение I
• если n даже вычислить N=Mn/2 и вернуть N*N
• если n нечетно, вычислить N=Mn-1 и вернуть M*N