Lineares Gleichungssystem

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Als lineares Gleichungssystem bezeichnet man in der linearen Algebra ein System aus linearen Gleichungen, die mehrere unbekannte Größen (Variablen) enthalten.

Ein entsprechendes System für drei Unbekannte $x 1$ , $x 2$ , $x 3$ sieht beispielsweise wie folgt aus:

$\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}$

Allgemein lässt sich ein lineares Gleichungssystem mit $m$ Gleichungen und $n$ Unbekannten immer in die folgende Form bringen:

$\begin{matrix} a_{11} x_1 + a_{12} x_2 & \cdots & a_{1n} x_n & = & b_1\\ a_{21} x_1 + a_{22} x_2 & \cdots & a_{2n} x_n & = & b_2\\ &&&\vdots&\\ a_{m1} x_1 + a_{m2} x_2 & \cdots & a_{mn} x_n & = & b_m\\ \end{matrix}$

Mit Gleichungssystemen werden Zusammenhänge modelliert um interessierende Größen bestimmen zu können.

Inhaltsverzeichnis

1 Beispiel
- 1.1 Aufgabe
- 1.2 Lösung
2 Matrixform
3 Bezeichnungen
4 Lösbarkeit
- 4.1 Lösungsmenge
- 4.2 Bestimmung über die erweiterte Koeffizientenmatrix
5 Formen von Gleichungssystemen
6 Lösungsverfahren
7 Siehe auch
8 Weblinks

[Bearbeiten] Beispiel

[Bearbeiten] Aufgabe

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?

[Bearbeiten] Lösung

Das Alter des Vaters wird durch die Variable $x$ und das des Sohnes durch $y$ repräsentiert. Die Angaben aus der Aufgabenstellung bilden in formalisierter Form ein lineares Gleichungssystem mit zwei Unbekannten.

$\begin{matrix} (1) & x & + & y & = & 62 \\ (2) & x & - & 6 & = & 4 & \cdot & (y - 6) \end{matrix}.$

Subtrahiert man in Gleichung $(1)$ auf beiden Seiten $x$ , dann entsteht die Gleichung

$(1') \quad y = 62 - x.$

Setzt man nun $(1')$ in $(2)$ ein, so folgt

$\begin{matrix} (2)& x & - & 6 & = & 4 & \cdot & (y - 6) \\ &x & - & 6 & = & 4 & \cdot & (62 - x - 6) & \\ &x & - & 6 & = & 4 & \cdot & (56 - x) & \\ &x & - & 6 & = & 224 & - & 4x & | & +4x\ +6 \\ & & & 5x & = & 230 & & & | & \div5 \\ & & & x & = & 46 \end{matrix}.$

Setzt man dieses Ergebnis in $(1')$ ein so folgt dann

$\begin{matrix} (1') & y & = & 62 & - & x \\ & y & = & 62 & - & 46 \\ & y & = & 16 \end{matrix}.$

Also ist der Vater 46 Jahre und der Sohn 16 Jahre alt, zusammen also 62 Jahre. Vor sechs Jahren waren der Vater 40 Jahre und der Sohn 10 Jahre alt, der Vater also viermal so alt wie der Sohn.

[Bearbeiten] Matrixform

Für die Behandlung von linearen Gleichungssystemen ist es nützlich, alle Koeffizienten $a i j$ zu einer Matrix $A$ , der sogenannten Koeffizientenmatrix zusammenzufassen:

$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$

Des Weiteren lassen sich auch alle Unbekannten und die rechte Seite des Gleichungssystems als einspaltige Matrizen niederschreiben:

$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}.$

Damit schreibt sich ein lineares Gleichungssystem kurz

A x = b .

Sowohl die Koeffizienten $a i j$ , die Unbekannten $x i$ , als auch die rechten Seiten $b j$ entstammen dem selben Körper. Insbesondere gilt

$A \in \mathbb{K}^{{m}\times{n}}$ , $b \in \mathbb{K}^{m}$ und $x \in \mathbb{K}^{n}.$

Zur Festlegung eines linearen Gleichungssystems ist die Angabe der Unbekannten nicht nötig. Es genügt die Angabe der erweiterten Koeffizientenmatrix, die entsteht wenn an die Koeffizientenmatrix $A$ eine Spalte mit der rechten Seite $b$ des Gleichungssystems angefügt wird:

$\begin{pmatrix}A & b\end{pmatrix} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ & & & \vdots & \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{pmatrix}.$

[Bearbeiten] Bezeichnungen

Man nennt das Gleichungssystem homogen, wenn alle $b i$ gleich 0 sind, ansonsten inhomogen. Homogene Gleichungssysteme haben stets 0 als gültige Lösung, inhomogene nie.

Hat das Gleichungssystem weniger Gleichungen als Unbekannte, so spricht man von einem unterbestimmten Gleichungssystem. Hat es jedoch mehr Gleichungen als Unbekannte, nennt man es ein überbestimmtes Gleichungssystem (typischerweise gibt es keine exakte Lösung, woraufhin man oft an einer Stelle mit minimalem Fehler interessiert ist, siehe Ausgleichsrechnung). Hat das Gleichungssystem genau gleich viele Gleichungen wie Unbekannte spricht man von einem quadratischen Gleichungssystem.

[Bearbeiten] Lösbarkeit

Ein Vektor $x$ ist eine Lösung des linearen Gleichungssystems, wenn $A \cdot x = b$ gilt. Ob und wie viele Lösungen ein Gleichungssystem besitzt ist unterschiedlich. Bei linearen Gleichungssystemen treten drei Fälle auf:

das lineare Gleichungssystem hat keine Lösung.
das lineare Gleichungssystem hat genau eine Lösung.
das lineare Gleichungssystem hat unendlich viele Lösungen.

Dabei ist das lineare Gleichungssystem genau dann lösbar, wenn der Rang der Koeffizientenmatrix $A$ gleich dem Rang der erweiterten Koeffizientenmatrix ist. Entspricht der Rang der erweiterten Koeffizientenmatrix auch noch der Anzahl der Unbekannten, so besitzt das Gleichungssystem genau eine Lösung.

Bei einem quadratischen Gleichungssystem gibt die 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 b) ersetzt. Nur wenn alle Nebendeterminanten den Wert Null haben, kann das System unendlich viele Lösungen haben, ansonsten ist das Gleichungssystem unlösbar.

Insbesondere überbestimmte Gleichungssysteme besitzen oft keine Lösung. Hier sind dann Gleichungen vorhanden, die im Widerspruch zueinander stehen. Beispielsweise besitzt das folgende Gleichungssystem keine Lösung, da $x 1$ nicht beide Gleichungen erfüllen kann:

$\begin{matrix} 3x_1 & = & 2\\ 4x_1 & = & 2. \end{matrix}$

Dass ein lineares Gleichungssystem unendlich viele Lösungen hat, kommt dagegen insbesondere bei unterbestimmten Gleichungssystemen vor. Beispielsweise besitzt das folgende, aus nur einer Gleichung bestehende Gleichungssystem unendlich viele Lösungen, nämlich alle Vektoren mit $x 2 = 1 - x 1$ :

x 1 + x 2 = 1.

[Bearbeiten] Lösungsmenge

Die Lösungsmenge eines linearen Gleichungssystems besteht aus allen Vektoren $x$ , für die $A x = b$ erfüllt ist:

L = {x | A x = b}.

Liegt ein homogenes lineares Gleichungssystem vor, so bildet dessen Lösungsmenge einen Vektorraum. Damit sind für eine oder mehrere Lösungen $x_i \in \mathbb{K}^n$ auch deren Linearkombinationen $\sum\alpha_i\, x_i$ (mit beliebigen $\alpha_i \in \mathbb{K}$ ) Lösungen des Gleichungssystems. Den so entstandenen Lösungsraum nennt man Kern der Matrix $A$ . Das inhomogene Gleichungssystem ist genau dann eindeutig lösbar, wenn der Nullvektor die einzige Lösung („triviale Lösung“) des homogenen Gleichungssystems ist.

Die Lösungsmenge eines inhomogenen linearen Gleichungssystem ist eine lineare Mannigfaltigkeit bzw. ein affiner Raum.

Die Lösungsmenge eines linearen Gleichungssystems verändert sich nicht, wenn man eine der drei elementaren Zeilenumformungen durchführt

Vertauschen zweier (kompletter) 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 nicht, wenn das Gleichungssystem mit einer regulären Matrix multipliziert wird.

[Bearbeiten] 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 der elementaren Zeilenumformungen auf eine Dreiecksform gebracht wird:

$\left( \begin{array}{cccc|c} c_{11}&c_{12}&\dots&c_{1n}&d_1\\ 0&c_{22}&\dots&c_{2n}&d_2\\ \vdots&&\ddots&\vdots&\vdots\\ 0&\dots& & c_{mn}&d_m \end{array}\right)$

Die Anzahl der Lösungen lässt sich dann an der letzten Zeile ablesen. Gibt es in der letzten Zeile mindestens zwei Einträge aus der Matrix die ungleich Null sind (dies impliziert weniger Gleichungen als Unbekannte), so gibt es keine Lösungen. Ebenfall keine Lösungen gibt es, falls alle c_i in der letzten Zeile Null sind, $d m$ aber nicht. Ist $c m n$ als einziges c_i in der letzten Zeile ungleich Null, so ist das Gleichungssystem eindeutig lösbar. Ist $c m n$ gleich Null und $d m$ auch, gibt es unendlich viele Lösungen.

[Bearbeiten] 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.

[Bearbeiten] Stufenform, Treppenform

In der Stufenform (auch Zeilenstufenform, Stufengestalt, Staffelgestalt, Treppenform oder Treppennormalform) verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Man kann ein beliebiges Gleichungssystem durch Anwendung des gaußschen Eliminationsverfahrens in diese Form bringen.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind 0):

Polynomform	Matrixform
$\begin{matrix} 6 x_1 & + & 3 x_2 & + & 4 x_3 & = & 1\\ & & & - & 5 x_3 & = & 10 \end{matrix}$	$\begin{pmatrix}6&3&4\\0&0&-5\end{pmatrix}\,\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}1\\10\end{pmatrix}$

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

Lösung des obigen Beispiels:

Polynomform	Matrixform
Auflösen der zweiten Zeile nach $x 3$ : $x_3 = \frac{10}{-5} = -2$ Einsetzen von $x 3$ in die erste Zeile: $6 x_1 + 3 x_2 + 4 \cdot (-2) = 1$ Auflösen der ersten Zeile nach $x 2$ : $x 2 = - 2 x 1 + 3$ Damit sind alle Vektoren der Form $\begin{pmatrix}t \\ 3-2\,t \\ -2\end{pmatrix}$ Lösungen des Gleichungssystems.	Durch Anwendung des Gauß-Algorithmus formt man die Matrix in folgende Form um: $\left( \begin{array}{ccc\|c}2&1&0&3\\0&0&1&-2\end{array}\right)$ Da der Rank der Matrix gleich 2 ist, jedoch drei Variablen gesucht sind muss man mit $t$ erweitern. Im gegebenen Beispiel wird $x 1 = t$ gesetzt: $\left( \begin{array}{ccc\|c}2&1&0&3\\0&0&1&-2\\1&0&0&t\end{array}\right)$ Die Anwendung des Gauß-Jordan-Algorithmus liefert unmittelbar: $\left(\mathbf{I}\left\|\begin{matrix}t\\3-2\,t\\-2\end{matrix}\right.\right)$

Polynomform

Matrixform

Auflösen der zweiten Zeile nach $x 3$ :

$x_3 = \frac{10}{-5} = -2$
Einsetzen von $x 3$ in die erste Zeile:

$6 x_1 + 3 x_2 + 4 \cdot (-2) = 1$
Auflösen der ersten Zeile nach $x 2$ :

$x 2 = - 2 x 1 + 3$
Damit sind alle Vektoren der Form $\begin{pmatrix}t \\ 3-2\,t \\ -2\end{pmatrix}$ Lösungen des Gleichungssystems.

Durch Anwendung des Gauß-Algorithmus formt man die Matrix in folgende Form um:

$\left( \begin{array}{ccc|c}2&1&0&3\\0&0&1&-2\end{array}\right)$
Da der Rank der Matrix gleich 2 ist, jedoch drei Variablen gesucht sind muss man mit $t$ erweitern. Im gegebenen Beispiel wird $x 1 = t$ gesetzt:

$\left( \begin{array}{ccc|c}2&1&0&3\\0&0&1&-2\\1&0&0&t\end{array}\right)$
Die Anwendung des Gauß-Jordan-Algorithmus liefert unmittelbar:

$\left(\mathbf{I}\left|\begin{matrix}t\\3-2\,t\\-2\end{matrix}\right.\right)$

[Bearbeiten] 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 $a i i$ der Hauptdiagonale von $0$ verschieden sind. Die Dreiecksform entsteht bei Anwendung des gaußschen Eliminationsverfahrens, wenn das Gleichungssystem genau eine Lösung hat.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind 0):

Polynomform	Matrixform
$\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}$	$\begin{pmatrix}6&3&4\\0&8&5\\0&0&2\end{pmatrix}\,\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}1\\-1\\6\end{pmatrix}$

Man unterscheidet bei Dreiecksform weiter in die obere und die untere Dreiecksform:

obere	untere
Dreiecksform
$\begin{pmatrix}2&3&1\\0&3&5\\0&0&5\end{pmatrix}$	$\begin{pmatrix}2&0&0\\5&7&0\\1&3&4\end{pmatrix}$

Wie lineare Gleichungssysteme in Stufenform können auch solche in Dreiecksform durch Rückwärtseinsetzen gelöst werden.

[Bearbeiten] Reduzierte Stufenform

Auch die reduzierte Stufenform ist ein Sonderfall der Stufenform. Bei ihr treten die jeweils ersten Unbekannten jeder Zeile nur ein einziges Mal auf und haben den Koeffizienten $1$ . Die reduzierte Stufenform eines linearen Gleichungssystems ist eindeutig: es gibt also für jedes lineare Gleichungssystem genau eine reduzierte Stufenform. Man kann ein beliebiges lineares Gleichungssystem durch Anwendung des Gauß-Jordan-Algorithmus in diese Form bringen.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind 0):

Polynomform	Matrixform
$\begin{matrix} x_1 & & & & & + & 4 x_4 & = & -1\\ & & x_2 & & & - & 5 x_4 & = & -9\\ & & & & x_3 & - & 7 x_4 & = & 10\end{matrix}$	$\left( \mathbf{I},\begin{pmatrix}4\\-5\\-7\end{pmatrix}\right) \, \begin{pmatrix}x_1\\x_2\\x_3\\x_4\end{pmatrix}= \begin{pmatrix}-1\\-9\\10\end{pmatrix}$

Die Lösung des linearen Gleichungssystems kann direkt abgelesen werden. Im Fall des obigen Beispiels sind alle Vektoren der Form $( - 4 t, - 1,5 t - 9,7 t + 10, t) T$ Lösungen.

[Bearbeiten] Lösungsverfahren

Die Methoden zur Lösung von linearen Gleichungssystemen unterteilt man in iterative und direkte Verfahren. Beispiele für direkte Verfahren sind das Einsetzungsverfahren, das Gleichsetzungsverfahren und das Additionsverfahren für einfache Gleichungssystemen, das auf dem Additionsverfahren basierende gaußsche Eliminationsverfahren, das ein Gleichungssystem auf Stufenform bringt. Eine Variante des Gauß-Verfahrens ist die Cholesky-Zerlegung, die nur für symmetrische, positiv definite Matrizen funktioniert. Doppelt so viel Aufwand wie das Gauß-Verfahren braucht die QR-Zerlegung, die dafür stabiler ist. Die Cramer’sche 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- und Jacobi-Verfahren. Diese konvergieren nicht für jede Matrix und sind für viele praktische Probleme sehr langsam. Modernere Verfahren sind vorkonditionierte Krylow-Unterraum-Verfahren, die insbesondere für große dünnbesetzte Matrizen sehr schnell sind.

Bei Anwendungen (z.B. Geodäsie) sind oft überbestimmte Gleichungssysteme zu lösen. Um den Messfehler von Messungen zu verringern, wird auf verschiedene Arten gemessen und es existieren mehr Messergebnisse als Unbekannte. In der Regel widersprechen sich die Gleichungen, wenn mehr Gleichungen als Unbekannte vorhanden sind. Als weitere Bedingung wird dann fast immer gestellt, dass die 2-Norm (die Addition der einzelnen Komponentenquadrate) des Residuenvektors minimal wird. Das liefert die Methode der kleinsten Quadrate.

Die Frage, wieviele arithmetische Operationen mindestens nötig sind, um ein beliebiges lineares Gleichungssystem zu lösen, ist offen. Die beste theoretische untere Schranke liefert ein praktisch nicht anwendbarer Algorithmus von Coppersmith und Winograd aus dem Jahre 1990, der ein $n \times n$ -System in $O (n 2,376)$ löst.

[Bearbeiten] Siehe auch

[Bearbeiten] Weblinks

Applet zum Lösen linearer Gleichungssysteme
Arndt Brünner Scripts Der Online-Rechner zum Lösen linearer Gleichungssysteme.
Online-Löser für lineare Gleichungssysteme (englisch, aber unterstützt Parameter)

Von „http://de.wikipedia.org../../../l/i/n/Lineares_Gleichungssystem_222e.html“

Kategorie: Lineare Algebra

Lineares Gleichungssystem

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Beispiel

[Bearbeiten] Aufgabe

[Bearbeiten] Lösung

[Bearbeiten] Matrixform

[Bearbeiten] Bezeichnungen

[Bearbeiten] Lösbarkeit

[Bearbeiten] Lösungsmenge

[Bearbeiten] Bestimmung über die erweiterte Koeffizientenmatrix

[Bearbeiten] Formen von Gleichungssystemen

[Bearbeiten] Stufenform, Treppenform

[Bearbeiten] Dreiecksform

[Bearbeiten] Reduzierte Stufenform

[Bearbeiten] Lösungsverfahren

[Bearbeiten] Siehe auch

[Bearbeiten] Weblinks

Views

Navigation

Mitmachen

Suche

Andere Sprachen