Jak obliczyć moc macierzy kwadratowych?

Załóżmy, że otrzymujemy macierz i pozwólmy . Jak szybko możemy obliczyć moc A ^ m tej macierzy? m ∈ N 0 A $A \in \mathbb R^{N\times N}$$m \in \mathbb N_0$$A^m$

Kolejną najlepszą rzeczą w porównaniu do obliczania produktów jest zastosowanie szybkiego potęgowania, które wymaga produktów macierzy \ mathcal O (\ log m) .O ( log m $m$$\mathcal O(\log m )$

W przypadku matryc diagonalizowanych można zastosować rozkład wartości własnej. Jego naturalne uogólnienie, rozkład Jordana, jest niestabilny w wyniku perturbacji i dlatego się nie liczy (afaik).

Czy można przyspieszyć potęgowanie macierzy w ogólnym przypadku?

Szybkie potęgowanie sugeruje, że przydatna jest również odmiana tego pytania:

Czy kwadrat ogólnej macierzy $A$ można obliczyć szybciej niż przy użyciu znanych algorytmów mnożenia macierzy?

Jak zauważasz, obliczanie może być wykonane w razy liczba operacji mnożenia macierzy na macierzach. Odpowiedź na twoje drugie pytanie brzmi: nie, przynajmniej dla asymptotycznej złożoności - kwadrat macierzy i mnożenie macierzy mają równoważny czas / złożoność arytmetyczną (aż do stałych czynników). Zmniejszenie kwadratu do mnożenia macierzy jest oczywiste. Aby ograniczyć namnażanie się kwadratury, załóżmy, że chcemy obliczyć iloczyn i . Utwórz macierz ze strukturą bloku: O ( log m ) N × N A B 2 n × 2 n $A^m$$O(\log m)$$N \times N$$A$$B$$2n \times 2n$$C$

$[0~~A]$

$[B~~0]$

Oznacza to, że ma macierz wszystkich zer w swojej górnej lewej ćwiartce i prawej dolnej ćwiartce. Zauważ, że zawiera w lewym górnym kwadrancie.n × n C 2 A ⋅ $C$$n \times n$$C^2$$A\cdot B$