Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil II/Vorlesung 32/latex
\setcounter{section}{32}
\epigraph { Verwandle große Schwierigkeiten in kleine und kleine in gar keine } { Chinesische Weisheit }
\zwischenueberschrift{Das Lösen von linearen Gleichungssystemen}
Es ist von vornherein gar nicht so klar, was man unter dem Lösen eines \zusatzklammer {linearen} {} {} Gleichungssystems verstehen soll. Jedenfalls geht es um eine möglichst gute Beschreibung der Lösungsmenge. Wenn es nur eine Lösung gibt, so geht es darum, diese Lösung zu finden und anzugeben. Wenn es überhaupt keine Lösung gibt, geht es darum, dies festzustellen und zu begründen. Im Allgemeinen ist aber die Lösungsmenge eines Gleichungssystems groß. Dann versteht man unter der Lösung eines Systems, freie Variablen zu identifizieren, die beliebige Werte annehmen dürfen, und explizit zu beschreiben, wie die anderen \zusatzklammer {abhängigen} {} {} Variablen von diesen freien Variablen abhängen. Man spricht auch von einer \stichwort {expliziten Beschreibung} {} der Lösungsmenge.
Lineare Gleichungssysteme können systematisch mit dem \stichwort {Eliminationsverfahren} {} gelöst werden, bei dem nach und nach Variablen eliminiert werden und schließlich ein besonders einfaches äquivalentes Gleichungssystem
\zusatzklammer {in Dreiecksgestalt} {} {}
entsteht, das direkt gelöst werden kann
\zusatzklammer {bzw. von dem gezeigt werden kann, dass es keine Lösung besitzt} {} {.}
Wir betrachten ein typisches Beispiel mit vielen Variablen.
\inputbeispiel{}
{
Wir wollen das inhomogene lineare Gleichungssystem
\mathdisp {\begin{matrix}
2x & +5y & +2z & & -v & = & 3 \\
3x & -4y & & +u & +2v & = & 1 \\
4x & & -2z & +2u & & = & 7 \,
\end{matrix}} { }
über $\R$
\zusatzklammer {oder $\Q$} {} {}
lösen. Wir eliminieren zuerst $x$, indem wir die erste Zeile $I$ beibehalten, die zweite Zeile $II$ durch
\mathl{II - { \frac{ 3 }{ 2 } }I}{} und die dritte Zeile $III$ durch
\mathl{III-2I}{} ersetzen. Das ergibt
\mathdisp {\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
\zusatzklammer {neuen} {} {}
dritten Zeile mit Hilfe der zweiten Zeile $y$ eliminieren. Wegen der Brüche eliminieren wir aber lieber $z$
\zusatzklammer {dies eliminiert gleichzeitig $u$} {} {.}
Wir belassen also die erste und zweite Zeile und ersetzen die dritte Zeile $III$ durch
\mathl{III-2II}{.} Dies ergibt, wobei wir das System in einer neuen Reihenfolge der Variablen\zusatzfussnote {Eine solche Umstellung ist ungefährlich, wenn man den Namen der Variablen mitschleppt. Wenn man dagegen das System in Matrizenschreibweise aufführt, also die Variablennamen einfach weglässt, so muss man sich diese Spaltenvertauschungen merken} {.} {}
aufschreiben, das System
\mathdisp {\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
\zusatzklammer {oder \anfuehrung{frei}{}} {} {}
vorgeben. Die dritte Zeile legt dann $y$ eindeutig fest, es muss nämlich
\mavergleichskettedisp
{\vergleichskette
{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
\mavergleichskettealign
{\vergleichskettealign
{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
}
}
{}
{}{.}
Die erste Zeile legt dann $x$ fest, nämlich
\mavergleichskettealign
{\vergleichskettealign
{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
}
}
{}
{}{.}
Daher kann man die Gesamtlösungsmenge als
\mathdisp {{ \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 \R \right\} }} { }
schreiben. Eine besonders einfache Lösung ergibt sich, wenn man die freien Variablen
\mathkor {} {u} {und} {v} {}
gleich $0$ setzt. Dies führt auf die spezielle Lösung
\mavergleichskettedisp
{\vergleichskette
{ (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
\mathkor {} {u} {und} {v} {}
als Koeffizienten rausziehen und dann die Lösungsmenge auch als
\mathdisp {{ \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 \R \right\} }} { }
schreiben. Dabei ist
\mathdisp {{ \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 \R \right\} }} { }
eine Beschreibung der allgemeinen Lösung des zugehörigen homogenen linearen Gleichungssystems.
}
\inputdefinition
{}
{
Es sei $K$ ein \definitionsverweis {Körper}{}{} und seien zwei \zusatzklammer {inhomogene} {} {} \definitionsverweis {lineare Gleichungssysteme}{}{} zur gleichen Variablenmenge gegeben. Die Systeme heißen \definitionswort {äquivalent}{,} wenn ihre Lösungsmengen übereinstimmen.
}
\inputfaktbeweis
{Lineare Algebra/Variablenmenge/Lineares Gleichungssystem/Äquivalente Systeme/Manipulationen/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $K$ ein
\definitionsverweis {Körper}{}{} und
\mathdisp {\begin{matrix} a _{ 1 1 } x _1 + a _{ 1 2 } x _2 + \cdots + a _{ 1 n } x _{ n } & = & c_1 \\ a _{ 2 1 } x _1 + a _{ 2 2 } x _2 + \cdots + a _{ 2 n } x _{ n } & = & c_2 \\
\vdots & \vdots & \vdots \\ a _{ m 1 } x _1 + a _{ m 2 } x _2 + \cdots + a _{ m n } x _{ n } & = & c_m \end{matrix}} { }
ein
\definitionsverweis {inhomogenes lineares Gleichungssystem}{}{} über $K$.}
\faktfolgerung {Dann führen die folgenden Manipulationen an diesem Gleichungssystem zu einem
\definitionsverweis {äquivalenten Gleichungssystem}{}{.}
\aufzaehlungsechs{Das Vertauschen von zwei Gleichungen.
}{Die Multiplikation einer Gleichung mit einem Skalar
\mavergleichskette
{\vergleichskette
{ s
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Das einfache Weglassen einer Gleichung, die doppelt vorkommt.
}{Das Verdoppeln einer Gleichung
\zusatzklammer {im Sinne von eine Gleichung zweimal hinschreiben} {} {.}
}{Das Weglassen oder Hinzufügen einer Nullzeile
\zusatzklammer {einer Nullgleichung} {} {.}
}{Das Ersetzen einer Gleichung $H$ durch diejenige Gleichung, die entsteht, wenn man zu $H$ eine andere Gleichung $G$ des Systems addiert.
}}
\faktzusatz {}
\faktzusatz {}
}
{
Die meisten Aussagen sind direkt klar. (2) ergibt sich einfach daraus, dass wenn
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i = 1}^n a_i \xi_i
}
{ =} {c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt, dass dann auch
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i = 1}^n (s a_i) \xi_i
}
{ =} { s c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{ s
}
{ \in }{ K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Bei
\mavergleichskette
{\vergleichskette
{ s
}
{ \neq }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
kann man diesen Übergang durch Multiplikation mit $s^{-1}$ rückgängig machen.
(6). Es sei $G$ die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i = 1}^n a_ix_i
}
{ =} { c
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und $H$ die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i = 1}^n b_ix_i
}
{ =} { d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wenn ein Tupel
\mavergleichskette
{\vergleichskette
{ (\xi_1 , \ldots , \xi_n)
}
{ \in }{ K^n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die beiden Gleichungen erfüllt, so erfüllt es auch die Gleichung
\mavergleichskette
{\vergleichskette
{H'
}
{ = }{G+H
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Und wenn das Tupel die beiden Gleichungen
\mathkor {} {G} {und} {H'} {}
erfüllt, so auch die Gleichung
\mathkor {} {G} {und} {H=H'-G} {.}
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
\mathl{H + \lambda G}{}
\zusatzklammer {mit \mathlk{G \neq H}{}} {} {}
ersetzt. Dabei wird
\mavergleichskette
{\vergleichskette
{ \lambda
}
{ \in }{ K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
so gewählt, dass die neue Gleichung eine Variable weniger besitzt als die alte. Man spricht von \stichwort {Elimination einer Variablen} {.} Diese Elimination wird nicht nur für eine Zeile durchgeführt, sondern für alle Zeilen mit Ausnahme von einer
\zusatzklammer {geeignet gewählten} {} {}
\anfuehrung{Arbeitszeile}{} $G$ und mit einer fixierten \anfuehrung{Arbeitsvariablen}{.} Das folgende \stichwort {Eliminationslemma} {} beschreibt diesen Rechenschritt.
\inputfaktbeweis
{Lineares Gleichungssystem/Eliminationslemma/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $K$ ein
\definitionsverweis {Körper}{}{} und $S$ ein
\zusatzklammer {inhomogenes} {} {}
lineares Gleichungssystem über $K$ in den Variablen
\mathl{x_1 , \ldots , x_n}{.}}
\faktvoraussetzung {Es sei $x$ eine Variable, die in mindestens einer Gleichung $G$ mit einem von $0$ verschiedenen Koeffizienten $a$ vorkommt.}
\faktfolgerung {Dann lässt sich jede von $G$ verschiedene\zusatzfussnote {Mit verschieden ist hier gemeint, dass die beiden Gleichungen einen unterschiedlichen Index im System haben. Es ist also sogar der Fall erlaubt, dass
\mathkor {} {G} {und} {H} {}
dieselbe, aber doppelt aufgeführte Gleichung ist} {.} {}
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,
\definitionsverweis {äquivalent}{}{}
zum Ausgangssystem $S$ ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Durch Umnummerieren kann man
\mavergleichskette
{\vergleichskette
{x
}
{ = }{x_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
erreichen. Es sei $G$ die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ ax_1 + \sum_{i = 2}^n a_ix_i
}
{ =} {b
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {mit \mathlk{a \neq 0}{}} {} {}
und $H$ die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ cx_1 + \sum_{i = 2}^n c_ix_i
}
{ =} {d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Dann hat die Gleichung
\mavergleichskettedisp
{\vergleichskette
{H'
}
{ =} {H - { \frac{ c }{ a } } G
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
die Gestalt
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskette
{\vergleichskette
{H
}
{ = }{H' + { \frac{ c }{ a } } G
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind die Gleichungssysteme
\definitionsverweis {äquivalent}{}{.}
Das praktische Verfahren, bei dem man sukzessive das Verfahren im Beweis des vorstehenden Lemmas anwendet, um auf Dreiecksgestalt bzw. Stufengestalt zu kommen, nennt man \stichwort {Gaußsches Eliminationsverfahren} {}
\zusatzklammer {oder \stichwort {Additionsverfahren} {}} {} {.}
Es werden also Variablen eliminiert, indem man geeignete Vielfache von Gleichungen zu anderen Gleichungen hinzuaddiert.
\inputfaktbeweis
{Lineares inhomogenes Gleichungssystem/Elimination/Stufengestalt und Dreiecksgestalt/Fakt}
{Satz}
{}
{
\faktsituation {Jedes
\zusatzklammer {inhomogene} {} {}
lineare Gleichungssystem über einem Körper $K$}
\faktfolgerung {lässt sich durch die in
Lemma 32.3
beschriebenen elementaren Umformungen und durch das Weglassen von überflüssigen Gleichungen in ein
\definitionsverweis {äquivalentes lineares Gleichungssystem}{}{}
der Stufenform
\mathdisp {\begin{matrix}
b_{1s_1} x_{s_1} & + b_{1 s_1 +1} x_{s_1+1} & \ldots & \ldots & \ldots & \ldots & \ldots & +b_{1 n} x_{n} & = & d_1 \\
0 & \ldots & 0 & b_{2 s_2} x_{s_2} & \ldots & \ldots & \ldots & + b_{2 n} 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_{m n} x_n & = & d_m \\
( 0 & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & 0 & = & d_{m+1} )
\end{matrix}} { }
überführen, bei dem alle Startkoeffizienten
\mathl{b_{1s_1}, b_{2 s_2} , \ldots , b_{m s_m}}{} von $0$ verschieden sind.}
\faktzusatz {Dabei ist
\zusatzklammer {bei
\mavergleichskettek
{\vergleichskettek
{d_{m+1}
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
die letzte Zeile überflüssig oder aber
\zusatzklammer {bei
\mavergleichskettek
{\vergleichskettek
{d_{m+1}
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
das System besitzt keine Lösung.
Durch Variablenumbenennungen erhält man ein äquivalentes System der Form
\mathdisp {\begin{matrix}
c_{11} y_1 & + c_{12} y_2 & \ldots & + c_{1m} y_m & +c_{1 m+1} y_{m+1} & \ldots & +c_{1 n} y_{n} & = & d_1 \\
0 & c_{22} y_2 & \ldots & \ldots & \ldots & \ldots & + c_{2 n} y_{n} & = & d_2 \\
\vdots & \ddots & \ddots & \vdots & \vdots & \vdots & \vdots & = & \vdots \\
0 & \ldots & 0 & c_{mm} y_m & + c_{m m+1} y_{m+1} & \ldots & +c_{m n} y_n & = & d_m \\
( 0 & \ldots & \ldots & 0 & 0 & \ldots & 0 & = & d_{m+1} )
\end{matrix}} { }
mit Diagonalelementen
\mavergleichskette
{\vergleichskette
{c_{ii}
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
}
{
Dies folgt direkt aus dem Eliminationslemma, mit dem man sukzessive Variablen eliminiert. Man wendet es auf die erste \zusatzklammer {in der gegebenen Reihenfolge} {} {} Variable \zusatzklammer {diese sei \mathlk{x_{s_1}}{}} {} {} an, die in mindestens einer Gleichung mit einem von $0$ verschiedenen Koeffizienten auftaucht \zusatzklammer {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 \zusatzklammer {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.
Wenn wir
\mathl{y_1=x_{s_1},y_2=x_{s_2} , \ldots , y_m =x_{s_m}}{} setzen und die anderen Variablen mit
\mathl{y_{m+1} , \ldots , y_n}{} benennen, so erhält man das angegebene System in Dreiecksgestalt.
Es kann sein, dass die Variable $x_1$ gar nicht in dem System mit einem von $0$ verschiedenen Koeffizienten vorkommt, und, dass in einer Variablenelimination gleichzeitig mehrere Variablen eliminiert werden. Dann erhält man wie beschrieben ein Gleichungssystem in Stufenform, das erst durch Variablenvertauschungen in die Dreiecksform gebracht werden kann.
\inputbemerkung
{}
{
Gelegentlich möchte man ein \stichwort {simultanes lineares Gleichungssystem} {} der Form
\mathdisp {\begin{matrix} a _{ 1 1 } x _1 + a _{ 1 2 } x _2 + \cdots + a _{ 1 n } x _{ n } & = & c_1 & ( = & d_1, & = & e_1, \ldots ) \\ a _{ 2 1 } x _1 + a _{ 2 2 } x _2 + \cdots + a _{ 2 n } x _{ n } & = & c_2 & ( = & d_2, & = & e_2, \ldots ) \\
\vdots & \vdots & \vdots \\ a _{ m 1 } x _1 + a _{ m 2 } x _2 + \cdots + a _{ m n } x _{ n } & = & c_m &( = & d_m, & = & e_m, \ldots ) \end{matrix}} { }
lösen. Es sollen also für verschiedene Störvektoren Lösungen des zugehörigen inhomogenen Gleichungssystems berechnet werden. Grundsätzlich könnte man dies als voneinander unabhängige Gleichungssysteme betrachten, es ist aber geschickter, die Umwandlungen, die man auf der linken Seite macht, um Dreiecksgestalt zu erreichen, simultan auf der rechten Seiten mit allen Störvektoren durchzuführen. Ein wichtiger Spezialfall bei
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt vor, wenn die Störvektoren die Standardvektoren durchlaufen, siehe
Verfahren 36.12.
}
Wir besprechen noch kurz weitere Verfahren, ein lineares Gleichungssystem zu lösen.
\inputbemerkung
{}
{
Ein weiteres Verfahren, ein lineares Gleichungssystem zu lösen, ist das \stichwort {Einsetzungsverfahren} {.} Dabei werden ebenfalls Variablen sukzessive eliminiert, allerdings in einer anderen Weise. Wenn man mit diesem Verfahren die Variable $x_1$ eliminieren möchte, so löst man eine Gleichung, sagen wir $G_1$, in der $x_1$ mit einem von $0$ verschiedenen Koeffizienten vorkommt, nach $x_1$ auf, und erhält eine neue Gleichung der Form
\mathdisp {G_1': \, \, \, x_1 = F_1} { , }
wobei in $F_1$ die Variable $x_1$ nicht vorkommt. In allen weiteren Gleichungen
\mathl{G_2 , \ldots , G_m}{} ersetzt man die Variable $x_1$ durch $F_1$ und erhält
\zusatzklammer {nach Umformungen} {} {}
ein Gleichungssystem
\mathl{G_2' , \ldots , G_m'}{} ohne die Variable $x_1$, das zusammen mit $G_1'$ äquivalent zum Ausgangssystem ist.
}
\inputbemerkung
{}
{
Ein anderes Verfahren, ein lineares Gleichungssystem zu lösen, ist das \stichwort {Gleichsetzungsverfahren} {.} Dabei werden ebenfalls Variablen sukzessive eliminiert, allerdings in anderer Weise. Bei diesem Verfahren löst man die Gleichungen
\mathbed {G_i} {}
{i=1 , \ldots , m} {}
{} {} {} {,}
nach einer festen Variablen, sagen wir $x_1$ auf. Es seien
\zusatzklammer {nach Umordnung} {} {}
\mathl{G_1 , \ldots , G_k}{} die Gleichungen, in denen die Variable $x_1$ mit einem von $0$ verschiedenen Koeffizienten vorkommt. Diese Gleichungen bringt man in die Form
\mathdisp {G_i': \, \, \, x_1= F_i} { , }
wobei in $F_i$ die Variable $x_1$ nicht vorkommt. Das Gleichungssystem bestehend aus
\mathdisp {G_1', F_1=F_2, F_1=F_3 , \ldots , F_1=F_k, G_{k+1} , \ldots , G_m} { }
ist zum gegebenen System äquivalent. Mit diesem System ohne $G_1'$ fährt man fort.
}
\inputbemerkung
{}
{
Die in Satz 32.5, Bemerkung 32.7 und Bemerkung 32.8 beschriebenen Verfahren zur Lösung eines linearen Gleichungssystems unterscheiden sich hinsichtlich Schnelligkeit, strategischer Konzeption, Systematik, Komplexität der Koeffizienten, Fehleranfälligkeit. Beim Eliminationsverfahren tritt die systematische Reduzierung der Variablenanzahl \zusatzklammer {Dimensionsreduktion} {} {} besonders deutlich hervor und man kann mit ihm eigentlich keine Fehler \zusatzklammer {außer Rechenfehler} {} {} machen und weiß immer, wie es weiter geht. Allerdings treten diese Vorteile erst ab zumindest drei Variablen hervor. Bei zwei Variablen ist es nahezu egal, welchen Weg man wählt.
Die Bewertung der Verfahren hängt auch wesentlich von konkreten Besonderheiten des vorliegenden Systems ab. Solche Besonderheiten muss man berücksichtigen, um \anfuehrung{Abkürzungen}{} auf dem Weg zur Lösung zu sehen. Die bewusste Wahl eines für das konkrete Problem angemessenen Lösungsweges nennt man \stichwort {Adaptivität} {}
\zusatzklammer {ein Begriff, der im didaktischen Kontext mit unterschiedlichen Bedeutungen verwendet wird} {} {.}
Wenn beispielsweise eine Zeile des Systems die Form
\mavergleichskette
{\vergleichskette
{ x
}
{ = }{ 3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt, so sollte man erkennen, dass daraus unmittelbar ein Teil der Lösung ablesbar ist, und nicht zu dieser Zeile andere Zeilen hinzuaddieren und dadurch viele Variablen reinkriegen. Hier sollte man stattdessen in den anderen Zeilen das $x$ durch die $3$ ersetzen und dann weiter machen. Oder: Wenn es vier Gleichungen gibt, wobei in zwei Gleichungen nur die Variablen
\mathkor {} {x} {und} {y} {}
und in den beiden anderen Gleichungen nur die Variablen
\mathkor {} {z} {und} {w} {}
vorkommen, so sollte man erkennen, dass im Prinzip zwei entkoppelte lineare Systeme mit je zwei Variablen vorliegen und diese getrennt lösen. Oder: Es kann sein, dass ein kleines Teilsystem des Gleichungssystems bereits sicherstellt, dass es gar keine Lösung gibt. Dann muss man nur dies herausarbeiten und die anderen Gleichungen gar nicht berücksichtigen. Und: die genaue Fragestellung beachten! Wenn gefragt ist, ob ein bestimmtes Tupel eine Lösung ist, so muss man das Tupel nur in die Gleichungen einsetzen, Manipulationen an den Gleichungen sind nicht nötig.
}
\inputbemerkung
{}
{
Unter einem \stichwort {linearen Ungleichungssystem} {} über den rationalen Zahlen oder den reellen Zahlen versteht man ein System der Form
\mathdisp {\begin{matrix}
a _{ 1 1 } x _1 + a _{ 1 2 } x _2 + \cdots + a _{ 1 n } x _{ n } & \star & c_1 \\
a _{ 2 1 } x _1 + a _{ 2 2 } x _2 + \cdots + a _{ 2 n } x _{ n } & \star & c_2 \\
\vdots & \vdots & \vdots \\
a _{ m 1 } x _1 + a _{ m 2 } x _2 + \cdots + a _{ m n } x _{ n } & \star & c_m \, ,
\end{matrix}} { }
wobei
\mathl{\star}{} gleich
\mathl{\leq}{} oder
\mathl{\geq}{} ist. Die Lösungsmenge ist deutlich schwieriger zu beschreiben als im Gleichungsfall. Eine Eliminierung von Variablen ist im Allgemeinen nicht möglich.
}
\zwischenueberschrift{Lineare Gleichungssysteme in Dreiecksgestalt}
\inputfaktbeweis
{Lineares inhomogenes Gleichungssystem/Strenge Dreiecksgestalt/Lösung/Fakt}
{Satz}
{}
{
\faktsituation {Es sei ein inhomogenes lineares Gleichungssystem über einem Körper $K$ in Dreiecksgestalt
\mathdisp {\begin{matrix}
a_{11} x_1 & + a_{12} x_2 & \ldots & +a_{1m} x_m & \ldots & + a_{1 n} x_{n} & = & c_1 \\
0 & a_{22} x_2 & \ldots & \ldots & \ldots & + a_{2 n} x_{n} & = & c_2 \\
\vdots & \ddots & \ddots & \vdots & \vdots & \vdots & = & \vdots \\
0 & \ldots & 0 & a_{mm} x_m & \ldots & +a_{m n} x_n & = & c_m \\
\end{matrix}} { }
mit
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gegeben, wobei vorne die Diagonalelemente $a_{i i}$ alle ungleich $0$ seien.}
\faktfolgerung {Dann stehen die Lösungen
\mathl{(x_1 , \ldots , x_m, x_{m+1} , \ldots , x_n)}{} in Bijektion zu den Tupeln
\mavergleichskette
{\vergleichskette
{ ( x_{m+1} , \ldots , x_n)
}
{ \in }{ K^{n-m}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
D.h. die hinteren
\mathl{n-m}{} Einträge sind frei wählbar und legen eine eindeutige Lösung fest, und jede Lösung wird dabei erfasst.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies ist klar, da bei gegebenem
\mathl{(x_{m+1} , \ldots , x_n)}{} die Zeilen von unten nach oben sukzessive die anderen Variablen eindeutig festlegen.
Bei
\mavergleichskette
{\vergleichskette
{ m
}
{ = }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es keine freien Variablen und es ist
\mavergleichskette
{\vergleichskette
{ K^0
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und das Gleichungssystem besitzt genau eine Lösung. Ein beliebiges lineares Gleichungssystem formt man mit Hilfe des Eliminationslemmas in ein äquivalentes lineares Gleichungssystem in Stufengestalt um. Dann stellt man fest, dass es entweder keine Lösung besitzt oder aber man kann aus der Stufengestalt eine Beschreibung der Lösungsmenge erhalten.