imported>AmeisenBot: Bot: Ergänze :Kategorie:Wikipedia:Artikel mit Video

2026-03-16T15:17:09Z

Bot: Ergänze Kategorie:Wikipedia:Artikel mit Video

Neue Seite

Ein '''lineares Gleichungssystem''' (kurz '''LGS''') ist in der [[Lineare Algebra|linearen Algebra]] eine Menge [[Lineare Gleichung|linearer Gleichungen]] mit einer oder mehreren [[Variable (Mathematik)|Unbekannten]]. In der Theorie der linearen Gleichungssysteme fragt man nach Lösungen eines vorgelegten linearen Gleichungssystems, also nach konkreten Werten für die Unbekannten, so dass alle Gleichungen zugleich erfüllt sind.<ref>{{Literatur |Autor=[[Albrecht Beutelspacher]] |Titel=Lineare Algebra |Auflage=8. |Verlag=Springer Spektrum |Ort=Wiesbaden |Datum=2014 |ISBN=978-3-658-02412-3 |Seiten=105}}</ref>

Ein entsprechendes System mit drei Unbekannten <math>x_1, x_2, x_3</math> sieht beispielsweise wie folgt aus:
:<math>\begin{matrix}
3x_1 & + & 2x_2 & - & x_3 & = & 1\\
2x_1 & - & 2x_2 & + & 4x_3 & = & -2\\
-x_1 & + & {1 \over 2}x_2 & - & x_3 & = & 0
\end{matrix}</math>
Für <math>x_1 = 1, \ x_2 = -2, \ x_3 = -2</math> sind alle drei Gleichungen erfüllt, es handelt sich um eine [[Lösung (Mathematik)|Lösung]] des Systems. Diese besteht also im Unterschied zur [[Lösungsmenge]] einer einzigen Gleichung in diesem Beispiel – ''alle'' Punkte einer [[Ebene (Mathematik)#Ebenengleichungen|Ebene]] im [[3D#Dreidimensionaler euklidischer Raum|dreidimensionalen Raum]] – aus ''einem'' [[n-Tupel]], in diesem Fall einem Zahlentripel. Dieses wird auch als [[Vektor|Lösungsvektor]] bezeichnet. Zur Anzahl der möglichen Lösungen siehe den Abschnitt [[#Lösbarkeit|Lösbarkeit]].

Allgemein lässt sich ein lineares Gleichungssystem mit <math>m</math> Gleichungen und <math>n</math> Unbekannten immer in die folgende Form bringen:
:<math>\begin{matrix}
a_{1,1} x_1 + a_{1,2} x_2 \, + & \dotsb & +\, a_{1,n} x_n & = & b_1\\
a_{2,1} x_1 + a_{2,2} x_2 \, + & \dotsb & +\, a_{2,n} x_n & = & b_2\\
&&&\vdots&\\
a_{m,1} x_1 + a_{m,2} x_2 \, + & \dotsb & +\, a_{m,n} x_n & = & b_m\\
\end{matrix}</math>

Lineare Gleichungssysteme werden als ''homogen'' bezeichnet, wenn alle <math>b_i</math> gleich 0 sind, andernfalls als ''inhomogen.'' Homogene Gleichungssysteme besitzen stets mindestens die sogenannte ''triviale Lösung'', bei der alle Variablen gleich 0 sind. Bei inhomogenen Gleichungssystemen kann dagegen der Fall eintreten, dass überhaupt keine Lösung existiert.

== „Spaltenweise“ und „zeilenweise“ geometrische Interpretation ==
Geht man von einer vorgegebenen [[Basis (Vektorraum)|Basis]] <math>\vec e_1, \dotsc, \vec e_m</math> eines <math>m</math>-dimensionalen [[Vektorraum]]es aus, so lassen sich die reellen Zahlen in der <math>j</math>-ten „Spalte“ des Gleichungssystems, also die Zahlen <math>a_{ij}, i=1, \dotsc, m</math> als Koeffizienten eines Vektors <math>\vec a_j:= \sum_i a_{ij} \vec e_i</math> auffassen. Ebenso lassen sich <math>b_i, i=1, \dotsc, m</math> als Koeffizienten eines Lösungsvektors <math>\vec b:= \sum_i b_{i} \vec e_i</math> interpretieren.

Damit lässt sich die Lösung eines linearen Gleichungssystems auf das Problem zurückführen, den Lösungsvektor <math>\vec b</math> durch eine [[Linearkombination]] der Vektoren <math>\vec a_j</math> darzustellen. Gesucht sind also Folgen reeller
Zahlen <math>x_j, j=1,\ldots,n</math>, sodass
<math> x_1 \vec a_{1} + x_2 \vec a_{2} + \cdots + x_n \vec a_{n} = \vec b
</math>.

Alternativ lässt sich jede der m Zeilen eines linearen Gleichungssystems geometrisch als Gleichung einer [[Hyperebene]] in einem n-dimensionalen Vektorraum deuten, wobei n die Anzahl der Variablen bzw. Unbekannten ist. Spezialfälle von Hyperebenen sind Geraden in der Ebene und Ebenen im Raum.

Hierbei geht man von einer vorgegebenen Basis <math>\vec e_1, \dotsc, \vec e_n </math> eines <math>n</math>-dimensionalen Vektorraumes sowie von der dualen Basis <math>\vec e^1, \dotsc, \vec e^n </math> des Vektorraumes der zugehörigen [[Linearform]]en aus. Dann lassen sich die reellen Zahlen <math>a_{ij}</math> der <math>i</math>-ten Zeile als Koeffizienten einer Linearform <math>\varphi_i:= \sum_j a_{ij}\vec e^j</math> interpretieren. Ebenso lassen sich die <math>x_j</math> als Koeffizienten eines Vektors <math>\vec x:= \sum_j x_j \vec e_j</math> auffassen. Die <math>i</math>-te Gleichung des linearen Gleichungssystems (<math>i=1, \dotsc, m</math>):
<math> a_{i1} x_1 + a_{i2} x_2 + \dotsb + a_{in} x_n = b_i
</math>
ist dann die Bestimmungsgleichung der affinen Hyperebene
:<math>
\mathfrak H_i := \{ \vec x \mid \varphi_i(\vec x) = b_i \}
</math>
Damit lässt sich die Lösung eines linearen Gleichungssystems auf ein Schnittproblem von Hyperebenen zurückführen: Gesucht ist die Menge <math>\mathfrak H_1 \cap \ldots \cap \mathfrak H_m</math> der gemeinsamen Punkte aller Hyperebenen.

Keine dieser beiden Sichtweisen ist grundsätzlich der anderen vorzuziehen. Wichtig für ein umfassendes Verständnis ist vielmehr die geschickte Kombination der verschiedenen Perspektiven. Der im Abschnitt [[#Lösbarkeitskriterien|Lösbarkeitskriterien]] zitierte [[Satz von Kronecker-Capelli]] ergibt sich z. B. als unmittelbare Folge des „spaltenweisen“ Ansatzes. Die unten angegebenen [[#Lösbarkeit|Beispiele]] für die Lösung als Schnitt von zwei Geraden in der Ebene basieren hingegen auf der „zeilenweisen“ Interpretation des Gleichungssystems.

== Beispiel ==
[[Datei:Ein Vater und ein Sohn sind zusammen 62 Jahre alt 48pt.svg|mini|Die Graphen der Fragestellung, die sich im Punkt <math>A(46 \mid 16)</math> schneiden]]
Lineare Gleichungssysteme entstehen vielfach als Modelle von praktischen Aufgabenstellungen. Ein typisches Beispiel aus der [[Schulmathematik]] lautet wie folgt:
{{Zitat
|Text=Ein Vater und ein Sohn sind zusammen 62 Jahre alt. Vor sechs Jahren war der Vater viermal so alt wie damals der Sohn. Wie alt ist jeder?}}
Es lässt sich auch durch das folgende lineare Gleichungssystem beschreiben:
:<math>\begin{matrix}
\text{(I)} & v + s & = & 62 \\
\text{(II)} & v - 6 & = & 4 \cdot (s - 6)
\end{matrix}
</math>
Die Variable <math>v</math> repräsentiert hier das Alter des Vaters und die Variable <math>s</math> das des Sohnes. Das Gleichungssystem wird in einem ersten Schritt üblicherweise in eine Standardform gebracht, bei der auf der linken Seite nur Terme mit Variablen und auf der rechten Seite reine Zahlen stehen. Im vorliegenden Beispiel wird dazu die zweite Gleichung [[Ausmultiplizieren|ausmultipliziert]] und umgestellt.
:<math>\begin{matrix}
\text{(I)} & v + s & = & 62 \\
\text{(II)} & v - 4s & = & -18
\end{matrix}</math>
Um dieses Gleichungssystem zu lösen, kann auf eine Vielzahl von Lösungsverfahren ([[#Lösungsverfahren|siehe Lösungsverfahren]]) zurückgegriffen werden. Beispielhaft wird hier das [[Additionsverfahren (Mathematik)|Additionsverfahren]] verwendet. Um zunächst die Variable <math>v</math> zu eliminieren, wird die erste Gleichung von der zweiten subtrahiert.
:<math>\begin{align}
v - 4s - (v + s) &= -18 - 62\\
-5s &= -80\\
\end{align}</math>
Die entstandene Gleichung wird nach der Variablen <math>s</math> aufgelöst, indem beide Seiten durch <math>-5</math> geteilt werden. Das ergibt das Alter <math>s</math> des Sohnes, der 16 Jahre alt ist. Dieser Wert für <math>s</math> wird wieder in die erste Gleichung eingesetzt.
:<math>v + 16 = 62</math>
Durch die Auflösung der Gleichung nach der Variablen <math>v</math> lässt sich das Alter des Vaters berechnen, der 46 Jahre alt ist.

Die Aufgabe lässt sich auch geometrisch lösen, indem die beiden Zeilen des linearen Gleichungssystems als Geradengleichungen interpretiert werden. Dabei werden die Variable <math>v</math> als <math>x</math> und die Variable <math>s</math> als <math>y</math> bezeichnet und beide Gleichungen nach <math>y</math> aufgelöst:
:<math>\begin{matrix}
\text{(I)} & y & = & - x & + & 62 \\
\text{(II)} & y & = & 0{,}25x & + & 4{,}5
\end{matrix}</math>
Der Schnittpunkt der beiden Geraden ist der Punkt <math>\textstyle ( 46 \mid 16 )</math>, wobei die erste Koordinate dem Alter des Vaters und die zweite dem Alter des Sohnes entspricht (siehe Grafik).

== Matrixform ==
Für die Behandlung von linearen Gleichungssystemen ist es nützlich, alle [[Koeffizient]]en <math>a_{ij}</math> zu einer [[Matrix (Mathematik)|Matrix]] <math>A</math>, der sogenannten '''Koeffizientenmatrix''' zusammenzufassen:
:<math>A = \begin{pmatrix}
a_{1, 1} & a_{1, 2} & \cdots & a_{1n}\\
a_{2, 1} & a_{2, 2} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{pmatrix}</math>
Des Weiteren lassen sich auch alle Unbekannten und die rechte Seite des Gleichungssystems zu einspaltigen Matrizen (das sind [[Vektor|Spaltenvektoren]]) zusammenfassen:
:<math>x = \begin{pmatrix} x_1\\ x_2 \\ \vdots \\ x_n\end{pmatrix};\qquad
b = \begin{pmatrix} b_1\\ b_2 \\ \vdots \\ b_m\end{pmatrix}</math>
Damit schreibt sich ein lineares Gleichungssystem unter Benutzung der [[Matrix-Vektor-Multiplikation]] kurz
:<math>A \cdot x = b.</math>
Sowohl die Koeffizienten <math>a_{ij}</math>, die Unbekannten <math>x_j</math> als auch die <math>b_i</math> entstammen demselben [[Körper (Algebra)|Körper]] <math>K</math>. Insbesondere gilt
:<math>A \in K^{{m}\times{n}},</math> <math>b \in K^{m}</math> und <math>x \in K^{n}</math>.
Zur Festlegung eines linearen Gleichungssystems ist die Angabe der Unbekannten nicht nötig. Es genügt die Angabe der [[Erweiterte Matrix|erweiterten Koeffizientenmatrix]], die entsteht, wenn an die Koeffizientenmatrix <math>A</math> eine Spalte mit der rechten Seite <math>b</math> des Gleichungssystems angefügt wird:
:<math>\left(\begin{array}{c|c}A & b\end{array}\right) =
\left(\begin{array}{cccc|c}
a_{1, 1} & a_{1, 2} & \cdots & a_{1n} & b_1\\
a_{2, 1} & a_{2, 2} & \cdots & a_{2n} & b_2\\
\vdots & \vdots & \ddots & \vdots & \\
a_{m1} & a_{m2} & \cdots & a_{mn} & b_m
\end{array}\right)</math>

== Lösbarkeit ==
[[Datei:Lineare Gleichungssysteme und Lösungsverfahren - kolleg24 Mathematik.webm|mini|Lösungen von Linearen Gleichungen ]]
Ein Vektor <math>x</math> ist eine Lösung des linearen Gleichungssystems, wenn <math>A \cdot x = b</math> gilt. Ob und wie viele Lösungen ein Gleichungssystem besitzt, ist unterschiedlich. Bei linearen Gleichungssystemen über einem unendlichen Körper <math>K</math> können drei Fälle auftreten:
* Das lineare Gleichungssystem hat keine Lösung, d. h., die Lösungsmenge ist die leere Menge.
* Das lineare Gleichungssystem hat genau eine Lösung, d. h., die Lösungsmenge enthält genau ein Element.
* Das lineare Gleichungssystem hat unendlich viele Lösungen. Die Lösungsmenge enthält in diesem Falle unendlich viele ''n''-Tupel, die alle Gleichungen des Systems erfüllen.
Über einem endlichen Körper ist die Anzahl der Lösungen eine Potenz der [[Mächtigkeit (Mathematik)|Mächtigkeit]] von <math>K</math>.

{{Klappbox|hintergrundfarbe=hintergrundfarbe5|1=Beispiele für Lösbarkeit mit geometrischer Interpretation (Schnitt von zwei Geraden in der Ebene)|2=
Die beiden Gleichungen des linearen Gleichungssystems werden jeweils als Normalenform einer Geradengleichung in der Ebene gedeutet.
* '''Eindeutige Lösung:'''
:<math>\begin{matrix}
2 x_1 & - x_2 & = & 4\\
x_1 & + 3x_2 & = & -5\\
\end{matrix}</math>
:Die beiden Geradengleichungen lauten:
: <math>\begin{pmatrix} 2 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 4 \quad</math> und <math>\quad \begin{pmatrix} 1 \\ 3 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = -5</math>
:Die beiden Normalenvektoren sind nicht [[Kollinearität|kollinear]], also auch die beiden Geraden nicht. Sie schneiden sich deshalb in genau einem Punkt.
:Der Schnittpunkt <math>\textstyle (1 \mid -2)</math> bedeutet, dass die Lösung <math>x_1 = 1</math> und <math>x_2 = -2</math> ist. Die Lösungsmenge ist einelementig: <math>\textstyle L = \{(1, -2)\}</math>.
* '''Keine Lösung:'''
:<math>\begin{matrix}
2x_1 & - x_2 & = & 4\\
4x_1 & - 2x_2 & = & 1\\
\end{matrix}</math>
:Die entsprechenden Geradengleichungen sind
: <math>\begin{pmatrix} 2 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 4 \quad</math> und <math>\quad \begin{pmatrix} 4 \\ -2 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 1</math>.
:Die Normalenvektoren sind kollinear, daher sind die beiden Geraden parallel.
:Sie sind aber nicht identisch, daher gibt es keine Schnittpunkte und damit auch keine Lösung. Die Lösungsmenge ist leer: <math>\textstyle L = \{\}</math>.
* '''Unendlich viele Lösungen:'''
:<math>\begin{matrix}
2x_1 & - x_2 & = & 4\\
4x_1 & - 2x_2 & = & 8\\
\end{matrix}</math>
:Die beiden Geradengleichungen lauten
: <math>\begin{pmatrix} 2 \\ -1 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 4 \quad</math> und <math>\quad \begin{pmatrix} 4 \\ -2 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = 8</math>.
:Die Normalenvektoren sind kollinear. Die beiden Geraden sind nicht nur parallel, sondern sogar identisch.
:Es gibt somit unendlich viele Schnittpunkte und damit auch unendlich viele Lösungen. Die Lösungsmenge ist <math>\textstyle L = \{(x_1, x_2) \mid 2x_1 - x_2 = 4\}</math>.

Entsprechende Überlegungen können auch auf Ebenen im Raum bzw. Hyperebenen im ''n''-dimensionalen Vektorraum übertragen werden.
}}

=== Lösbarkeitskriterien ===
Ein lineares Gleichungssystem ist genau dann lösbar, wenn der [[Rang (Lineare Algebra)|Rang]] der Koeffizientenmatrix <math>A</math> gleich dem Rang der erweiterten Koeffizientenmatrix <math>(A\mid b)</math> ist ([[Satz von Kronecker-Capelli]])''.'' Ist der Rang der Koeffizientenmatrix gleich dem Rang der erweiterten Koeffizientenmatrix und auch gleich der Anzahl der Unbekannten, so besitzt das Gleichungssystem genau eine Lösung.

Bei einem quadratischen Gleichungssystem, also im Fall <math>m=n</math> (siehe unten), gibt die [[Determinante (Mathematik)|Determinante]] Auskunft über die Lösbarkeit. Das Gleichungssystem ist genau dann eindeutig lösbar, wenn der Wert der Determinante der Koeffizientenmatrix ungleich null ist. Ist der Wert jedoch gleich null, hängt die Lösbarkeit von den Werten der Nebendeterminanten ab. Bei diesen wird jeweils eine Spalte der Koeffizientenmatrix durch die Spalte der rechten Seite (den Vektor <math>b</math>) ersetzt. Nur wenn alle Nebendeterminanten den Wert null haben, kann das System unendlich viele Lösungen haben, ansonsten ist das Gleichungssystem unlösbar.

Insbesondere Gleichungssysteme mit mehr Gleichungen als Unbekannten, sogenannte [[Überbestimmung|überbestimmte Gleichungssysteme]], besitzen häufig keine Lösung. Beispielsweise besitzt das folgende Gleichungssystem keine Lösung, da <math>x_1</math> nicht beide Gleichungen erfüllen kann:
:<math>\begin{matrix}
3x_1 & = & 2\\
4x_1 & = & 2
\end{matrix}</math>

Näherungslösungen von überbestimmten Gleichungssystemen werden dann meist über die [[Ausgleichungsrechnung]] definiert und bestimmt.

Dass ein lineares Gleichungssystem unendlich viele Lösungen hat, kann nur vorkommen, wenn es weniger [[Lineare Unabhängigkeit|linear unabhängige]] Gleichungen als Unbekannte gibt und der zugrundeliegende [[Körper (Algebra)|Körper]] <math>K</math> unendlich viele Elemente enthält. Beispielsweise besitzt das folgende (aus nur einer Gleichung bestehende) Gleichungssystem unendlich viele Lösungen, nämlich alle Vektoren mit <math>x_2 = 1 - x_1:</math>
:<math>x_1 + x_2 = 1</math>

=== Lösungsmenge ===
Die [[Lösungsmenge]] eines linearen Gleichungssystems besteht aus allen Vektoren <math>x</math>, für die <math>Ax = b</math> erfüllt ist:
:<math>L = \left\{x \mid Ax = b\right\}</math>

Liegt ein ''homogenes'' lineares Gleichungssystem vor, so bildet dessen Lösungsmenge <math>L</math> einen [[Untervektorraum]] von <math>K^n</math>. Damit gilt die [[Superposition (Mathematik)|Superpositionseigenschaft]], nach der für eine oder mehrere Lösungen <math>x_i \in K^n</math> auch deren [[Linearkombination]]en <math>\textstyle\sum\alpha_i\, x_i</math> (mit beliebigen <math>\alpha_i \in K</math>) Lösungen des Gleichungssystems sind. Die Lösungsmenge heißt daher auch ''Lösungsraum'' und ist identisch mit dem [[Kern (Algebra)|Kern]] der [[Matrix (Mathematik)|Matrix]] <math>A</math>. Bezeichnet <math>r</math> den Rang der Matrix <math>A</math>, dann ist nach dem [[Rangsatz]] die Dimension des Lösungsraumes gleich dem [[Defekt (Mathematik)|Defekt]] <math>d = n-r</math> der Matrix <math>A</math>.

Ist die Lösungsmenge eines ''inhomogenen'' linearen Gleichungssystem nicht leer, dann ist sie ein [[affiner Unterraum]] von <math>K^n</math>. Sie hat dann die Form <math>v + U</math>, wobei <math>U</math> der Lösungsraum des zugehörigen homogenen Gleichungssystems ist und <math>v</math> eine beliebige Lösung des inhomogenen Gleichungssystems. Ein inhomogenes Gleichungssystem ist folglich genau dann eindeutig lösbar, wenn der [[Nullvektor]] die einzige Lösung („triviale Lösung“) des homogenen Gleichungssystems ist. Insbesondere gilt entweder <math>L = \emptyset</math> oder <math>\operatorname{dim}(L) = n-r</math> mit <math>r=\operatorname{Rang}(A)</math>.

Die Lösungsmenge eines linearen Gleichungssystems verändert sich nicht, wenn eine der drei elementaren Zeilenumformungen durchgeführt wird:
# Vertauschen zweier Zeilen
# Multiplizieren einer Zeile mit einer von null verschiedenen Zahl
# Addieren einer Zeile (oder des Vielfachen einer Zeile) zu einer anderen Zeile
Die Lösungsmenge eines quadratischen linearen Gleichungssystems verändert sich sogar dann nicht, wenn das Gleichungssystem mit einer [[Reguläre Matrix|regulären Matrix]] multipliziert wird.

=== Bestimmung über die erweiterte Koeffizientenmatrix ===
Die Form der Lösungsmenge lässt sich grundsätzlich mit Hilfe der erweiterten Koeffizientenmatrix bestimmen, indem diese mit Hilfe elementarer Zeilenumformungen (siehe [[Gauß-Verfahren]]) auf Stufenform gebracht wird:
:<math>\left(
\begin{array}{cccccc|c}
a_{1, 1} & a_{1, 2} & \cdots & a_{1k} & \cdots & a_{1n} & b_1 \\
0 & a_{2, 2} & \cdots & a_{2k} & \cdots & a_{2n} & b_2 \\
\vdots & \ddots & \ddots & \vdots & \ddots & \vdots & \vdots \\
0 & \cdots & 0 & a_{kk} & \cdots & a_{kn} & b_k \\
\vdots & \ddots & \vdots & 0 & \cdots & 0 & \vdots \\
0 & \cdots & 0 & 0 & \cdots & 0 & b_m \\
\end{array}
\right)</math>
Um immer genau diese Form zu erhalten, muss man manchmal auch Spaltenvertauschungen durchführen. Spaltenvertauschungen ändern die Reihenfolge der Variablen, was man am Schluss berücksichtigen muss. Außerdem wird hier auch angenommen, dass die Koeffizienten <math>a_{jj}, j=1, \dotsc, k </math> nicht null sind.

Die Anzahl der Lösungen lässt sich dann an den <math>b_i</math> ablesen:
* Ist mindestens eines der <math>b_{k+1}, \dotsc, b_m</math> ungleich null, so gibt es keine Lösung.
* Sind alle <math>b_{k+1}, \dotsc, b_m</math> gleich null (oder <math>k = m</math>), so gilt:
** Ist <math>k = n</math>, so ist das Gleichungssystem eindeutig lösbar.
** Ist <math>k < n</math>, gibt es unendlich viele Lösungen. Der Lösungsraum hat die [[Dimension (Vektorraum)|Dimension]] <math>n - k</math>.

Durch weitere elementare Zeilenumformungen (siehe [[Gauß-Jordan-Verfahren]]) kann die Matrix in folgende Form gebracht werden:
:<math>\left(
\begin{array}{ccccccc|c}
1 & 0 & \cdots & 0 & a_{1, k+1} & \cdots & a_{1n} & b_1 \\
0 & 1 & \ddots & 0 & a_{2, k+1} & \cdots & a_{2n} & b_2 \\
\vdots & \ddots & \ddots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & \cdots & 0 & 1 & a_{k, k+1} & \cdots & a_{kn} & b_k \\
\vdots & \ddots & \vdots & 0 & \cdots & \cdots & 0 & \vdots \\
0 & \cdots & 0 & 0 & \cdots & \cdots & 0 & b_m \\
\end{array}
\right)</math>
Sofern es überhaupt eine Lösung gibt (<math>b_{k+1}, \dotsc, b_m = 0</math>), gilt für die Lösungsmenge <math>L</math>:
:<math>
L = \left\{\begin{array}{c|c}
\left(
\begin{array}{c}
b_1 \\
\vdots \\
b_k \\
0 \\
\vdots \\
0 \\
\end{array}
\right)
+
\left(
\begin{array}{cccc}
-a_{1, k+1} & -a_{1, k+2} & \cdots & -a_{1n} \\
\vdots & \ddots & \ddots & \vdots \\
-a_{k, k+1} & -a_{k, k+2} & \cdots & -a_{kn} \\
1 & 0 & \cdots & 0 \\
0 & 1 & \ddots & \vdots \\
\vdots & \ddots & \ddots & 0 \\
0 & \cdots & \cdots & 1 \\
\end{array}
\right)
\cdot
\begin{pmatrix}
s_{k+1} \\ s_{k+2} \\ \vdots \\ s_n
\end{pmatrix}
&
\begin{pmatrix}
s_{k+1} \\ s_{k+2} \\ \vdots \\ s_n
\end{pmatrix} \in K^{n-k}
\end{array}\right\}
</math>
Hierbei ist <math>s = \begin{pmatrix}
s_{k+1} \\ s_{k+2} \\ \vdots \\ s_n
\end{pmatrix}</math> der Vektor der freien Variablen.

== Formen von Gleichungssystemen ==
Lineare Gleichungssysteme können in Formen vorliegen, in denen sie leicht gelöst werden können. Vielfach werden beliebige Gleichungssysteme mittels eines Algorithmus in eine entsprechende Gestalt gebracht, um anschließend eine Lösung zu finden.

=== Quadratisch ===
Von einem ''quadratischen Gleichungssystem'' ist die Rede, wenn die Zahl der Unbekannten gleich der Zahl der Gleichungen ist. Ein Gleichungssystem dieser Form kann, wenn die Zeilen oder Spalten [[Lineare Unabhängigkeit|linear unabhängig]] sind, eindeutig gelöst werden (Lösungsverfahren werden weiter unten besprochen).

=== Stufenform, Treppenform ===
In der ''Stufenform'' (auch ''Zeilenstufenform'', ''Zeilennormalform'', ''Stufengestalt'', ''Staffelgestalt'', ''Treppenform'', ''Treppenstufenform'' oder ''Treppennormalform'') verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Durch die Anwendung des [[Gaußsches Eliminationsverfahren|gaußschen Eliminationsverfahrens]] kann jedes Gleichungssystem in diese Form gebracht werden.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind <math>0</math>):
:<math>\begin{matrix}
6 x_1 & + & 3 x_2 & + & 4 x_3 & = & 1\\
& & & - & 5 x_3 & = & 10
\end{matrix}</math>

Lineare Gleichungssysteme in Stufenform können durch Rückwärtseinsetzen (Rücksubstitution) gelöst werden. Beginnend mit der letzten Zeile wird damit die Unbekannte berechnet und das gewonnene Ergebnis jeweils in die darüberliegende Zeile eingesetzt, um die nächste Unbekannte zu berechnen.

Lösung des obigen Beispiels:
# Auflösen der zweiten Zeile nach <math>x_3:</math>
#: <math>x_3 = \frac{10}{-5} = -2</math>
# Einsetzen von <math>x_3</math> in die erste Zeile:
#: <math>6 x_1 + 3 x_2 + 4 \cdot (-2) = 1</math>
# Auflösen der ersten Zeile nach <math>x_2:</math>
#: <math>x_2 = -2 x_1 + 3</math>
# Mit <math>x_1=t</math> sind alle Vektoren der Form <math>\begin{pmatrix}t \\ -2t + 3 \\ -2\end{pmatrix}</math> Lösungen des Gleichungssystems.

=== Dreiecksform ===
Die ''Dreiecksform'' ist ein Sonderfall der Stufenform, bei der jede Zeile genau eine Unbekannte weniger als die vorhergehende hat. Das bedeutet, dass alle Koeffizienten <math>a_{ii}</math> der [[Hauptdiagonale]] von <math>0</math> verschieden sind. Die Dreiecksform entsteht bei Anwendung des [[Gaußsches Eliminationsverfahren|gaußschen Eliminationsverfahrens]], wenn das Gleichungssystem genau eine Lösung hat.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind <math>0</math>):
:<math>\begin{matrix}
6 x_1 & + & 3 x_2 & + & 4 x_3 & = & 1\\
& & 8 x_2 & + & 5 x_3 & = & -1\\
& & & - & 2 x_3 & = & 6
\end{matrix}</math>
Wie lineare Gleichungssysteme in Stufenform können auch solche in Dreiecksform durch Rückwärtseinsetzen gelöst werden.

=== Reduzierte Stufenform ===
Auch die ''reduzierte Stufenform'' (auch ''normierte Zeilenstufenform'') ist ein Sonderfall der Stufenform. Bei ihr treten die jeweils ersten Unbekannten jeder Zeile nur ein einziges Mal auf und haben den Koeffizienten <math>1</math>. Die reduzierte Stufenform eines linearen Gleichungssystems ist eindeutig: Es gibt also für jedes lineare Gleichungssystem genau eine reduzierte Stufenform. Durch die Anwendung des [[Gauß-Jordan-Algorithmus]] kann ein beliebiges lineares Gleichungssystem in diese Form gebracht werden.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind <math>0</math>):
:<math>\begin{matrix}
x_1 & & & & & + & 4 x_4 & = & -1\\
& & x_2 & & & - & 5 x_4 & = & -9\\
& & & & x_3 & - & 7 x_4 & = & 10
\end{matrix}</math>

Die Lösung des linearen Gleichungssystems kann nun direkt abgelesen werden: Sofern <math>x_4=t</math> gesetzt und das Gleichungssystem rekursiv gelöst wird, ergeben sich alle Vektoren der Form <math>(-4t - 1, 5t - 9, 7t + 10, t)^\mathsf{T}</math> als Lösungen.

=== Weitere Formen ===
In der Praxis relevant sind die Sonderfälle [[Dünnbesetzte Matrix|dünnbesetzter Matrizen]] (sehr große Matrizen mit relativ wenigen Elementen ungleich null) und [[Bandmatrix|Bandmatrizen]] (ebenfalls große Matrizen, deren nicht verschwindende Elemente sich um die Hauptdiagonale konzentrieren), die sich mit speziell angepassten Lösungsverfahren (s. u.) behandeln lassen.

== Lösungsverfahren ==
Die Methoden zur Lösung von linearen Gleichungssystemen werden in [[Iterationsverfahren|iterative]] und [[Direktes Verfahren|direkte]] Verfahren unterteilt. Beispiele für direkte Verfahren sind das [[Einsetzungsverfahren]], das [[Gleichsetzungsverfahren]] und das [[Additionsverfahren (Mathematik)|Additionsverfahren]] für einfache Gleichungssysteme sowie das auf dem Additionsverfahren basierende [[Gaußsches Eliminationsverfahren|gaußsche Eliminationsverfahren]], das ein Gleichungssystem auf Stufenform bringt. Eine Variante des Gauß-Verfahrens ist die [[Cholesky-Zerlegung]], die nur für [[Symmetrische Matrix|symmetrische]], [[Definitheit|positiv definite Matrizen]] funktioniert. Doppelt so viel Aufwand wie das Gauß-Verfahren braucht die [[QR-Zerlegung]], die dafür [[Stabilität (Numerik)|stabiler]] ist. Die [[Cramersche Regel]] verwendet Determinanten, um Formeln für die Lösung eines quadratischen linearen Gleichungssystems zu erzeugen, wenn dieses eindeutig lösbar ist. Für die numerische Berechnung ist sie auf Grund des hohen Rechenaufwands jedoch nicht geeignet.

Iterative Verfahren sind beispielsweise die zur Klasse der [[Splitting-Verfahren]] gehörenden [[Gauß-Seidel-Verfahren|Gauß-Seidel-]] und [[Jacobi-Verfahren]]. Diese konvergieren nicht für jede Matrix und sind für viele praktische Probleme sehr langsam. Modernere Verfahren sind etwa [[Vorkonditionierung|vorkonditionierte]] [[Krylow-Unterraum-Verfahren]], die insbesondere für große [[Dünnbesetzte Matrix|dünnbesetzte Matrizen]] sehr schnell sind, sowie [[Mehrgitterverfahren]] zur Lösung von Systemen, die aus der [[Diskretisierung]] bestimmter [[Partielle Differentialgleichung|partieller Differentialgleichungen]] stammen.

Bei Anwendungen (z. B. [[Geodäsie]]) werden oft Messungen unterschiedlichen Typs ausgeführt, und es werden, um die Auswirkung von [[Messfehler]]n zu verringern, mehr Messungen ausgeführt, als Unbekannte zu bestimmen sind. Jede Messung liefert eine Gleichung zur Bestimmung der Unbekannten. Wenn diese Gleichungen nicht alle linear sind, wird das Gleichungssystem mit Verwendung von bekannten Näherungswerten der Unbekannten [[Linearisierung|linearisiert]]. Dann sind anstelle der eigentlichen Unbekannten deren kleine Abweichungen von den Näherungswerten zu bestimmen. In der Regel widersprechen sich die Gleichungen, wenn mehr Gleichungen als Unbekannte vorhanden sind, sodass es keine strenge Lösung gibt. Als Ausweg wird dann üblicherweise durch eine [[Ausgleichungsrechnung|Ausgleichung]] mittels der [[Methode der kleinsten Quadrate]] eine Lösung bestimmt, die typischerweise keine Gleichung exakt erfüllt, aber unter vernünftigen Annahmen über die Messfehler eine optimale Näherung der „wahren“ Messgrößen angibt.

Die derzeit beste bekannte asymptotische obere Schranke an arithmetischen Operationen, um ein beliebiges lineares Gleichungssystem zu lösen, liefert ein praktisch nicht anwendbarer Algorithmus von [[Don Coppersmith]] und [[Shmuel Winograd]] aus dem Jahre 1990, der ein <math>n \times n</math>-System in [[Landau-Symbole|O(n<sup>2,376</sup>)]] löst.<ref>[[Gene Golub|Gene H. Golub]], Charles F. Van Loan: ''Matrix Computations.'' 3rd edition, reprint. Johns Hopkins University Press, Baltimore MD u. a. 1996, ISBN 0-8018-5414-8.</ref> Klar ist, dass mindestens O(n<sup>2</sup>) Operationen notwendig sind; nicht jedoch, ob diese untere Schranke auch erreicht werden kann.

Fast [[Singuläre Matrix|singuläre]] lineare Gleichungssysteme können durch [[Singulärwertzerlegung]] auf [[Numerische Mathematik|numerische Weise]] passabel gelöst werden.

== Literatur ==
* [[Ferdinand Georg Frobenius|G. Frobenius]]: ''Zur Theorie der linearen Gleichungen.'' In: ''Journal für die reine und angewandte Mathematik (= Crelle’s Journal.)'' Bd. 129, 1905 {{ISSN|0075-4102}}, S. 175–180, [https://gdz.sub.uni-goettingen.de/id/PPN243919689_0129 Göttinger Digitalisierungszentrum.]
* [[Andreas Meister]]: ''Numerik linearer Gleichungssysteme. Eine Einführung in moderne Verfahren.'' 2., überarbeitete Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.
* Falko Lorenz: ''Lineare Algebra.'' Band 1, 4. Auflage. Spektrum Akademischer Verlag, Heidelberg u. a. 2003, ISBN 3-8274-1406-7.
* [[Gerd Fischer (Mathematiker)|Gerd Fischer]]: ''Lineare Algebra.'' 15., verbesserte Auflage. Vieweg, Wiesbaden 2005, ISBN 3-8348-0031-7.

== Weblinks ==
{{Commonscat|System of linear equations|Lineares Gleichungssystem}}
* [http://www.gecco.info/math/dokumente.html PDF-Sammlung auf gecco.info.] Ausführliche Beschreibung verschiedener Lösungsmöglichkeiten von linearen Gleichungssystemen (einfach, ohne Matrizen).
* [https://www.arndt-bruenner.de/mathe/scripts/gleichungssysteme.htm Arndt Brünner Scripts.] Online-Rechner zum Lösen linearer Gleichungssysteme.
* [https://wims.univ-cotedazur.fr/wims/wims.cgi?module=tool/linear/linsolver.en Online-Löser] auf ''Université Côte d'Azur'', für lineare Gleichungssysteme (französisch oder englisch).
* [https://www.youtube.com/watch?v=V77joKwBifU Einführung zu den drei Lösungsverfahren (Video)] für Schüler und Studenten.

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4035826-4}}

[[Kategorie:Lineare Algebra]]
[[Kategorie:Wikipedia:Artikel mit Video]]

Lineares Gleichungssystem - Versionsgeschichte

imported>AmeisenBot: Bot: Ergänze :Kategorie:Wikipedia:Artikel mit Video