Mnożenie 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
rząd macierzy
wielomian charakterystyczny

edytuj ten szablon

[edytuj] Definicja formalna

Formalnie rzecz biorąc, mnożenie macierzy jest działaniem dwuargumentowym, które parze macierzy $A_{m \times n}, B_{n \times p}$ przyporządkowuje macierz $C_{m \times p}$ o współczynnikach:

$c_{ij}= a_{i1} \cdot b_{1j} + a_{i2} \cdot b_{2j} + \dots + a_{in} \cdot b_{nj} = \sum_{k=1}^n a_{ik} \cdot b_{kj}$ ,

gdzie:

$i = 1, 2, \dots, m$ ,

$j = 1, 2, \dots, p$ ,

n

- liczba kolumn pierwszej macierzy (albo, równoważnie, liczba wierszy drugiej macierzy).

[edytuj] Algorytm mnożenia

Poniżej zilustrowany został sposób obliczania elementów $\color{Red} c_{12}$ oraz $\color{Blue} c_{33}$ macierzy wynikowej $C_{4 \times 3}$ , będącej iloczynem macierzy $A_{4 \times 2}$ i $B_{2 \times 3}$ .

Przykładowo, element $\color{Red} c_{12}$ powstaje z sumy iloczynów odpowiadających sobie elementów z pierwszego wiersza macierzy $A$ i drugiej kolumny macierzy $B$ (elementy macierzy składowych bierzemy zgodnie z kierunkiem strzałek). Innymi słowy, aby wyznaczyć element $\color{Red} c_{12}$ , musimy wymnożyć pierwszy element z pierwszego wiersza macierzy $A$ przez pierwszy element z drugiej kolumny macierzy $B$ , i do tego dodać iloczyn drugiego elementu z pierwszego wiersza macierzy $A$ i drugiego elementu z drugiej kolumny macierzy $B$ . Opisane obliczenia poniżej:

$\color{Red} c_{12} \color{Black} = a_{11} \cdot b_{12} + a_{12} \cdot b_{22}$ .

Podobnie postępujemy z wyróżnionym na niebiesko elementem macierzy $C$ z trzeciego wiersza i trzeciej kolumny:

$\color{Blue} c_{33} \color{Black} = a_{31} \cdot b_{13} + a_{32} \cdot b_{23}$ .

[edytuj] Przykład

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \\ \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} (1 \cdot 3 + 0 \cdot 2 + 2 \cdot 1) & (1 \cdot 1 + 0 \cdot 1 + 2 \cdot 0) \\ (-1 \cdot 3 + 3 \cdot 2 + 1 \cdot 1) & (-1 \cdot 1 + 3 \cdot 1 + 1 \cdot 0) \\ \end{bmatrix} = \begin{bmatrix} 5 & 1 \\ 4 & 2 \\ \end{bmatrix}$

[edytuj] Własności

Operacja mnożenia macierzy ma następujące własności (proszę zwrócić uwagę na wymagania dotyczące wymiarów macierzy, dla których mnożenie jest wykonalne):

łączność: $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ dla macierzy $A_{k \times m}, B_{m \times n}, C_{n \times p}$ ,

rozdzielność względem dodawania:
- prawostronna: $(A + B) \cdot C = A \cdot C + B \cdot C$ dla macierzy $A_{m \times n}, B_{m \times n}, C_{n \times k}$ ,
- lewostronna: $C \cdot (A + B) = C \cdot A + C \cdot B$ dla macierzy $A_{m \times n}, B_{m \times n}, C_{k \times m}$ .

Uwaga! Mnożenie macierzy najczęściej nie jest przemienne, nawet gdy oba mnożenia $A B$ i $B A$ są wykonalne.

[edytuj] Złożoność obliczeniowa

Naiwny algorytm mnożenia macierzy o wymiarach $x \times y$ i $y \times z$ wymaga $x y z$ mnożeń. Dla macierzy kwadratowych daje to algorytm klasy $O (n 3)$ .

Istnieją wydajniejsze algorytmy rozwiązywania tego zadania. Pierwszy z takich algorytmów podał w 1969 r. Volker Strassen - złożoność tego algorytmu to około $O (n 2,807)$ . Nie jest on jednak zwykle używany w praktyce z powodu braku stabilności numerycznej. Najlepszy obecnie znany algorytm mnożenia macierzy, podany przez Dona Coppersmitha i Shmuela Winograda, ma złożoność rzędu ok. $O (n 2,376)$ . Dolne oszacowanie złożoności mnożenia macierzy, wynikające z konieczności obliczenia $n 2$ wartości, to $Ω(n 2)$ .

Jeśli to możliwe, należy skorzystać z algorytmów wykorzystujących szczególne własności macierzy, np. mnożenie macierzy diagonalnych jest algorytmem klasy $O (n)$ .