0/14

15 Reelle Matrizen

0/14/4

15.4 Gauß’scher Algorithmus

0/14/4/1

15.4.2 Lösungsschritte des Gauß’schen Algorithmus

Die Lösung eines linearen Gleichungssystems $A \cdot \vec{x} = \vec{c}$ erfolgt durch Umformung in zwei, ggf. drei Schritten:
I. Vorwärtselimination mit
Ia. eventueller Pivotisierung (d.h. Vertauschen von Zeilen, bis die Diagonalelemente $\neq 0$ )
II. Rückwärtselimination

I. Vorwärtselimination

1.

Eliminationsschritt: (

a_{11} \neq 0

)

subtrahiere	$a_{21} ∕ a_{11}$ -fache der 1.Zeile von 2.Zeile
⋮	$a_{31} ∕ a_{11}$ -fache der 1.Zeile von 3.Zeile
⋮	⋮

Durch den ersten Eliminationsschritt entstehen in der 1. Spalte der Matrix Nullen, außer

a_{1} 1

sind alle

a_{i} 1 = 0

2.

Eliminationsschritt: (

a_{22} \neq 0

)

subtrahiere	$a_{32} ∕ a_{22}$ -fache der 2.Zeile von 3.Zeile
⋮	$a_{42} ∕ a_{22}$ -fache der 2.Zeile von 4.Zeile
⋮	⋮

3.

Solange wiederholen, bis die Dreiecksform vorliegt. (Die Koeffizienten der Matrix in Dreiecksform werden ab hier der Übersichtlichkeit halber mit Koeffizienten

{a^{'}}_{i k}

bzw.

{c^{'}}_{i}

bezeichnet.)

Ia. Pivotisierung

1.: Das Gauß-Verfahren versagt, falls das Diagonalelement oder Pivotelement (engl. für Dreh- und Angelpunkt) $a_{k k}$ eines Eliminationsschrittes gleich Null ist, $a_{k k} = 0$ (Abbruch des Verfahrens bei Division durch Null).
2.: Pivotsuche: Ist ein Diagonalelement $a_{k k} = 0$ , so vertauscht man die Pivot-Zeile k vor Ausführung des k-ten Eliminationsschrittes mit derjenigen Zeile $m > k$ , die den betragsmäßig größten Koeffizienten für $x_{k}$ besitzt:
3.: Neue Pivotzeile $m$ , neues Pivotelement $a_{m k}$ .

II. Rückwärtselimination
Aus der Dreiecksform werden die Lösungen $x_{i}$ durch schrittweises Rückwärtseinsetzen gewonnen:

1.: Zuerst die unterste Zeile nach $x_{n}$ auflösen.
2.: Die anderen Elemente $x_{i}, i = n - 1, \dots, 1$ des Lösungsvektors $x$ bestimmt man dann rekursiv mit der Gleichung $x_{n} =$ $\frac{{c^{'}}_{n}}{{a^{'}}_{n n}}$ , $x_{i} = \frac{{c^{'}}_{i}}{{a^{'}}_{i i}} - \sum_{k = i + 1}^{n} x_{k} \cdot \frac{{a^{'}}_{i k}}{{a^{'}}_{i i}}, i = n - 1, \dots, 1$

.
Sei $A$ eine $4 x 4$ -Matrix, dann lautet das Gleichungssystem $A \cdot \vec{x} = \vec{c}$ mit dem unbekannten Vektor $\vec{x} = {(x_{-} 1, x_{2}, \dots x_{n})}^{T}$ :

$a_{11} x_{1}$	$+$	$a_{12} x_{2}$	$+$	$a_{13} x_{3}$	$+$	$a_{14} x_{4}$	$=$	$c_{1}$
		$a_{22} x_{2}$	$+$	$a_{23} x_{3}$	$+$	$a_{24} x_{4}$	$=$	$c_{2}$
				$a_{33} x_{3}$	$+$	$a_{34} x_{4}$	$=$	$c_{3}$
						$a_{44} x_{4}$	$=$	$c_{4}$

x_{4}

erhält man aus der letzten Zeile:

x_{4} = \frac{c_{4}}{a_{44}}

Der Wert für

x_{4}

wird in die vorletzte Zeile eingesetzt, diese nach

x_{3}

aufgelöst:

x_{3} = \frac{c_{3} - a_{34} x_{4}}{a_{33}}

.
.
Das gleiche Schema wird auf die darüberliegenden Zeilen angewandt, bis alle Werte von

\vec{x}

bestimmt sind.