Lineares Gleichungssystem

Grundidee und Aufbau

Ein lineares Gleichungssystem (LGS) ist eine Menge linearer Gleichungen mit einer oder mehreren Unbekannten. Gesucht sind Werte für die Unbekannten, die alle Gleichungen gleichzeitig erfüllen. Eine Lösung wird als n-Tupel beziehungsweise Lösungsvektor aufgefasst.

Allgemein besteht ein LGS aus m Gleichungen und n Unbekannten: a₁,₁x₁ + a₁,₂x₂ + … + a₁,ₙxₙ = b₁, … aₘ,₁x₁ + aₘ,₂x₂ + … + aₘ,ₙxₙ = bₘ.

Ein System heißt homogen, wenn alle bᵢ = 0 sind. Es besitzt dann immer die triviale Lösung, bei der alle Variablen 0 sind. Andernfalls heißt es inhomogen; bei einem solchen System kann es auch keine Lösung geben.

Geometrische und matrixbezogene Sicht

In der spaltenweisen Interpretation werden die Zahlen einer Spalte als Koeffizienten eines Vektors aⱼ aufgefasst. Gesucht sind Zahlen xⱼ, sodass x₁a₁ + x₂a₂ + … + xₙaₙ = b. Das bedeutet: Der Lösungsvektor b soll als Linearkombination der Spaltenvektoren dargestellt werden.

In der zeilenweisen Interpretation beschreibt jede Gleichung eine affine Hyperebene in einem n-dimensionalen Vektorraum. In zwei Dimensionen sind solche Hyperebenen Geraden, im dreidimensionalen Raum Ebenen. Die Lösungsmenge ist der gemeinsame Schnitt aller Hyperebenen. Beide Sichtweisen ergänzen sich; der Satz von Kronecker-Capelli folgt etwa unmittelbar aus der spaltenweisen Betrachtung.

Für die Matrixdarstellung werden die Koeffizienten zur Koeffizientenmatrix A, die Unbekannten zum Spaltenvektor x und die rechten Seiten zum Spaltenvektor b zusammengefasst. Das LGS lautet dann A·x = b mit A ∈ K^(m×n), b ∈ K^m und x ∈ K^n. Zur vollständigen Festlegung genügt die erweiterte Koeffizientenmatrix (A|b), die durch Anhängen der Spalte b an A entsteht.

Lösbarkeit und typische Fälle

Über einem unendlichen Körper K gibt es genau drei Möglichkeiten: keine Lösung, genau eine Lösung oder unendlich viele Lösungen. Über einem endlichen Körper ist die Anzahl der Lösungen eine Potenz der Mächtigkeit von K.

Geometrisch entsprechen diese Fälle beispielsweise zwei Geraden in der Ebene, die sich in einem Punkt schneiden, parallel und verschieden sind oder identisch verlaufen. Für 2x₁ − x₂ = 4 und x₁ + 3x₂ = −5 sind die Normalenvektoren nicht kollinear; die Geraden schneiden sich genau einmal bei (1 | −2), also L = {(1,−2)}.

Bei 2x₁ − x₂ = 4 und 4x₁ − 2x₂ = 1 sind die Normalenvektoren kollinear, die Geraden aber verschieden. Es gibt keine Lösung, L = {}. Bei 2x₁ − x₂ = 4 und 4x₁ − 2x₂ = 8 sind die Geraden identisch. Daher gibt es unendlich viele Lösungen: L = {(x₁,x₂) | 2x₁ − x₂ = 4}. Die Überlegungen lassen sich auf Ebenen und Hyperebenen übertragen.

Kriterien und Lösungsmenge

Nach dem Satz von Kronecker-Capelli ist ein LGS genau dann lösbar, wenn der Rang der Koeffizientenmatrix A gleich dem Rang der erweiterten Koeffizientenmatrix (A|b) ist. Sind beide Ränge außerdem gleich der Anzahl n der Unbekannten, gibt es genau eine Lösung.

Für ein quadratisches System mit m = n gilt: Ist det(A) ≠ 0, ist das System eindeutig lösbar. Bei det(A) = 0 hängt die Lösbarkeit von den Nebendeterminanten ab. Nur wenn alle Nebendeterminanten 0 sind, kann das System unendlich viele Lösungen besitzen; andernfalls ist es unlösbar.

Die Lösungsmenge ist L = {x | Ax = b}. Bei einem homogenen System ist sie ein Untervektorraum von Kⁿ, also der Kern von A. Sie besitzt die Superpositionseigenschaft: Linearkombinationen von Lösungen sind wiederum Lösungen. Hat A den Rang r, beträgt die Dimension des Lösungsraums n − r.

Ist ein inhomogenes System lösbar, ist seine Lösungsmenge ein affiner Unterraum der Form v + U. Dabei ist v eine beliebige Lösung des inhomogenen Systems und U der Lösungsraum des zugehörigen homogenen Systems. Die Lösungsmenge ist entweder leer oder hat die Dimension n − r. Ein inhomogenes System ist genau dann eindeutig lösbar, wenn das zugehörige homogene System nur die triviale Lösung besitzt.

Die Lösungsmenge bleibt bei elementaren Zeilenumformungen unverändert: beim Vertauschen zweier Zeilen, beim Multiplizieren einer Zeile mit einer von null verschiedenen Zahl sowie beim Addieren einer Zeile oder eines Vielfachen zu einer anderen Zeile.

Bestimmung mit der erweiterten Matrix

Die erweiterte Koeffizientenmatrix wird durch elementare Zeilenumformungen in Stufenform gebracht. Gegebenenfalls sind Spaltenvertauschungen nötig; sie ändern die Reihenfolge der Variablen, was am Ende berücksichtigt werden muss.

Bezeichnen k die Anzahl der Pivotpositionen und bₖ₊₁,…,bₘ die Einträge unterhalb der letzten Pivotzeile, gilt:

• Ist mindestens eines dieser bᵢ ungleich 0, gibt es keine Lösung.
• Sind alle diese bᵢ gleich 0 oder gilt k = m, ist das System lösbar.
• Für k = n ist die Lösung eindeutig.
• Für k < n gibt es unendlich viele Lösungen; der Lösungsraum hat die Dimension n − k.

Durch das Gauß-Jordan-Verfahren kann die Matrix in reduzierte Stufenform gebracht werden. Die Pivotvariablen werden dabei direkt bestimmt, während die übrigen Variablen freie Variablen sind. Werden diese freien Variablen durch sₖ₊₁,…,sₙ beschrieben, lässt sich jede Lösung als eine bestimmte Lösung plus eine Linearkombination von Vektoren schreiben.

Formen und Lösungsverfahren

Ein quadratisches LGS hat gleich viele Unbekannte wie Gleichungen. Sind seine Zeilen oder Spalten linear unabhängig, ist es eindeutig lösbar.

In der Stufenform nimmt die Zahl der auftretenden Unbekannten von Zeile zu Zeile um mindestens eine ab. Sie entsteht durch das gaußsche Eliminationsverfahren und wird durch Rückwärtseinsetzen gelöst. Im Beispiel 6x₁ + 3x₂ + 4x₃ = 1, −5x₃ = 10 folgt x₃ = −2 und x₂ = −2x₁ + 3. Mit x₁ = t sind alle Lösungen (t, −2t + 3, −2).

Die Dreiecksform ist ein Sonderfall der Stufenform: Jede Zeile enthält genau eine Unbekannte weniger als die vorhergehende, und alle Diagonalelemente aᵢᵢ sind von 0 verschieden. Auch sie wird durch Rückwärtseinsetzen gelöst. In der reduzierten Stufenform treten die ersten Unbekannten der Zeilen jeweils nur einmal mit Koeffizient 1 auf. Diese Form ist eindeutig und wird mit dem Gauß-Jordan-Algorithmus erzeugt; die Lösungen können direkt abgelesen werden.

Zu den direkten Verfahren gehören Einsetzungs-, Gleichsetzungs- und Additionsverfahren, das gaußsche Eliminationsverfahren, die Cholesky-Zerlegung für symmetrische, positiv definite Matrizen, die stabilere QR-Zerlegung sowie die Cramersche Regel. Die Cramersche Regel ist wegen ihres hohen Rechenaufwands für numerische Berechnungen ungeeignet.

Iterative Verfahren sind unter anderem das Gauß-Seidel- und das Jacobi-Verfahren. Sie konvergieren nicht für jede Matrix und können langsam sein. Vorkonditionierte Krylow-Unterraum-Verfahren eignen sich besonders für große dünnbesetzte Matrizen; Mehrgitterverfahren werden unter anderem bei Systemen aus der Diskretisierung bestimmter partieller Differentialgleichungen eingesetzt. Dünnbesetzte Matrizen und Bandmatrizen werden mit speziell angepassten Verfahren behandelt.

Bei mehr Messungen als Unbekannten, etwa in der Geodäsie, widersprechen sich die Gleichungen wegen Messfehlern meist. Eine strenge Lösung existiert dann häufig nicht. Durch Ausgleichung mit der Methode der kleinsten Quadrate wird eine Näherung bestimmt, die unter geeigneten Annahmen über die Messfehler optimal sein soll. Für ein beliebiges n×n-System gibt der Algorithmus von Don Coppersmith und Shmuel Winograd aus dem Jahr 1990 eine asymptotische obere Schranke von O(n²,376) arithmetischen Operationen; mindestens O(n²) Operationen sind notwendig. Fast singuläre Systeme können numerisch mit der Singulärwertzerlegung behandelt werden.