Traditionelle Lösung von Ax = b

"Naive" Gauß-Elimination

Gleichungssysteme mit einer regulären unteren bzw. oberen Dreiecksmatrix als Koeffizientenmatrix sind durch Vorwärts- bzw. Rückwärtssubsitution direkt (mit je n^2 Operationen) zu lösen.

Die Idee des Gauß-Algorithmus' (siehe Anhang C.1) ist daher, die (reguläre) Koeffizientenmatrix A auf die Form A = LR zu bringen, wobei L bzw. R eine untere bzw. obere Dreiecksmatrix darstellt. Ist der Algorithmus durchführbar (d.h. A_{kk}^{(k)} <> 0 für k=1,\,2,\,...,\,n-1), so kann man ein n × n-Gleichungssystem mit Hilfe von \frac23n^3 + O(n^2) Operationen lösen.

Gleichzeitig liefert der Gauß-Algorithmus (sofern er durchführbar ist) eine LR-Zerlegung von A (d.h. eine Darstellung der Form A = LR, wobei L bzw. R eine untere bzw. obere Dreiecksmatrix ist) vermöge

L_{jk} & := & \{ \begin{array}{cl}\frac{A_{jk}^{(k)}{......s \\ [0.5ex]0 & *s & 0 & A_{nn}^{(n)}\end{array} )

Ist A in R^{n × n} strikt diagonaldominant, d.h. es gilt

sum_{j=1}\atop{j <> k}^n | A_{kj}| < | A_{kk}|   forall \, k in \{1,\,2,\,...,\,n\}

so ist der Gauß-Algorithmus durchführbar.

Oft hat man mit nur schwach besetzten Matrizen zu tun, d.h. nur "wenige" Elemente sind ungleich Null. Diese Matrizen werden im Sparse-Format gespeichert, d.h. abgespeichert wird (j,k,A_{jk}) für alle NNE (Nicht-Null-Elemente). Führt man dann allerdings den Gauß-Algorithmus durch, so kommt es zum Fill-In, d.h. es entstehen zahlreiche neue NNE, die abgespeichert werden müssen. Die sogenannte Skyline-Technik berücksichtigt dieses Phänomen, indem nur die Diagonalelemente und solche A_{jk}, für die entweder ein Eintrag A_{jl} <> 0 (mit 1 <= l <= k < j) oder ein Eintrag A_{lk} <> 0 (mit 1 <= l <= j < k) ist, gespeichert werden.


 Diese Seite erfüllt die HTML-4.01-Spezifikationen!
Übersicht
Zurück Home Weiter
Index