Lineare Gleichungssysteme

Lineare Gleichungssysteme haben entweder genau eine, keine, oder unendlich viele Lösungen.
Systeme von $m$ linearen Gleichungen mit $n$ Unbekannten $x_1;x_2;x_3;\dots ;x_n$

$$\begin{array}{rl}{a}_{11}\cdot x_1+a_{12}\cdot x_2+\cdots +a_{1n}\cdot x_n& =b_1\\ a_{21}\cdot x_1+a_{22}\cdot x_2+\cdots +a_{2n}\cdot x_n& =b_2\\ \dots & \\ a_{m1}\cdot x_1+a_{32}\cdot x_2+\cdots +a_{mn}\cdot x_n& =b_m\end{array}$$

Kurz $(m\times n)$-System

$$\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{m1}& \dots & a_{mn}\end{array}\right)\cdot \left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)=\left(\begin{array}{c}{b}_1\\ ⋮\\ b_n\end{array}\right)$$

Durch Hinzufügen des Vektors $b$ zur Koeffizientenmatrix entsteht die sogenannte “erweiterte Matrix” des LGS $B$

$$B=(A;B)=\left(\begin{array}{cccc}{a}_{11}& \dots & a_{1n}& b_1\\ ⋮& \ddots & ⋮& ⋮\\ a_{m1}& \dots & a_{mn}& b_n\end{array}\right)$$

Homogenes LGS	Inhomogenes LGS
$b=0$ also alle $b_i=0$	$b\ne 0$

Lösen von LGS

Erlaubte Operationen:

1. Multiplizieren von Gleichungen mit $p\in \mathbb{R}\setminus \{0\}$
2. Addition des $p$-fachen einer Gleichung zu einer anderen Gleichung unter Beibehaltung der 1. Gleichung
3. Vertauschen von Gleichungen

Der Gauß-Algorithmus zum Lösen eines LGS

Ziel ist es, die Matrix in die obere Dreiecksform zu bringen.

1. Eindeutig Lösbares, Homogenes LGS $(n\times n)$

$$\begin{array}{lc}\left(\begin{array}{cccccc}2x_1& -x_2& -x_3& =& 2& (a)\\ 4x_1& +0& +6x_3& =& 2& (b)\\ -3x_1& +2x_2& -x_3& =& 1& (c)\end{array}\right)=\left(\begin{array}{cccc}2& -1& -1& 2\\ 4& 0& 6& 2\\ -3& 2& -1& 1\end{array}\right)& c^{\ast }=2\ast c+3\ast a\\ & \\ \left(\begin{array}{ccccc}2& -1& -1& 2& (a)\\ 4& 0& 6& 2& (b)\\ 0& 1& -5& 8& (c^{\ast })\end{array}\right)& b^{\ast }=b-2\ast a\\ & \\ \left(\begin{array}{ccccc}2& -1& -1& 2& (a)\\ 0& 2& 8& -2& (b^{\ast })\\ 0& 1& -5& 8& (c^{\ast })\end{array}\right)& c^{\ast \ast }=2\ast c^{\ast }-b^{\ast }\\ & \\ \left(\begin{array}{ccccc}2& -1& -1& 2& (a)\\ 0& 2& 8& -2& (b^{\ast })\\ 0& 0& -18& 18& (c^{\ast \ast })\end{array}\right)\to x_3=-1x_2=3x_1=2& \end{array}$$

2. Nicht-eindeutig lösbares, inhomogenes $(n\times n)$ System

Keine Lösung durch Widerspruch

$$\begin{array}{lc}\left(\begin{array}{ccccc}3& 2& -1& -2& (a)\\ 0& 1& -1& 1& (b)\\ 4.5& 3& -1.5& 0& (c)\end{array}\right)& c^{\ast }=3\ast a-2\ast c\\ & \\ \left(\begin{array}{ccccc}3& 2& -1& -2& (a)\\ 0& 1& -1& 1& (b)\\ 0& 0& 0& -6& (c)\end{array}\right)& \perp \to \text{Keine Lo¨sung}\end{array}$$

Unendlich viele Lösungen durch $0=0$ Zeile

$$\begin{array}{lc}\left(\begin{array}{ccccc}1& -2& 1& 3& (a)\\ 0& 1& -3& -5& (b)\\ -2& 4& -2& -6& (c)\end{array}\right)& c^{\ast }=2\ast a+c\\ & \\ \left(\begin{array}{ccccc}1& -2& 1& 3& (a)\\ 0& 1& -3& -5& (b)\\ 0& 0& 0& 0& (c)\end{array}\right)& x_3=t\\ & \\ x_2-3t=-5& \\ \to x_2=3t-5& \\ & \\ x_1-2\ast (3t-5)+t=3& \\ x_1-6t-10+t=3& \\ x_1+10-5+t=3& \\ \to x_1=5t-7& \\ & \\ L=\left((5t-7);(3t-5);t\right)& \end{array}$$

3. Homogenes System $A\ast x=0$

Besitzt immer die triviale Lösung $x_1=x_2=x_3=0$
Wenn eine weitere Lösung gefunden wird, hat das LGS unendlich viele Lösungen.
Vgl. Cramer’sche Regel für ein (2x2)-System

4. Unterbestimmtes LGS - Weniger Gleichungen als Unbekannte

Falls das LGS überhaupt lösbar ist, hat es unendlich viele Lösungen da mindestens eine Unbekannte frei gewählt werden kann.

5. Überbestimmtes LGS

Ein LGS ist dann überbestimmt, wenn es mehr Gleichungen als Unbekannte besitzt. Zum Lösen werden bei $n$ Unbekannten die ersten $n$ beliebigen Gleichungen verwendet. Anschließend müssen die Lösungen mit allen Gleichungen verifiziert werden, ein einzelner Widerspruch führt zur Ungültigkeit der Ergebnisse.

6. LGS mit Parametern

$$\begin{array}{lc}\left(\begin{array}{ccccc}1& -1& \frac{r}{3}& 1& (a)\\ 0& 3& -r& 0& (b)\\ 3& -3& r^2& r+2& (c)\end{array}\right)& c^{\ast }=c-3\ast a\\ & \\ \left(\begin{array}{ccccc}1& -1& \frac{r}{3}& 1& (a)\\ 0& 3& -r& 0& (b)\\ 0& 0& (r^2-r)& r-1& (c^{\ast })\end{array}\right)& x_3=\frac{r-1}{r^2-r}\to r\ne \{0;1\}\\ & \\ \to x_3=\frac{r-1}{r^2-r}=\frac{r-1}{r\ast (r-1)}=\frac{1}{r}& \\ & \\ \to x_2-r\ast \left(\frac{1}{r}\right)=0& \\ \to x_2=\frac{1}{3}& \\ & \\ \to x_1-\frac{1}{3}+\frac{r}{3}\ast \left(\frac{1}{r}\right)=1& \\ \to x_1=1& \\ & \\ & \\ L_r=\left\{\left(1;\frac{1}{3};\frac{1}{r}\right)\right\}& \\ r=0\text{ fu¨hrt in c∗ zu einem Widerspruch}& \\ & \\ L_0=\{\}& \\ & \\ r=1\text{ fu¨hrt in c∗ zu einer Tautologie}& \\ \dots & \\ L_1=\left\{\left(1;\frac{1}{3}t;t\right)t\in \mathbb{R}\right\}& \end{array}$$

Zusammenfassung

	$A+x=bb\ne 0$ Inhomogen	$A\ast x=0$ Homogen
$det(A)\ne 0$	Eindeutig lösbar	Nur triviale Lösung $0$
$det(A)=0$	Entweder Unendlich viele Lösungen oder gar keine	Unendendlich viele, nicht-triviale Lösungen und die triviale Lösung
Der Gauß-Algorithmus ist auf jedes $(n\times m)$-System anwendbar, Cramer’sche Regel nur im Sonderfall $n=m$ anwendbar.
Für $n>3$ wird der Rechenaufwand zur Bestimmung der Determinanten zu groß.
$\to$ Gauß Algo ist dann deutlich schneller / bzw. besser.