Lineares Gleichungssystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein lineares Gleichungssystem (kurz LGS) ist in der linearen Algebra eine Menge linearer Gleichungen mit einer oder mehreren Unbekannten, die alle gleichzeitig erfüllt sein sollen.

Ein entsprechendes System für drei Unbekannte sieht beispielsweise wie folgt aus:

Für sind alle drei Gleichungen erfüllt, es handelt sich um eine Lösung des Systems.

Allgemein lässt sich ein lineares Gleichungssystem mit Gleichungen und Unbekannten immer in die folgende Form bringen:

Lineare Gleichungssysteme werden, wenn alle gleich 0 sind, homogen genannt, andernfalls inhomogen. Homogene Gleichungssysteme besitzen stets mindestens die sogenannte triviale Lösung, bei der alle Variablen gleich 0 sind. Bei inhomogenen Gleichungssystemen kann dagegen der Fall eintreten, dass überhaupt keine Lösung existiert.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Die Graphen der Fragestellung, die sich im Punkt A(46;16) schneiden.

Lineare Gleichungssysteme entstehen vielfach als Modelle von praktischen Aufgabenstellungen. Beispielsweise lässt sich die Aufgabenstellung

„Ein Vater und ein Sohn sind zusammen 62 Jahre alt. Vor sechs Jahren war der Vater viermal so alt wie damals der Sohn. Wie alt ist jeder?“

durch das folgende lineare Gleichungssystem darstellen.

Die Variable repräsentiert hier das Alter des Vaters und die Variable das des Sohnes. Das Gleichungssystem wird in einem ersten Schritt üblicherweise in eine Standardform gebracht, bei der auf der linken Seite nur Terme mit Variablen und auf der rechten Seite die reinen Zahlen stehen. Im vorliegenden Beispiel wird dazu die zweite Gleichung ausmultipliziert und umgestellt.

Um dieses Gleichungssystem zu lösen, kann auf eine Vielzahl von Lösungsverfahren zurückgegriffen werden. Beispielhaft wird hier das gaußsche Eliminationsverfahren verwendet. Um zunächst die Variable zu eliminieren, wird die erste Gleichung von der zweiten subtrahiert.

Die entstandene Gleichung wird nach der Variablen aufgelöst, indem beide Seiten durch geteilt werden. Das ergibt das Alter des Sohnes, der 16 Jahre alt ist. Dieser Wert für wird wieder in die erste Gleichung eingesetzt.

Durch die Auflösung der Gleichung nach der Variablen lässt sich das Alter des Vaters berechnen, der 46 Jahre alt ist.

Matrixform[Bearbeiten | Quelltext bearbeiten]

Für die Behandlung von linearen Gleichungssystemen ist es nützlich, alle Koeffizienten zu einer Matrix der sogenannten Koeffizientenmatrix zusammenzufassen:

Des Weiteren lassen sich auch alle Unbekannten und die rechte Seite des Gleichungssystems zu einspaltigen Matrizen (das sind Spaltenvektoren) zusammenfassen:

Damit schreibt sich ein lineares Gleichungssystem unter Benutzung der Matrix-Vektor-Multiplikation kurz

Sowohl die Koeffizienten , die Unbekannten als auch die entstammen demselben Körper . Insbesondere gilt

und

Zur Festlegung eines linearen Gleichungssystems ist die Angabe der Unbekannten nicht nötig. Es genügt die Angabe der erweiterten Koeffizientenmatrix, die entsteht, wenn an die Koeffizientenmatrix eine Spalte mit der rechten Seite des Gleichungssystems angefügt wird:

Lösbarkeit[Bearbeiten | Quelltext bearbeiten]

Ein Vektor ist eine Lösung des linearen Gleichungssystems, wenn gilt. Ob und wie viele Lösungen ein Gleichungssystem besitzt, ist unterschiedlich. Bei linearen Gleichungssystemen treten drei Fälle auf:

  • Das lineare Gleichungssystem hat keine Lösung.
  • Das lineare Gleichungssystem hat genau eine Lösung.
  • Das lineare Gleichungssystem hat unendlich viele Lösungen, falls kein endlicher Körper ist, ansonsten ist die Anzahl der Lösungen eine Potenz der Mächtigkeit von

Lösbarkeitskriterien[Bearbeiten | Quelltext bearbeiten]

Ein lineares Gleichungssystem ist genau dann lösbar, wenn der Rang der Koeffizientenmatrix gleich dem Rang der erweiterten Koeffizientenmatrix ist (Bedingung nach Fontené, Rouché und Frobenius[1][2]). Ist der Rang der (erweiterten) Koeffizientenmatrix auch noch gleich der Anzahl der Unbekannten, so besitzt das Gleichungssystem genau eine Lösung.

Bei einem quadratischen Gleichungssystem, also im Fall (siehe unten), gibt die Determinante Auskunft über die Lösbarkeit. Das Gleichungssystem ist genau dann eindeutig lösbar, wenn der Wert der Determinante der Koeffizientenmatrix ungleich null ist. Ist der Wert jedoch gleich null, hängt die Lösbarkeit von den Werten der Nebendeterminanten ab. Bei diesen wird jeweils eine Spalte der Koeffizientenmatrix durch die Spalte der rechten Seite (den Vektor ) ersetzt. Nur wenn alle Nebendeterminanten den Wert null haben, kann das System unendlich viele Lösungen haben, ansonsten ist das Gleichungssystem unlösbar.

Insbesondere Gleichungssysteme mit mehr Gleichungen als Unbekannten, sogenannte überbestimmte Gleichungssysteme, besitzen häufig keine Lösung. Beispielsweise besitzt das folgende Gleichungssystem keine Lösung, da nicht beide Gleichungen erfüllen kann:

Näherungslösungen von überbestimmten Gleichungssystemen werden dann meist über die Ausgleichungsrechnung definiert und bestimmt.

Dass ein lineares Gleichungssystem unendlich viele Lösungen hat, kann nur vorkommen, wenn es weniger linear unabhängige Gleichungen als Unbekannte gibt und der zugrundeliegende Körper unendlich viele Elemente enthält. Beispielsweise besitzt das folgende (aus nur einer Gleichung bestehende) Gleichungssystem unendlich viele Lösungen, nämlich alle Vektoren mit

Lösungsmenge[Bearbeiten | Quelltext bearbeiten]

Die Lösungsmenge eines linearen Gleichungssystems besteht aus allen Vektoren für die erfüllt ist:

Liegt ein homogenes lineares Gleichungssystem vor, so bildet dessen Lösungsmenge einen Untervektorraum von Damit gilt die Superpositionseigenschaft, nach der für eine oder mehrere Lösungen auch deren Linearkombinationen (mit beliebigen ) Lösungen des Gleichungssystems sind. Die Lösungsmenge heißt daher auch Lösungsraum und ist identisch mit dem Kern der Matrix  Bezeichnet den Rang der Matrix  dann ist nach dem Rangsatz die Dimension des Lösungsraumes gleich dem Defekt der Matrix 

Ist die Lösungsmenge eines inhomogenen linearen Gleichungssystem nicht leer, dann ist sie ein affiner Unterraum von Sie hat dann die Form wobei der Lösungsraum des zugehörigen homogenen Gleichungssystems ist und eine beliebige Lösung des inhomogenen Gleichungssystems. Ein inhomogenes Gleichungssystem ist folglich genau dann eindeutig lösbar, wenn der Nullvektor die einzige Lösung („triviale Lösung“) des homogenen Gleichungssystems ist. Insbesondere gilt entweder oder mit

Die Lösungsmenge eines linearen Gleichungssystems verändert sich nicht, wenn eine der drei elementaren Zeilenumformungen durchgeführt wird:

  1. Vertauschen zweier Zeilen
  2. Multiplizieren einer Zeile mit einer von null verschiedenen Zahl
  3. Addieren einer Zeile (oder des Vielfachen einer Zeile) zu einer anderen Zeile

Die Lösungsmenge eines quadratischen linearen Gleichungssystems verändert sich sogar dann nicht, wenn das Gleichungssystem mit einer regulären Matrix multipliziert wird.

Bestimmung über die erweiterte Koeffizientenmatrix[Bearbeiten | Quelltext bearbeiten]

Die Form der Lösungsmenge lässt sich grundsätzlich mit Hilfe der erweiterten Koeffizientenmatrix bestimmen, indem diese mit Hilfe der elementaren Zeilenumformungen auf eine Dreiecksform gebracht wird:

Die Anzahl der Lösungen lässt sich dann an der letzten Zeile ablesen:

  • Sind alle in der letzten Zeile null, aber nicht, so gibt es keine Lösungen.
  • Ist als einziges in der letzten Zeile ungleich null, so ist das Gleichungssystem eindeutig lösbar.
  • Ist gleich null und auch, gibt es unendlich viele Lösungen.
  • Gibt es in der letzten Zeile mindestens zwei Einträge aus der Matrix, die ungleich null sind, so gibt es unendlich viele Lösungen. (Dies impliziert weniger Gleichungen als Unbekannte.)

Formen von Gleichungssystemen[Bearbeiten | Quelltext bearbeiten]

Lineare Gleichungssysteme können in Formen vorliegen, in denen sie leicht gelöst werden können. Vielfach werden beliebige Gleichungssysteme mittels eines Algorithmus in eine entsprechende Gestalt gebracht, um anschließend eine Lösung zu finden.

Quadratisch[Bearbeiten | Quelltext bearbeiten]

Von einem quadratischen Gleichungssystem ist die Rede, wenn die Zahl der Unbekannten gleich der Zahl der Gleichungen ist. Ein Gleichungssystem dieser Form kann, wenn die Zeilen oder Spalten linear unabhängig sind, eindeutig gelöst werden (Lösungsverfahren werden weiter unten besprochen).

Stufenform, Treppenform[Bearbeiten | Quelltext bearbeiten]

In der Stufenform (auch Zeilenstufenform, Zeilennormalform, Stufengestalt, Staffelgestalt, Treppenform, Treppenstufenform oder Treppennormalform) verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Durch die Anwendung des gaußschen Eliminationsverfahrens kann ein beliebiges Gleichungssystem in diese Form gebracht werden.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind ):

Lineare Gleichungssysteme in Stufenform können durch Rückwärtseinsetzen (Rücksubstitution) gelöst werden. Beginnend mit der letzten Zeile wird damit die Unbekannte berechnet und das gewonnene Ergebnis jeweils in die darüberliegende Zeile eingesetzt, um die nächste Unbekannte zu berechnen.

Lösung des obigen Beispiels:

  1. Auflösen der zweiten Zeile nach
  2. Einsetzen von in die erste Zeile:
  3. Auflösen der ersten Zeile nach
  4. Mit sind alle Vektoren der Form Lösungen des Gleichungssystems.

Dreiecksform[Bearbeiten | Quelltext bearbeiten]

Die Dreiecksform ist ein Sonderfall der Stufenform, bei der jede Zeile genau eine Unbekannte weniger als die vorhergehende hat. Das bedeutet, dass alle Koeffizienten der Hauptdiagonale von verschieden sind. Die Dreiecksform entsteht bei Anwendung des gaußschen Eliminationsverfahrens, wenn das Gleichungssystem genau eine Lösung hat.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind ):

Wie lineare Gleichungssysteme in Stufenform können auch solche in Dreiecksform durch Rückwärtseinsetzen gelöst werden.

Reduzierte Stufenform[Bearbeiten | Quelltext bearbeiten]

Auch die reduzierte Stufenform ist ein Sonderfall der Stufenform. Bei ihr treten die jeweils ersten Unbekannten jeder Zeile nur ein einziges Mal auf und haben den Koeffizienten Die reduzierte Stufenform eines linearen Gleichungssystems ist eindeutig: Es gibt also für jedes lineare Gleichungssystem genau eine reduzierte Stufenform. Durch die Anwendung des Gauß-Jordan-Algorithmus kann ein beliebiges lineares Gleichungssystem in diese Form gebracht werden.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind ):

Die Lösung des linearen Gleichungssystems kann nun direkt abgelesen werden: Sofern gesetzt und das Gleichungssystem rekursiv gelöst wird, ergeben sich alle Vektoren der Form als Lösungen.

Weitere Formen[Bearbeiten | Quelltext bearbeiten]

In der Praxis relevant sind die Sonderfälle dünnbesetzter Matrizen (sehr große Matrizen mit relativ wenigen Elementen ungleich null) und Bandmatrizen (ebenfalls große Matrizen, deren nicht verschwindende Elemente sich um die Hauptdiagonale konzentrieren), die sich mit speziell angepassten Lösungsverfahren (s. u.) behandeln lassen.

Lösungsverfahren[Bearbeiten | Quelltext bearbeiten]

Die Methoden zur Lösung von linearen Gleichungssystemen werden in iterative und direkte Verfahren unterteilt. Beispiele für direkte Verfahren sind das Einsetzungsverfahren, das Gleichsetzungsverfahren und das Additionsverfahren für einfache Gleichungssysteme sowie das auf dem Additionsverfahren basierende gaußsche Eliminationsverfahren, das ein Gleichungssystem auf Stufenform bringt. Eine Variante des Gauß-Verfahrens ist die Cholesky-Zerlegung, die nur für symmetrische, positiv definite Matrizen funktioniert. Doppelt so viel Aufwand wie das Gauß-Verfahren braucht die QR-Zerlegung, die dafür stabiler ist. Die Cramersche Regel verwendet Determinanten, um Formeln für die Lösung eines quadratischen linearen Gleichungssystems zu erzeugen, wenn dieses eindeutig lösbar ist. Für die numerische Berechnung ist sie auf Grund des hohen Rechenaufwands jedoch nicht geeignet.

Iterative Verfahren sind beispielsweise die zur Klasse der Splitting-Verfahren gehörenden Gauß-Seidel- und Jacobi-Verfahren. Diese konvergieren nicht für jede Matrix und sind für viele praktische Probleme sehr langsam. Modernere Verfahren sind etwa vorkonditionierte Krylow-Unterraum-Verfahren, die insbesondere für große dünnbesetzte Matrizen sehr schnell sind, sowie Mehrgitterverfahren zur Lösung von Systemen, die aus der Diskretisierung bestimmter partieller Differentialgleichungen stammen.

Bei Anwendungen (z.  B. Geodäsie) werden oft Messungen unterschiedlichen Typs ausgeführt, und es werden, um die Auswirkung von Messfehlern zu verringern, mehr Messungen ausgeführt, als Unbekannte zu bestimmen sind. Jede Messung liefert eine Gleichung zur Bestimmung der Unbekannten. Wenn diese Gleichungen nicht alle linear sind, wird das Gleichungssystem mit Verwendung von bekannten Näherungswerten der Unbekannten linearisiert. Dann sind anstelle der eigentlichen Unbekannten deren kleine Abweichungen von den Näherungswerten zu bestimmen. In der Regel widersprechen sich die Gleichungen, wenn mehr Gleichungen als Unbekannte vorhanden sind, so dass es keine strenge Lösung gibt. Als Ausweg wird dann üblicherweise durch eine Ausgleichung mittels der Methode der kleinsten Quadrate eine Lösung bestimmt, die typischerweise keine Gleichung exakt erfüllt, aber unter vernünftigen Annahmen über die Messfehler eine optimale Näherung der „wahren“ Messgrößen angibt.

Die derzeit beste bekannte asymptotische obere Schranke an arithmetischen Operationen, um ein beliebiges lineares Gleichungssystem zu lösen, liefert ein praktisch nicht anwendbarer Algorithmus von Don Coppersmith und Shmuel Winograd aus dem Jahre 1990, der ein -System in O(n2,376) löst.[3] Klar ist, dass mindestens O(n2) Operationen notwendig sind; nicht jedoch, ob diese untere Schranke auch erreicht werden kann.

Literatur[Bearbeiten | Quelltext bearbeiten]

  • G. Frobenius: Zur Theorie der linearen Gleichungen. In: Journal für die reine und angewandte Mathematik = Crelle’s Journal. Bd. 129, 1905 ISSN 0075-4102, S. 175–180, Digitalisat.
  • Andreas Meister: Numerik linearer Gleichungssysteme. Eine Einführung in moderne Verfahren. 2., überarbeitete Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.
  • Falko Lorenz: Lineare Algebra. Band 1. 4. Auflage. Spektrum Akademischer Verlag, Heidelberg u. a. 2003, ISBN 3-8274-1406-7.
  • Gerd Fischer: Lineare Algebra. 15., verbesserte Auflage. Vieweg, Wiesbaden 2005, ISBN 3-8348-0031-7.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Frobenius: Zur Theorie der linearen Gleichungen. 1905, S. 175–180.
  2. Fischer: Lineare Algebra. 2005, S. 130.
  3. Gene H. Golub, Charles F. Van Loan: Matrix Computations. 3rd edition, reprint. Johns Hopkins University Press, Baltimore MD u. a. 1996, ISBN 0-8018-5414-8.