Das Gauß-Jordansche Eliminationsverfahren
Wir stellen nun ein Lösungsverfahren für unsere Gleichungssysteme vor. Der Verfahrenstyp wird oft als Gauß-Jordansches Eliminationsverfahren bezeichnet, seine Ursprünge reichen aber bis in die vorchristliche chinesische Mathematik zurück. Den Ausgangspunkt bildet die Beobachtung, dass sich der Lösungsraum eines Gleichungssystems
a1, 1 x1 + a1, 2 x2 + … + a1, n xn = b1, (Gleichung 1)
a2, 1 x1 + a2, 2 x2 + … + a2, n xn = b2, (Gleichung 2)
… …
am, 1 x1 + am, 2 x2 + … + am, n xn = bm. (Gleichung m)
durch die folgenden vier elementaren Operationen nicht ändert:
| (Ei′ = α · Ei) | Multiplikation der i-ten Gleichung mit α ∈ K, α ≠ 0. |
| (Ei′ = Ei + α Ej) | Addition des α-fachen der j-ten zur i-ten Gleichung, i ≠ j. |
| (σi, j) | Vertauschung der i-ten und der j-ten Gleichung. |
| (πi, j) | Vertauschung der i-ten und der j-ten Spalte des Systems (einschließlich der Variablen xi und xj). |
Die ersten drei dieser Operationen können wir analog auch für Matrizen ausführen, indem wir „n-te Gleichung“ durch „n-te Zeile“ ersetzen. Bei der Spaltenvertauschung ist dagegen etwas Umsicht geboten, da in Matrizenschreibweise keine benannten Variablen mehr zur Verfügung stehen. Wir können aber Spaltenvertauschungen auch für Matrizen zulassen, wenn wir nebenbei mitschreiben, welche Vertauschungen wir durchgeführt haben. Dann geht keinerlei Information verloren und wir können Matrizen weiterhin als bequeme Notation für Gleichungssysteme ansehen.
Wir streben durch wiederholte Ausführung dieser Operationen folgende Form an:
Definition (Dr-Form)
Eine (m × n)-Matrix A ist in Dr-Form für ein 0 ≤ r ≤ min(m, n), falls gilt:
| (i) | ai, i = 1 | für alle 1 ≤ i ≤ r, |
| (ii) | ai, j = 0 | für alle 1 ≤ i, j ≤ r mit i ≠ j, |
| (iii) | ai, j = 0 | für alle i, j mit r < i ≤ m. |
In einer derartigen Matrix steht also links oben die (r × r)-Diagonalmatrix Dr, deren Diagonale mit Einsen bestückt ist und die außerhalb ihrer Diagonale nur Null-Einträge aufweist. Weiter sind alle Einträge in den Zeilen r + 1, …, m der Matrix gleich 0.
Der Lösungsraum eines Gleichungssystems in Dr-Form lässt sich nun aus der erweiterten Koeffizientenmatrix direkt ablesen:
Satz (Lösungsraum für Dr-Formen)
Sei A x = b ein Gleichungssystem mit einer (m × n)-Matrix A = (aij)ij in Dr-Form. Sei L der Lösungsraum des Systems. Dann gilt:
Ist bi ≠ 0 für ein i mit r < i ≤ m, so ist das System unlösbar.
Andernfalls ist der Kn-Vektor b* = (b1, …, br, 0, …, 0) ∈ L, und es gilt:
(a) | Ist r = n, so ist L = { b* }. |
(b) | Ist r < n, so ist L = L0 + b* mit dem folgenden Lösungsraum L0 des homogenen Systems A x = 0: L0 = { αr + 1 yr + 1 + … + αn yn | αi ∈ K für alle r < i ≤ n }, wobei yi = (− a1 i, …, − ar i, 0, …, 0) + ei ∈ Kn für alle r < i ≤ n. |
Beweis
Wir zeigen, dass in (b) jede Lösung von A x = 0 ein Element von L0 ist. (Die anderen Behauptungen des Satzes sind unschwer einzusehen.). Sei also (α1, …, αn) eine beliebige Lösung von A x = 0. Dann gilt
αi + ∑r < j ≤ n ai j αj = 0 für alle 1 ≤ i ≤ r,
und damit ist
(α1, …, αn) = αr + 1 yr + 1 + … + αn yn ∈ L0.
Wir zeigen nun, dass wir durch unsere vier Operationen eine Dr-Form erreichen können:
Satz (Eliminationsverfahren)
Sei A x = b ein Gleichungssystem einer (m × n)-Matrix A = (ai j)i j.
Dann lässt sich (A, b) durch die vier elementaren Operationen in die Form (A′, b′) überführen mit A′ in Dr-Form für ein r ≤ min(m, n).
Ist π = πk ∘ … ∘ π1 : { 1, …, n } → { 1, …, n } die Bijektion der durchgeführten Spaltenvertauschungen π1, …, πk, so gilt
L = { π−1(x) | x ∈ L′ },
für die Lösungsräume L von A x = b und L′ von A′ x = b′.
Beweis
Wir konstruieren rekursiv (Ai, bi) für i = 0, 1, …, r, r ≤ min(n, m).
Dabei ist die j-te Spalte von Ai der Vektor ej ∈ Km für alle 1 ≤ j ≤ i.
Zu Beginn sei (A0, b0) = (A, b). Sei nun (Ai, bi) konstruiert für ein i ≥ 0.
Ist Ai in Di-Form, so ist (A′, b′) = (Ai, bi) mit r = i wie gewünscht.
Andernfalls existieren Indizes i*, j* > i mit Ai(i*, j*) ≠ 0.
Nach einer evtl. Zeilenvertauschung gefolgt von einer evtl. Spaltenvertauschung können wir also annehmen, dass Ai(i + 1, i + 1) ≠ 0.
Durch Zeilenmultiplikation und -addition können wir nun die (i + 1)-te Spalte der Matrix (Ai, bi) in den Spaltenvektor ei + 1 überführen. Mit der so entstehenden Matrix (Ai + 1, bi + 1) wiederholen wir das Verfahren.
Das Verfahren produziert eine Matrix (A′, b′) = (Ar, br) mit A′ in Dr-Form.
Eine Induktion nach i ≤ r zeigt, dass
L = { (πk(i) ∘ … ∘ π1)−1(x) | x ∈ Kn, Ai x = bi },
wobei π1, …, πk(i) die Spaltenvertauschungen sind, die bis zum i-ten Schritt durchgeführt wurden. Dies zeigt die Behauptung über den Lösungsraum.
Wir können das im Beweis enthaltene Verfahren leicht deterministisch machen und so einen „Algorithmus von Gauß-Jordan“ erhalten, indem wir im Rekursionsschritt i* und j* geeignet minimal wählen. Gilt Ai(i + 1, i + 1) ≠ 0, so sind gar keine Vertauschungen notwendig. Ist Ai(i*, i + 1) ≠ 0 für ein i* > i, so genügt eine Zeilenvertauschung. Wir können damit die Anzahl der Spaltenvertauschungen so gering wie möglich halten.
Das Verfahren zeigt für quadratische Matrizen:
Korollar (Überführung in Diagonalform)
Sei A eine (n × n)-Matrix. Dann sind äquivalent:
(a) | fA : Kn → Kn ist bijektiv. |
(b) | A lässt sich mit Hilfe der ersten drei elementaren Operationen in die Diagonalmatrix Dn überführen. |
Beweis
Die Aussage ist klar, falls wir alle vier Operationen zulassen. Wird aber eine Vertauschung der (i + 1)-ten Spalte im Rekursionsschritt notwendig, so bleibt diese Spalte eine Spalte von
Ai + 1, …, Ar,
da alle ihre Komponenten ab der Stelle i + 1 gleich 0 sind.
Folglich ist A′(n, n) = 0, d. h. es gilt r < n. Damit ist aber A′ x = b′ unlösbar für alle b′, deren n-te Komponente von 0 verschieden ist. Also ist A x = b nicht für alle b lösbar, und damit ist fA nicht bijektiv.
Wir führen zur Illustration das Eliminationsverfahren nun noch für das folgende Gleichungssystem mit K = ℚ durch. Die erweiterte Koeffizientenmatrix (A0, b0) ist rechts notiert.
x1 | − | x2 | + | x3 | = | − 1 | |||
x1 | − | x2 | − | x4 | = | 1 | |||
− | x3 | − | x4 | = | 2 | ||||
− | 2 x1 | + | 2x2 | + | x3 | = | − 1 |
1 | − 1 | 1 | 0 | | | − 1 |
1 | − 1 | 0 | − 1 | | | 1 |
0 | 0 | − 1 | − 1 | | | 2 |
− 2 | 2 | 1 | 0 | | | − 1 |
Zuerst berechnen wir (A1, b1) durch „Ausräumen der ersten Spalte“:
1 | − 1 | 1 | 0 | | | − 1 |
0 | 0 | − 1 | − 1 | | | 2 |
0 | 0 | − 1 | − 1 | | | 2 |
0 | 0 | 3 | 0 | | | − 3 |
(A1, b1)
1 | 0 | 1 | − 1 | | | − 1 |
0 | − 1 | − 1 | 0 | | | 2 |
0 | − 1 | − 1 | 0 | | | 2 |
0 | 0 | 3 | 0 | | | − 3 |
Spaltentausch π2, 4
Wir notieren nun den Spaltentausch π2, 4 und berechnen dann (A2, b2):
1 | 0 | 1 | − 1 | | | − 1 |
0 | 1 | 1 | 0 | | | − 2 |
0 | 0 | 0 | 0 | | | 0 |
0 | 0 | 3 | 0 | | | − 3 |
(A2, b2)
1 | 0 | 1 | − 1 | | | − 1 |
0 | 1 | 1 | 0 | | | − 2 |
0 | 0 | 3 | 0 | | | − 3 |
0 | 0 | 0 | 0 | | | 0 |
Zeilentausch σ3, 4
Wir tauschen die dritte und vierte Zeile und erhalten nun (A3, b3) in D3-Form, indem wir die Koordinate (3, 3) auf 1 normieren und dann oberhalb dieser Koordinate „ausräumen“:
1 | 0 | 0 | − 1 | | | 0 | ||
0 | 1 | 0 | 0 | | | − 1 | L′ = { α (1, 0, 0, 1) | α ∈ ℚ } + (0, − 1, − 1, 0). | |
0 | 0 | 1 | 0 | | | − 1 | L = { α (1, 1, 0, 0) | α ∈ ℚ } + (0, 0, − 1, − 1). | |
0 | 0 | 0 | 0 | | | 0 |
(A3, b3) = (A′, b′)
Den Lösungsraum L′ von A3 x = b3 lesen wir ab, und Vertauschung der Koordinaten 2 und 4 liefert den Lösungsraum L des ursprünglichen Systems A x = b.