Strassen-Algorithmus -> Beweis?

26.04.2012, 20:46	bandchef	Auf diesen Beitrag antworten »
Strassen-Algorithmus -> Beweis? Aufgabe: Stellen sie sich vor, Sie sollen zwei quadratische Matrizen M,N $\begin{eqnarray} \in \mathbb R^{n x n} \end{eqnarray}$ miteinander multiplizieren. Sei $\begin{eqnarray} n=2^i \end{eqnarray}$ für ein $\begin{eqnarray} i\in \mathbb N \end{eqnarray}$ , dann kann man M,N und $\begin{eqnarray} O=M\cdot N \end{eqnarray}$ wie folgt zerlegen: $\begin{eqnarray} M = \begin{pmatrix} M_{11} & M_{12} \\ M_{21} & M_{22} \end{pmatrix} \end{eqnarray}$ , $\begin{eqnarray} N = \begin{pmatrix} N_{11} & N_{12} \\ N_{21} & N_{22} \end{pmatrix} \end{eqnarray}$ und $\begin{eqnarray} O = \begin{pmatrix} O_{11} & O_{12} \\ O_{21} & O_{22} \end{pmatrix} \end{eqnarray}$ : Zeigen Sie, dass die Einträge der Produktmatrix O wie folgt berechnen werden können: $\begin{eqnarray} H_1 = (M_{11}+M_{22})\cdot (N_{11} + N_{22})<br /> H_2 = (M_{21} + M_{22}) \cdot N_{11}<br /> H_3 = M_{11}\cdot (N_{12}-N_{22})<br /> H_4 = M_{22}\cdot (N_{21}-N_{11})<br /> H_5 = (M_{11} + M_{12}) \cdot N_{22}<br /> H_6 = (M_{21} - M_{11}) \cdot (N_{11}+N_{12})<br /> H_7 = (M_{12} - M_{22}) \cdot (N_{21} + N_{22}) \end{eqnarray}$ $\begin{eqnarray} O_{11} = H_1 + H_4 - H_5 + H_7<br /> O_{12} = H_3 + H_5<br /> O_{21} = H_2 + H_4<br /> O_{22} = H_1 - H_2 + H_3 + H_6 \end{eqnarray}$ Hey Leute! Wie ihr oben ja lesen könnte, soll ich dieses Berechnungsschema beweisen. Ich hab mir nun hierzu eine 2x2-Matrix aufgeschrieben mit selbst gewählten Werten und hab diese Matrix mit Methode wie man händisch Matrizen multipliziert berechnet und hab auf meinem Blatt hier auch dieses Schema angewendet. Bei beiden Methoden komm ich auf die gleiche Ergebnismatrix. Als Beweis wird das wohl noch nicht reichen. Wie ich das aber nun "richtig" Beweise, dass dieses obige für mich "neue" Schema IMMER für die obigen Einschränkungen gilt, weiß ich nicht. Könnt ihr mir da vielleicht weiterhelfen?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »