Lineare Gleichungssysteme

Methoden

Motivation

Wenn mehrere lineare Gleichungen von den Variablen erfüllt werden sollen, spricht man von einem linearen Gleichungssystem, das wir oft als LGS abkürzen. Englisch: system of linear equations oder linear system. Lineare Gleichungssysteme kommen in vielen Anwendungen vor: Geometrie, Naturwissenschaften, Technik, Informatik, Wirtschaft etc. Sie haben die Vorteile, dass sie mit Hilfe von Matrizen und Vektoren kompakt dargestellt werden können, ihre Lösbarkeit leicht bestimmbar ist und dass es effiziente Lösungsverfahren gibt. Zudem können viele nicht-lineare Probleme näherungsweise durch lineare Gleichungssysteme beschrieben werden, siehe z. B. das Newtonverfahren oder die Finite-Elemente-Methode.

Modellierung

Wie kommt man zu einem linearen Gleichungssystem? Im folgenden betrachten wir einige Beispiele aus verschiedenen Anwendungsgebieten.

Geometrie

Wann schneiden sich zwei Geraden in der Ebene, und wie berechnet man ggf. den Schnittpunkt? Jede Gerade kann durch eine lineare Gleichung der Form \(ax + by = c\) beschrieben werden. Dabei sind \(a\), \(b\) und \(c\) gegebene Zahlen. Linear bedeutet hier, dass die Variablen \(x\) und \(y\) nur mit einer Zahl multipliziert und addiert werden dürfen, aber z. B. nicht potenziert oder multipliziert werden dürfen. Die Gleichung \(ax + by = c\) beschreibt alle Punkte \((x, y)\), die auf der Geraden liegen. Wir suchen nun alle Punkte \((x, y)\), die beide Gleichungen erfüllen, also auf beiden Geraden liegen. Diese Schnittpunkte bilden die Lösungsmenge des linearen Gleichungssystems. Unsere geometrische Vorstellung sagt uns, dass es drei Möglichkeiten gibt: Die Geraden schneiden sich in einem Punkt, sie sind parallel und haben keinen Schnittpunkt, oder sie sind identisch und haben unendlich viele Schnittpunkte. Die geometrische Intuition stimmt und lässt auf höhere als zwei Dimensionen verallgemeinern.

Beispiel: \[ \begin{aligned} 2x - 5y & = 8 \\ -x + 7y & = 5 \end{aligned} \] Die Geraden schneiden sich in einem Punkt, nämlich im Punkt \((x, y) = (9, 2)\).

Kinematik

Die Kinematik beschäftigt sich mit der Beschreibung der Bewegung von Körpern. Wenn sich zum Beispiel zwei Flugzeuge in einer Ebene (z. B. auf einer Landkarte) gleichförmig geradlinig bewegen, dann können ihre Positionen zu jedem Zeitpunkt \(t\) durch Vektoren \(P_1(t) = Q_1 + t v_1\) und \(P_2(t)=Q_2 + t v_2\) mit \(Q_i, v_i \in \mathbb{R}^2\) für \(i=1,2\) beschrieben werden, siehe Geradengleichung in Parameterform. Die Punkte \(Q_i\) sind ihre Positionen zum Zeitpunkt \(t=0\), und die Vektoren \(v_i\) sind die Geschwindigkeiten der Flugzeuge.

Beispiel: \[ \begin{aligned} P_1(t) & = \begin{pmatrix} 1 \\ -2 \end{pmatrix} + t \begin{pmatrix} -3 \\ 4 \end{pmatrix} \\ P_2(t) & = \begin{pmatrix} -6 \\ 6 \end{pmatrix} + t \begin{pmatrix} 1 \\ -1 \end{pmatrix} \end{aligned} \] Wir suchen den Schnittpunkt ihrer Bewegungsbahnen und die Zeiten, zu denen die Körper diesen erreichen. Dazu lösen wir die Vektorgleichung \(P_1(t_1) = P_2(t_2)\) nach \(t_1\) und \(t_2\). Dies ist gleichwertig mit dem linearen Gleichungssystem \[ \begin{aligned} 1 - 3t_1 & = -6 + t_2 \\ -2 + 4t_1 & = 6 - t_2 \end{aligned} \] Die Lösung ist gegeben durch \(t_1 = 1\) und \(t_2 = 4\). Die Bahnen der Flugzeuge scheiden sich also an der Position \(P_1(1) = P_2(4) = \begin{pmatrix} -2 \\ 2 \end{pmatrix}\). Das Flugzeug 1 hat diesen Punkt zum Zeitpunkt \(t_1 = 1\) erreicht, und das Flugzeug 2 zum Zeitpunkt \(t_2 = 4\). Da die Vektorgleichung als lineares Gleichungssystem geschrieben werden kann, ist die Lösungsstruktur dieselbe: Es kann keine, eine oder unendlich viele Lösungen geben.

Kräftezerlegung

Um eine gegebene Kraft \(F = \begin{pmatrix} 7 \\ -7 \\ 4 \end{pmatrix}\) in ihre Komponenten bzgl. den zwei Richtungen \(v_1=\begin{pmatrix} 2 \\ 1 \\ -1 \end{pmatrix}\) und \(v_2=\begin{pmatrix} 1 \\ -3 \\ 2 \end{pmatrix}\) zu zerlegen, müssen wir die Vektorgleichung \(x_1 v_1 + x_2 v_2 = F\) nach \(x_1\) und \(x_2\) lösen. Die Vektorgleichung \[ x_1 \begin{pmatrix} 2 \\ 1 \\ -1 \end{pmatrix} + x_2 \begin{pmatrix} 1 \\ -3 \\ 2 \end{pmatrix} = \begin{pmatrix} 7 \\ -7 \\ 4 \end{pmatrix} \] ist gleichwertig mit dem linearen Gleichungssystem \[ \begin{aligned} 2x_1 + x_2 & = 7 \\ x_1 - 3x_2 & = -7 \\ -x_1 + 2x_2 & = 4 \end{aligned} \] Die Lösung ist gegeben durch \(x_1 = 2\) und \(x_2 = 3\), und die Zerlegung der Kraft lautet \(F = 2 v_1 + 3 v_2\).

Nicht jede Kraft \(F\in\mathbb{R}^3\) kann in die gegeben zwei Richtungen \(v_1, v_2 \in \mathbb{R}^3\) zerlegt werden. Nur wenn die Kraft in der von den beiden Richtungen aufgespannten Ebene liegt, ist eine Zerlegung möglich. Falls die beiden Richtungen linear abhängig sind, d. h. wenn sie auf einer Geraden liegen, ist einen Zerlegung (falls sie existiert) nicht eindeutig, und es gibt unendlich viele Zerlegungen. Wieder ist die Lösungsstruktur dieselbe: Es kann keine, eine oder unendlich viele Lösungen geben.

Elektrischer Schaltkreis

Die Schaltung in Abbildung Abbildung 1 hat die Daten \(U_\text{bat,1} = 10.8\) V, \(U_\text{bat,2} = 3.2\) V, \(R_1 = 6\) \(\Omega\), \(R_2 = 8\) \(\Omega\), \(R_3 = 4\) \(\Omega\).

Abbildung 1: Elektrischer Schaltkreis

Die Kirchhoffschen Regeln besagen:

• Die Summe aller Ströme, die in einen Knoten hineinfließen, ist gleich der Summe aller Ströme, die aus dem Knoten herausfließen.
• Die Summe aller Spannungen in einer Masche ist gleich Null.

Diese Regeln wenden wir in Abbildung 2 auf die Schaltung an und erhalten das folgende lineare Gleichungssystem.

Abbildung 2: Anwendung der Kirchhoffschen Regeln

\[ \begin{aligned} I_1 - I_2 - I_3 & = 0 \\ I_1 R_1 + I_2 R_2 & = U_\text{bat,1} \\ I_2 R_2 - I_3 R_3 & = U_\text{bat,2} \end{aligned} \] Die Lösung ist gegeben durch \(I = 1\) A, \(I_2 = 0.6\) A, \(I_3 = 0.4\) A. Das stimmt mit unserer physikalischen Intuition überein, dass es eine eindeutige Lösung geben sollte.

Quelle und Details: LEIFIphysik

Wirtschaft

Sie haben Ihr Moped mit einer Mischung von Superbenzin und E10 getankt. Dabei haben Sie für 5 Liter dieser Mischung insgesamt 6.50 Euro bezahlt. Wie viel Liter sind von jeder Sorte getankt worden, wenn 1 Liter Superbenzin 1.35 EUR und 1 Liter E10 1.20 EUR kosten?

Wir führen die Variablen \(x_1\) und \(x_2\) ein, die die Literzahl von Superbenzin bzw. E10 bezeichnen. Dann können wir die obige Fragestellung als das folgende lineare Gleichungssystem formulieren. \[ \begin{aligned} x_1 + x_2 & = 5 \\ 1.35 x_1 + 1.2 x_2 & = 6.5 \end{aligned} \] Lösung: Es wurden \(x_1 = \frac{10}{3} \simeq 3.3\) Liter Superbenzin und \(x_2 =​ \frac{5}{3} \simeq 1.7\) Liter E10 getankt.

Bezüglich der allgemeinen Lösungseigenschaften von Problemen dieses Typs halten wir fest: Wenn die Preise von Superbenzin und E10 unterschiedlich sind, dann gibt es eine eindeutige Lösung. Wenn die Preise gleich sind, dann gibt es keine Lösung, wenn die Gesamtmenge mal dem Preis nicht den angegebenen Kosten entspricht, oder unendlich viele Lösungen, wenn diese Inkonsistenz nicht gegeben ist.

Quelle: Aufgabe 7 in Serlo

Chemie

Chemische Reaktionsgleichungen beschreiben die Verhältnisse der Reaktanten und Produkte einer gegebenen Stoffumwandlung. Zum Beispiel reagiert bei der Verbrennung das Gas Propan (\(C_3 H_8\)) mit Sauerstoff (\(O_2\)) zu Kohlendioxid (\(CO_2\)) und Wasser (\(H_2 O\)), beschrieben durch die Reaktionsgleichung \[ x_1 C_3 H_8 + x_2 O_2 \rightarrow x_3 CO_2 + x_4 H_2 O. \] Um die Reaktion ins Gleichgewicht zu bringen, gilt es die ganzzahligen Lösungen \(x_1,...,x_4\) zu finden, so dass die Gesamtzahlen von Kohlenstoff-, Wasserstoff- und Sauerstoffatomen auf der rechten und linken Seite der Reaktionsgleichung übereinstimmen. Eine systematische Methode, um das Reaktionsgleichgewicht zu bestimmen, ist die Formulierung einer vektoriellen Gleichung, welche die Zahlen der Atome aller in der Reaktion vorkommenden Elemente beschreibt: \[ x_1 \begin{pmatrix} 3 \\ 8 \\ 0 \end{pmatrix} + x_2 \begin{pmatrix} 0 \\ 0 \\ 2 \end{pmatrix} = x_3 \begin{pmatrix} 1 \\ 0 \\ 2 \end{pmatrix} + x_4 \begin{pmatrix} 0 \\ 2 \\ 1 \end{pmatrix}. \] Die vektorielle Gleichung entspricht den Massenbilanzen für die drei Elemente \(C\), \(H\) und \(O\). Wir bestimmen die Lösungsmenge in \(\mathbb{R}^4\) und finden die Lösung mit kleinstmöglichen ganzen Zahlen \(x_1,...,x_4\): Das Gaußschen Eliminationsverfahren, das wir später genau durchgehen, liefert, dass das lineare Gleichungssystem unendlich viele Lösungen (genauer: eine 1-dimensionale Lösungsmenge) hat, die z. B. mit \(x_4\) parametrisiert werden kann: \[ \begin{aligned} x_4 & = \text{frei wählbar} \\ x_3 & = \frac{3}{4} x_4 \\ x_2 & = \frac{5}{4} x_4 \\ x_1 & = \frac{1}{4} x_4 \end{aligned} \] Die Lösung mit kleinstmöglichen ganzen Zahlen ist \(x_1 = 1, x_2 = 5, x_3 = 3,x_4 = 4\), also \[ C_3 H_8 + 5 O_2 \rightarrow 3 CO_2 + 4 H_2 O. \] Dass es unendlich viele Lösungen geben muss, falls die Reaktion chemisch möglich ist, leuchtet ein, da man von den Reaktanten beliebig viele Moleküle im gleichen Verhältnis nehmen kann, um die Reaktion zu starten.

Schreibweisen

Gleichungsform

Ein lineares Gleichungssystem mit \(n\) Variablen \(x_1,...,x_n\) und \(m\) Gleichungen hat die Gleichungsform \[ \begin{aligned} A_{11} x_1 + A_{12} x_2 + ... + A_{1n} x_n & = b_1 \\ A_{21} x_1 + A_{22} x_2 + ... + A_{2n} x_n & = b_2 \\ ... & \\ A_{m1} x_1 + A_{m2} x_2 + ... + A_{mn} x_n & = b_m \end{aligned} \]

Matrix-Vektor-Form

Zur Übersichtlichkeit, zur Behandlung im Rahmen der Matrizenrechnung und zur Bestimmung der Lösung am Computer wird das lineare Gleichungssystem in Matrix-Vektor-Form geschrieben. Dabei werden die gegebenen Zahlen \(A_{ij}\) in eine \(m\times n\) Matrix \(A\) zusammengefasst, die Variablen \(x_i\) in einen Vektor \(x \in \mathbb{R}^n\) und die gegebenen Zahlen \(b_i\) in einen Vektor \(b \in \mathbb{R}^m\) geschrieben. Die Daten des Problems sind also die Matrix \(A\) und der Vektor \(b\). Die gesuchte Größe ist der Variablen-Vektor \(x\). Die Matrix-Vektor-Form lautet: \[ \begin{pmatrix} A_{11} & A_{12} & ... & A_{1n} \\ A_{21} & A_{22} & ... & A_{2n} \\ ... & ... & ... & ... \\ A_{m1} & A_{m2} & ... & A_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ ... \\ b_m \end{pmatrix} \] Die Matrix-Vektor-Form kann kompakt als \[ Ax = b \] geschrieben werden, was eine Vektorgleichung im \(\mathbb{R}^m\) ist. Die Matrix \(A\) heißt Koeffizientenmatrix. Der Vektor \(b\) heißt rechte Seite. Das Produkt \(Ax\) von \(A\) mit \(x\) ist das Ergebnis der sogenannten Matrixmultiplikation, die wir im Abschnitt Matrizenrechnung genauer betrachten werden. Sie ist definiert durch \[ \begin{pmatrix} A_{11} & A_{12} & ... & A_{1n} \\ A_{21} & A_{22} & ... & A_{2n} \\ ... & ... & ... & ... \\ A_{m1} & A_{m2} & ... & A_{mn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{pmatrix} = \begin{pmatrix} A_{11} x_1 + A_{12} x_2 + ... + A_{1n} x_n \\ A_{21} x_1 + A_{22} x_2 + ... + A_{2n} x_n \\ ... \\ A_{m1} x_1 + A_{m2} x_2 + ... + A_{mn} x_n \end{pmatrix} \] Damit ist die Notation \(Ax = b\) nicht nur kompakt, sondern es stehen einem auch die Methoden der Matrizenrechnung zur Verfügung, um das lineare Gleichungssystem zu lösen. Insbesondere ist die Matrixmultiplikation linear, d. h. es gilt \(A(x_1 + x_2) = Ax_1 + Ax_2\) und \(A(cx) = cAx\) für alle \(x_1, x_2, x \in \mathbb{R}^n\) und \(c \in \mathbb{R}\).

Erweiterte Koeffizientenmatrix

Zum effizienten händischen Berechnen der Lösung verwenden wir noch eine weitere Schreibweise, die erweiterte Koeffizientenmatrix \((A|b)\) . Dabei werden die Daten des LGS , d. h. die \(m \times n\) Koeffizientenmatrix \(A\) und der \(m\times 1\) Vektor \(b\), in eine \(m\times (n+1)\) Matrix \((A|b)\) zusammengefasst: \[ (A|b) = \begin{pmatrix} A_{11} & A_{12} & ... & A_{1n} & b_1 \\ A_{21} & A_{22} & ... & A_{2n} & b_2 \\ ... & ... & ... & ... & ... \\ A_{m1} & A_{m2} & ... & A_{mn} & b_m \end{pmatrix} \]

Begriffe

• Die Lösungsmenge (Lösungsraum) eines LGS \(Ax = b\) ist die Menge aller Vektoren \(x\), die das LGS erfüllen.
• Ein LGS heißt homogen, wenn \(b = 0\), d. h. wenn es sich als \(Ax = 0\) schreiben lässt.
• Die Lösungsmenge eines homogenen LGS \(Ax=0\) heißt Kern oder Nullraum (engl. null space) der Matrix \(A\).
• Wenn \(b \neq 0\), dann heißt das LGS inhomogen.
• Wenn \(m = n\), d. h. wenn das LGS gleich viele Gleichungen wie Unbekannte (=Variablen) hat, dann spricht man von einem quadratischen LGS.
• Wenn \(m > n\), dann heißt das LGS überbestimmt.
• Wenn \(m < n\), dann heißt das LGS unterbestimmt.

Lösungsstruktur Teil 1

Die Lösungsmenge eines LGS kann im Allgemeinen leer sein, oder aus genau einer Lösung bestehen, oder unendlich viele Lösungen enthalten. Etwas mehr kann man über inhomogene und homogene LGS sagen:

• Ein homogenes LGS \(Ax = 0\) hat immer mindestens eine Lösung, nämlich die triviale Lösung (Nulllösung) \(x = 0\). Wenn es eine weitere Lösung gibt, dann gibt es unendlich viele Lösungen.
• Ein inhomogenes LGS \(Ax = b\) mit \(b \neq 0\) hat entweder keine Lösung, genau eine Lösung oder unendlich viele Lösungen. Der Lösungsraum besteht aus dem Lösungsraum des homogenen LGS \(Ax = 0\) und einer beliebigen speziellen (=partikulären) Lösung des inhomogenen LGS \(Ax = b\). Das stimmt, weil man zu jeder speziellen Lösung eine beliebige Lösung des homogenen LGS addieren kann, und weil die Differenz zweier spezieller Lösungen eine Lösung des homogenen LGS ist: \[ \begin{aligned} Ax_1 = b, Ax_0 = 0 & \Rightarrow A(x_1 - x_0) = Ax_1 - Ax_0 = b - 0 = b, \\ Ax_1 = b, Ax_2 = b & \Rightarrow A(x_1 - x_2) = Ax_1 - Ax_2 = b - b = 0. \end{aligned} \]

Achtung

Die Dimensionen \(m\) und \(n\) eines LGS - d. h ob das LGS mehr, weniger oder mehr Gleichungen als Variablen hat - geben keinen Aufschluss darüber, wie viele Lösungen (keine, eine oder unendlich viele) es hat!

Lösungsverfahren

Einsetzen und Gleichsetzen

Bei LGS mit sehr kleinen Dimensionen \(n\) und \(m\) oder speziellen Strukturen kann man durch Einsetzen und Gleichsetzen die Lösung finden, siehe Gleichsetzungsverfahren und Einsetzungsverfahren.

Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren (GEV) ist dagegen immer anwendbar und ist das Standardlösungsverfahren für LGS. Die Idee des GEV besteht darin, die erweiterte Koeffizientenmatrix \((A|b)\) eines LGS \(Ax = b\) durch elementare Umformungen in eine sogenannte Trapezform (Stufenform, Treppenform) zu bringen, aus der die Lösungsmenge leicht berechnet werden kann. Die elementaren Umformungen ändern zwar die Daten (\(A\) und \(b\)) des LGS aber nicht die Lösungsmenge. Die elementaren Umformungen sind:

• Vertauschen zweier Gleichungen
• Multiplikation einer Gleichung mit einer Zahl \(\neq 0\)
• Addition einer Gleichung zu einer anderen Gleichung
• Vertauschen zweier Spalten, d. h. Vertauschen zweier Variablen

Eine Matrix \(T\) ist in Trapezform, wenn sie in der folgenden Form ist: \[ \begin{pmatrix} T_{11} & T_{12} & \ldots & T_{1r} & T_{1,r+1} & \ldots & T_{1n} \\ 0 & T_{22} & \ldots & T_{1r} & T_{2,r+1} & \ldots & T_{2n} \\ 0 & 0 & \ddots & \vdots & \vdots & \ldots & \vdots \\ \vdots & \vdots & \ldots & T_{rr} & T_{r,r+1} & \ldots & T_{rn} \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0 \\ \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\ 0 & 0 & \ldots & 0 & 0 & \ldots & 0 \\ \end{pmatrix} \] Dabei sind \(T_{11} \neq 0\), \(T_{22} \neq 0\), …, \(T_{rr} \neq 0\). An der Anzahl \(r\) an Stufen kann der Rang (engl. rank) der Matrix abgelesen werden. Man schreibt \(\text{rank}(T) = r\). Der Rang einer Matrix ist definiert als die Anzahl linear unabhängiger Spalten- oder Zeilenvektoren der Matrix. Durch elementare Umformungen ändert sich der Rang einer Matrix nicht.

Beispiel: \[ \begin{aligned} x_1 + 2x_2 - 2x_3 & = 7 \\ 2x_1 + 3x_2 & = 0 \\ 3x_1 + 3x_2 + 6x_3 & =-21 \end{aligned} \] Wir bringen das LGS, das dem Schnitt von drei Ebenen im Raum entspricht, zuerst von der Gleichungsform in die erweiterte Koeffizientenmatrix: \[ \begin{pmatrix} 1 & 2 & -2 & 7 \\ 2 & 3 & 0 & 0 \\ 3 & 3 & 6 &-21 \end{pmatrix} \] Wir addieren das \(-2\)-fache der ersten Gleichung zur zweiten Gleichung und das \(-3\)-fache der ersten Gleichung zur dritten Gleichung: \[ \begin{pmatrix} 1 & 2 & -2 & 7 \\ 0 & -1 & 4 &-14 \\ 0 & -3 & 12 &-42 \end{pmatrix} \] Wir addieren das \(-3\)-fache der zweiten Gleichung zur dritten Gleichung: \[ \begin{pmatrix} 1 & 2 & -2 & 7 \\ 0 & -1 & 4 &-14 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] Nun ist die Trapezform erreicht. Man hätte die dritte Gleichung anfangs durch \(3\) dividieren können, um die Zahlen klein zu halten. Der Rang der Koeffizientenmatrix und der erweiterten Koeffizientenmatrix ist \(2\). Wir können die Lösungsmenge nun leicht durch Rückwärtseinsetzen bestimmen:

• Die Variable \(x_3\) ist frei wählbar, d. h. sie kann beliebige Werte aus \(\mathbb{R}\) annehmen.
• Die Variable \(x_2\) ist durch \(x_3\) bestimmt, d. h. sie kann nicht frei gewählt werden: Aus der zweiten Zeile (Gleichung) \(-x_2 + 4x_3 = -14\) folgern wir, dass \(x_2 = 4x_3 + 14.\)
• Die Variable \(x_1\) ist durch \(x_2\) und \(x_3\) bestimmt, d. h. sie kann nicht frei gewählt werden: Aus der ersten Zeile (Gleichung) \(x_1 + 2x_2 - 2x_3 = 7\) folgern wir, dass \(x_1 = -2x_2 + 2x_3 + 7 = -6x_3 - 21\).

Die Lösungsmenge wir also aus allen \(x = \begin{pmatrix} -6x_3 - 21 \\ 4x_3 + 14 \\ x_3 \end{pmatrix}\) mit \(x_3 \in \mathbb{R}\) gebildet. Die Lösungsmenge ist 1-dimensional, da eine Variable frei gewählt werden kann. Geometrisch ist die Lösungsmenge eine Gerade im \(\mathbb{R}^3\) mit der Geradengleichung \(x = \begin{pmatrix} -21 \\ 14 \\ 0 \end{pmatrix} + x_3 \begin{pmatrix} -6 \\ 4 \\ 1 \end{pmatrix}\).

Allgemeine Strategie zur Umformung auf Trapezform:

1. Man schreibt das LGS als erweiterte Koeffizientenmatrix.
2. Wenn die Zahl in der ersten Spalte und ersten Zeile - das erste Pivotelement - nicht Null ist, dann vertauscht man die erste Zeile mit einer passenden anderen Zeile. Ist dies nicht möglich, vertauscht man die erste Spalte mit einer passenden anderen Spalte der Koeffizientenmatrix.
3. Außer dem trivialen Fall, dass die Koeffizientenmatrix nur Nullen enthält, können wir nun annehmen, dass das erste Pivotelement nicht Null ist. Indem man passende Vielfache der ersten Zeile von den anderen Zeilen subtrahiert, können wir Nullen unter dem ersten Pivotelement erzeugen.
4. Nun verwendet man die Zahl in der zweiten Zeile und zwei Spalten - das zweite Pivotelement - um Nullen unter dem zweiten Pivotelement zu erzeugen. Evtl. müssen davor noch Zeilen- oder Spaltenvertauschungen (aber nicht mit der ersten Zeile oder Spalte) durchgeführt werden, damit das zweite Pivotelement nicht Null ist.
5. Etc.

Wenn man eine allgemeinere Art der Stufenform zulässt, bei der sich in jeder Zeile die Zahl der Variablen auch um mehr als eine verringern kann, dann sind keine Spaltenvertauschungen (und somit auch keine Variablenvertauschungen) notwendig.

Lösungsstruktur Teil 2

Wir betrachten ein LGS \(Ax = b\) mit \(m\) Gleichungen und \(n\) Variablen. Die \(m\times n\)-Koeffizientenmatrix \(A\) habe den Rang \(r\), der sicher kleiner gleich \(m\) und kleiner gleich \(n\) ist. Dann gilt:

• Falls \(r = m\), dann existiert mindestens eine Lösung.
• Falls \(r = n\), dann ist eine Lösung, falls sie existiert, eindeutig.
• Falls \(r = m = n\), dann existiert genau eine Lösung.

Um die Lösungsstruktur besser beurteilen zu können, muss man auch den Rang der erweiterten Koeffizientenmatrix \((A|b)\) kennen:

• Falls \(r = \text{rank}(A) = \text{rank}(A|b)\), dann ist das LGS lösbar:
  • Falls \(r = n\), dann hat das LGS genau eine Lösung.
  • Falls \(r < n\), dann hat das LGS unendlich viele Lösungen mit \(n - r\) frei wählbaren Variablen. Die Lösungsmenge ist also \(n - r\)-dimensional.
• Falls \(\text{rank}(A) < \text{rank}(A|b)\), dann hat das LGS keine Lösung.

Die letzten drei Fälle sind in Abbildung Abbildung 3 dargestellt.

Abbildung 3: Trapezformen

Python

Für die Lösung von LGS mit Python verwenden wir die Pakete

• NumPy, insbesondere das Modul numpy.linalg und von
• SciPy das Modul scipy.linalg.
• Für die grafische Darstellung verwenden wir das Paket matplotlib.

Die notwendigen Funktionen werden im Kapitel Python Tutorial eingeführt. Wir verwenden dabei die folgenden, üblichen Abkürzungen:

import numpy as np
import scipy as sp
import matplotlib.pyplot as plt

Die zentralen Python-Funktionen sind:

• @: Operator der Matrixmultiplikation, z. B. A@x
• np.linalg.matrix_rank(A): Gibt den Rang der Matrix \(A\) zurück.
• np.linalg.solve(A, b): Ist nur für quadratische LGS \(Ax = b\) anwendbar! Wenn die \(n \times n\)-Matrix \(A\) maximalen (man sagt: vollen) Rang \(n\) hat, liefert solve die eindeutige Lösung. Andernfalls liefert solve eine Fehlermeldung!

Das heißt, wir können in Python zwar mittels matrix_rank die Lösungsstruktur eines LGS bestimmen jedoch bisher nur bestimmte, quadratische LGS direkt lösen. Für die direkte Lösung von allgemeinen LGS in Python werden wir in den kommenden Kapiteln die notwendigen Methoden aber noch kennenlernen.

Beispiele

GEV eindeutige Lsg.

Wir betrachten das LGS \[ \begin{aligned} 4x_1 - x_2 - x_3 & = 6 \\ x_1 + 2x_3 & = 0 \\ -x_1 + 2x_2 + 2x_3 & = 2 \\ 3x_1 - x_2 & = 3 \end{aligned} \] Die erweiterte Koeffizientenmatrix ist \[ \begin{pmatrix} 4 & -1 & -1 & 6 \\ 1 & 0 & 2 & 0 \\ -1 & 2 & 2 & 2 \\ 3 & -1 & 0 & 3 \end{pmatrix} \] Wir vertauschen zuerst die erste und die zwei Zeile und bringen dann die Matrix in mehreren Schritten in die folgende Trapezform: \[ \begin{pmatrix} 1 & 0 & 2 & 0 \\ 0 & -1 & -9 & 6 \\ 0 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] Der Rang der Koeffizientenmatrix und der erweiterten Koeffizientenmatrix ist \(3\). Die Lösungsmenge ist also 0-dimensional, d. h. es gibt genau eine Lösung. Diese kann durch Rückwärtseinsetzen bestimmt werden: Die dritte Zeile \(-x_3 = 1\) ergibt \(x_3 = -1\). Setzen wir dies in die zweite Zeile \(-x_2 - 9x_3 = 6\) ein, erhalten wir \(x_2 = 3\) Setzt man schließlich die Werte für \(x_3\) und \(x_2\) in die erste Zeile ein erhält man \(x_1 = 2\).

Quelle: Papula Bd 2, Seite 81, Beispiel (2)

GEV keine Lsg.

Wir betrachten das LGS \[ \begin{aligned} -x_1 + 5x_2 & = 4 \\ 3x_1 - 5x_2 & = 8 \\ 5x_1 - 7x_2 & =-11 \end{aligned} \] Die erweiterte Koeffizientenmatrix ist \[ \begin{pmatrix} -1 & 5 & 4 \\ 3 & -5 & 8 \\ 5 & -7 &-11 \end{pmatrix} \] Diese kann in die folgende Trapezform gebracht werden: \[ \begin{pmatrix} -1 & 5 & 4 \\ 0 & 1 & 2 \\ 0 & 0 &-3 \end{pmatrix} \] Der Rang der erweiterten Koeffizientenmatrix ist \(3\), der Rang der Koeffizientenmatrix ist \(2.\) Das LGS hat also keine Lösung.

GEV und Python

Wir lösen das folgende LGS in Python mittels GEV, bestimmen die Lösungsstruktur mit dem Rang und lösen das LGS, falls möglich, mit np.linalg.solve: \[ \begin{aligned} 4x_2 - 3x_3 & = 3 \\ -x_1 + 7x_2 - 5x_3 & = 4 \\ -x_1 + 8x_2 - 6x_3 & = 5 \end{aligned} \]

A = np.array([[ 0,  4, -3],
              [-1,  7, -5],
              [-1,  8, -6]])
b = np.array([[3], 
              [4], 
              [5]])
Ab = np.hstack((A, b))  # stack arrays horizontally, i.e., column wise
print('Koeffizientenmatrix A:')
print(A)
print('Rechte Seite b:')
print(b)
print('Erweiterte Koeffizientenmatrix (A|b):')
print(Ab)

# Vertausche 1. und 3. Zeile:
Ab_orig = Ab.copy()  # copy because we will change Ab and want to keep Ab_orig
Ab[0] = Ab_orig[2]
Ab[2] = Ab_orig[0]
print('Erweiterte Koeffizientenmatrix [A|b] nach Zeilentausch')
print(Ab)
 
# Neue 2. Zeile = Z2 - Z1:
Ab[1] = Ab[1] - Ab[0]
print('Erweiterte Koeffizientenmatrix [A|b] nach 1. Zeilenaddition')
print(Ab)

# Neue 3. Zeile = Z3 + 4*Z2:
Ab[2] = Ab[2] + 4*Ab[1]
print('Erweiterte Koeffizientenmatrix [A|b] nach 2. Zeilenaddition')
print(Ab)

# Rücksubstitution:
x3 = Ab[2,3]/Ab[2,2]
x2 = 1/Ab[1,1]*(Ab[1,3] - Ab[1,2]*x3)
x1 = 1/Ab[0,0]*(Ab[0,3] - Ab[0,2]*x3 - Ab[0,1]*x2)
x = np.array([[x1], [x2], [x3]])
print(f"Lösung: x = \n{x}")

# Lösungsstruktur mit Rang:
rA   = np.linalg.matrix_rank(A)
rAb  = np.linalg.matrix_rank(np.hstack((A, b))) 
print(f"Rang A = {rA} und Rang [A|b] = {rAb}")

# Lösung mit np.linalg.solve:
# Achtung: verwendbar, weil A quadratisch ist und vollen Rang hat.
sol  = np.linalg.solve(A,b)
print(f"Lösung mit np.linalg.solve: x = \n{sol}")
check = np.dot(A, x)
print(f"Check, dass Ax = \n{check} gleich b = \n{b}")

Koeffizientenmatrix A:
[[ 0  4 -3]
 [-1  7 -5]
 [-1  8 -6]]
Rechte Seite b:
[[3]
 [4]
 [5]]
Erweiterte Koeffizientenmatrix (A|b):
[[ 0  4 -3  3]
 [-1  7 -5  4]
 [-1  8 -6  5]]
Erweiterte Koeffizientenmatrix [A|b] nach Zeilentausch
[[-1  8 -6  5]
 [-1  7 -5  4]
 [ 0  4 -3  3]]
Erweiterte Koeffizientenmatrix [A|b] nach 1. Zeilenaddition
[[-1  8 -6  5]
 [ 0 -1  1 -1]
 [ 0  4 -3  3]]
Erweiterte Koeffizientenmatrix [A|b] nach 2. Zeilenaddition
[[-1  8 -6  5]
 [ 0 -1  1 -1]
 [ 0  0  1 -1]]
Lösung: x = 
[[ 1.]
 [-0.]
 [-1.]]
Rang A = 3 und Rang [A|b] = 3
Lösung mit np.linalg.solve: x = 
[[ 1.]
 [ 0.]
 [-1.]]
Check, dass Ax = 
[[3.]
 [4.]
 [5.]] gleich b = 
[[3]
 [4]
 [5]]

Unendlich viele Lsg.

Wir betrachten das LGS \[ \begin{aligned} x_1 - 3x_2 + x_3 & = 0 \\ -2x_1 + 5x_2 + 5x_3 & = -7 \end{aligned} \] Die erweiterte Koeffizientenmatrix lautet \[ \begin{pmatrix} 1 & -3 & 1 & 0 \\ -2 & 5 & 5 & -7 \end{pmatrix} \] Diese kann in die folgende Trapezform gebracht werden: \[ \begin{pmatrix} 1 & -3 & 1 & 0 \\ 0 & -1 & 7 & -7 \end{pmatrix} \] Die erweiterte Koeffizientenmatrix hat den Rang \(2\), die Koeffizientenmatrix hat den Rang \(2\). Die Anzahl der Variablen ist \(3\). Das LGS hat also 3 - 2 = 1 frei wählbare Variable, nämlich \(x_3\), und somit unendlich viele Lösungen: \[ \begin{aligned} x_2 & = 7 + 7x_3 \\ x_1 & = 3x_2 - x_3 = 21 + 21x_3 - x_3 = 21 + 20x_3 \end{aligned} \]

A = np.array([[ 1,-3, 1],
              [-2, 0, 5]])
b = np.array([[ 0],
              [-7]])
Ab = np.hstack((A, b))
print("Rang von A  =", np.linalg.matrix_rank(A))
print("Rang von Ab =", np.linalg.matrix_rank(Ab))
print("Anzahl der Variablen =", np.shape(A)[1])
print("Daher: unendlich (1-dim.) viele Lösungen.")

Rang von A  = 2
Rang von Ab = 2
Anzahl der Variablen = 3
Daher: unendlich (1-dim.) viele Lösungen.

Keine Lösung

Wir betrachten das LGS \[ \begin{aligned} x_1 - 3x_2 & = 0 \\ 2x_1 + 2x_2 & = 7 \\ 5x_1 + x_2 & = 1 \end{aligned} \] Die erweiterte Koeffizientenmatrix lautet \[ \begin{pmatrix} 1 & -3 & 0 \\ 2 & 2 & 7 \\ 5 & 1 & 1 \end{pmatrix} \] Diese kann in die folgende Trapezform gebracht werden: \[ \begin{pmatrix} 1 & -3 & 0 \\ 0 & 8 & 7 \\ 0 & 0 &-13 \end{pmatrix} \] Der Rang der erweiterten Koeffizientenmatrix ist \(3\), der Rang der Koeffizientenmatrix ist \(2\). Das LGS hat also keine Lösung.

A = np.array([[ 1,-3],
              [ 2, 2],
              [ 5, 1]])
b = np.array([[0],
              [7],
              [1]])
Ab = np.hstack((A, b))
print("Rang von A  =", np.linalg.matrix_rank(A))
print("Rang von Ab =", np.linalg.matrix_rank(Ab))
print("Daher: keine Lösung.")

Rang von A  = 2
Rang von Ab = 3
Daher: keine Lösung.

Eindeutige Lösung

Wir betrachten das LGS \[ \begin{aligned} x_1 - 3x_2 & = 4 \\ -2x_1 & =-2 \\ 5x_1 + x_2 & = 4 \end{aligned} \] Die erweiterte Koeffizientenmatrix lautet \[ \begin{pmatrix} 1 & -3 & 4 \\ -2 & 0 &-2 \\ 5 & 1 & 4 \end{pmatrix} \] Diese kann in die folgende Trapezform gebracht werden: \[ \begin{pmatrix} 1 & -3 & 4 \\ 0 & -1 & 1 \\ 0 & 0 & 0 \end{pmatrix} \] Der Rang der erweiterten Koeffizientenmatrix ist \(2\), der Rang der Koeffizientenmatrix ist \(2\). Das LGS hat also genau eine Lösung, nämlich \(x_2 = -1\) und \(x_1 = 1\).

A = np.array([[ 1,-3],
              [-2, 0],
              [ 5, 1]])
b = np.array([[ 4],
              [-2],
              [ 4]])
Ab = np.hstack((A, b))
print("Rang von A  =", np.linalg.matrix_rank(A))
print("Rang von Ab =", np.linalg.matrix_rank(Ab))
print("Anzahl der Variablen =", np.shape(A)[1])
print("Daher: genau eine Lösung.")

Rang von A  = 2
Rang von Ab = 2
Anzahl der Variablen = 2
Daher: genau eine Lösung.

Aufgaben

Verständnisfragen und kurze Aufgaben

1. Wir betrachten das lineare Gleichungssystem \[ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \\ 3 & 14 & 17 \end{pmatrix} x= \begin{pmatrix} 4 \\ 8 \\ 12 \end{pmatrix}. \] Bestimmen Sie anhand des GEV, wie viele Lösungen es für das LGS gibt.
2. Was ist der Rang einer Matrix, und wozu kann man ihn verwenden?
3. Wie bestimmen Sie, ob ein allgemeines LGS \(Ax = b\) keine, eine oder unendlich viele Lösungen hat?
4. Gegeben sei das LGS \(Ax = b\). Der Rang der Koeffizientenmatrix \(A\) sei geringer als der Rang der erweiterten Koeffizientenmatrix \((A|b)\), also \(\text{rank}(A) < \text{rank}(A|b)\). Wie viele Lösungen hat das gegebene LGS?

Ergebnisse:

1. unendlich viele Lösungen
2. Siehe Lösungsverfahren.
3. Siehe Lösungsstruktur Teil 2.
4. keine Lösung

Modellierungsbeispiele

Rechnen Sie alle Beispiele aus dem Abschnitt Modellierung von Hand und in Python nach.

Vektorgleichung und lineares Gleichungssystem

Welchem linearen Gleichungssystem entspricht die Vektorgleichung \[ x \begin{pmatrix} -1 \\ 3 \\ 2 \end{pmatrix} + y \begin{pmatrix} 4 \\ -2 \\ 4 \end{pmatrix} = \begin{pmatrix} -9 \\ 7 \\ 5 \end{pmatrix}? \] Bestimmen Sie seine Lösungsmenge mit dem GEV von Hand. Überprüfen Sie Ihr Ergebnis grafisch in der \(x\)-\(y\)-Ebene.

Ergebnis: Die Lösungsmenge ist die leere Menge. Die drei Geraden schneiden sich nicht in einem Punkt.

Gaußsches Eliminationsverfahren

Bestimmen Sie von Hand mit Hilfe des GEV, ob folgendes lineares Gleichungssystem nicht-triviale Lösungen hat. \[ \begin{aligned} 2x_1 - 5x_2 + 8x_3 & = 0 \\ -2x_1 - 7x_2 + x_3 & = 0 \\ 4x_1 + 2x_2 + 7x_3 & = 0 \end{aligned} \] Überprüfen Sie Ihr Ergebnis am Computer.

Ergebnis: Das Gleichungssystem hat nicht-triviale Lösungen, nämlich alle Vielfachen von \(x = \begin{pmatrix} -17 \\ 6 \\ 8 \end{pmatrix}.\)

GEV und Python

Lösen Sie folgende LGS mittels des GEV von Hand. Geben Sie jeweils den Rang der (erweiterten) Koeffizientenmatrix an.

Beispiel A: \[ \begin{aligned} x_1 + x_2 + x_3 & = 1 \\ x_1 + 2x_2 + 2x_3 & = 1 \\ x_1 + 2x_2 + 3x_3 &= 1 \end{aligned} \] Beispiel B: \[ \begin{aligned} -x_1 + 3x_2 - 2x_3 & = 1 \\ -x_1 + 4x_2 - 3x_3 & = 0 \\ -x_1 + 5x_2 - 4x_3 &= 0 \end{aligned} \] Beispiel C: \[ \begin{aligned} -x_1 + 3x_2 - 2x_3 & = 4 \\ -x_1 + 4x_2 - 3x_3 & = 5 \\ -x_1 + 5x_2 - 4x_3 &= 6 \end{aligned} \] Verifizieren Sie die Ergebnisse mittels Python.

Ergebnisse:

• Beispiel A: Rang von \(A\) ist 3, und Rang von \((A|b)\) ist 3. Das LGS hat die eindeutige Lösung \(x = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\).
• Beispiel B: Rang von \(A\) ist 2, und Rang von \((A|b)\) ist 3, LGS hat keine Lösung.
• Beispiel C: Rang von \(A\) ist 2, und Rang von \((A|b)\) ist 3, LGS hat unendlich viele Lösungen. \(x_3\) ist frei wählbar, \(x_2 = 1 + x_3\) und \(x_1 = -1 + x_3\).

Existenz und Eindeutigkeit

Gegeben ist das lineare Gleichungssystem: \[ \begin{aligned} 2x_1 - 4x_2 - 2x_3 & = b_1 \\ -5x_1 + x_2 + x_3 & = b_2 \\ 7x_1 - 5x_2 - 3x_3 & = b_3 \end{aligned} \] Hat das lineare Gleichungssystem für alle Vektoren \(b\) eine eindeutige Lösung? Lösen Sie dieses Problem am Computer.

Ergebnis: Das lineare Gleichungssystem \(Ax=b\) hat nicht für alle Vektoren \(b\) eine eindeutige Lösung, denn der Rang von \(A\) ist nur 2 und somit nicht voll.

Rang

Bestimmen Sie von Hand mittels elementarer Umformungen den Rang von \[ A = \begin{pmatrix} 1 & 0 & -1 & 1 \\ 2 & 3 & 1 & 5 \\ 3 & 2 & -1 & 6 \\ 0 & 5 & 5 & 5 \end{pmatrix}, \] und überprüfen Sie das Ergebnis am Computer.

Ergebnis: Rang von \(A\) ist 3.

Lösbarkeit

Zeigen Sie von Hand, dass das folgende lineare Gleichungssystem nicht lösbar ist, und überprüfen Sie das Ergebnis am Computer. \[ \begin{aligned} x_1 + x_2 - x_3 &= 2 \\ -2x_1 + x_3 &= -2 \\ 5x_1 - x_2 + 2x_3 &= 4 \\ 2x_1 + 6x_2 - 3x_3 &= 5 \end{aligned} \]

Ergebnis: Rang der Koeffizientenmatrix ist 3, der Rang der erweiterten Koeffizientenmatrix ist 4.

Elektrischer Schaltkreis

Der elektrische Schaltkreis in Abbildung Abbildung 4 ist parametrisiert durch: \(U_1 = 230\) V, \(U_2 = 370\) V, \(R_1 = 200\) Ohm, \(R_2 = 100\) Ohm und \(R_3 = 300\) Ohm.

Abbildung 4: Elektrischer Schaltkreis

1. Formulieren Sie das lineare Gleichungssystem für die Stromstärken \(I_1\), \(I_2\), und \(I_3\) in der Form \(Ax = b\).
2. Lösen Sie \(Ax = b\) händisch.
3. Bestimmen Sie in Python die Lösungsstruktur, und lösen Sie, falls möglich, das LGS in Python mit dem Befehl np.linalg.solve.

Ergebnis: \(I_1 = 0.5\) A, \(I_1 = 1.3\) A, \(I_3 = 0.8\) A

Parabel durch drei Punkte

Stellen Sie ein LGS zur Bestimmung der Koeffizienten \(\alpha, \beta, \gamma\) der Parabel (=quadratische Funktion) \[ y(x) = \alpha + \beta x + \gamma x^2 \] auf, welche durch die Punkte \((1, 1), (2, 2)\) und \((3,0)\) geht. Lösen Sie anschließend das LGS, und stellen Sie die Lösung grafisch dar.

Ergebnis: \(y(x) = -3 + 5.5x - 1.5x^2\).

Diät

Quelle: Lay, David; Lay, Steven; McDonald, Judi (2021): Linear Algebra and Its Applications. 6th edition, Pearson Education Limited.

Die Formel für die Cambridge-Diät, eine beliebte Diät in den 1980er Jahren, basiert auf jahrelanger Forschung. Um die gewünschten Mengen und Verhältnisse der Nährstoffe zu erreichen, musste man eine Vielfalt von Lebensmitteln einbeziehen. Jedes Lebensmittel liefert mehrere der erforderlichen Inhaltsstoffe, jedoch nicht in den genau richtigen Anteilen. So war zum Beispiel fettfreie Milch eine wichtige Eiweißquelle, enthielt aber zu viel Kalzium. Daher wurde Sojamehl für einen Teil des Eiweißes verwendet, da Sojamehl wenig Kalzium enthält. Allerdings enthält Sojamehl zu viel Fett, so dass Molke hinzugefügt wurde, da sie im Verhältnis zum Kalzium weniger Fett liefert. Leider enthält die Molke zu viele Kohlenhydrate … Das folgende Beispiel veranschaulicht das Problem in kleinem Maßstab. In der Tabelle Tabelle 1 sind drei der Bestandteile der Diät aufgeführt, zusammen mit den Mengen bestimmter Nährstoffe.

Tabelle 1: Enthaltene Nährstoffmenge (g) pro 100 g der Zutat

Nährstoff	fettfreie Milch	Sojamehl	Molke	Geforderte Nährstoffmenge (g)
Eiweiß	36	51	13	33
Kohlenhydrate	52	34	74	45
Fett	0	7	1.1	3

Wenn möglich, finden Sie eine Kombination aus fettfreier Milch, Sojamehl und Molke, um die geforderten Mengen an Eiweiß, Kohlenhydraten und Fett zu erhalten.

Ergebnis: Die Diät erfordert 27.7 g fettfreie Milch, 39.2 Einheiten Sojamehl und 23.3 Einheiten Molke.

Lösbarkeit

1. Geben Sie ein Zahlenbeispiel für ein lineares Gleichungssystem in Matrixform an, das 2 Gleichungen, 3 Variablen und keine Lösung hat.
2. Geben Sie ein Zahlenbeispiel für ein lineares Gleichungssystem in Matrixform an, das mindestens 2 Gleichungen, mindestens 2 Variablen und einen 1-dimensionalen Lösungsraum hat.

Ergebnis:

1. zwei parallele, aber nicht gleiche Ebenen im Raum
2. zwei gleiche Geraden in der Ebene

Unter- und überstimmte LGS

Lösen Sie von Hand folgende LGS, und geben Sie jeweils den Rang der (erweiterten) Koeffizientenmatrix an:

Beispiel A: \[ \begin{aligned} x_1 + 2x_2 + x_3 + 2x_4 & = 0 \\ 2x_1 + 4x_2 + x_3 + 3x_4 & = 0 \\ 3x_1 + 6x_2 + x_3 + 4x_4 &= 0 \end{aligned} \] Beispiel B: \[ \begin{aligned} 2 x_1 + x_2 + x_3 & = 0 \\ 4 x_1 + 2 x_2 + x_3 & = 0 \\ 6 x_1 + 3 x_2 + x_3 & = 0 \\ 8 x_1 + 5 x_2 + x_3 & = 0 \end{aligned} \] Beispiel C: \[ \begin{aligned} x_1 + 2x_2 + x_3 + 2x_4 & = 3 \\ 2x_1 + 4x_2 + x_3 + 3x_4 & = 4 \\ 3x_1 + 6x_2 + x_3 + 4x_4 & = 5 \end{aligned} \] Beispiel D: \[ \begin{aligned} 2 x_1 + x_2 + x_3 & = 2 \\ 4 x_1 + 2 x_2 + x_3 & = 5 \\ 6 x_1 + 3 x_2 + x_3 & = 8 \\ 8 x_1 + 5 x_2 + x_3 & = 8 \end{aligned} \] Verifizieren Sie Ihre händischen Ergebnisse mit Python.

Ergebnisse:

• Beispiel A: \(x_4\) ist frei wählbar, \(x_3 = -x_4\), \(x_2\) ist auch frei wählbar, \(x_1 = - 2x_2 - x_4\).
• Beispiel B: Es gibt nur die triviale Lösung.
• Beispiel C: Lösung aus Beispiel A ist verschoben um \(\begin{pmatrix} 1 \\ 0 \\ 2 \\ 0 \end{pmatrix}\).
• Beispiel D: \(x_3 = -1\), \(x_2 = -3\), \(x_1 = 3\).

Ill-Conditioned Linear System

Lösen Sie in Python die beiden LGS \(Ax = b\) \[ \begin{aligned} 0.835x_1 + 0.667x_2 & = 0.168 \\ 0.333x_1 + 0.266x_2 & = 0.067 \\ \end{aligned} \] und \[ \begin{aligned} 0.835x_1 + 0.667x_2 & = 0.168 \\ 0.333x_1 + 0.266x_2 & = 0.066 \\ \end{aligned} \] die sich nur im Wert \(b_2\) unterscheiden. Erklären Sie den großen Unterschied in den Lösungen. Eine Koeffizientenmatrix wie in diesem Beispiel heißt ill-conditioned und das LGS heißt ill-conditioned system.

Ergebnis: Lösung des ersten LGS: \(\begin{pmatrix} 1 \\ -1 \end{pmatrix}\), Lösung des zweiten LGS: \(\begin{pmatrix} -665.99999998 \\ 833.99999998 \end{pmatrix}\). Die Gleichungen, die zu jeder Zeile gehören, entsprechen fast parallelen Geraden, deren Schnittpunkt durch eine kleine Änderung in \(b\) stark beeinflusst wird.

LGS mit Parameter

Bestimmen Sie alle jene Werte für \(\alpha\) im LGS \[ \begin{aligned} 2x_1 + 2x_2 + 3x_3 & = 0 \\ 4x_1 + 8x_2 + 12x_3 & = -4 \\ 6x_1 + 2x_2 + \alpha x_3 & = 4 \end{aligned} \] sodass

1. eine eindeutige Lösung existiert,
2. unendliche viele Lösungen existieren.

Gibt es Werte für \(\alpha\), bei denen das LGS keine Lösung hat?

Ergebnis: \(\alpha = 3\) führt auf unendliche Lösungen, \(\alpha \ne 3\) führt auf eine eindeutige Lösung. Es existiert immer eine Lösung.

Theoriefragen

1. Bisher wurden nur Änderungen eines LGS durch Operationen an den Zeilen der erweiterten Koeffizientenmatrix betrachtet. Es ist jedoch auch möglich, äquivalente Operationen (Vertauschen, Multiplikation mit einem Skalar, Addition) mit den Spalten durchzuführen. Welche Auswirkung haben die Spaltenoperationen auf die Unbekannten (=Variablen)?
2. Die Lösung eines lösbaren LGS mit 4 Gleichungen und 8 Unbekannten enthält 5 freie Variablen. Wie groß ist der Rang der Koeffizientenmatrix?
3. Welche Struktur hat die Lösungsmenge eines homogenen LGS mit mehr Unbekannten als Gleichungen?
4. Wie lässt sich überprüfen, ob ein LGS \(Ax = b\) ill-conditioned ist? Was bedeutet ill-conditioned für die Lösung des LGS?
5. Wie viele unterschiedliche Trapezformen gibt es für eine \(3 \times 4\) Matrix?
6. Der Rang der \(m \times n\) Matrix \(A\) sei \(m\). Was bedeutet dies für die Lösungsmenge des LGS \(Ax = b\)?

Ergebnis:

1. Vertauschen von Spalten entspricht dem Vertauschen der Reihenfolge der Unbekannten. Multiplikation mit einem Skalar ändert die “Einheit” der Unbekannten. Addition zweier Spalten ändert die Repräsentation der Unbekannten, vgl. Basiswechsel.
2. 3
3. unendlich viele Lösungen
4. Überprüfung, ob kleine Änderung von Elementen im Vektor \(b\) zu großen Änderungen in der Lösung führen. Z. B. problematisch, wenn Elemente in \(b\) aus Daten geschätzt werden.
5. 15
6. Die erweiterte Koeffizientenmatrix hat auch den Rang \(m\). Das LGS hat entweder genau eine (für \(m = n\)) oder unendlich viele (für \(m < n\)) Lösungen. Der Fall \(m > n\) ist nicht möglich, da die Koeffizientenmatrix dann nicht den Rang \(m\) haben würde.

Lösungsmenge

1. Untersuchen Sie von Hand und am Computer die Lösungsstruktur des linearen Gleichungssystems (d. h. ohne es zu lösen).
2. Bestimmen Sie anschließend im Falle der Lösbarkeit von Hand und am Computer sämtliche Lösungen.

\[ \begin{pmatrix} 1 & 2 &-3\\ 0 & 1 &-1\\ 2 & 9 &11 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 5 \\ 8 \\ 50 \end{pmatrix} \]

Ergebnis:

1. Die Koeffizientenmatrix hat den Rang 3, die erweiterte Koeffizientenmatrix hat den Rang 3. Alternativ: Die Koeffizientenmatrix hat eine nicht-Null-Determinante.
2. \(x_1 = -11\), \(x_2 = 8\), \(x_3 = 0\).

Lösungsmenge

Bestimmen Sie von Hand die Lösungsmenge des LGS \[ \begin{pmatrix} -2 & 1 & 1 \\ 1 &-2 & 1 \\ 1 & 1 &-2 \end{pmatrix} \begin{pmatrix}x_1 \\ x_2 \\ x_3 \end{pmatrix}= \begin{pmatrix}0 \\ 0 \\ 0 \end{pmatrix}. \]

Ergebnis: Das LGS hat die unendlich viele Lösungen \(x_1 = x_2 = x_3\) mit \(x_3\) als freien Parameter.