Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] [Suche] Englische Flagge
Mathematik-Online-Kurs: Lineare Algebra - Matrizen - Matrix-Operationen

Matrix-Multiplikation

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

Das Produkt einer $ (n \times m)$-Matrix $ A$ und einer $ (m \times s)$-Matrix $ B$ ist die $ (n \times s)$-Matrix

$\displaystyle C=AB\; , \qquad c_{ij} = \sum_{k=1}^m a_{ik}b_{kj}\,, $

d.h. zur Definition von $ c_{ij}$ werden die Produkte der Elemente aus Zeile $ i$ von $ A$ und Spalte $ j$ von $ B$ summiert:

$\displaystyle \left( \begin{array}{ccccc} & & \vphantom{b_{1j}} & & \\ & & ... ...antom{a_{im}} \\ & & \vdots & & \\ & & b_{mj} & & \end{array}\right) \,. $

Man beachte, dass dazu die Spaltenzahl von $ A$ mit der Zeilenzahl von $ B$ übereinstimmen muss.

Die Matrixmultiplikation entspricht der Komposition der linearen Abbildungen

$\displaystyle T: u \mapsto v=Bu,\quad S: v \mapsto w=Av\, , $

d.h. $ C$ ist die Matrixdarstellung von $ S \circ T$.

Für die Komposition der durch

$\displaystyle w_i = \sum_{k=1}^m a_{ik} v_k,\quad v_k = \sum_{j=1}^s b_{kj} u_j $

definierten Abbildungen erhält man

$\displaystyle w_i = \sum_k \sum_j a_{ik} b_{kj} u_j = \sum_j \left[ \sum_k a_{ik} b_{kj} \right] u_j\, . $

Der Ausdruck in eckigen Klammern ist das Matrixprodukt und stimmt also mit der Matrix $ C$ der Komposition der Abbildungen überein.
(Autoren: Höllig/Hörner)
Im Folgenden sind einige konkrete Matrix-Produkte angegeben:
\begin{displaymath}\left( \begin{array}{rrr} 1 & 10 & 100 \\ 100 & 10 & 1 \end{... ...}{rrr} 1 & 3 & 2 \\ 2 & 1 & 3 \\ 3 & 2 & 1 \end{array}\right)\end{displaymath} $\displaystyle =$ $\displaystyle \left(\begin{array}{rrr} 321 & 213 & 132 \\ 123 & 312 & 231 \\ \end{array}\right)$  
\begin{displaymath}\left( \begin{array}{r} 1\\ 2\\ 3 \end{array}\right) \left( \begin{array}{rr} 7 & 13 \end{array}\right)\end{displaymath} $\displaystyle =$ \begin{displaymath}\left( \begin{array}{rr} 7 & 13 \\ 14 & 26 \\ 21 & 39 \end{array}\right)\end{displaymath}  
\begin{displaymath}\left( \begin{array}{rr} 3 & 4 \end{array}\right) \left( \begin{array}{r} 3\\ 4 \end{array}\right)\end{displaymath} $\displaystyle =$ $\displaystyle 25$  
\begin{displaymath}\left( \begin{array}{rr} 1 & \mathrm{i} \\ \mathrm{i} & 1 \e... ...ht) \left( \begin{array}{r} 1 \\ \mathrm{i} \end{array}\right)\end{displaymath} $\displaystyle =$ \begin{displaymath}\left( \begin{array}{r} 0 \\ 2\mathrm{i} \end{array}\right)\end{displaymath}  

(Autoren: Höllig/Hörner)
Berechnet man das Produkt $ C=AB$ von zwei $ (2\times2)$-Matrizen $ A$, $ B$ in der üblichen Weise, so benötigt man $ 8$ Multiplikationen. Sehr überraschend hat Strassen gezeigt, dass $ 7$ Multiplikationen ausreichen [V. Strassen: Gaussian elimination is not optimal, Numer. Math. 13 (1969). 357-361]. Man berechnet die Produkte

\begin{displaymath} \begin{array}{rcl} p_1 &=& (a_{1,2}-a_{2,2})(b_{2,1}+b_{2,2... ...2,1}-b_{1,1}) \\ p_7 &=& (a_{2,1}+a_{2,2})b_{1,1} \end{array}\end{displaymath}

und erhält die Elemente der Produktmatrix $ C$ durch Bilden der Summen

\begin{displaymath} \begin{array}{rcccl} c_{1,1} &=& a_{1,1}b_{1,1}+a_{1,2}b_... ...{2,1}b_{1,2}+a_{2,2}b_{2,2} &=& p_2-p_3+p_5-p_7. \end{array}\end{displaymath}

Wendet man diese Konstruktion in Blockform rekursiv auf Matrizen der Dimension $ n=2^k$ an, so ergibt sich eine Reduktion der Multiplikationen von $ n^3$ auf $ O(n^{\log_2 7})$. Dieses Resultat konnte sogar noch auf $ O(n^{2.376\ldots})$ verbessert werden [D. Coppersmith, S. Winograd: Matrix Multiplication via arithmetic progressions, J. Symb. Comp. 9 (1990), 251-280]. Es wird vermutet, daß sogar $ O(n^2)$ möglich ist -- der optimale Exponent ist jedoch noch unbekannt.

Für Matrizen von reellen oder komplexen Zahlen hat dieses Resultat heute keine praktische Bedeutung mehr, da die Berechnungen meist mit Hilfe von Computern durchgeführt werden, die fast ebenso schnell multiplizieren wie addieren können. Es ist daher nicht sinnvoll, 8 Multiplikationen und 4 Additionen durch 7 Multiplikationen und 18 Additionen zu ersetzen. Der mathematischen Brillianz des Resultates tut das jedoch keinen Abbruch.

(Autoren: Höllig/Hörner)
[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]
  automatisch erstellt am 23.5.2011