Informations- und Kommunikationstechnik

Lineare Gleichungssysteme

Als lineare Gleichung wird eine Gleichung 1. Grades bezeichnet, bei der die unbekannte Größe in der 1. Potenz vorliegt. Ist der Koeffizient der Unbekannten ungleich null, so erhält man durch Auflösen nach ihr die allgemeine Lösungsgleichung.

Normalform:  a1·x1 + a0 = 0  daraus folgt:  x1 = −a0 / a1   mit  a1 ≠ 0

Ein lineares Gleichungssystem besteht aus mehreren linearen Gleichungen und Unbekannten in der 1. Potenz, die in den Gleichungen vorkommen und zusammen gültig sind. Zum Berechnen werden mindestens so viele Gleichungen benötigt, wie es Unbekannte gibt. Mithilfe von Einsetzungs-, Gleichsetzungs- und Additionsverfahren lassen sich nacheinander die einzelnen Unbekannten bestimmen. Programmierbare Verfahren, wo Gleichungen manuell nicht umgestellt werden können, verwenden Determinanten zur Bestimmung der Unbekannten.

Eliminierungsverfahren nach Gauß

Auf ein lineares Gleichungssystem werden Additions- und Multiplikationsverfahren angewendet. Es findet eine äquivalente Umformung der gegebenen Gleichungen statt, bei der die Lösungsmenge des linearen Gleichungssystems erhalten bleibt. Das Ziel ist es, nacheinander aus jeder Gleichung eine der Unbekannten zu eliminieren, sodass am Ende eine Bestimmungsgleichung für die letzte Unbekannte bleibt. Die folgenden Regeln gelten für den Gauß-Algorithmus:

Das folgende konkrete Beispiel zeigt den Ablauf des Gauß-Algorithmus für ein lineares Gleichungssystem mit drei Gleichungen und drei Unbekannten. Die Unbekannte x1 mit dem niedrigsten Koeffizienten steht in der Gl.(I) an der richtigen Stelle und bleibt im weiteren Verlauf unverändert als Eliminationszeile Gl.(E) bestehen.

In den Gl.(II') und (III') ist x1 zu eliminieren. Die Gl.(E) wird dazu mit einem Faktor multipliziert, sodass bei der Addition mit Gl.(II') und Gl.(III') die erste Unbekannte wegfällt. Der Faktor errechnet sich als Quotient aus den Koeffizienten der Gl.(II') und Gl.(E) sowie Gl.(III') und Gl.(E) und ist noch mit (−1) zu multiplizieren.

Im dritten Gleichungsblock bleibt die Eliminationszeile E2 unverändert. Es wird wie vorher ein neuer Quotientenfaktor ermittelt, mit (−1) und der Gl.(E2) multipliziert. Die Addition mit Gl.(III'') eliminiert dort die zweite Unbekannte x2. Gl.(III') wird zur dritten Eliminationszeile E3, aus der die dritte Unbekannte direkt berechnet werden kann.

konkreter Gauß-Algorithmus

Die Eliminationszeilen im vierten Gleichungsblock lassen sich als Dreieck interpretieren. Die Werte der Unbekannten errechnen sich von der unteren Spitze ausgehend nach oben zu. Beim Gauß-Algorithmus kommt es nicht auf die Reihenfolge an, nach der die Unbekannten eliminiert werden.

Cramersche Regel

Lineare Gleichungssysteme lassen sich mithilfe von Determinanten lösen. Das Verfahren dazu wurde in der ersten Hälfte des 18. Jahrhunderts vom Schweizer Mathematiker Gabriel Cramer entwickelt. Das Lösungsschema mit Determinanten wird am einfachsten linearen Gleichungssystem bestehend aus zwei Gleichungen mit zwei Unbekannten nachvollzogen. Die Gleichungen sind in allgemeingültiger Schreibweise aufgestellt.

Determinanten für y-Bestimmungsgleichung

Die Gleichung (I) wird als Eliminationszeile (E) verwendet. Sie wird mit dem negativen Quotientenfaktor aus den Koeffizienten der Unbekannten x multipliziert. Das Ergebnis ist Gl.(1), die zur Gl.(II) addiert wird. Das Ergebnis ist die Gl.(II'). In ihr ist x eliminiert und man erhält die Bestimmungsgleichung (E2) für y, die noch entsprechend umzuformen ist.

Der Nenner ist die Lösungsgleichung der Koeffizientendeterminante (D). Der Zähler ist die Lösungsgleichung einer Determinante (Dy). Werden die Koeffizienten von y in (D) durch die Ergebnisse b1 und b2 ersetzt, so folgt daraus die Determinante Dy. Die Bestimmungsgleichung für y ist der Quotient aus Dy / D.

Die fehlende Bestimmungsgleichung für x lässt sich herleiten, wenn Gl.(E2) in die Ausgangsgleichung (I) eingesetzt und umgeformt wird. Sollen die daraus folgenden vielfachen Rechenschritte erspart bleiben, können die oben dargestellten Schritte der Eliminierung auch für die Unbekannte y durchgeführt werden. Bei induktiver Schlussfolgerung kann man die Bestimmungsgleichung für x mit der Koeffizientendeterminante D und einer Determinante Dx auch direkt angeben. Dx entsteht beim Ersetzen der Koeffizientenspalte von x in D durch die Ergebnisspalte.

Determinanten für x-Bestimmungsgleichung

Das System aus n Gleichungen und n Unbekannten stellt ein quadratisches lineares (n, n)-Gleichungssystem dar. Mit quadratischen n-reihigen Determinanten lassen sich eindeutige Lösungen finden, wenn die Koeffizientendeterminante ungleich null und nicht alle absoluten Glieder in der Ergebnisspalte null sind. Die jeweiligen Zählerdeterminanten erhält man durch Ersetzen der zu ermittelnden Unbekannten durch die Spalte der absoluten Glieder.

Die Cramersche Regel am Zahlenbeispiel

Das anfangs der Seite berechnete lineare Gleichungssystem soll an dieser Stelle mithilfe von Determinanten gelöst werden. Es wird die Koeffizientendeterminante erstellt. Nacheinander werden aus ihr die Hilfsdeterminanten durch den entsprechenden Spaltenersatz mit der Ergebnisspalte gebildet. Die Werte der Determinanten können mithilfe der Regel nach Sarrus ermittelt werden.

Zahlenbeispiel für die Cramer-Regel

Das lineare Gleichungssystem mit Determinanten berechnet liefert die gleichen Ergebnisse wie das Eliminierungsverfahren nach Gauß. Das Verfahren nach Cramer ist für die in der Praxis oft vorkommenden nicht allzu großen Gleichungssysteme gut manuell einsetzbar. Es kann programmiert werden, um damit auch umfangreiche Gleichungssysteme automatisch berechnen zu lassen.