Aufwand m LGS mittels gegebener Cholesky-Zerlegung

Aufrufe: 86     Aktiv: 02.09.2021 um 13:42

0
Hey,

ich habe für ein numerisches Verfahren (a)  2n^3+n^2*m Operationen
und für ein Verfahren (b) 2n^2*m Operationen und solle diese vergleichen.
Ich bin mir da etwas unsicher.
Für (a) dachte ich, erhalte ich die landau Schreibweise O(n^3) für n>=m
und O(n^2*m) für m>n.
Für (b) ist es klar, O(n^2*m)

Also habe ich für n>m für (a) mit O(n^3) einen größeren Aufwand als für (b) (O(n^2+m))
Für n=m habe ich für beide Aufwand O(n^3)
und für m>n habe ich für beide Aufwand O(n^2*m).

Habe ich das so richtig interpretiert?
Vielen Dank im vorraus!
gefragt

Punkte: 14

 

Hat niemand eine Idee?   ─   user7be8f1 01.09.2021 um 18:07
Kommentar schreiben
1 Antwort
1
Bei der Landau-Notation geht es um Größenordnungen, die benutzt man, wenn man die Anzahl der Operationen nur asymptotisch kennt. Hier kennt man aber die Anzahl der Operationen genau (jedenfalls sagst Du das, mich würde die Aufgabenstellung im Original interessieren).
Es ist hier also nicht sinnvoll mit O(...) zu argumentieren. Eine Möglichkeit wäre einfach Aufwand a) durch Aufwand b) zu dividieren. Dann sieht man sehr schön, was in welcher Situation größer ist.
Aber wie gesagt: Bitte erstmal die Aufgabenstellung im Original, sonst bleibt eine Antwort spekulativ.
Ich weiß auch gar nicht, was bei einem LGS, also nxn-LGS, das m sein soll.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 16.14K

 

Hier die Aufgabe:

Es seien A ∈R^(n×n) eine symmetrische und positiv definite Matrix und b(1),b(2),...,b(m) ∈Rn.
Es sei A = LLT die Cholesky-Zerlegung von A mit der unteren Dreiecksmatrix L ∈ R^(n×n).
Vergleichen Sie den Aufwand der folgenden beiden Vorgehensweisen zur Lösung der m linearen
Gleichungssysteme Ax(i) = b(i) ,i = 1,2,...,m:

(a) Man bestimmt zuerst die Inverse A^(−1) = (z(1),z(2),...,z(n)), indem man n lineare Glei-
chungssysteme Az(j) = ej mit der Cholesky-Zerlegung von A für die kanonischen Basis-
vektoren ej ∈ Rn löst. Anschließend werden x(i) = A^(−1)*b(i) mittels der Matrix-Vektor-
Multiplikation berechnet.

=> Hier erhalte ich 2n^3 für Berechnung von A^(-1) mittels Lösung n-LGS mittels Cholesky-Zerlegung (2n^2 für Lösung eines LGS mittels Cholesky, da lösen von zwei LGS in Dreiecksform)
und die Matrix Vektor Multpilkation benötigt nach Vorlesung n^2 Operationen, also da m- Vektoren x^(i) berechnet werden, n^(2)*m
=> insgesamt für(a) also 2n^3+ n^(2)*m

(b) Mit der Cholesky-Zerlegung von A werden die Lösungen von Ax(i) = b(i) für i =
1,2,...,m bestimmt
=> mit Cholesky Zerlegung werden 2 LGS in Dreiecksform gelöst, also 2n^2
=> da m LGS gelöst werden müssen, 2n^2*m
  ─   user7be8f1 02.09.2021 um 08:41

Aha, so wird das schon viel klarer. Die Frage zielt darauf ab (steht da nicht so, aber ist wohl so gemeint), ab wann sich die Berechnung der Inversen lohnt. Also: ab welchem m.
Lösen eines LGS in Dreiecksform benötigt n(n+1)/2 Op, wenn Du Deine Überlegungen entsprechend korrigierst (Rest stimmt so) und die Hinweise in meiner Antwort oben berücksichtigst, wird es relativ einfach.
  ─   mikn 02.09.2021 um 12:31

Lösen eines LGS in Dreiecksform benötigt aber doch n Schritte:
In Schritt k werden (k-1) Multiplikationen und (k-1) Subtraktionen durchgeführt, sowie eine abschließende Divison also 2*(k-1)+1=2k-1.
Insgesamt dann \(\sum_{k=1}^n (2k-1)= n(n+1)-n=n^2\).
Haben wir so auch in der Vorlesung bewiesen.
  ─   user7be8f1 02.09.2021 um 13:14

Achso. Ich war von Multiplikationen angegeben. Man sollte immer die komplette Aufgabenstellung angeben (was ist m? Was sind Operationen?). Die Def. von "Operation" ist nicht einheitlich.
Wenn man nicht nur Mult./Div. zählt, sondern auch Add./Subtr. mitzählt, kommt man aber auch auf andere Zahlen. Dann ist z.B. Matrix*Vektor auch nicht n^2 Operationen, sondern n^2 Multiplikationen PLUS einige Additionen. Und beim Lösen der Systeme mit den Einheitsvektoren als rechte Seite gibt es etwas weniger Additionen als normal wg der Nullen.
Kurz: Mit dem Zählen auch der Add./Subtr. wird die ganze Rechnung komplizierter. Das hängt jetzt an der genauen Definition der Begriffe "Aufwand", "Operation" in der Vorlesung.
  ─   mikn 02.09.2021 um 13:42

Kommentar schreiben