Zurück Letzter Update 7.01.2016. Lineare Gleichungssysteme und Gauß'scher Algorithmus
In der Mathematik bezeichnet man mit Matrix ein rechteckiges Schema, in dem Zahlen oder Funktionen angeordnet werden.
Hier geht es zunächst nur um Matrizen, deren Elemente Zahlen sind (reelle oder komplexe). In der allgemeinen Darstellung
haben die Zahlen zwei Indizes, den ersten für die Zeilennummern, den zweiten für die Spaltennummer.
⎛
a11
a12
....
a1n
a21
a22
....
a2n
.....
.....
am2
....
⎜
A = ⎜
⎜.....
⎝
am1
⎞
⎟
⎟ = (aik )i=1...m, k=1...´n
..... ⎟
amn
⎠
Die dargestellte Matrix hat m Zeilen (erster Index) und n Spalten (zweiter Index). In der Matrix sind also m ∗ n Zahlen
gespeichert, etwa reelle oder komplexe. Dazu unten mehr. Lineare Gleichungssysteme GaußAlgorithmus (Eliminationsverfahren) Vorbemerkung: Das Gauß'sche Eliminationsverfahren ist ein Algorithmus zur Lösung linearer Gleichungssysteme, gleichgültig
aus welchem Modellkontext sie stammen. Ich stelle das Verfahren hier vorwiegend an Beispielen der
Vektorrechnung/analytischen Geometrie vor, weil man sich dann unter der Lösungsmenge konkrete Objekte wie Geraden,
Punke, Ebenen vorstellen kann. Und auch, weil dieser Kontext aus der Schule schon bekannt ist. Das Verfahren ist jedoch
generell auf beliebige lineare Gleichungssysteme anwendbar und nicht auf diesen Kontext beschränkt. Siehe dazu auch Aufgaben . 3
Motivation: Beispiel 1: Wir möchten die Schnittmenge der folgenden drei Ebenen im IR bestimmen:
E1 : 2x + y + z = 0,
E2 : x + y + z = 1,
E3 : x + z = 1
Die Schnittmenge ist die Menge aller Punkte, die alle drei Gleichungen simultan erfüllt. Dies könnte in diesem Kontext
prinzipiell hier ein Punkt, die leere Menge, eine Gerade oder eine Ebene sein. Welcher Fall hier vorliegt, zeigt uns gleich eine
kurze Rechnung mit dem GaußAlgorithmus. Wir fassen diese drei Ebenengleichungen in ein Gleichungssystem zusammen. Daneben schreiben wir nur die Koeffizienten
des Systems und die rechte Seite der Gleichungen als Matrix mit 3 Zeilen und 4 Spalten auf. (Die sogenannte erweiterte
Koeffzientenmatrix, die 3x3 Matrix links ist die eigentliche Koeffizientenmatrix. )
2x + y + z = 0
x + y + z = 2
x + 0y + z = 1
x
y
z
⎜2
⎜
⎜1
1
1
1
1
0⎟
⎟
2⎟
0
1
1
⎛
⎝
1
rechte Seite ⎞
⎠
In der ersten Spalte der erweiterten Koeffizientenmatrix stehen also die Koeffizienten der x , in der zweiten die der y usw. und
in der vierten Spalte die rechten Seiten der Gleichungen. Die Überschrift können wir in Zukunft weglassen, sofern wir keine
Spalten vertauschen. Den Clou an der Sache erkannte schon Gauß: Man kann mit der Koeffizientenmatrix genauso rechnen wie mit dem
Gleichungssystem. Also etwa Vielfache von Zeilen auf andere Zeilen addieren mit dem Ziel, in der Matrix möglichst viele Nullen
zu erzeugen und dann "rückwärts" durch Auflösen die Unbekannten x, y, z zu bestimmen. Man bildet also bei der hier vorgestellten Version des Verfahrens nur Linearkombinationen von Zeilen der erweiterten
Koeffizientenmatrix so, dass in einer Spalte Nullen enstehen und fährt dann mit den nächsten Spalte fort. Das ist der Kern des sogenannten Gauß'schen Eliminationsverfahrens oder auch GaußAlgorithmus. Der Vorteil des Rechnens
mit dem reinen Zahlenschema wird sofort klar, wenn man es einmal parallel durchführt. Übersichtlicher und schneller, da
weniger Schreibarbeit, als das rechnen mit Gleichungen, in denen Unbekannte stehen. Gauß schrieb dazu einem Freund:
"Hast du einmal so gerechnet, wirst du niemals wieder anders rechnen wollen". Der Nachteil soll auch erwähnt werden: Das
Verfahren ist natürlich etwas unflexibler als eine Kombination von den aus der Schule bekannten Additions, Einsetz und
Gleichsetzungsverfahren. Bei größeren Gleichungssystemen verliert man jedoch bei diesen gemischten Verfahren schnell die
Übersicht, bzw erstickt an der Schreibarbeit. Nicht so beim GaußVerfahren. Man kann diesen Algorithmus daher auch gut
programmieren. Wir führen dieses Verfahren einmal parallel durch, damit man die Äquivalenz erkennt. Ab dann nur noch mit der
Koeffizientenmatrix. Wir picken uns den ersten Koeffizienten von x heraus, also die Zahl in der 1. Zeile und 1. Spalte, die 2, das sogenannte
Pivotelement (1;1) (pivot (engl./frz.): Dreh und Angelpunkt). Dann soll mit diesem Element in der darunter stehenden Spalte Nullen erzeugt werden, indem man zum Beispiel (1.
Möglichkeit) Vielfache der ersten Zeile auf die anderen Zeilen addiert. Zeilen werden hier mit römischen Buchstaben
bezeichnet. Also etwa
−0, 5 ∗ I + II → II,
−0, 5 ∗ I + III → III
Lies: Multipliziere die erste Zeile (I) mit −0, 5 , addiere das auf die zweite Zeile (II) und speichere das Ergebnis in der zweiten
Zeile (II) usw. Ergebnis:
2x + y + z = 0
x + y + z = 2
2x + y + z = 0
0, 5y + 0, 5z = 2
→
x + 0y + z = 1
−0, 5y + 0, 5z = 1
2
1
1
0
2
1
1
⎜1
1
1
2⎟ → ⎜0
0, 5
0, 5
2⎟
0
1
1
−0, 5
0, 5
1
⎛
⎝
1
⎞
⎛
⎠
⎝
0
0
⎞
⎠
2. Möglichkeit. Oder man addiert die erste Zeile auf Vielfache der anderen, mit dem Ziel, die Koeffizienten von x zu Null zu
machen. I + (−2) ∗ II → II,
2x + y + z = 0
x + y + z = 2
2x + y + z = 0
→
−y − z = −4
x + 0y + z = 1
y − z = −2
I + (−2) ∗ III → III
2
1
1
0
2
1
1
⎜1
1
1
2⎟ → ⎜0
−1
−1
−4 ⎟
0
1
1
1
−1
−2
⎛
⎝
1
⎞
⎠
⎛
⎝
0
0
⎞
⎠
Es gäbe auch noch mehr Möglichkeiten, die wir aber hier unterdrücken. Wenn man ganzzahlig rechnen will, was sich für die
Handrechnung empfiehlt, muss man beide Möglichkeiten kombinieren, sofern beide Koeffizienten verschieden von 1 sind. In beiden Fällen stehen unterhalb des Pivotelementes 2 nur noch Nullen. Die erste Zeile ist unverändert. Man hat hier natürlich implizit einen Satz benutzt: Die Addition von Vielfachen einer Zeile (Gleichung) auf eine andere Zeile ändert die Lösungsmenge nicht! Wir wählen uns nun ein neues Pivotelemenent, etwa den Koeffzienten von y aus der zweiten Gleichung (Zeile) und erzeugen
mit diesem nach unten Nullen. Dabei gehe ich hier vom ganzzahligen (zweiten ) Zwischenresultat aus. Hier also Pivot −1 . Der
Leser kann zum Vergleich auch den ersten Fall weiterrechnen. Operation: II + III → III ergibt:
2x + y + z = 0
−y − z = −4
−2z = −6
2
1
1
⎜0
−1
−1
−4 ⎟
0
−2
−6
⎛
⎝
0
0
⎞
⎠
Nun beginnt die Phase "Rückwärtsauflösen":
III : − 2z = −6 ⇒ z = 3,
II : −y − 3 = −2 ⇒ y = 1,
I : 2x + 1 + 3 = 0 ⇒ x = −2
Die Schnittmenge ist somit der Punkt mit den Koordinaten (−2|1|3). Den GaußAlgorithmus haben wir hier mit der Pivotfolge (1;1) und (2;2) durchgeführt. Diese Zahlen bezeichnen die Indizes des
Pivotelemente.
In den Aufgaben finden Sie zwei Beispiele zu typischen GaußTableaus zum übersichtlichen Rechnen
Weitere Beispiele Beispiel 2: Gesucht: Schnittmenge der Ebenen
E1 : 2x + y + z = 0,
E2 : 4x + 3y + 3z = 1,
E3 : 8x + 6y + 6z = 2
Wir stellen die Koeffizientenmatrix des Gleichungssystems auf und führen zwei Schritte des GaußAlgorithmus durch mit der
Pivotfolge (1;1), (2;2):
⎛
⎞
⎛
⎞
⎛
⎞
2
1
1
0
2
1
1
0
2
1
1
0
⎜4
3
3
1⎟ → ⎜0
1
1
1 ⎟ → ⎜0
1
1
1⎟
6
6
2
2
2
2
0
0
0
⎛
⎝
8
⎞
⎛
⎠
⎝
0
⎞
⎛
⎠
⎝
0
⎞
⎠
Das Gleichungssystem ist lösbar, Rückwärtsauflösen ergibt
1
y + z = 1 ⇒ y = 1 − z,
2x + y + z = 0 ⇒ x = −
Die Schnittmenge ist also eine Gerade. In Parameterdarstellung (als Parameter z
= t
2
gewählt) kann man sie zum Beispiel so
schreiben:
⎛
x
⎛
⎞
−
1
2
z
⎠
0
⎛
⎞
1 ⎟ + t ⎜ −1 ⎟ ,
⎜ y⎟ = ⎜
⎝
⎞
⎝
0
⎝
⎠
1
t ∈ IR
⎠
Bei genauem Hinsehen ist klar: Die zweite und die dritte Ebenengleichung stellen dieselbe Ebene dar, die dritte Gleichung
bringt also keine neue Bedingung in das Gleichungssystem. Beispiel 3: Gesucht ist wieder die Schnittmenge der Ebenen
E1 : 2x + y + z = 0,
E2 : 4x + 3y + 3z = 1,
E3 : 8x + 6y + 6z = 5
Wieder GaußAlgorithmus mit Pivot (1;1), Rechnung : und danach
2
1
1
0
⎜4
3
3
1 ⎟ 6
6
5
⎛
⎝
8
⎞
⎠
P ivot(1; 1)
(−2) ∗ I + II → II
2
1
1
0
→ ⎜0
1
1
1⎟
2
2
5
⎛
⎝
(−4) ∗ I + III → III
0
P ivot(2; 2)
⎞
⎠
2
1
1
0
→ ⎜0
1
1
1⎟
0
0
3
⎛
(−2) ∗ II + III → III.
⎝
0
⎞
⎠
Die letzte Zeile der umgeformten Matrix steht für die Gleichung
0 = 0x + 0y + 0z = 3
Diese Gleichung besitzt keine Lösung, die Lösungsmenge ist die leere Menge, die Schnittmenge der drei Ebenen ist also leer.
Dies hätte man bei genauem Hinsehen schon anhand der Gleichungen sehen können. Die Ebenen E2 und E3 sind parallel
(derselbe Normalenvektor), aber verschieden (rechte Seite!). Beispiel 4: Schnittmenge der Ebenen
E1 : 2x + y + z = 1,
E2 : 6x + 3y + 3z = 3,
E3 : −2x + −y − z = −1
Hier genügt ein GaußSchritt, Pivot (1;1):
2
1
1
1
2
1
1
1
6
3
3
3⎟ → ⎜ 0
0
0
0⎟
−2
−1
−1
0
0
0
⎛
⎜
⎝
Die Lösungsmenge ist also die Ebene E1
= E2 = E3
−1
⎞
⎠
⎛
⎝
0
⎞
⎠
, alle Gleichungen stellen also dieselbe Ebene dar. Berechtigte Frage: Warum rechnet man überhaupt mit dem GaußAlgorithmus und löst dies nicht gleich durch "genaues
Hinsehen"? Antwort: Unsere Demonstartionsbeispiele sind bewusst kleine (n=3) Beispiele, die den geometrischen Hintergrund illustrieren
sollen. Bei technischen Berechnungen (z.B. FiniteElement Methoden ) treten Gleichungssysteme mit tausenden oder gar
Millionen Unbekannten auf. Da kann niemand mehr die Lösungsstruktur "per genaues Hinsehen" ermitteln. Den Gauß
Algorithmus kann man hingegen progammieren und dem Rechner dann die Lösung überlassen.
Wenn eine einfache Pivotfolge nicht möglich ist/Varianten des Gauß Verfahrens Hin und und wieder kommt es vor, dass bei einer Rechnung gerade der Koeffizient Null wird, den man normalerweise gerne als
nächstes PivotElement gewählt hätte. Beispiel 5 ⎛
⎞
⎛
⎞
2
1
1
0
2
1
1
0
⎜4
2
3
1⎟ → ⎜ 0
0
1
1⎟
6
6
2
2
2
2
⎛
⎝
8
⎞
⎛
⎠
⎝
0
⎞
⎠
Hier könnte man mit dem Rückwärtsauflösen einfach in Zeile II beginnen, also im Prinzip zweite und dritte Zeile vertauschen. Wir betrachten nun ein größeres Gleichungssystem (4 Gleichungen, 4 Unbekannte x,y,z, w), hier nur Koeffizientenmatrix und
rechte Seite als erweiterte Matrix geschrieben:
2
1
1
2
0
2
1
1
2
0
⎜4
⎜
⎜8
2
3
6
0
1
2
6
6
10
1⎟
⎜0
⎟ → ⎜
⎜0
2⎟
2
2
2
1⎟
⎟
2⎟
−2
−2
−4
⎛
P ivot(1; 1)
(−2) ∗ I + II → II,
(−1) ∗ I + IV → IV
⎝
2
−1
−1
−2
0
⎞
⎛
⎠
⎝
0
0
⎞
⎠
Das nächste übliche Pivotelement (2;2) ist leider Null. Welche Möglichkeiten hätte man, um die Rechnung weiter zu führen? 1. Man könnte Zeilen vertauschen, etwa II und IV. Das ist an sich unproblematisch, man muss allerdings die Matrix noch einmal
abschreiben, das bedeutet höherer Aufwand, Fehlerquelle. 2. Man könnte Spalten vertauschen. Dabei muss man aber dann auch die geänderte Zuordnung zu den Variablen beachten,
sonst kommt man bei Handrechnung bei größeren Systemen leicht durcheinander. Man sollte dann unbedingt die aktuellen
Variablennamen über den Spalten notieren, damit das Rückwärtsauflösen klappt. Ich rate von diesem Vorgehen allerdings
generell ab, weil es Verwirrung stiftet und fehleranfällig ist. 3. Mit dem GaußAlgorithmus flexibler rechnen und einfach andere Pivots wählen. Wesentlich ist doch nur, dass man nachher
zum Rückwärtsauflösen genügend viele Nullen in der Matrix stehen hat. Es böte sich als Pivot Element (2,3) an, wie bereits
oben markiert. Mit einer Eins als Pivot rechnet es sich ohnehin einfach. 2
1
1
2
0
2
1
1
2
0
2
1
1
2
0
⎜0
⎜
⎜0
0
1
2
0
1
2
1
2
2
2
2
0
−2
1⎟
⎜0
⎟ → ⎜
⎜0
0⎟
0
2
1⎟
⎜0
⎟ → ⎜
⎜0
2⎟
2
0
−2
1⎟
⎟
0⎟
0
0
−2
2
⎛
P ivot(2; 3)
(−2) ∗ II + III → III,
2II + IV → IV
⎝
0
−2
−2
−4
0
⎞
⎠
⎛
⎝
0
−2
0
0
2
⎞
⎠
⎛
⎝
0
⎞
⎠
Den letzten Gaußschritt mit Pivot (3,2), also III + IV → IV habe ich nur eingefügt, damit man den Rang dann leichter
bestimmen zu kann (s.u.). Mit einer Zeilenvertauschung kann man die letzte Matrix dann auf die obere Dreiecksform
/gestaffeltes Gleichungssystem bringen. Zum Gleichungslösen wäre der letzte eigentlich gar nicht mehr nötig gewesen, da in der vorletzten Matrix bereits genug Nullen
in der Matrix standen , um rückwärts auflösen zu können.
Die Lösung ist damit (x; y; z; w)
IV :
−2w = −2, ⇒
w = −1,
III :
2y − 2w = 0 ⇒
w = y = −1,
II :
z + 2w = 1 ⇒
z = 3,
I :
2x + y + z + 2w = 0 ⇒
x = 0
= (0; −1; 3; −1)
GaußJordan Verfahren: Nullen nach oben und unten erzeugen Wir betrachten noch einmal Beispiel 1, aber erzeugen mit den Pivotelementen Nullen unterhalb und oberhalb in der jeweiligen
Spalte.
2
1
1
0
2
1
1
⎜1
1
1
2 ⎟ → ⎜0
−1
0
1
1
1
⎛
⎝
1
⎞
⎠
⎛
⎝
0
Im letzten Schritt haben wir −0, 5 ∗ III
Lösungen fast ablesen.
0
2
0
0
−1
−4 ⎟ → ⎜ 0
−1
−1
−1
−2
0
−2
+ II → II
⎞
⎠
⎛
⎝
0
−4
2
0
0
−4
−4 ⎟ → ⎜ 0
−1
0
−1 ⎟
0
−2
−6
⎞
⎠
⎛
⎝
0
−6
⎞
⎠
gerechnet. Nun ist das System vollständig entkoppelt, wir können die
2x = −4 ⇒ x = −2,
−1y = −1,
−2z = −6 ⇒ z = 3.
Das GaußJordan Verfahren verwendet man also zum Beispiel, um die Inverse einer Matrix zu bestimmen. Dazu muss man
simultan n Gleichungssysteme lösen, als Matrizengleichung (E bezeichnet die Einheitsmatrix).
AX = E,
Gauss-Jordan: (A|E) → (E|A
−1
)
Gleichungssysteme bei denen die Zahl der Gleichungen (m) nicht der Zahl der Unbekannten (n)
entspricht. Beispiel 6: n > m Mehr Unbekannte als Gleichungen. (vergleiche Beispiel 3) Zwei Fälle sind möglich: Unendlich viele Lösungen oder keine Lösung. (a) Gesucht ist die Schnittmenge der Ebenen
E1 : 2x + y + z = 0,
E2 : 4x + 3y + 3z = 1,
Gleichungssystem aufstellen, GaußAlgorithmus mit Pivot (1;1) ( (−2) ∗ I
2x + y + z = 0
2
1
1
0
(
4x + 3y + 3z = 1,
+ II → II, (−4) ∗ I + III → III
2
1
1
0
0
1
1
1
) → (
4
3
3
1
) .
)
Rückwärtsauflösen: y + z = 1, y = 1 − z, 2x + y + z = 0, x = −1/2. Die Schnittmenge ist also eine Gerade (unendlich viele Lösungen), Lösungsdarstellung durch Parametrisierung wie in Beispiel
2. (b) Gesucht ist die Schnittmenge der Ebenen
E2 : 4x + 3y + 3z = 1,
E3 : 8x + 6y + 6z = 5
Gleichungssystem aufstellen, wieder GaußAlgorithmus mit Pivot (1;1), ein Schritt genügt.
4x + 3y + 3z = 1,
4
3
3
1
(
8x + 6y + 6z = 5
8
Die letzte Zeile der letzten Matrix bedeutet rückübersetzt 0
4
3
3
1
0
0
0
3
) → (
6
= 3
6
5
)
, das Gleichungssystem hat somit keine Lösung. Beispiel 7: n < m Gleichungssystem mit mehr Gleichungen als Unbekannte. Drei Fälle sind möglich: Keine Lösung, genau eine Lösung, unendlich viele Lösungen. Die Beispiele (3 Gleichungen, zwei
Unbekannte) können vom Leser mit wenigen GaußSchritten durchgerechnet werden.
ö
ö
(a) keine L sung: ö
(b) genau eine L sung: x + y = 1,
(c) unendlich viele L sungen: x + y = 1,
,
x + y = 1,
,
x − y = 3
x − y = 3
−x − y = −1
2x + y = 2
2x + y = 3
2x + 2y = 2
Regeln und Tipps für die effiziente Rechnung mit dem GaußAlgorithmus. Für die Handrechnung beachte man folgendes: 1. Wenn man nicht unbedingt an die starre Pivotfolge (1;1) , (2;2) usw. gebunden ist, wählt man möglichst Pivots ganzzahlig
und betragsklein, etwa 1, 1 oder 2. Brüche oder große Zahlen machen die Matrizen schnell unübersichtlich, erhöhen den
Rechenaufwand und die Fehlerquote. Der GaußAlgorithmus hat die unangenehme Eigenschaft, dass sich anfängliche
Fehler bis zum Ende fortpflanzen!
2. Ganz wichtig: Aus jeder Zeile und jeder Spalte höchstens einmal ein Pivotelement wählen! Wenn man dies nicht
beachtet, zerstört man sich schon mühsam erzeugte Nullen wieder und rechnet redundant.
3. Wenn möglich beim Rechnen nur multiplizieren, nicht dividieren. Auf oft unnütze Schritte wie Normierungen von Zeilen in
der Matrix verzichten, wenn dadurch komplizierte Brüche entstehen. Generell die Matrizen so wenig wie möglich
umschreiben und abschreiben (Fehlerquelle!). Beim Rückwärtsauflösen die Variablenreihenfolge beachten.
4. Gewöhnen Sie sich ein festes System beim Rechnen an. Etwa Zeilen immer nur zu addieren, nicht einmal eine addieren,
dann wieder eine subtrahieren usw. Durcheinander erhöht die Fehlerrate.
5. Wenn Parameter in der Matrix stecken, dann sollte man diese möglichst nicht, oder erst so spät wie möglich als Pivot
wählen, weil ab dann oft Fallunterscheidungen und somit parallele Rechnungen nötig werden. Wenn viele Nullen in einer
Zeile sind, kann es günstig sein, diese als PivotZeile zu wählen, vorausgesetzt das mögliche Pivotlelement ist nicht
unangenehm.
6. Anders als hier in meiner HTML Darstellung, in der ich aus Übersichtsgründen die Matrizen meist nebeneinander gepackt
habe (weil man sonst zum Vergleiche zuviel hin und her scrollen muss) sollten Sie bei Handrechnung die Matrizen
untereinander schreiben. Die an den Zeilen vorgenommenen Rechenoperationen schreiben Sie daneben. Manche Leute
zeichnen sich auch regelrechte Tableaus mit Kästchen. Das hilft die Übersicht zu bewahren.
7. Wenn man das Verfahren programmiert und mit Gleitkommazahlen rechnet, dann wählt man anders als bei der
Handrechnung immer das betragsgrößte Element einer Spalte als Pivotelement. Grund:Rundungsfehlerdämpfung.
Rang einer Matrix und Lösbarkeit von Gleichungssystemen. Der Rang einer Matrix ist die Anzahl der linear unabhängigen Zeilen (oder Spalten, Zeilenrang=Spaltenrang). Man kann dem Rang ablesen, wenn man den GaussAlgorithmus so weit wie möglich durchführt, d.h, bis kein Pivotelement
mehr gewählt werden kann. Die Ergebnismatrix besteht dann aus Zeilen, in denen mindestens ein Element nicht Null ist, sowie
eventuell auch Zeilen, die nur Nullen enthalten, den Nullzeilen. Die Zahl der Zeilen, in denen nicht alle Elemente Null sind, bestimmt dann den Rang. Kurz: Rang (A) ist die Zahl der Nichtnullzeilen nach vollständiger GaußRechnung. Der Rang ist maximal, wenn er das Minimum aus Zeilen und Spaltenanzahl beträgt (min(m,n)) Bei einer 3x4 Matrix kann der Rang z.B. höchstens 3 sein, bei einer 4x3 Matrix ebenso. Rang(A ) = Anzahl der Nichtnullzeilen (mindestens ein Element ungleich Null) der Matrix nach vollständiger
Durchführung des GaußAlgorithmus Bei Verwendung der Pivotfolge (1;1), (2;2) (3;3) ... (Diagonalelemente) erhält man automatisch eine obere Dreiecksmatrix
(gestaffeltes Gleichungssystem). Der Rang ist hier leicht abzulesen. Vergleiche Beispiel 3 in Vektorräume Bei anderen Pivotwahlen kann man aus dem Ergebnis durch Zeilenvertauschung eine obere Dreieicksmatrix herstellen, der
Rang bleibt erhalten. Siehe Beispiel 5, Rang(A) =4. Beispiel 8: (a)Jeweils 1 GaußSchritt, Pivot immer (1;1):
3
1
Rang (
9
3
3
1
0
0
) = Rang (
1
3
2
Rang (
) = 1
3
1
2
0
0
−5
) = Rang (
9
3
3
1
1
) = 2
2
Rang (
3
1
2
0
0
0
) = Rang (
9
3
6
) = 1
(b) 5x5 Matrix mit Rang=4 durch Zeilenvertauschung (ändert Rang nicht) auf obere Dreieicksform gebracht
Zeilenvertauschungen II → II I
III → V
IV → I I
V → IV
′
′
′
′
2
1
1
2
0
2
1
1
2
⎜0
⎜
⎜0
⎜
⎜
⎜0
0
1
2
2
0
−2
0
0
0
0
1
2
2
0
−2
1⎟
⎜0
⎟
⎜
0 ⎟ → ⎜0
⎟
⎜
⎟
⎜
⎜0
0⎟
0
0
0
0⎟
⎟
1⎟
⎟
⎟
2⎟
0
0
0
0
⎛
⎝
0
0
0
0
2
⎞
⎛
⎠
⎝
0
0
⎞
⎠
Die Matrix hat 4 linear unabhängige Zeilen, wie man an der "Nullenstruktur" abliest. Nach etwas Training mit Matrizen muss man diese Vertauschung nicht immer schriftlich ausführen. Man muss nur sicher sein,
den GaußAlgorithmus so weit wie möglich gerechnet zu haben. Ein Gleichungssystem in Matrixform schreiben Ein Gleichungssystem wie in den Beispielen 15 kann man sich auch in folgender Form geschrieben denken (vergleiche
Matrixmultiplikation):
2x + y + z = 0
Ax⃗ = b
⃗ in Beispiel 1: x + y + z = 2
2
1
1
⎜1
1
1 ⎟ ⋅ ⎜ y ⎟ = ⎜2 ⎟
0
1
⎛
⟺
x + 0y + z = 1
⎝
1
⎞
⎠
⎛
⎝
x
z
⎞
⎠
⎛
⎝
0
1
⎞
⎠
Allgemein: A ist hier die mxnKoeffizientenmatrix. Gleichungssystem:
Ax⃗ = b
⃗ m
n
⃗ m Gleichungen, n Unbekannte b ∈ R , x⃗ ∈ R
Wir hatten in Beispiel 15 auf die erweiterte Koeffizientenmatrix (A|b) (Größe mx(n+1) ) den GaußAlgorithmus angewendet.
Aus den Ergebnissen können wir Informationen über den Rang ablesen: Rangbestimmmung in dem Beispielen: Quadratische Gleichungssysteme (quadratische Koeffizientenmatrix n=m). Beispiel 1: Rang(A) = Rang(A|b) = 3 , maximaler Rang, Gleichung war nach Rechnung eindeutig lösbar. Beispiel 2: Rang(A) = Rang(A|b) = 2 , kein maximaler Rang, Gleichung war nach Rechnung lösbar, aber nicht eindeutig. Beispiel 3: Rang(A) = 2 < Rang(A|b) = 3 : Gleichung nicht lösbar. Beispiel 4: Rang(A) = Rang(A|b) = 1 , kein maximaler Rang, Gleichung war nach Rechnung lösbar, aber nicht eindeutig. Beispiel 5: Rang(A) = Rang(A|b) = 4 , maximaler Rang, Gleichung war nach Rechnung eindeutig lösbar. Weniger Gleichungen als Unbekannte, m
< n
, "flache Koeffizientenmatrix" : Beispiel 6a: A 2x3 Matrix, Rang(A) = 2 = Rang(A,b) < 3=n : Unendlich viele Lösungen. Beispiel 6b: A 2x3 Matrix, Rang (A) = 2 < Rang(A|b) = 3: Keine Lösung. Beispiel 7(a) Rang(A) = 2 < Rang(A|b) = 3 : Keine Lösung. Beispiel 7(b) Rang(A) = 2 = Rang(A|b) = 2 : Genau eine Lösung. Beispiel 7(c) Rang(A) = 1 = Rang(A|b) = 1 < n=2 : Unendlich viele Lösungen, 1=n1 freie Parameter. Hinter dieser Beobachtung an den Beispielen steht auch ein allgemeiner Satz: Kriterien für die Lösbarkeit des Gleichungssystemen Ax⃗ = b ⃗ Bezeichnungen: A sei eine reelle (oder komplexe) mxnMatrix. Homogenes Gleichungssystem Ax⃗ = 0 Inhomogenes Gleichungssystem Ax⃗ =
⃗ b ≠ 0
1. Allgemeines Kriterium für beliebige A mxn Matrix (n, m
Das inhomogene Gleichungssystem Ax⃗ =
m
⃗ b ∈ IR
≥ 1, )
, m Gleichungen, n Unbekannte. : ist genau dann lösbar mit Lösung(en) x⃗ ∈
IR
n
, wenn
r = Rang(A) = Rang(A|b)
vorliegt. Die Lösung enthält dann genau n − r freie Parameter. Im einzelnen bedeutet das: 2. Sonderfall quadratische Gleichungssysteme n = m : Folgende Fälle sind möglich: (a) A hat maximalen Rang: Falls Rang(A) = n vorliegt, dann ist das Gleichungssystem für jede rechte Seite b ∈ Rn
eindeutig lösbar. Die Erweiterung mit b kann den bereits maximalen Rang nicht mehr erhöhen, zwangsläufig also auch Rang(A|b) = n,
somit ist die rechte Seite b für die Lösbarkeit nicht relevant. r = n : Somit keine freien Parameter in der Lösung. Ferner: Die homogene Gleichung Ax = 0 hat dann auch nur die eindeutige Lösung x = 0 . (b) A hat nicht den maximalen Rang: r = Rang(A) < n UND es ist r = Rang(A) = Rang(A|b). Dann ist das Gleichungsystem lösbar, jedoch nicht eindeutig. Die Lösbarkeit hängt in diesem Fall von b ab, das Gleichungssystem ist nicht für jede rechte Seite lösbar. Es gibt dann unendlich viele Lösungen mit n − r freien Parametern. Der Nullraum (Kern) N (A) = {x ∈ Rn |Ax = 0} ist ein Untervektorraum von Rn mit der Dimension n − r . In diesem Fall lässt sich jede Lösung x des Systems in der Form
x = xs + xh ,
ö
xh ∈ N (A), xs eine spezielle L sung von Ax = b
darstellen. (Zerlegungssatz). Zerlegung der Lösung in homogenen Anteil xh und inhomogenen Anteil xs . , Vergleiche
Beispiel 2 und 4. ) (c) Falls Rang(A) < Rang(A|b) dann gibt es keine Lösung des inhomogenen Gleichungssystems. 3. m < n , Gleichungssysteme mit mehr Unbekannten (n) als Gleichungen (m), flache Koeffizientenmatrix: Ax = b
ist nur lösbar wenn r
= Rang(A) = Rang(A|b),
der Zerlegungssatz aus 2(b) gilt auch hier. n − r
4. m
> n
≥ 1
jedoch nie eindeutig lösbar. Wieder ist dim(N(A) ) = nr und
freie Parameter.
mehr Gleichungen (m) als Unbekannte (n), "hohe" Koeffizientenmatrix: Generell lösbar wenn Rang(A)=Rang(A|b), eindeutig lösbar wenn noch Rang(A)=Rang(A|b)= n,
nicht eindeutig lösbar wenn r= Rang(A)=Rang(A|b) <
unlösbar wenn Rang(A)
n
, Zerlegungssatz aus 2(b) gilt auch hier. ≠ Rang(A|b).
Bemerkung: Für eine quadratische nxn Matrix besteht noch folgender äquivalenter Zusammenhang mit der Determinante:
Rang(A) = n
⟺ det(A) ≠ 0
Rang(A) < n
⟺ det(A) = 0
Reguläre und singuläre Matrix : eine nxn Matrix mit Rang n heißt regulär, ist der Rang <
n
so heißt sie singulär Nochmal: Mit der Determinante kann man nur feststellen, ob der Rang maximal ist oder nicht. Den genauen Rang kann man für
Rang(A) <
n
nur an der z.B. mit dem GaußVerfahren bearbeiteten Matrix ablesen. Es ist also völlig überflüssig und sinnlos zuerst die Determinante der Koeffizientenmatrix auszurechen, und dann
nochmal ein GaußVerfahren beim Gleichungssystem zu starten! Die Determinante kann man allenfalls ausrechnen, wenn
man lediglich wissen will, ob das System überhaupt eindeutig lösbar ist aber an der Lösung selber gar nicht interessiert ist. Und auch das macht man nur dann, wenn die Determinante aufgrund der Matrixstruktur schneller/einfacher zu rechnen ist, als
ein GaußVerfahren. In der Regel erleichtert man sich die Determinantenberechnung aber doch wieder durch einige Gauß
Schritte (Entwicklungssatz), dann kann also besser das GaußVerfahren auch gleich auf die Koeffizientenmatrix loslassen und
alle gewünschten Infos am Ergebnis ablesen.
Unangenehme Koeffizienten und parameterabhängige Gleichungen Kleiner Test: Sie haben den GaußAlgorithmus gut verstanden, können flexibel damit rechnen und damit die Lösbarkeit von
Gleichungssystemen entscheiden, und ihre Lösungen berechnen? Prima dann versuchen Sie sich doch mal an folgender
Aufgaben. 1. Aufgabe.
7x + 2y + 9z = 1
3x + y + z = 1
11x + 5y + 4z = 1
Tipp: Pivots geschickt wählen.´ Wenn Sie viel Zeit haben und gerne rechnen, dürfen Sie natürlich auch gerne die PivotFolge
(1;1) , (2;2) probieren. ;) 2. Aufgabe: Hier sind die Koeffizienten teilweise Parameter (s, t ), wie in technischen Problemstellungen häufig vorkommend. Gesucht ist die Lösungsmenge (Achtung: diese ist parameterabhängig, Parameter sind s, t !) des folgenden linearen
Gleichungssystems.
tx + y + 3z + 2w = 2
x + z + w = s
2x + y + 2z + w = 1
Für welche Parameter t ist das folgende Vektorsystem eine Basis des R3 ?
⎛
Weitere Aufgaben hier
t
⎞
⎛
1
⎞
⎛
3
⎞
⎜1 ⎟,
⎜0 ⎟,
⎜1 ⎟
⎝
⎝
⎝
2
⎠
1
⎠
2
⎠
© Copyright 2024 ExpyDoc
