Matrixmultiplikation und ihre Kosten

Abbildungen hintereinanderschalten

Das Produkt $AB$ ist die Abbildung, die man erhält, wenn man erst $B$ und dann $A$ anwendet: $(AB)\mathbf{x}=A(B\mathbf{x})$. Der Eintrag $(i,j)$ des Produkts ist das Skalarprodukt von Zeile $i$ von $A$ mit Spalte $j$ von $B$, die Formate müssen also passen: Eine $m\times n$-Matrix mal eine $n\times p$-Matrix ergibt eine $m\times p$-Matrix. Das Produkt ist assoziativ, $(AB)C=A(BC)$, und distributiv über die Summe, im Allgemeinen aber nicht kommutativ: $AB\neq BA$, weil die Reihenfolge zweier Aktionen zählt.

Die Berechnung von $AB$ für eine $m\times n$- und eine $n\times p$-Matrix kostet $mnp$ Multiplikations-Additionen (etwa $2mnp$ Gleitkommaoperationen). Bei zwei $n\times n$-Matrizen sind das $n^3$: Verdoppelt man $n$, wird die Arbeit achtmal so groß. Eine Matrix mal ein Vektor kostet nur $n^2$. Da das Produkt assoziativ ist, ändert die Klammerung das Ergebnis nicht, kann die Kosten aber enorm verändern.

• Formatregel: $(m\times n)(n\times p)=(m\times p)$; die inneren Größen müssen übereinstimmen.
• Nicht kommutativ: $AB\neq BA$ im Allgemeinen, vertauschen Sie die Faktoren also nie.
• Kosten: $mnp$ Multiplikations-Additionen; Matrix mal Vektor $n^2$, Matrix mal Matrix $n^3$.

Lab: Was bewertet wird

• Das Produkt AB20 Pkt.
• Das Produkt BA15 Pkt.
• Das Format eines Produkts10 Pkt.
• Multiplikations-Additionen zählen15 Pkt.
• Zwei Klammerungen20 Pkt.
• Warum die Klammerung zählt20 Pkt.