Lineares Gleichungssystem/Eliminationsverfahren/Einführung/Textabschnitt

Lineare Gleichungssysteme werden mit dem Eliminationsverfahren gelöst, bei dem nach und nach Variablen eliminiert werden und schließlich ein besonders einfaches äquivalentes Gleichungssystem entsteht, das direkt gelöst werden kann (bzw. von dem gezeigt werden kann, dass es keine Lösung besitzt). Bei kleinen Systemen können auch das Einsetzungsverfahren oder das Gleichsetzungsverfahren sinnvoll sein.

Definition

Es sei ${}K$ ein Körper und seien zwei (inhomogene) lineare Gleichungssysteme zur gleichen Variablenmenge gegeben. Die Systeme heißen äquivalent, wenn ihre Lösungsmengen übereinstimmen.

Lemma

Es sei ${}K$ ein Körper und

${\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+\cdots +a_{1n}x_{n}&=&c_{1}\\a_{21}x_{1}+a_{22}x_{2}+\cdots +a_{2n}x_{n}&=&c_{2}\\\vdots &\vdots &\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\cdots +a_{mn}x_{n}&=&c_{m}\end{matrix}}$

ein inhomogenes lineares Gleichungssystem über ${}K$.

Dann führen die folgenden Manipulationen an diesem Gleichungssystem zu einem äquivalenten Gleichungssystem.

1. Das Vertauschen von zwei Gleichungen.
2. Die Multiplikation einer Gleichung mit einem Skalar ${}s\neq 0$.
3. Das einfache Weglassen einer Gleichung, die doppelt vorkommt.
4. Das Verdoppeln einer Gleichung (im Sinne von eine Gleichung zweimal hinschreiben).
5. Das Weglassen oder Hinzufügen einer Nullzeile (einer Nullgleichung).
6. Das Ersetzen einer Gleichung ${}H$ durch diejenige Gleichung, die entsteht, wenn man zu ${}H$ eine andere Gleichung ${}G$ des Systems addiert.

Beweis

Die meisten Aussagen sind direkt klar. (2) ergibt sich einfach daraus, dass wenn

${}\sum _{i=1}^{n}a_{i}\xi _{i}=c\,$

gilt, dass dann auch

${}\sum _{i=1}^{n}(sa_{i})\xi _{i}=sc\,$

für jedes ${}s\in K$ gilt. Bei ${}s\neq 0$ kann man diesen Übergang durch Multiplikation mit ${}s^{-1}$ rückgängig machen.

(6). Es sei ${}G$ die Gleichung

${}\sum _{i=1}^{n}a_{i}x_{i}=c\,$

und ${}H$ die Gleichung

${}\sum _{i=1}^{n}b_{i}x_{i}=d\,.$

Wenn ein Tupel ${}(\xi _{1},\ldots ,\xi _{n})\in K^{n}$ die beiden Gleichungen erfüllt, so erfüllt es auch die Gleichung ${}H'=G+H$. Und wenn das Tupel die beiden Gleichungen ${}G$ und ${}H'$ erfüllt, so auch die Gleichung ${}G$ und ${}H=H'-G$.

$\Box$

Für die praktische Lösung eines linearen Gleichungssystems sind die beiden Manipulationen (2) und (6) am wichtigsten, wobei man in aller Regel diese beiden Schritte kombiniert und eine Gleichung ${}H$ durch eine Gleichung der Form ${}H+\lambda G$ (mit ${}G\neq H$) ersetzt. Dabei wird ${}\lambda \in K$ so gewählt, dass die neue Gleichung eine Variable weniger besitzt als die alte. Man spricht von Elimination einer Variablen. Diese Elimination wird nicht nur für eine Zeile durchgeführt, sondern für alle Zeilen mit der Ausnahme von einer (geeignet gewählten) „Arbeitszeile“ ${}G$ und mit einer fixierten „Arbeitsvariablen“. Das folgende Eliminationslemma beschreibt diesen Rechenschritt.

Lemma

Es sei ${}K$ ein Körper und ${}S$ ein (inhomogenes) lineares Gleichungssystem über ${}K$ in den Variablen ${}x_{1},\ldots ,x_{n}$. Es sei ${}x$ eine Variable, die in mindestens einer Gleichung ${}G$ mit einem von ${}0$ verschiedenen Koeffizienten ${}a$ vorkommt.

Dann lässt sich jede von ${}G$ verschiedene Gleichung ${}H$ durch eine Gleichung ${}H'$ ersetzen, in der ${}x$ nicht mehr vorkommt, und zwar so, dass das neue Gleichungssystem ${}S'$, das aus ${}G$ und den Gleichungen ${}H'$ besteht, äquivalent zum Ausgangssystem ${}S$ ist.

Beweis

Durch Umnummerieren kann man ${}x=x_{1}$ erreichen. Es sei ${}G$ die Gleichung

${}ax_{1}+\sum _{i=2}^{n}a_{i}x_{i}=b\,$

(mit $a\neq 0$) und ${}H$ die Gleichung

${}cx_{1}+\sum _{i=2}^{n}c_{i}x_{i}=d\,.$

Dann hat die Gleichung

${}H'=H-{\frac {c}{a}}G\,$

die Gestalt

${}\sum _{i=2}^{n}{\left(c_{i}-{\frac {c}{a}}a_{i}\right)}x_{i}=d-{\frac {c}{a}}b\,,$

in der ${}x_{1}$ nicht mehr vorkommt. Wegen ${}H=H'+{\frac {c}{a}}G$ sind die Gleichungssysteme äquivalent.

$\Box$

Satz

Jedes (inhomogene) lineare Gleichungssystem über einem Körper ${}K$

lässt sich durch die in Fakt beschriebenen elementaren Umformungen und durch das Weglassen von überflüssigen Gleichungen in ein äquivalentes lineares Gleichungssystem der Stufenform

${\begin{matrix}b_{1s_{1}}x_{s_{1}}&+b_{1s_{1}+1}x_{s_{1}+1}&\ldots &\ldots &\ldots &\ldots &\ldots &+b_{1n}x_{n}&=&d_{1}\\0&\ldots &0&b_{2s_{2}}x_{s_{2}}&\ldots &\ldots &\ldots &+b_{2n}x_{n}&=&d_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\vdots &\vdots &\vdots &=&\vdots \\0&\ldots &\ldots &\ldots &0&b_{m{s_{m}}}x_{s_{m}}&\ldots &+b_{mn}x_{n}&=&d_{m}\\(0&\ldots &\ldots &\ldots &\ldots &\ldots &\ldots &0&=&d_{m+1})\end{matrix}}$

überführen, bei dem alle Startkoeffizienten ${}b_{1s_{1}},b_{2s_{2}},\ldots ,b_{ms_{m}}$ von ${}0$ verschieden sind.

Dabei ist bei ${}d_{m+1}=0$ die letzte Zeile überflüssig, oder aber, bei ${}d_{m+1}\neq 0$, das System besitzt keine Lösung.

Beweis

Dies folgt direkt aus dem Eliminationslemma, mit dem man sukzessive Variablen eliminiert. Man wendet es auf die erste (in der gegebenen Reihenfolge) Variable (diese sei $x_{s_{1}}$) an, die in mindestens einer Gleichung mit einem von ${}0$ verschiedenen Koeffizienten auftaucht (wenn sie nur in einer Gleichung auftaucht, so ist im Eliminationsprozess nichts zu tun). Diese Eliminationsschritte wendet man solange an, solange das im Eliminationsschritt entstehende variablenreduzierte Gleichungssystem (also ohne die vorhergehenden Arbeitsgleichungen) noch mindestens eine Gleichung mit einem von ${}0$ verschiedenen Koeffizienten enthält. Zum Schluss bleiben nur Gleichungen ohne Variablen übrig. Diese sind entweder alle die Nullgleichung, oder aber das System besitzt keine Lösung.

$\Box$

Lemma

Es sei ein inhomogenes lineares Gleichungssystem über einem Körper ${}K$ in Dreiecksgestalt

${\begin{matrix}a_{11}x_{1}&+a_{12}x_{2}&\ldots &+a_{1m}x_{m}&\ldots &+a_{1n}x_{n}&=&c_{1}\\0&a_{22}x_{2}&\ldots &\ldots &\ldots &+a_{2n}x_{n}&=&c_{2}\\\vdots &\ddots &\ddots &\vdots &\vdots &\vdots &=&\vdots \\0&\ldots &0&a_{mm}x_{m}&\ldots &+a_{mn}x_{n}&=&c_{m}\\\end{matrix}}$

mit ${}m\leq n$ gegeben, wobei vorne die Diagonalelemente ${}a_{ii}$ alle ungleich ${}0$ seien.

Dann stehen die Lösungen ${}(x_{1},\ldots ,x_{m},x_{m+1},\ldots ,x_{n})$ in Bijektion zu den Tupeln ${}(x_{m+1},\ldots ,x_{n})\in K^{n-m}$. D.h. die hinteren ${}n-m$ Einträge sind frei wählbar und legen eine eindeutige Lösung fest, und jede Lösung wird dabei erfasst.

Beweis

Dies ist klar, da bei gegebenem ${}(x_{m+1},\ldots ,x_{n})$ die Zeilen von unten nach oben sukzessive die anderen Variablen eindeutig festlegen.

$\Box$

Bei ${}m=n$ gibt es keine freien Variablen und das Gleichungssystem besitzt genau eine Lösung.

Beispiel

Wir wollen das inhomogene lineare Gleichungssystem

${\begin{matrix}2x&+5y&+2z&&-v&=&3\\3x&-4y&&+u&+2v&=&1\\4x&&-2z&+2u&&=&7\,\end{matrix}}$

über ${}\mathbb {R}$ (oder ${}\mathbb {Q}$) lösen. Wir eliminieren zuerst ${}x$, indem wir die erste Zeile ${}I$ beibehalten, die zweite Zeile ${}II$ durch ${}II-{\frac {3}{2}}I$ und die dritte Zeile ${}III$ durch ${}III-2I$ ersetzen. Das ergibt

${\begin{matrix}2x&+5y&+2z&&-v&=&3\\&-{\frac {23}{2}}y&-3z&+u&+{\frac {7}{2}}v&=&{\frac {-7}{2}}\\&-10y&-6z&+2u&+2v&=&1\,.\end{matrix}}$

Wir könnten jetzt aus der (neuen) dritten Zeile mit Hilfe der zweiten Zeile ${}y$ eliminieren. Wegen der Brüche eliminieren wir aber lieber ${}z$ (dies eliminiert gleichzeitig ${}u$). Wir belassen also die erste und zweite Zeile und ersetzen die dritte Zeile ${}III$ durch ${}III-2II$. Dies ergibt, wobei wir das System in einer neuen Reihenfolge der Variablen aufschreiben, das System

${\begin{matrix}2x&+2z&&+5y&-v&=&3\\&-3z&+u&-{\frac {23}{2}}y&+{\frac {7}{2}}v&=&{\frac {-7}{2}}\\&&&13y&-5v&=&8\,.\end{matrix}}$

Wir können uns nun ${}v$ beliebig (oder „frei“) vorgeben. Die dritte Zeile legt dann ${}y$ eindeutig fest, es muss nämlich

${}y={\frac {8}{13}}+{\frac {5}{13}}v\,$

gelten. In der zweiten Gleichung können wir wieder ${}u$ beliebig vorgeben, was dann ${}z$ eindeutig festlegt, nämlich

${}{\begin{aligned}z&=-{\frac {1}{3}}{\left(-{\frac {7}{2}}-u-{\frac {7}{2}}v+{\frac {23}{2}}{\left({\frac {8}{13}}+{\frac {5}{13}}v\right)}\right)}\\&=-{\frac {1}{3}}{\left(-{\frac {7}{2}}-u-{\frac {7}{2}}v+{\frac {92}{13}}+{\frac {115}{26}}v\right)}\\&=-{\frac {1}{3}}{\left({\frac {93}{26}}-u+{\frac {12}{13}}v\right)}\\&=-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v.\end{aligned}}$

Die erste Zeile legt dann ${}x$ fest, nämlich

${}{\begin{aligned}x&={\frac {1}{2}}{\left(3-2z-5y+v\right)}\\&={\frac {1}{2}}{\left(3-2{\left(-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v\right)}-5{\left({\frac {8}{13}}+{\frac {5}{13}}v\right)}+v\right)}\\&={\frac {1}{2}}{\left({\frac {30}{13}}-{\frac {2}{3}}u-{\frac {4}{13}}v\right)}\\&={\frac {15}{13}}-{\frac {1}{3}}u-{\frac {2}{13}}v.\end{aligned}}$

Daher kann man die Gesamtlösungsmenge als

${\left\{{\left({\frac {15}{13}}-{\frac {1}{3}}u-{\frac {2}{13}}v,{\frac {8}{13}}+{\frac {5}{13}}v,-{\frac {31}{26}}+{\frac {1}{3}}u-{\frac {4}{13}}v,u,v\right)}\mid u,v\in \mathbb {R} \right\}}$

schreiben. Eine besonders einfache Lösung ergibt sich, wenn man die freien Variablen ${}u$ und ${}v$ gleich ${}0$ setzt. Dies führt auf die spezielle Lösung

${}(x,y,z,u,v)=\left({\frac {15}{13}},\,{\frac {8}{13}},\,-{\frac {31}{26}},\,0,\,0\right)\,.$

In der allgemeinen Lösung kann man ${}u$ und ${}v$ als Koeffizienten rausziehen und dann die Lösungsmenge auch als

${\left\{{\left({\frac {15}{13}},{\frac {8}{13}},-{\frac {31}{26}},0,0\right)}+u{\left(-{\frac {1}{3}},0,{\frac {1}{3}},1,0\right)}+v{\left(-{\frac {2}{13}},{\frac {5}{13}},-{\frac {4}{13}},0,1\right)}\mid u,v\in \mathbb {R} \right\}}$

schreiben. Dabei ist

${\left\{u{\left(-{\frac {1}{3}},0,{\frac {1}{3}},1,0\right)}+v{\left(-{\frac {2}{13}},{\frac {5}{13}},-{\frac {4}{13}},0,1\right)}\mid u,v\in \mathbb {R} \right\}}$

eine Beschreibung der allgemeinen Lösung des zugehörigen homogenen linearen Gleichungssystems.