5.5 Lineare Gleichungssysteme

Lineare Gleichungssysteme sollten im Wesentlichen aus der Schulmathematik bekannt sein. Hier konzentrieren wir uns auf die Struktur der Lösungensmengen und auf Aspekte beim Lösen mit dem Computer.

Da lineare Gleichungssysteme eine der Aufgabenstellungen sind, die besonders gut mit dem Computer behandelt werden können, bemüht man sich in allen Teilgebieten von Naturwissenschaften, Technik und Wirtschaftswissenschaften zu lösenden praktische Probleme in Form linearer Gleichungssysteme zu fomulieren. Zusätzlich tauchen lineare Gleichungssysteme auch zahlreich als Teilproblem in komplexeren Modellen und zugehörigen Lösungsverfahren auf.

5.5.1Matrix-Vektor-Schreibweise¶

Ein lineares Gleichungssystem (kurz: LGS) mit $m$ Gleichungen und $n$ Unbekannten hat die Form

Die $a_{ij}$ und die $b_i$ sind gegeben. Die $x_j$ sind gesucht.

Setzt man

so kann man das LGS deutlich kompakter und handhabbarer mit einem Matrix-Vektor-Produkt als

schreiben. Die Matrix $A$ wird als Systemmatrix bezeichnet, der gegebene Vektor $b$ als rechte Seite.

5.5.2Struktur der Lösungsmenge¶

5.5.2.1Anzahl der Lösungen¶

LGS können keine, genau eine oder unendlich viele Lösungen besitzen. Ein einfaches Beispiel ohne Lösung ist

Das LGS

besitzt hingegen genau eine Lösung.

Die Lösungsmenge eines LGS mit unendlich vielen Lösungen besitzt eine sehr konkrete und nützliche Struktur. Zur weiteren Untersuchung unterscheiden wir zwei Typen von LGS:

5.5.2.2Homogene LGS¶

Die Lösungsmenge eines homogenen LGS mit $n$ Unbekannten ist offensichtlich ein linearer Unterraum des $\bbR^n$, denn die Summe zweier Lösungen ist wieder eine Lösung und alle Vielfachen von Lösungen sind Lösungen. In Formeln:

bzw.

Somit kann es beispielsweise auch kein homogenes LGS gegeben, welches genau zwei Lösungen besitzt, da dann automatisch die Summe der beiden Lösungen eine dritte Lösung liefern würde.

Beachte, dass der Nullvektor eine Lösung jedes homogenen LGS ist. Falls dies die einzige Lösung ist, ist die Lösungsmenge gerade der triviale Unterraum $\{0\}$. Das andere Extrem ist ein homogenes LGS mit Nullmatrix (nur Nullen) als Systemmatrix. Dann ist die Lösungsmenge ganz $\bbR^n$.

5.5.2.3Inhomogene LGS¶

Bei einem inhomogenen LGS ist die Lösungsmenge stets eine Untermannigfaltigkeit oder die leere Menge. Hat ein inhomogenes LGS eine Lösung $x^\ast\in\bbR^n$ (und ggf. noch mehr), so können wir das LGS als

schreiben. Setzen wir nun $\tilde{x}:=x-x^\ast$, so ist dies äquivalent zu dem homogenen LGS

(alles nach links bringen und $A$ ausklammern). Dessen Lösungsmenge ist ein Unterraum und aus der Beziehung $x=x^\ast+\tilde{x}$ sehen wir, dass die Lösungsmenge des ursprünglichen inhomogenen LGS eine Untermannigfaltigkeit ist. Die Lösungsmenge eines inhomogenen LGS ist stets eine verschobene Version der Lösungsmenge des homogene LGS mit identischer Systemmatrix!

5.5.2.4Geometrische Interpretation¶

Visualisiert man die Lösungsmenge eines LGS mit zwei oder drei Unbekannten, so erhält man wahlweise die leere Menge, einen Punkt, eine Gerade, eine Ebene oder den ganzen Raum. Entsprechend eng verknüpft sind Geraden und Ebenen mit linearen Gleichungssystemen.

Im $\bbR^2$ korrespondieren Geraden mit den Lösungsmengen von LGS mit zwei Unbekannten und einer Gleichung:

Dabei dürfen $a_{11}$ und $a_{12}$ nicht gleichzeitig Null sein (warum?).

Im $\bbR^3$ korrespondieren Ebenen mit den Lösungsmengen von LGS mit drei Unbekannten und einer Gleichung:

Dabei dürfen wieder $a_{11},a_{12},a_{13}$ nicht gleichzeitig Null sein.

Geraden im $\bbR^3$ entsprechen den Lösungsmengen von LGS mit drei Unbekannten und zwei Gleichungen:

Die Lösungsmenge dieses LGS ist der Durchschnitt der Lösungsmenge der ersten Gleichung und der Lösungsmenge der zweiten Gleichung, also die Schnittgerade der beiden durch die beiden Gleichungen beschriebenen Ebenen. Sind diese Ebenen parallel oder identisch, so erhält man keine Gerade als Lösungsmenge des LGS.

Völlig analog kann man sich überlegen, dass ein Punkt in $\bbR^2$ als Schnitt zweier (nicht paralleler oder identischer) Geraden entsteht, oder, alternativ, als Lösung eines LGS mit zwei Unbekannten und zwei Gleichungen.

5.5.3Manuelles Lösen¶

LGS löst man praktisch immer mit dem Computer (siehe unten). Dennoch sollen hier kurz zwei Ideen skizziert werden, wie man ein (kleines) LGS manuell lösen kann. Das manuelle Vorgehen ist insofern relevant als dass der Computer im Wesentlichen genauso vorgeht (aber dabei viel schneller ist). Auch begegnen uns hier einige neue Begriffe, die später in anderem Kontext benötigt werden. Praktisch relevante LGS besitzen heute tausende Unbekannte und Gleichungen, sodass manuelles Lösen nicht möglich ist.

5.5.3.1Gauß-Algorithmus¶

Die Grundidee des als Gauß-Algorithmus bekannten Vorgehens ist das systematische Vereinfachen des Gleichungssystems ohne dabei die Lösungsmenge zu verändern. Folgende Operationen sind dabei hilfreich und ändern die Lösungsmenge nicht:

• Vertauschen der Reihenfolge der Gleichungen,

• Multiplizieren einer Gleichung mit einem Faktor (außer Null),

• ein Vielfaches einer Gleichung zu einer anderen Gleichung hinzuaddieren,

• Gleichungen streichen, bei denen alle Koeffizienten und die rechte Seite Null sind.

Mit diesen Operationen kann man jedes LGS auf Stufenform bringen, d.h. die Anzahl der Unbekannten mit Nicht-Null-Koeffizient wird von Gleichung zu Gleichung kleiner. Dabei richtet man den Ablauf so ein, dass die Unbekannten in der natürlichen Reihenfolge wegfallen. So taucht $x_1$ dann nur noch in der ersten (oder keiner) Gleichung auf; $x_2$ erscheint höchstens in den ersten beiden Gleichungen usw. Welche Operation wann und wie anzuwenden ist um eine Stufenform des LGS zu erhalten, folgt einem einfachen Schema, welches man ohne nenneswerte Denkarbeit abarbeiten kann (für solche Aufgaben wurde der Computer erfunden...).

Ist das LGS in Stufenform, so kann man mit der letzten Gleichung beginnend die Lösung Gleichung für Gleichung leicht zusammensetzen. Dieser Vorgang wird als Rückwärtseinsetzen bezeichnet und folgt ebenfalls wieder einem klaren Schema ohne Notwendigkeit des Nachdenkens.

Da wir den Gauß-Algorithmus dem Computer überlassen, verzichten wir hier auf Details und Sonderfälle und belasses es bei einigen Beispielen:

Die Dimension der Lösungsmenge eines LGS kann man gut an der Systemmatrix des LGS in Stufenform ablesen. Dazu folgender Begriff:

Man kann zeigen, dass der Rang gleichzeitig auch der maximalen Anzahl linear unabhängiger Spalten in $A$ entspricht. Für $A\in\bbR^{m\times n}$ gilt also $0\leq\rg A\leq\min\{m,n\}$.

Zur Berechnung des Rangs einer Matrix kann der Gauß-Algorithmus verwendet werden, denn der Rang ist gerade die Anzahl an Nicht-Null-Zeilen der Stufenform der Matrix. Beachte, dass je nach gewähltem Vorgehen unterschiedliche Stufenformen entstehen können. Alle werden aber die gleiche Anzahl an Nicht-Null-Zeilen haben.

Die Dimension der Lösungsmenge eines homogenen (!) LGS ist gerade $m-\rg A$, wobei $m$ die Anzahl der Gleichungen ist. Bei einem inhomogenen LGS mit $\rg A<m$ (also Null-Zeilen in der Systemmatrix der Stufenform) besitzt das LGS entweder keine Lösung oder die Lösungsmenge hat die Dimension $m-\rg A$.

Die folgenden beiden Begriffe sind intuitiv klar, bedürfen aber einer Diskussion im Kontext des Gauß-Algorithmus:

Man kann nun etwas unbedacht Aussagen formulieren wie “unterbestimmte LGS haben unendlich viele Lösungen” oder “überbestimmte LGS sind nicht lösbar”. Dies ist aber nicht immer korrekt. Einerseits können unterbestimmte LGS trotzdem sich widersprechende Gleichungen enthalten, also keine Lösung besitzen. Andererseits können überbestimmte LGS redundante Gleichungen enthalten, sodass dennoch Lösungen existieren. Das tatsächliche Lösungsverhalten eines LGS erkennt man erst an der Stufenform!

5.5.3.2Inverse Matrix¶

Für LGS mit quadratischer Systemmatrix $A\in\bbR^{n\times n}$ kann man, sofern das LGS eindeutig lösbar ist, die Lösung als Matrix-Vektor-Produkt mit einer geeigneten Matrix angeben. Dazu folgender Begriff:

Man kann zeigen, dass eine Matrix $A\in\bbR^{n\times n}$ genau dann invertierbar ist, wenn $\rg A=n$ gilt. In diesem Fall kann man das LGS

auf beiden Seiten von links mit der Inversen multiplizieren:

Wegen $A^{-1}\,A=I$ und $I\,x=x$ erhalten wir mit

eine direkte Berechnungsvorschrift für die Lösung des LGS. Es bleibt somit nur die Frage zu klären, wie man zu $A^{-1}$ kommt.

Das manuelle Aufstellen der Inversen ist sehr mühsam. Man kann das Problem auf das Lösen von $n$ LGS zurückführen, die alle die gleiche Systemmatrix (nämlich $A$) besitzen; nur die rechten Seiten unterscheiden sich (das sind gerade die $n$ Spalten von $I$). Hintergrund ist der Zusammenhang

für Matrix-Vektor-Produkte (vgl. Hinweise zum Matrix-Vektor-Produkt). Wenn nun $A\,B=I$ gelten soll, so müssen also die LGS

erfüllt sein, wobei $e_1,\ldots,e_n$ die Spalten von $I$ sind ($e_k$ hat eine Eins als $k$-te Komponente, sonst Nullen). Diese LGS können mit dem Gauß-Algorithmus gelöst werden.

Aufgrund des Rechenaufwands ist das Lösen von linearen Gleichungssystemen mittels inverser Matrix nur sinnvoll, wenn das LGS sehr oft für verschiedene rechte Seiten (und gleiche Systemmatrix) gelöst werden muss. Dieser Fall tritt in der Praxis gar nicht so selten auf. Aus Sicht des Anwenders (d.h. (Vermessungs-)Ingenieurs oder (Geo-)Informatikers) sind solche Fragen aber wenig relevant, da diese Themen innerhalb von auf effizientes Lösen von LGS spezialisierten Software-Bibliotheken behandelt und entschieden werden und damit dem Auge des Anwenders verborgen bleiben.

Einige nützliche Zusammenhänge beim Rechnen mit Inversen seien noch erwähnt. Diese lassen sich leicht herleiten. Für quadratische Matrizen $A,B\in\bbR^{n\times n}$ gilt:

• Sind $A$ und $B$ invertierbar, so ist auch $A\,B$ invertierbar und es gilt

  $$(A\,B)^{-1}=B^{-1}\,A^{-1}.$$

  (32)

• Ist $A$ invertierbar, so ist auch $A^{-1}$ invertierbar und es gilt

  $$(A^{-1})^{-1}=A.$$

  (33)

• Ist $A$ invertierbar, so ist auch $A^\rmT$ invertierbar und es gilt

  $$(A^\rmT)^{-1}=(A^{-1})^\rmT.$$

  (34)

  Manchmal schreibt man auch $A^{-T}$ für die Inverse der Transponierten (bzw. für die Transponierte der Inversen).

• $A$ ist genau dann invertierbar, wenn $\det A\neq 0$ gilt.

5.5.4Symbolisches Lösen¶

Mit SymPy können lineare Gleichungssysteme wahlweise direkt als Liste von Gleichungen gelöst werden oder in der Matrix-Vektor-Form. Als Liste von Gleichungen:

import sympy

x, y, z = sympy.symbols('x y z')

sympy.linsolve([
    2 * x + y + z - 0,
    -6 * x + 3 * y + 9 * z - 6,
    2 * x + 2 * y + 3 * z - 1
], [x, y, z])

Beachte, dass sympy.linsolve auf der rechten Seite der Gleichungen von Nullen ausgeht, wir also die rechte Seite des zu lösenden LGS zunächst auf die linke Seite bringen müssen.

Das Lösen in Matrix-Vektor-Schreibweise funktioniert nur bei invertierbarer Systemmatrix:

A = sympy.Matrix([
    [2, 1, 1],
    [2, -1, 9],
    [2, 2, -1]
])
b = sympy.Matrix([0, 6, 1])

A.solve(b)

Da symbolisch (nicht numerisch) gelöst wird, können im LGS auch allgemeine Parameter enthalten sein:

c = sympy.symbols('c')
A = sympy.Matrix([
    [2, 1, c],
    [2, -1, 9],
    [2, 2, -1]
])
b = sympy.Matrix([0, 6, 1])

A.solve(b)

Die Inverse einer Matrix kann ebenfalls mit SymPy berechnet werden:

A = sympy.Matrix([
    [2, 1, 1],
    [2, -1, 9],
    [2, 2, -1]
])

A.inv()

5.5.5Numerisches Lösen¶

Mit NumPy können LGS numerisch gelöst werden. Dies ist deutlich schneller als das symbolische Lösen. Bei kleinen LGS (z.B. die obigen Beispiele) spielt dieser Geschwindigkeitsvorteil keine Rolle. Praktisch relevante LGS sind aber viel größer und symbolisch nicht mehr in akzeptabler Zeit lösbar.

Das numerische Lösen funktioniert nur, wenn die Systemmatrix invertierbar ist.

import numpy as np

A = np.array([
    [2, 1, 1],
    [2, -1, 9],
    [2, 2, -1]
])
b = np.array([0, 6, 1])

np.linalg.solve(A, b)

Auch die Inverse kann numerisch brechnet werden:

A = np.array([
    [2, 1, 1],
    [2, -1, 9],
    [2, 2, -1]
])

np.linalg.inv(A)

5.5.6Beispiel: Koordinaten bzgl. einer Basis¶

Hatten noch die Frage offen gelassen, wie wir zu einer gegebenen Basis $\{b_1,\ldots,b_r\}$ in einem Unterraum $U$ von $\bbR^n$ die Koordinaten eines Vektors $x\in U$ bzgl. dieser Basis berechnen können. Wie wir nun sehen werden, führt diese Frage auf ein LGS, dessen Lösung gerade die gesuchten Koordinaten sind.

Sei $x\in\bbR$. Gesucht sind die Zahlen $\lambda_1,\ldots,\lambda_r$, sodass

gilt. Schreiben wir die Basisvektoren als Spalten in eine Matrix $B\in\bbR^{n\times r}$, so soll also

gelten (vgl. dazu auch Hinweise zum Matrix-Vektor-Produkt).

Für einen echten Unterraum (also $r<n$) ist dieses LGS überbestimmt, wird also nicht für alle $x\in\bbR^n$ eine Lösung besitzen. Man kann jedoch zeigen, dass dieses LGS für $x\in U$ stets eindeutig lösbar ist. Für $U=\bbR^n$ ist die in diesem Fall quadratische Matrix $B$ also insbesondere invertierbar.

Für den Fall $r=n$ können wir noch weitere nützliche Beobachtungen machen: Handelt es sich bei $\{b_1,\ldots,b_n\}$ um eine ONB in $\bbR^n$, so folgt aus

durch Bilden des Skalarprodukts mit $b_l$, dass

also

gilt. Die gesuchten Koordinaten von $x$ bzgl. $\{b_1,\ldots,b_n\}$ erhält man damit ohne nennenswerte Mühe als Matrix-Vektor-Produkt.

Da die Gleichung $x=B\,B^\rmT\,x$ für beliebige $x\in\bbR^n$ wie gezeigt hergeleitet werden kann, muss

gelten. Offensichtlich gilt auch

Die Matrix $B$ ist also invertierbar und die Inverse ist

Matrizen, bei denen die Inverse gerade die transponierte Matrix ist, spielen in verschiedenen Teilgebieten von Mathematik (und auch Physik) ein Rolle und bekommen deshalb einen eigenen Name:

Folgende Eigenschaften von Orthogonalmatrizen sind gelegentlich hilfreich (und leicht einzusehen):

• Es gilt

  $$A^\rmT\,A=I\quad\text{und}\quad A\,A^\rmT=I.$$

  (43)

• Die Spalten von $A$ bilden ein Orthonormalsystem (wegen $A^\rmT\,A=I$).

• Die Zeilen von $A$ bilden ein Orthonormalsystem (wegen $A\,A^\rmT=I$).

• Die Transponierte $A^\rmT$ ist ebenfalls eine Orthogonalmatrix (weil $A=(A^\rmT)^\rmT$ ihre Inverse ist).

• Das Produkt zweier Orthogonalmatrizen $A,B\in\bbR^n$ ist wieder eine Orthogonalmatrix, denn

  $$(A\,B)^{-1}=B^{-1}\,A^{-1}=B^\rmT\,A^\rmT=(A\,B)^\rmT.$$

  (44)

5.5.7Beispiel: Kreuzprodukt¶

In der Ebene steht man gelegentlich vor der Aufgabe, zu einem gegebenen Vektor $a\in\bbR^2\setminus\{0\}$ einen zweiten Vektor $b\in\bbR^2\setminus\{0\}$ zu finden, sodass beide Vektoren senkrecht zueinander verlaufen. Analog möchte man gelegentlich im Raum zu zwei gegebenen, linear unabhängigen Vektoren $a,b\in\bbR^3\setminus\{0\}$ einen dritten Vektor $c\in\bbR^3\setminus\{0\}$ finden, der sowohl senkrecht zu $a$ als auch senkrecht zu $b$ verläuft. Diese Aufgabenstellung können wir als LGS formulieren:

• Für $a,b\in\bbR^2\setminus\{0\}$ soll $a\circ b=0$ gelten ($b$ gesucht), d.h.

  $$a_1\,b_1+a_2\,b_2=0.$$

  (45)

• Für $a,b,c\in\bbR^3\setminus\{0\}$ sollen $a\circ c=0$ und $b\circ c=0$ gelten ($c$ gesucht), d.h.

  $${\begin{align} a_1\,c_1+a_2\,c_2+a_3\,c_3&=0\\ b_1\,c_1+b_2\,c_2+b_3\,c_3&=0. \end{align}}$$

  (46)

In beiden Fällen handelt es sich um homogene LGS. Der Rang der Systemmatrizen

ist 1 bzw. 2 ($a$ und $b$ sind als linear unabhängig vorausgesetzt!), also um 1 niedriger als die Anzahl der Unbekannten. Somit ist die Lösungsmenge (Unterraum!) in beiden Fällen eindimensional, d.h. die Richtung des gesuchten Vektors ist bis auf das Vorzeichen festgelegt. Da wir die Länge des gesuchten Vektors frei wählen können, wählen wir diese so, dass die Darstellung des Vektors als Formel möglichst einfach wird.

Durch Einsetzen in das entsprechende LGS prüft man leicht nach:

• In $\bbR^2$ erfüllt

  $$b={\begin{bmatrix}-a_2\\a_1\end{bmatrix}}$$

  (48)

  die Anforderungen.

• In $\bbR^3$ erfüllt

  $$c={\begin{bmatrix}a_2\,b_3-a_3\,b_2\\a_3\,b_1-a_1\,b_3\\a_1\,b_2-a_2\,b_1\end{bmatrix}}$$

  (49)

  die Anforderungen.

Man kann zeigen, dass die Länge $\|a\times b\|$ des Kreuzprodukts gerade dem Flächeninhalt des von $a$ und $b$ aufgespannten Parallelogramms entspricht.

Zu zwei linear unabhängigen Vektoren liefert uns das Kreuzprodukt gerade einen Vektor, der zusammen mit den beiden Ausgangsvektoren ein Rechtssystem bildet. Wählt man stattdessen gerade einen Vektor in entgegengesetzter Richtung, so erhält man ein Linkssystem. Da diese beiden Begriffe im Folgenden keine Rolle spielen, verweisen wir für eine genauere Erklärung auf den Wikipedia-Artikel zu Rechtssystemen (beachte insbesondere die Rolle der Determinante bei der Unterscheidung von Rechts- und Linkssystemen!).

Für das Rechnen mit Kreuzprodukten kann man sich einige nützliche Zusammenhänge überlegen, z.B. $0\times a=0$ und $a\times b=-(b\times a)$. Für eine Übersicht solcher Zusammenhänge sei bei Bedarf auf die entsprechende Auflistung im Wikipedia-Artikel zum Kreuzprodukt verwiesen. Bei praktischen Aufgabenstellungen aus Vermessungswesen und Informatik wird man nur äußerst selten mit Kreuzprodukten rechnen müssen. Das Ergänzen zweier Vektoren zu einer Basis in $\bbR^3$ mittels Kreuzprodukt ist hingegen öfter von Nutzen.