es seien A∈R^N×N sowie a,b∈R^N für N∈W geben Sie für die folgenden Operationen jeweils deren berechenaufwand in O-Notation an z.B. O(N^2). Dabei seien die für die jeweilige Berechnung notwendigen Voraussetzungen erfüllt. Die Antwort muss nicht begründet werden. a) das Skalarprodukt <a,b> b) die euklidische vektornorm IIxII2 c) das Matrix-Vektor-Produkt A.a d) das Lösen des linearen Gleichungssystems Ax=b mithilfe des Gauß-Algorithmus e) das Zerlegen von A in eine untere Dreiecksmatrix L ∈×∈R N×N und eine obere Dreiecksmatrix R N×N mit =A=L.R f) Das Lösen des linearen Gleichungssystems Ax=b wenn eine Zerlegung aus e) bereits gegeben ist (d.h. L und R sind bereits bestimmt)
meine Lösung/
a) Der Rechenaufwand ist O(N) da jedes Element des einen Vektors mit dem entsprechenden Element des anderen Vektors multipliziert und diese Produkte dann aufsummiert werden.
b) Der Rechenaufwand ist O(N) da jedes Element des Vektors quadriert, diese quadrierten Werte aufsummiert und dann die Quadratwurzel gezogen wird.
c) Der Rechenaufwand ist O(N²) da jede Zeile der Matrix A mit dem Vektor a multipliziert wird, was jeweils NMultiplikationen erfordert, und dies für jede der N Zeilen der Matrix.
d) Der Rechenaufwand ist O(N³) da mehrere Schritte der Größenordnung N² durchgeführt werden müssen, um die Matrix auf obere Dreiecksform zu bringen, und dann noch ein Rücksubstitutionsschritt erforderlich ist.
e) Der Rechenaufwand ist O(N³) da dies ähnliche Operationen wie der Gauß-Algorithmus umfasst.
f) Der Rechenaufwand ist O(N²) da zwei sequenzielle Prozesse der Größenordnung N erforderlich sind: einmal für das Vorwärtseinsetzen mit L und einmal für das Rückwärtseinsetzen mit R
sind die Richtg ! (die Begründung nur zur Erklärung ob ich richtig bin)
Punkte: 48
N skaliert.
b) Länge N erfordert N Quadrierungen und Additionen sowie eine Wurzeloperation, was ebenfalls linear mit
N skaliert
c) Das Matrix-Vektor-Produkt einer NxN Matrix mit einem Vektor der Länge N beinhaltet N Multiplikationen und Additionen für jede der N Zeilen der Matrix.
d) Der Gauß-Algorithmus zum Lösen eines linearen Gleichungssystems umfasst Eliminierungsschritte, die mit der Anzahl der Variablen kubisch wachsen.
e) Die LU-Zerlegung einer NxN Matrix beinhaltet ähnliche Operationen wie der Gauß-Algorithmus und hat daher dieselbe kubische Komplexität.
f) Das Lösen eines linearen Gleichungssystems mit einer bereits durchgeführten LU-Zerlegung beinhaltet das Vorwärtseinsetzen und das Rückwärtseinsetzen, was typischerweise eine quadratische Anzahl von Operationen erfordert. ─ abdull 11.02.2024 um 17:51
Aufwand zur Adressberechnung, Sprünge, Auswertung von if- und anderen Bedingungen etc. zählen hingegen nicht.
Das ist recht grobschlächtig, aber das ist das O-Kalkül ja auch: O(10 N) = O(N).
─ m.simon.539 11.02.2024 um 21:53
https://de.wikipedia.org/wiki/Landau-Symbole#Beispiele_und_Notation ─ abdull 12.02.2024 um 16:57
Die Antwort war wie gezeigt ─ abdull 12.02.2024 um 17:23