Gleitpunktoperationen, Aufwandsabschätzung

13.02.2012, 15:43

Mig85

Gleitpunktoperationen, Aufwandsabschätzung

Also liebe Leute habe folgendes Problem folgende Aufgabe ist zu lösen:

Aufgabe 2 (Aufwandsabschätzungen)
a) Bestimmen Sie die Anzahl der elementaren Operationen (Addition, Subtraktion, Multiplikation,
Division), die nötig sind, um eine Matrix A lxm mit einem Vektor b bzw. mit
einer Matrix B mxn zu multiplizieren.

b) Bestimmen Sie für eine Matrix A nxn die Anzahl der elementaren Operationen, die
i) zur Berechnung der LR-Zerlegung,

ii) für das Vorwärts- und Rückwärtseinsetzen
nötig sind, wenn man ein Gleichungssystem Ax = b lösen will.

Ein (nicht mehr ganz neuer) PC schafft ca. 10 Gflops, also 10 Milliarden Gleitpunktoperationen pro
Sekunde. Welche Rechenzeiten sind in den Fällen l = m = n = 10^k mit k = 2; 3; : : : ; 6 zu erwarten,
wenn Sie jede elementare Rechenoperation als eine Gleitpunktoperation interpretieren?
Verwenden Sie dabei geeignete Einheiten (Sekunden, Stunden, Jahre, ...).

Gegeben sind zwei Summenformeln

$\begin{eqnarray*} \sum\limits_{k=1}^(n-1) k = 1/2(n-1)n \end{eqnarray*}$ und $\begin{eqnarray*} \sum\limits_{k=1}^(n-1) k² = 1/6(n-1)n(2n-1) \end{eqnarray*}$

Meine Lösungen bisher sind folgende

zu a) l*n*(2m-1)

zu b) $\begin{eqnarray*} \sum\limits_{k=1}^n (2n(n-1)) \end{eqnarray*}$ für die LR Zerlegung und $\begin{eqnarray*} 2* \sum\limits_{k=1}^n n \end{eqnarray*}$

Dafür brauchte ich aber die vorgegebenen Formeln nicht. Meine passen aber soweit ich das beurteilen kann.

Zu meinem Anliegen.

Sagt mir bitte ob meine Lösungen so weit richtig sind und erklärt mir wie ich nun weiter rechnen muss bzw. wofür die Summenformeln sind.

Liebe Grüße und vielen Dank

PS Ihr würdet im übrigen mindestens 4 Personen helfen falls das ein Anreiz ist ;-)

13.02.2012, 15:57

Math1986

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung
Bitte achte auf die Darstellung deiner Formeln (oberer Summationsindex)
$\begin{eqnarray*} \sum\limits_{k=1}^{n-1} k = \frac{1}{2}(n-1)n \end{eqnarray*}$ und $\begin{eqnarray*} \sum\limits_{k=1}^{n-1} k^2 = \frac{1}{6}(n-1)n(2n-1) \end{eqnarray*}$

Zitat:

$\begin{eqnarray*} \sum\limits_{k=1}^n (2n(n-1)) \end{eqnarray*}$ für die LR Zerlegung und $\begin{eqnarray*} 2* \sum\limits_{k=1}^n n \end{eqnarray*}$

Diese Gleichung in der Summe ist nun aber unabhängig vom Summationsindex verwirrt

Meinst du vielleicht:
$\begin{eqnarray*} \sum\limits_{k=1}^n (2k(k-1)) \end{eqnarray*}$
$\begin{eqnarray*} 2* \sum\limits_{k=1}^n k \end{eqnarray*}$

Wenn ja, kannst du einfach ausklammern und die Summenformeln darauf anwenden (beachte, dass der obere Summenindex bei deiner Lösung bis n geht, ist das richtig so?.

13.02.2012, 16:02

Mig85

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung
Ich denke es ist richtig das der obere Summationsindex bis n geht. Aber das ist ja gerade die Frage sind meine Summen richtig?

Ja es macht natürlich nur sinn wenn die k´s eingefügt sind danke dafür.

Aber ich weiß nicht was du meinst mit ausklammern und einsetzen.

Heisst das erstmal das meine Lösung bis zu diesem Punkt richtig ist?

13.02.2012, 16:14

Math1986

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung

Zitat:

Original von Mig85
Ich denke es ist richtig das der obere Summationsindex bis n geht. Aber das ist ja gerade die Frage sind meine Summen richtig?

Wie gesagt, der obere Index müsste nur bis n-1 gehen.

Poste mal bitte den kompletten Rechenweg.

Zitat:

Aber ich weiß nicht was du meinst mit ausklammern und einsetzen.

$\begin{eqnarray*} \sum\limits_{k=1}^n (2k(k-1)) = \sum\limits_{k=1}^n (2k^2-2k) = 2\sum\limits_{k=1}^n k^2-2\sum\limits_{k=1}^n k \end{eqnarray*}$
Darauf kannst du nun die gegebenen Summenformeln anwenden und erhälst so eine Polynomgleichung.

13.02.2012, 16:33

Mig85

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung
Also zur Berechnung der LR Zerlegung brauche ich bei einer 5x5 Matrix 80 Rechenoperationen. Das hab ich von Hand ausprobiert. Für um in der ersten Spalte 4 Nullen zu erzeugen brauche ich pro Null 10 Operationen. Inder zweiten Spalte......

und deswegen kam ich auf $\begin{eqnarray*} \sum\limits_{k=1}^n k = 2k(k-1) \end{eqnarray*}$ denn wenn man für n=5 einsetzt passt die Summe. Ist das jetzt reiner Zufall das, dass passt? Wenn ich nur bis 4 gehe also n-1 dann kommt 40 raus.

Ok du hast die von mir erstellte Summenformel genommen und ausmultipliziert soweit kann ich folgen, aber wie wende ich eine Summenformel auf eine Summenformel an, ich glaub ich steh aufm Schlauch. Bzw hab ich noch immer nicht verstanden wofür die gegebenen Formeln sind.

13.02.2012, 16:46

Math1986

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung

Zitat:

Original von Mig85
Also zur Berechnung der LR Zerlegung brauche ich bei einer 5x5 Matrix 80 Rechenoperationen. Das hab ich von Hand ausprobiert. Für um in der ersten Spalte 4 Nullen zu erzeugen brauche ich pro Null 10 Operationen. Inder zweiten Spalte......

und deswegen kam ich auf $\begin{eqnarray*} \sum\limits_{k=1}^n k = 2k(k-1) \end{eqnarray*}$ denn wenn man für n=5 einsetzt passt die Summe.

Nein, das passt eben nicht, deine Umformung ist falsch.
Abgesehen davon, dass du wieder mal n mit k verwechselt hast:
Die Summenformel von oben lautet doch ganz anders
Richtig wäre:
$\begin{eqnarray*} \sum_{k=1}^n k = \frac12 n(n+1) \end{eqnarray*}$
(beachte die Verschiebung des oberen Index!)

Also ist:
$\begin{eqnarray*} 1+\ldots+5 = 15 \end{eqnarray*}$
was man auch sehr schnell per Hand hätte nachrechnen können

Zitat:

Original von Mig85
Ist das jetzt reiner Zufall das, dass passt? Wenn ich nur bis 4 gehe also n-1 dann kommt 40 raus.

Wenn du nur bis 4 gehst, dann erhälst du
$\begin{eqnarray*} 1+\ldots+4 = 10 \end{eqnarray*}$

Zitat:

Original von Mig85
Ok du hast die von mir erstellte Summenformel genommen und ausmultipliziert soweit kann ich folgen, aber wie wende ich eine Summenformel auf eine Summenformel an, ich glaub ich steh aufm Schlauch. Bzw hab ich noch immer nicht verstanden wofür die gegebenen Formeln sind.

Ich habe doch (mit Ausnahme des oberen Index) genau die vorgegebenen Summenformeln da stehen.
Was ist dir daran unklar?

13.02.2012, 17:18

Mig85

Auf diesen Beitrag antworten »

RE: Gleitpunktoperationen, Aufwandsabschätzung
Also noch mal Schritt für Schritt:

bei Aufgabe a soll eine allgemein gültige Summenformel erstellt werden mit der man die Anzahl an nötigen Rechenoperationen erhält wenn eine Matrix mit einem Vektor bzw eine Matrix mit einer Matrix multipliziert wird.

meine Lösung ist, wenn A mxn und B lxm

dann gilt für die Anzahl an Operationen l*n*(2m-1)

Im Internet fand ich allerdings die Lösung n³ nun bin ich mir nicht sicher welche richtig ist.

Ich habe mit falkschem Schema eine 2x2 Matrix mit einem Vektor multipliziert und brauchte nur 6 Operationen andere schreiben von 12

$\begin{eqnarray*} \begin{pmatrix} a_1 & a_2 & \\ b_1 & b_2 \\ \end{pmatrix} * \begin{pmatrix} c_1 \\ c_2 \\\end{pmatrix} = \begin{pmatrix} a_1*c_1+a_2*c_2 \\ b_1 * c_1 + b_2 * c_2 \\ \end{pmatrix} \end{eqnarray*}$

oder verplan ich da was?

danach machen wir uns an b hoffe ich strapazier deiner Nerven nicht zu sehr ;-)

Neue Frage »

Antworten »

Gleitpunktoperationen, Aufwandsabschätzung

Verwandte Themen