H. Faßbender

Unter der direkten Lösung linearer Gleichungssysteme versteht man (numerische) Verfahren, welche (bei rundungsfehlerfreier Rechnung) nach endlich vielen Schritten die exakte Lösung eines linearen Gleichungssystems

\begin{eqnarray}Ax=b,\end{eqnarray}

mit

\begin{eqnarray}PA=LR.\end{eqnarray}

Dabei ist P eine Permutationsmatrix, L eine untere Dreiecksmatrix mit Einheitsdiagonale und R eine obere Dreiecksmatrix.

Das Element a_j1, welches im ersten Schritt des Verfahrens bestimmt wird, nennt man Pivotelement, den Teilschritt des Verfahrens daher auch Pivotsuche. Bei der Pivotsuche kann man theoretisch jedes a_k1 ≠ 0 als Pivotelement wählen. Aus Gründen des robusten numerischen Verhaltens empfiehlt es sich jedoch, nicht irgendein a_k1 ≠ 0 zu wählen.

Gewöhnlich trifft man im j-ten Schritt des Verfahrens die Wahl

\begin{eqnarray}|{a}_{kj}|=\mathop{\max }\limits_{i\ge j}|{a}_{ij}|,\end{eqnarray}

man wählt also unter den in Betracht kommenden Elementen der j-ten Spalte das betragsgrößte. Diese Art der Pivotsuche heißt Spaltenpivotsuche oder auch Kolonnenmaximumstrategie.

Das Gauß-Verfahren kann zusammenbrechen, wenn man keine Pivotsuche durchführt. Darüberhinaus ist aus Gründen der numerischen Stabilität eine Pivotsuche ratsam. Es gibt jedoch eine wichtige Klasse von Matrizen, bei der keine Pivotsuche nötig ist: Die Klasse der positiv definiten, symmetrischen Matrizen. Das Gauß-Verfahren läßt sich in diesem Fall durch Ausnutzung der Symmetrie sehr kompakt durchführen (Cholesky-Verfahren).

Besondere Techniken der Pivotisierung erlauben auch für symmetrische, nicht positiv definite Matrizen, die Symmetrie auszunutzen.

Bei exakter Rechnung berechnet das Gauß-Verfahren in endlich vielen Schritten die exakte Lösung des linearen Gleichungssystems Ax = b. Unvermeidliche Rundungsfehler beim Lösen mithilfe eines Rechners bewirken, daß die berechnete Lösung \(\tilde{x}\) nicht exakt die Lösung des gegebenen linearen Gleichungssystems Ax = b ist, sondern die exakte Lösung eines leicht gestörten Gleichungs-systems (A + F)x = b. Durch eine Rundungsfehleranalyse läßt sich die Größe von F abschätzen.

Das Gauß-Verfahren ist hauptsächlich für kleine bis mittelgroße lineare Gleichungssysteme geeignet, bei denen die Matrix A im Hauptspeicher des Rechners gehalten werden kann. Wendet man das Gauß-Verfahren auf sparse Matrizen an, also auf Matrizen mit vielen Nullelementen, werden im Verlauf des Verfahrens zahlreiche Nullelemente durch Nichtnullelemente ersetzt, so daß die resultierenden Matrizen L und R nur wenige Nullelemente im unteren bzw. oberen Dreieck besitzen. Dieses Phänomen der Erzeugung von Nichtnullelementen bezeichnet man auch als fill-in.

Typischerweise sind sparse Matrizen sehr groß, so daß die n² Matrixelemente nicht im Hauptspeicher eines Rechners gehalten werden können, wohl aber die nichtverschwindenden Elemente, wenn man spezielle Speichertechniken verwendet. Aufgrund des fill-ins können beim Gauß-Verfahren dann soviele zusätzliche Nichtnullelemente erzeugt werden, daß diese nicht mehr alle im Hauptspeicher des Rechners Platz finden. Man verwendet dann entweder ein Verfahren zur iterativen Lö-sung linearer Gleichungssysteme oder Varianten des Gauß-Verfahrens, welche mittels heuristischer, auf graphentheoretischen Konzepten basierenden Überlegungen versuchen, den fill-in möglichst gering zu halten.

Neben der LR-Zerlegung ist die QR-Zerlegung der Koeffizientenmatrix A in das Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R eine weitere Zerlegung einer Matrix, welche zur Lösung linearer Gleichungssyteme verwendet werden kann.

Aus Ax = b und A = QR mit Q^TQ = I folgt dann

\begin{eqnarray}Rx={Q}^{T}b,\end{eqnarray}

d. h. wie beim Gauß-Verfahren überführt man das System Ax = b in ein gestaffeltes Gleichungs-system, welches durch Rückwärtseinsetzen gelöst wird. Die Konstruktion einer QR-Zerlegung erfordert gegenüber der LR-Zerlegung einen etwa doppelt so hohen Rechenaufwand. Daher ist dieses Verfahren nicht sehr gebräuchlich zur Lösung linearer Gleichungssysteme.

Eine weitere Möglichkeit, ein lineares Gleichungssystem direkt zu lösen, besteht in der Anwendung der Cramerschen Regel. Dieses Verfahren ist wegen seines hohen Rechenaufwandes und der schlechten numerischen Eigenschaften in der Praxis nicht gebräuchlich. dert gegenüber der LR-Zerlegung einen etwa doppelt so hohen Rechenaufwand. Daher ist dieses Verfahren nicht sehr gebräuchlich zur Lösung linearer Gleichungssysteme.

Eine weitere Möglichkeit, ein lineares Gleichungssystem direkt zu lösen, besteht in der Anwendung der Cramerschen Regel. Dieses Verfahren ist wegen seines hohen Rechenaufwandes und der schlechten numerischen Eigenschaften in der Praxis nicht gebräuchlich.

[4] Schwarz, H.R.: Numerische Mathematik. B.G. Teubner Stuttgart, 1993.

[5] Stoer, J. und Bulirsch, R.: Numerische Mathematik I und II. Springer-Verlag Heidelberg, 1991/1994.