Der Gauss’sche Algorithmus

Lesedauer: 13 min | Vorlesen | Autor: Dr. Volkmar Naumburger

Auch wenn die Einführung der Determinanten in die Lösung linearer Gleichungssysteme deutlich zur Lösungsrationalisierung beigetragen hat, ist das Lösen von Determinanten mit einem Rang > 3 mit Hilfe der Entwicklung in Adjunkte sehr mühevoll. Deshalb wird nach Algorithmen gesucht, die insbesondere in der numerischen Mathematik erfolgversprechende Ansätze liefern können. Dazu ist der Gauss’sche Algorithmus zu zählen. Dazu zeigt Gl. 97 bereits einen Ansatz für den nach Gauss benannten Algorithmus.

Die Übertragung weiterer Eigenschaften von Determinanten auf die Lösung von LGS kann diese sehr stark vereinfacht werden.

Durch Anwendung von Gl. 79 weist den Weg zu einer Schritt weisen Wandlung zu einem LGS ähnlich einer Dreiecksdeterminante. Beispielhaft wird der Lösungsalgorithmus an einem linearen Gleichungssystem mit drei Variablen abgeleitet. Gl. 98 zeigt die Ausgangsgleichungen:

\( \begin{array}{l}I. & {a_{11} }x + {a_{12} }y + {a_{13} }z = {c_1}\\II. & {a_{21} }x + {a_{22} }y + {a_{23} }z = {c_2}\\III. & {a_{31} }x + {a_{32} }y + {a_{33} }z = {c_3}\end{array} \) Gl. 98

Zunächst werden die Koeffizienten der Gln. II und III so modifiziert, dass ein Subtraktion der Gl. I von den Gln. II und III dazu führt, dass die x-Terme dieser Gleichungen verschwinden:

\(\begin{array}{l}I. & {a_{11} }x + {a_{12} }y + {a_{13} }z = {c_1}\\II. & {a_{21} }x + {a_{22} }y + {a_{23} }z = {c_2} & & & | \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } }\\III. & {a_{31} }x + {a_{32} }y + {a_{33} }z = {c_3} & & & | \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } }\end{array}\) Gl. 99

\(\begin{array}{l}I. & {a_{11} }x + {a_{12} }y + {a_{13} }z = {c_1}\\II. & {a_{11} }x + {a_{22} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } }y + {a_{23} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } }z = {c_2} \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } & & |II - I\\III. & {a_{11} }x + {a_{32} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } }y + {a_{33} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } }z = {c_3} \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } & & |III - I\end{array}\) Gl. 100

\(\begin{array}{l}I. & {a_{11} }x\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + {a_{12} }y\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, + {a_{13} }z = {c_1}\\II. & 0 + \left( { {a_{22} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {a_{12} } } \right)y + \left( { {a_{23} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {a_{13} } } \right)z = {c_2} \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {c_1} & \\III. & 0 + \left( { {a_{32} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {a_{12} } } \right)y + \left( { {a_{33} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {a_{13} } } \right)z = {c_3} \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {c_1} & \end{array}\) Gl. 101

Zur besseren Übersicht werden die Klammerausdrücke durch alternative Koeffizienten ersetzt:

\(\begin{array}{l}I. & {a_{11} }x\,\, + {a_{12} }y\,\, + {a_{13} }z = {c_1}\\II. & 0\,\,\,\,\,\,\,\, + a_{_{11} }^1y + a_{_{12} }^1z = c_{_1}^1 & \\III. & 0\,\,\,\,\,\,\,\, + a_{_{21} }^1y + a_{22}^1z = c_{_2}^1 & \end{array}\) mit \(\begin{array}{l}c_{_1}^1 = {c_2}\frac{ { {a_{11} } } }{ { {a_{21} } } } - {c_1} & \\c_{_2}^1 = {c_3}\frac{ { {a_{11} } } }{ { {a_{31} } } } - {c_1} & \end{array}\)*) Gl. 102

*) Die hochgestellten Indize in den \(a_{ik}^1;\,\,\,c_i^1\) bedeuten, dass \(a_{ik}^1;\,\,\,c_i^1\) Ergebnis des ersten Rekursionsschrittes sind.

Im folgenden Schritt ist die y-Position der Gl. III zu räumen. Dazu wird Gl. III mit dem Faktor \(\frac{ {a_{_{11} }^1} }{ {a_{_{21} }^1} }\) beidseitig erweitert und um Gl. II vermindert:

\(\begin{array}{l}II. & a_{_{11} }^1y\,\,\, + \,\,\,\,\,\,\,\,\,\,\,\,a_{_{12} }^1z\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, = c_{_1}^1 & \\III. & \,0\,\,\,\,\,\,\,\,\, + \left[ {a_{_{22} }^1\frac{ {a_{_{11} }^1} }{ {a_{_{21} }^1} } - a_{_{12} }^1} \right]z = c_{_2}^1\frac{ {a_{_{11} }^1} }{ {a_{_{21} }^1} } - c_{_1}^1 & \end{array}\) Gl. 103

Wieder werden die verbleibenden Koeffizienten durch neue Bezeichner ersetzt:

\(\begin{array}{l}II. & a_{11}^1y\,\,\, + \,\,\,\,\,\,\,\,\,\,\,\,a_{12}^1z\,\,\,\,\,\,\,\,\,\, = c_1^1 & \\III. & \,0\,\,\,\,\,\,\,\,\, + \,\,\,\,\,\,\,\,\,\,\,\,\,a_1^2z\,\,\,\,\,\,\,\,\,\, = c_1^2 & \end{array}\) mit \(c_1^2 = c_2^1\frac{ {a_{11}^1} }{ {a_{21}^1} } - c_1^1 \) Gl. 104

Die hochgestellten Indize signalisieren, dass es sich nunmehr um Ergebnisse des zweiten Rekursionschrittes handelt.

Ausmultiplizieren ergibt das gesuchte Gleichungssystem in der Dreiecksgestalt:

\(\begin{array}{l}I. & {a_{11} }x\,\,\,\, + \,\,\,\,{a_{12} }y\,\,\,\,\,\,\, + \,\,\,\,\,\,\,\,{a_{13} }z = {c_1}\\II. & 0\,\,\,\,\,\,\,\,\,\, + \,\,\,\,a_{_{11} }^1y\,\,\,\,\,\, + \,\,\,\,\,\,\,a_{_{12} }^1z = c_1^1 & \\III. & 0\,\,\,\,\,\,\,\,\,\, + \,\,\,\,\,\,\,\,0\,\,\,\,\,\,\,\,\, + \,\,\,\,\,\,\,a_{11}^2z = c_1^2 & \end{array}\) Gl. 105

Lösung

a) Es ist offenbar, dass zur Lösung des Gleichungssystems zunächst aus Gl. III die Lösung für z, dann durch Einsetzen von z in Gl. II y und zuletzt durch Einsetzen von z und y in Gl. I x gefunden wird.

b) Für den Fall, dass nur der Wert der Koeffizientendeterminante gesucht ist, gilt das für Gl. 97 Gesagte:

\(D = {a_{11} } \cdot a_{11}^1 \cdot a_{11}^2 \cdot ....\) Gl. 106

All die hierfür erforderlichen Schritte sind leicht formalisierbar, so dass selbst große Determinanten rekursiv gelöst werden können.

Achtung: Das Gausssche Verfahren beinhaltet Quotienten, wie z.B. \(\frac{ { {a_{11} } } }{ { {a_{21} } } };\,\,\frac{ { {a_{11} } } }{ { {a_{31} } } }\). Damit besteht die Gefahr einer Division durch 0! Dem kann dadurch begegnet werden, dass durch geeignetes Vertauschen (Pivotisierung) von Zeilen oder Spalten nur durch Elemente ungleich 0 dividiert wird.

Beispiel:

Gegeben sei das Gleichungssystem

\( \begin{array}{l} I. & x + y + z = 3 \\ II. & y - z = 1 \\ III. & x - y + z = - 1 \end{array} \)

Gesucht sind der Wert der Koeffizientendeterminante und die Lösungen des Gleichungssystems.

Rekursion/1. Schritt

Untersuchung auf Divisionen durch 0:

Element a21=0 d.h. Pivotisierung ist erforderlich. Es werden die erste und dritte Spalte gegeneinander vertauscht:

\( \begin{array}{l} I. & z + y + x & = 3 \\ II. & - z + y & = 1 \\ III. & z - y + x & = -1 \end{array} \)

(Diese Vertauschung bleibt ohne jegliche Konsequenz, da für die Addition das Kommutativgesetz gilt.)

Daraus folgen:

\( a_{11}^1 = \left( { {a_{22} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {a_{12} } } \right) = 1\frac{1}{ { - 1} } - 1 = - 2; \\ a_{12}^1 = \left( { {a_{23} } \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {a_{13} } } \right) = 0\frac{1}{ { - 1} } - 1 = - 1; \\ c_1^1 = {c_2} \cdot \frac{ { {a_{11} } } }{ { {a_{21} } } } - {c_1} = 1\frac{1}{ { - 1} } - 3 = - 4; \\ a_{21}^1 = \left( { {a_{32} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {a_{12} } } \right) = 1\frac{1}{ { - 1} } - 1 = - 2; \\ a_{22}^1 = \left( { {a_{33} } \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {a_{13} } } \right) = 1\frac{1}{1} - 1 = 0; \\ c_2^1 = {c_3} \cdot \frac{ { {a_{11} } } }{ { {a_{31} } } } - {c_1} = -1\frac{1}{1} - 3 = - 4; \)

2. Schritt:

Untersuchung auf Divisionen durch 0 :

Außer a112=0 kein relevantes Element =0, d.h. Pivotisierung nicht erforderlich.

\( a_{11}^2 = \left( {a_{_{22} }^1\frac{ {a_{_{11} }^1} }{ {a_{_{21} }^1} } - a_{_{12} }^1} \right) = 0\frac{ { - 2} }{ { - 2} } - ( - 1) = 1 \\ c_1^2 = c_{_2}^1\frac{ {a_{_{11} }^1} }{ {a_{_{21} }^1} } - c_{_1}^1 = - 4\frac{ { - 2} }{ { - 2} } - ( - 4) = 0 \)

Lösung:

a) \(D = {a_{11} } \cdot a_{11}^1 \cdot a_{11}^2 = 1 \cdot \left( { - 2} \right) \cdot 1 = - 2\)

b) \( x = \frac{ {c_1^2} }{ {a_{11}^2} } = \frac{0}{1} = 0 \\ y = \frac{ {c_1^1 - a_{12}^1x} }{ {a_{11}^1} } = \frac{ { - 4 - \left( { - 1} \right) \cdot 0} }{ { - 2} } = 2 \\ z = \frac{ { {c_1} - {a_{12} }y - {a_{13} }x} }{ { {a_{11} } } } = \frac{ {3 - 1 \cdot 2 - 1 \cdot 0} }{1} = 1 \)

  Hinweis senden