Aufwand einer mathematischen Aufgabe berechnen

Question

ich habe bald eine Numerik Klausur und diese Aufgabe kommt mit einer Wahrscheinlichkeit von 25% genau so dran.

Da ich noch am Anfang des Lernens bin und mit Aufwand Berechnung noch etwas Schwierigkeiten habe, wollte ich fragen, ob mir jemand bei dieser Aufgabe helfen kann. Vielen Dank im voraus.

Es seien A ∈R^(n×n) eine symmetrische und positiv definite Matrix und b(1),b(2),...,b(m) ∈R^n.
Es sei A = LL^T 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 ∈ R^n löst. Anschließend werden x(i) = A^−1b(i) mittels der Matrix-Vektor-
Multiplikation berechnet.

(b) Mit der Cholesky-Zerlegung von A werden die Lösungen von Ax(i) = b(i) für i =
1,2,...,m bestimmt.

Comments

Hallo,

2 Fragen:

1. Müsst Ihr Addition und Multiplikationen / Divisionen separat zählen oder einfach alles nur als Operation?

2. Habt Ihr eine fertige Formel für den Aufwand zur Lösung eines Gleichungssystems, wenn die Matrix eine Dreiecksmatrix ist?

Gruß Mathhilf

---

1.) Addition und Multiplikation werden als eine Operation gezählt, dh.z.b. die Matrix-Vektor Multiplikation einer nxn Matrix hat den Aufwand O(n^2) (dh. n*n Operationen werden durchgeführt) oder die Matrix-Matrix Multiplaikation hat O(n^3).

2.) Nein haben keine Formel um den Aufwand zu berechnen. So wie ich es vertsanden habe, muss man die Operationen zählen.

Answer 1

Hallo,

die Lösung eines Gleichungssystems \(Ax=LL^Tx=b\), erfolgt ja durch Lösung der beiden Systeme \(Ly=b\) und \(L^Tx=y\). Also ist 2-mal ein lineares Gleichungssystem in Dreiecksform zu lösen.

Die Lösung eines solchen Systems besteht aus n Schritten, in Schritt k werden k-1 Multiplikationen und k-1 Additionen ausgeführt und eine abschließende Division also 2k-1 Operationen, insgesamt also

$$\sum_{k=1}^n (2k-1)= n(n+1)-n=n^2$$

Die Berechnung der Vektoren \(A^{-1}e_i\) erfordert dann\(2n^3\) Operationen. Die Berechnung der \(x_i\) braucht dann noch \(2n^3+2n^2m\) Operationen.

Wenn man die \(x_i\) direkt bestimmt, braucht man \(2n^2m\) Operationen.

Hmmh. Da schneidet a) schlecht ab. Kernpunkt ist, dass die Lösung des Gleichungssystems genau so viele Operationen erfordert wie die Matrix-Vektor-Multiplikation. Daher kann a) nicht besser sein.

Musst Du aber mal kritisch überprüfen.

Gruß Mathhilf

Comments

Vielen Dank für deine Antwort!

Ich habe eine kurze Nachfrage und zwar bei (a), nachdem ich mittels Cholesky \(A^{-1}\)

berechnet habe, ist der Aufwand für

\(x_i\) = \(A^{-1}b^{(i)}\)

nicht \(n^2m\) also ohne die 2 davor oder woher kommt diese?

---

Jede neue Komponente der Lösung braucht n Multiplikationen und n Additionen, daher 2n pro Komponente. Ehrlich gesagt weiß ich nicht, ob Multiplikationen und Additionen bei den heutigen Rechnern als gleichgewichtig gelten.