Potęgowanie macierzy

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Niniejszy artykuł jest częścią cyklu macierze.

Niektóre typy macierzy
macierz jednostkowa
macierz zerowa
macierz elementarna
macierz schodkowa
macierz trójkątna
macierz symetryczna
macierz diagonalna
macierz idempotentna
macierz nilpotentna
macierz hermitowska
macierz unitarna
macierz ortogonalna
(!) macierz dopełnień algebraicznych
(!) macierz dołączona
więcej...

Operacje na macierzach
mnożenie przez skalar
dodawanie i odejmowanie
mnożenie macierzy
potęgowanie macierzy
odwracanie macierzy
diagonalizacja macierzy
transpozycja macierzy
sprzężenie macierzy
operacje elementarne

Inne zagadnienia
wyznacznik macierzy
ślad macierzy
widmo macierzy
minor macierzy
wielomian charakterystyczny

edytuj ten szablon

Potęgowanie macierzy to działanie, które przyporządkowuje macierzy kwadratowej $A$ i liczbie całkowitej dodatniej $n$ macierz $B$ powstałą poprzez $(n - 1)$ -krotne pomnożenie macierzy $A$ przez siebie. Opisaną operację możemy przedstawić następująco:

$A^1 = A \,$ ,

$A^2 = A \cdot A$ ,

$A^3 = A \cdot A \cdot A$ ,

itd.

Wykorzystując rekurencję, możemy to zapisać następująco:

$A^{n+1} = A \cdot A^n$ .

Intuicyjnie, operacja potęgowania macierzy posiada następującą własność (analogicznie do zwykłego potęgowania liczb rzeczywistych):

$A^{n+m} = A^n \cdot A^m$ .

Możemy również zdefiniować potęgę zerową macierzy jako macierz jednostkową tego samego wymiaru:

(A n) 0 = I n

[edytuj] Złożoność obliczeniowa

Mnożenie macierzy w zwykły sposób (poprzez kolejne domnażanie) wymaga $O (N)$ mnożeń.

Są dwa efektywne algorytmy potęgowania macierzy:

algorytm binarny – liczymy $A, A 2, A 4, A 8$ i tak dalej, po czym mnożymy odpowiednie potęgi; wymaga to $O (l o g N)$ mnożeń,
potęgowanie za pomocą diagonalizacji – wymaga podniesienia macierzy diagonalnej do $n$ -tej potęgi (zob. złożoność obliczeniowa iloczynu macierzy); jeżeli macierz $A$ ma współczynniki całkowite, to macierz diagonalna nie musi zachować tej właściwości, co może spowodować błędy zaokrągleń, dlatego jest to metoda mniej ogólna.