Как вычислить степени квадратных матриц?

Предположим, нам дана матрица , и пусть . Как быстро мы можем вычислить мощность этой матрицы?$A \in \mathbb R^{N\times N}$$m \in \mathbb N_0$$A^m$

Следующая лучшая вещь по сравнению с вычислением продуктов - это использование быстрой экспоненты, для которой требуются матричные продукты .$m$$\mathcal O(\log m )$

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

Можно ли ускорить возведение матрицы в общем случае?

Быстрое возведение в степень предполагает, что вариант этого вопроса тоже полезен:

Можно ли вычислить квадрат общей матрицы быстрее, чем с помощью известных алгоритмов умножения матриц?$A$

Как вы заметили, вычисление может быть выполнено за O ( log m ), умноженное на количество операций для умножения матриц на N × N матриц. Ответ на ваш второй вопрос - нет, по крайней мере, для асимптотической сложности - матричный квадрат и умножение матриц имеют эквивалентную временную / арифметическую сложность (с точностью до постоянных множителей). Сокращение возведения в квадрат до умножения матриц очевидно. Чтобы уменьшить умножение на возведение в квадрат, предположим , что мы хотим вычислить произведение A и B . Форма 2 n × 2 n матрицы C с блочной структурой:$A^m$$O(\log m)$$N \times N$$A$$B$$2n \times 2n$$C$

$[0~~A]$

$[B~~0]$

То есть имеет матрицу из всех нулей n × n в своем верхнем левом квадранте и нижнем правом квадранте. Обратите внимание, что C 2 содержит A ⋅ B в своем верхнем левом квадранте.$C$$n \times n$$C^2$$A\cdot B$