9.9. Lineare Gleichungssysteme

In diesem Abschnitt untersuchen wir beliebige lineare Gleichungssysteme, also etwa Systeme von n Gleichungen mit m Unbekannten, die wir "klassisch" mit den Unbekannten ${\displaystyle x_1,\dots ,x_m}$ notieren:

oder als eine (!) Vektorgleichung mit dem Unbekanntenvektor x:

Durch die folgende Einführung eines Produkts zwischen zwei Vektoren lassen sich lineare Gleichungssysteme bequemer schreiben.

Definition: Für ${\displaystyle \mathit{x},\mathit{y}\in {ℝ}^m}$ heißt die Zahl ${\displaystyle \mathit{x}\cdot \mathit{y}=\sum _{i=1}^m{x}_i{y}_i=x_1{y}_1+\dots +x_m{y}_m}$ das Skalarprodukt von x und  y. Statt ${\displaystyle \mathit{x}\cdot \mathit{y}}$ schreibt man üblicherweise auch xy.

Zunächst eröffnet das Skalarprodukt eine zweite Möglichkeit, einen Bildvektor ${\displaystyle \left(a_{ij}\right)\mathit{x}}$ auszurechnen, und zwar über die Zeilenvektoren der Matrix ${\displaystyle \left(a_{ij}\right)}$.
 

Bemerkung:  Ist ${\displaystyle \left(a_{ij}\right)}$ eine n × m - Matrix, so gilt für ${\displaystyle \mathit{x}\in {ℝ}^m}$: ${\displaystyle \left(a_{ij}\right)\mathit{x}=\left(\begin{array}{c}{\mathit{a}}_{1•}\cdot \mathit{x}\\ ⋮\\ {\mathit{a}}_{n•}\cdot \mathit{x}\end{array}\right)}$ . Beweis: ${\displaystyle \begin{array}{ll}\left(a_{ij}\right)\mathit{x}\hfill & =x_1{\mathit{a}}_{•1}+\dots +x_m{\mathit{a}}_{•m}\hfill \\ \hfill & =\left(\begin{array}{ccc}{x}_1{a}_{11}& +\cdots +& x_m{a}_{1m}\\ ⋮& & ⋮\\ x_1{a}_{n1}& +\cdots +& x_m{a}_{nm}\end{array}\right)\hfill \\ \hfill & =\left(\begin{array}{ccc}{a}_{11}{x}_1& +\cdots +& a_{1m}{x}_m\\ ⋮& & ⋮\\ a_{n1}{x}_1& +\cdots +& a_{nm}{x}_m\end{array}\right)\hfill \\ \hfill & =\left(\begin{array}{c}{\mathit{a}}_{1•}\cdot \mathit{x}\\ ⋮\\ {\mathit{a}}_{n•}\cdot \mathit{x}\end{array}\right)\hfill \end{array}}$

Nach diesen Vorbereitungen formulieren wir nun den Begriff lineares Gleichungssystem in Matrixschreibweise. Solche Systeme lassen sich dadurch bequem und elegant notieren.
 

Definition: Ist ${\displaystyle \left(a_{ij}\right)}$ eine n × m - Matrix und ${\displaystyle \mathit{b}\in {ℝ}^n}$, so nenen wir eine Gleichung der Form ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$(*) ein lineares Gleichungssystem von n Gleichungen mit m Unbekannten (kurz: ein lineares n × m - System). Wir nennen das System (*) homogen, falls ${\displaystyle \mathit{b}=\mathbf{0}}$, und inhomogen falls ${\displaystyle \mathit{b}\ne \mathbf{0}}$. ${\displaystyle \left(a_{ij}\right)}$ ist die Koeffizientenmatrix von (*), b die rechte Seite von (*). Die Menge ${\displaystyle L=\{\mathit{x}\in {ℝ}^m|\left(a_{ij}\right)\mathit{x}=\mathit{b}\}=\cap \{\{\mathit{x}\in {ℝ}^m|{\mathit{a}}_{i•}\cdot \mathit{x}=b_i\}|1\le i\le n\}}$ heißt Lösungsmenge von (*). Im homogenen Fall ist offensichtlich ${\displaystyle L=Ker\left(a_{ij}\right)}$.

Die Lösungsmenge eines linaren Gleichungssystems ist interessant strukturiert:
 

Bemerkung:  ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ sei ein lineares Gleichungssystem mit nicht leerer Lösungsmenge L. Dann gilt für jedes ${\displaystyle \mathit{a}\in L}$: ${\displaystyle L=\mathit{a}+Ker\left(a_{ij}\right)}$ Nicht leere Lösungsmengen sind also immer affine Unterräume. Beweis: Sei ${\displaystyle \mathit{a}\in L}$, also ${\displaystyle \left(a_{ij}\right)\mathit{a}=\mathit{b}}$. Dann ist: ${\displaystyle \begin{array}{ll}\hfill \mathit{x}\in L& \iff \left(a_{ij}\right)\mathit{x}=\mathit{b}\hfill \\ \hfill & \iff \left(a_{ij}\right)\mathit{x}-\left(a_{ij}\right)\mathit{a}=\mathbf{0}\hfill \\ \hfill & \iff \left(a_{ij}\right)(\mathit{x}-\mathit{a})=\mathbf{0}\hfill \\ \hfill & \iff \mathit{x}-\mathit{a}\in Ker\left(a_{ij}\right)\hfill \\ \hfill & \iff \mathit{x}\in \mathit{a}+Ker\left(a_{ij}\right)\hfill \end{array}}$

Wir notieren zunächst zwei einfache Beispiele, in denen "nur" die Nullmatrix und die Einheitsmatrix des ${\displaystyle {ℝ}^n}$ als Koeffizientenmatrix auftreten. Dennoch enthalten beide Beispiele bereits grundlegende Züge für das Lösen allgemeiner Ssyteme. Gleichzeitig realisieren sie alle drei vorkommenden  Lösungsmöglichkeiten:

- keine Lösung
- genau eine Lösung, d.h. ${\displaystyle \dim L=0}$
- unendlich viele Lösungen, d.h. ${\displaystyle \dim L>0}$

 

Beispiel: ${\displaystyle \left(0\right)\mathit{x}=\mathit{b}\iff \mathit{x}\in \varnothing }$, falls ${\displaystyle \mathit{b}\ne \mathbf{0}}$. ${\displaystyle \left(0\right)\mathit{x}=\mathbf{0}\iff \mathit{x}\in {ℝ}^n}$. ${\displaystyle \left({\delta }_{ij}\right)\mathit{x}=\mathit{b}\iff \mathit{x}=\mathit{b}}$.

Das erste Beispiel gibt einen Hinweis auf die mögliche Lösbarkeit eines Gleichungssystems:
 

Bemerkung: Ist ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ ein lineares Gleichungssystem, so gilt: Tritt in der Koeffizientenmatrix ${\displaystyle \left(a_{ij}\right)}$ eine Nullzeile auf, die in der rechten Seite b nicht durch 0 bedient wird, ist die Lösungsmenge leer: ${\displaystyle L=\varnothing }$. Steht jeder Nullzeile von ${\displaystyle \left(a_{ij}\right)}$ eine Null in b gegenüber, so tragen diese Zeilen nicht zur Lösung bei und können vollständig weggelassen werden. Beweis: Sei etwa ${\displaystyle {\mathit{a}}_{k•}=\mathbf{0}}$. Ist nun ${\displaystyle b_k\ne 0}$, so hat ${\displaystyle \left(a_{ij}\right)\mathit{x}=\mathit{b}}$ zur Folge: ${\displaystyle 0={\mathit{a}}_{k•}\cdot \mathit{x}=b_k\ne 0}$ - Widerspruch. Ist dagegen ${\displaystyle b_k=0}$, so ist ${\displaystyle {\mathit{a}}_{k•}\cdot \mathit{x}=b_k}$ für alle x wahr, d.h. also: ${\displaystyle L=\cap \{\{\mathit{x}\in {ℝ}^m|{\mathit{a}}_{i•}\cdot \mathit{x}=b_i\}|1\le i\le n\}=\cap \{\{\mathit{x}\in {ℝ}^m|{\mathit{a}}_{i•}\cdot \mathit{x}=b_i\}|1\le i\le n,i\ne k\}}$.

 

Beispiel:   ${\displaystyle \left(\begin{array}{ccc}3& 1& 2\\ 0& 0& 0\\ 2& 0& 4\end{array}\right)\mathit{x}=\left(\begin{array}{c}3\\ 3\\ 2\end{array}\right)\iff \mathit{x}\in \varnothing }$   ${\displaystyle \left(\begin{array}{cc}0& 0\\ 1& 0\\ 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}0\\ 2\\ 7\end{array}\right)\iff \left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}2\\ 7\end{array}\right)\iff \mathit{x}=\left(\begin{array}{c}2\\ 7\end{array}\right)}$ .

Es reicht also, im Folgenden nur nullzeilenfreie Systeme zu betrachten! Als nächstes verallgemeinern wir die Äquivalenz ${\displaystyle \left({\delta }_{ij}\right)\mathit{x}=\mathit{b}\iff \mathit{x}=\mathit{b}}$, um auch nicht quadratische Systeme behandeln zu können.
 

Bemerkung und Bezeichnung: Ein lineares n × m - System der Form ${\displaystyle \left(\begin{array}{cc}(\ast )& \left({\delta }_{ij}\right)\end{array}\right)\mathit{x}=\mathit{b}\iff \left(\begin{array}{cc}(\ast )& \begin{array}{ccc}1& \cdots & 0\\ ⋮& \ddots & ⋮\\ 0& \cdots & 1\end{array}\end{array}\right)\mathit{x}=\mathit{b}}$ nennen wir maximal diagonalisiert. Das Lösungsverhalten eines solchen Gleichungssystems ist direkt ablesbar: Ist ${\displaystyle m=n}$, so gibt es keine (*)-Spalten, und die Koeffizientenmatrix ist die Einheitsmatrix. Die rechte Seite b ist also einzige Lösung: ${\displaystyle L=\{\mathit{b}\}=\mathit{b}+\{\mathbf{0}\}}$. Ist ${\displaystyle m>n}$, etwa ${\displaystyle m=n+k}$, so treten k (*)-Spalten auf, etwa ${\displaystyle {\mathit{w}}_{•1},\dots ,{\mathit{w}}_{•k}}$. Das System besitzt dann unendliche viele Lösungen. Die Lösungsmenge ist der k-dimensionale affine Unterraum ${\displaystyle L=\left(\begin{array}{c}\mathbf{0}\\ \mathit{b}\end{array}\right)+<\left(\begin{array}{c}{\mathit{e}}_1\\ -{\mathit{w}}_{•1}\end{array}\right),\dots ,\left(\begin{array}{c}{\mathit{e}}_k\\ -{\mathit{w}}_{•k}\end{array}\right)>}$. ${\displaystyle {\mathit{e}}_1,\dots ,{\mathit{e}}_k}$ ist dabei die Standardbasis und 0 der Nullvektor des ${\displaystyle {ℝ}^k}$. Beweis: ${\displaystyle \begin{array}{ll}\left(\begin{array}{cc}(\ast )& \left({\delta }_{ij}\right)\end{array}\right)\mathit{x}=\mathit{b}\hfill & \iff \left(\begin{array}{cccccc}{w}_{11}& \cdots & w_{1k}& 1& \cdots & 0\\ ⋮& & ⋮& ⋮& \ddots & ⋮\\ w_{n1}& \cdots & w_{nk}& 0& \cdots & 1\end{array}\right)\mathit{x}=\mathit{b}\hfill \\ \hfill & \iff \begin{array}{ccccc}{w}_{11}{x}_1& +\cdots +& w_{1k}{x}_k& +x_{k+1}=& b_1\\ ⋮& & ⋮& & ⋮\\ w_{n1}{x}_1& +\cdots +& w_{nk}{x}_k& +x_{k+n}=& b_n\end{array}\hfill \\ \hfill & \iff \begin{array}{l}{x}_1,\dots ,x_k\text{beliebig}\hfill \\ \begin{array}{ccc}{x}_{k+1}& =& b_1-w_{11}{x}_1-\cdots -w_{1k}{x}_k\\ ⋮& & ⋮\\ x_{k+n}& =& b_n-w_{n1}{x}_1-\cdots -w_{nk}{x}_k\end{array}\hfill \end{array}\hfill \\ \hfill & \iff \mathit{x}=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_k\\ b_1-w_{11}{x}_1-\cdots -w_{1k}{x}_k\\ ⋮\\ b_n-w_{n1}{x}_1-\cdots -w_{nk}{x}_k\end{array}\right),x_1,\dots ,x_k\text{beliebig}\hfill \\ \hfill & \iff \mathit{x}=\left(\begin{array}{c}0\\ ⋮\\ 0\\ b_1\\ ⋮\\ b_n\end{array}\right)+x_1\left(\begin{array}{c}1\\ ⋮\\ 0\\ -w_{11}\\ ⋮\\ -w_{n1}\end{array}\right)+\cdots +x_k\left(\begin{array}{c}1\\ ⋮\\ 0\\ -w_{1k}\\ ⋮\\ -w_{nk}\end{array}\right)\hfill \\ \hfill & \iff \mathit{x}\in \left(\begin{array}{c}\mathbf{0}\\ \mathit{b}\end{array}\right)+<\left(\begin{array}{c}{\mathit{e}}_1\\ -{\mathit{w}}_{•1}\end{array}\right),\dots ,\left(\begin{array}{c}{\mathit{e}}_k\\ -{\mathit{w}}_{•k}\end{array}\right)>\text{.}\hfill \end{array}}$ Der L zugrundeliegende Unterraum ist darüber hinaus der Kern der Koeffizientenmatrix.

 

Beispiel: ${\displaystyle \left(\begin{array}{cccc}3& 4& 1& 0\\ -2& 0& 0& 1\end{array}\right)\mathit{x}=\left(\begin{array}{c}5\\ 2\end{array}\right)\iff \mathit{x}\in \left(\begin{array}{c}0\\ 0\\ 5\\ 2\end{array}\right)+<\left(\begin{array}{c}1\\ 0\\ -3\\ 2\end{array}\right),\left(\begin{array}{c}0\\ 1\\ -4\\ 0\end{array}\right)>}$.

Ziel ist es nun, ein beliebiges lineares Gleichungssystem durch "geeignete Manipulationen" in ein maximal diagonalisiertes System umzuschreiben, ohne dabei die Lösungsmenge zu verändern. Wie gerade beschrieben, läßt sich die Lösungsmenge dann direkt ablesen. Dieses Verfahren zur Lösung linearer Gleichungssysteme heißt Gauß-Algorithmus.
 

Der Abschnitt über affine Unterräume endete mit der Aussage, dass der Schnitt zweier affiner Unterräume - sofern nicht leer - wieder ein affiner Unterraum ist. Mit den nun zur Verfügung stehenden Methoden können wir für affine Unterräume des ${\displaystyle {ℝ}^n}$ einen solchen Schnitt auch effektiv auszurechnen!

Zur Vorbereitung dient eine einfache, auch für beliebige Vektorräume gültige Aussage:
 

Bemerkung:  Sind ${\displaystyle M=a+W}$ und ${\displaystyle N=b+U}$ zwei affine Unterräume, so ist   ${\displaystyle M\cap N=\{x\in M|x-b\in U\}}$. D.h. für ${\displaystyle x\in M}$ gilt:  ${\displaystyle x\in M\cap N\iff x-b\in U}$. Der Beweis ergibt sich direkt aus der Äquivalenz  ${\displaystyle x\in N\iff x-b\in U}$.

Wir betrachten nun affine Unterräume des ${\displaystyle {ℝ}^n}$:  ${\displaystyle M=\mathit{a}+<{\mathit{w}}_1,\dots ,{\mathit{w}}_m>}$ und ${\displaystyle N=\mathit{b}+<{\mathit{v}}_1,\dots ,{\mathit{v}}_k>}$.
Für ${\displaystyle \mathit{x}\in M}$, etwa ${\displaystyle \mathit{x}={\alpha }_1{\mathit{w}}_1+\cdots +{\alpha }_m{\mathit{w}}_m}$, führt nun die Äquivalenz 

die Suche nach den Schnittelementen direkt zurück auf das Lösbarkeitsproblem einer aus den Daten von M und N gewonnen linearen Gleichung. Ihr Lösungsverhalten kann man mit Hilfe des Gauß-Algorithmus bestimmen.

Darüber hinaus liefert im Lösbarkeitsfall die Gleichung ${\displaystyle ({\mathit{v}}_1\dots {\mathit{v}}_k)\mathit{y}=\mathit{x}-\mathit{b}}$ für jeden Lösungsvektor  y  eine Darstellung von  x  als Element von N:
 

Wir üben dieses Verfahren an einigen Beispielen:

9.8

9.10.