flops/Rechenoperationen zählen < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Berechnen Sie die flops der Matrixmultiplikation zweier oberer (mxm)Dreiecksmatrizen. |
Hallo, ich komme irgendwie nicht weiter. also ich versuche die flops mit Hilfe von inneren Produkten zu zählen und komme so bei einer Matrizmultiplikation zweier vollen Matrizen auf [mm] 2m^3 [/mm] flops in führender Ordnung. Bei einer vollen mit einer oberen Dreieckmatriz komme ich auf [mm] m^3 [/mm] in führender Ordnung und bei dem Problem von oben bekomme ich:
[Dateianhang nicht öffentlich]
Könnte dieses Ergebnis richtig sein?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: PNG) [nicht öffentlich]
|
|
| |
|
Hallo,
> Berechnen Sie die flops der Matrixmultiplikation zweier
> oberer (mxm)Dreiecksmatrizen.
> Hallo, ich komme irgendwie nicht weiter. also ich versuche
> die flops mit Hilfe von inneren Produkten zu zählen und
> komme so bei einer Matrizmultiplikation zweier vollen
> Matrizen auf [mm]2m^3[/mm] flops in führender Ordnung.
Ja, das ist richtig. Eine Matrixmultiplikation A = B*C mit $B,C [mm] \in \IR^{m\times m}$ [/mm] wird errechnet durch die einzelnen Komponenten,
[mm] $A_{ij} [/mm] = [mm] \sum_{k=1}^{m}B_{ik} C_{kj}$,
[/mm]
und das sind $m$ Multiplikationen und $m-1$ Additionen, also insgesamt $2m-1$ Rechenschritte.
Da [mm] $m^2$ [/mm] Komponenten berechnet werden müssen, ergeben sich insgesamt [mm] $m^2*(2m-1) [/mm] = [mm] 2m^3 [/mm] - [mm] m^2$ [/mm] Rechenschritte.
> Bei einer
> vollen mit einer oberen Dreieckmatriz komme ich auf [mm]m^3[/mm] in
> führender Ordnung
Ja, denn hier ist die Rechnung eine andere: Ist zum Beispiel $C$ die obere Dreiecksmatrix, dann ist
[mm] $A_{ij} [/mm] = [mm] \sum_{k=1}^{j}B_{ik} C_{kj}$,
[/mm]
(Einträge [mm] $C_{kj}$ [/mm] mit $k > j$ sind Null)
d.h. $j$ Produkte und $j-1$ Additionen, insgesamt (2j-1) Rechenoperationen. Da im Allgemeinen $A = B*C$ wieder eine volle Matrix ist, müssen alle Einträge von $A$ berechnet werden, und es ergeben sich
[mm] $m*\sum_{j=1}^{m}(2j-1) [/mm] = [mm] m^3$
[/mm]
Rechenoperationen.
> und bei dem Problem von oben bekomme
> ich:
> [Dateianhang nicht öffentlich]
> Könnte dieses Ergebnis richtig sein?
Zunächst müssen wir uns anschauen, wie die Berechnungsformel sich verändert. Weil das Produkt zweier oberer Dreiecksmatrizen wieder eine obere Dreiecksmatrix ist, müssen nur Einträge mit $j [mm] \ge [/mm] i$ (Spalte [mm] $\ge$ [/mm] Zeile) berechnet werden. Wegen der Dreiecksgestalt der beiden Matrizen vereinfacht sich das Produkt zu:
[mm] $A_{ij} [/mm] = [mm] \sum_{k=i}^{j}B_{ik} C_{kj}$, [/mm] (*)
d.h. $(j-i+1)$ Produkte und $(j-i)$ Additionen, insgesamt $2(j-i)+1$ Rechenoperationen.
Die insgesamte Zahl der Rechenoperationen autet dann (beachte Dreiecksgestalt von $A$):
[mm] $\sum_{j=1}^{m}\sum_{i=1}^{j}\Big[ [/mm] 2(j-i) + [mm] 1\Big]$.
[/mm]
Dein Ergebnis ist also nicht richtig, du hast vermutlich bei der Anzahl der Rechenoperationen in (*) nicht aufgepasst :)
Viele Grüße,
Stefan
|
|
|
| |
|
vielen Dank!
ich komme mit deiner Hilfe auber auch auf 1/3 [mm] m^3 [/mm] flops in führender Ordnung!
|
|
|
| |
|
Hallo Susalmausal,
> ich komme mit deiner Hilfe auber auch auf 1/3 [mm]m^3[/mm] flops in
> führender Ordnung!
Das ist ja auch richtig.
Aber du hast nicht die richtige Summe gehabt. Es ist sozusagen "Glück", das auch bei deiner falschen Summe die richtige führende Ordnung herausgekommen ist.
Viele Grüße,
Stefan
|
|
|
| |
|
ja, ich weiß :)
vielen Dank, habs jetzt hoffentlich verstanden !!
|
|
|
|
