(Twitter)
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.
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
Link
geantwortet
mikn
Lehrer/Professor, Punkte: 38.91K
Lehrer/Professor, Punkte: 38.91K
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
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
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
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
Leider scheint diese Antwort Unstimmigkeiten zu enthalten und muss korrigiert werden.
Mikn wurde bereits informiert.