Was haben wir letzte Woche gemacht?
Wiederholen wir das ganz kurz auf diesem Gerät hier, damit auch die,
die es nachhaltig anschauen, sehen, um was es geht.
Wir wollten lösen A x gleich b, also ein lineares Gleichungssystem,
mit A eine invertierbare Matrix.
Die Voraussetzung der Invertierbarkeit hat uns garantiert, dass es
eine Lösung gibt und dass diese Lösung eindeutig ist.
So, die Idee war, dieses im Allgemeinen schwere Problem, es ist also
eins der leichten in der Numerik, aber trotzdem am Anfang noch schwer
genug, weil A selber eine Matrix ist, von der wir nicht viel
voraussetzen können, keine Struktur und so weiter.
Und wir haben gesehen, wenn wir eine obere 3x-Matrix haben oder eine
untere 3x-Matrix, dann lässt sich das leicht lösen.
Und dann war die Idee, ja, können wir vielleicht A zerlegen in ein
Produkt von solchen Matrizen, um dann eben einfach die Sache lösen zu
können.
Wir werden heute in einem Satz beweisen, dass das nicht immer der Fall
ist, aber es existiert für eine invertierbare Matrix immer eine
Permutationsmatrix P, die wir von links an das A heran multiplizieren.
Und für diese Matrix existiert eine Leerzerlegung.
Und die ist auch noch eindeutig.
Die ist eindeutig, sobald Sie P gewählt haben.
Sie können verschiedene P's finden, so dass P mal A eine Leerzerlegung
hat.
In dem Sinne sind die Leerzerlegungen nicht eindeutig.
Aber sobald Sie P gewählt haben und so ein P existiert, ist die
Zerlegung eindeutig.
So, jetzt schauen wir uns das mal kurz an.
Was macht eigentlich eine Permutationsmatrix, wenn man sie von links
an eine Matrix heran multipliziert oder an einen Vektor?
Wissen Sie noch, was eine Permutationsmatrix ist aus der linearen
Algebra?
Nicht mehr so genau.
Okay, doch jemand weiß es, ja?
Genau, die Idee war, dass die Einheitsmatrix, aber zwei Zeilen sind
vertauscht.
Das ist schon sehr nah dran.
Das sind spezielle Typen von Permutationsmatrixen.
Oder mehr, ganz genau, ja.
Also Sie können meinetwegen ausgehen von der Einheitsmatrix, ist ganz
gut.
Da haben wir nur Nullen und Einsen drin stehen, nichts anderes.
Und in der Permutationsmatrix stehen tatsächlich auch nur Nullen und
Einsen.
Und jetzt fangen Sie an, in der Identität, in der Einheitsmatrix,
fangen Sie an, die Zeilen zu mischen, zu permutieren, letztlich.
Und können sich das Ergebnis irgendwie vorstellen.
In der ersten Zeile stand ja vorher der erste Einheitsvektor liegend.
Und der liegt jetzt meinetwegen weiter unten in der Zeile.
Also alle Einheitsvektoren kommen vor und sie kommen ganz genau einmal
vor, ja.
So ist eine Permutationsmatrix aufgebaut.
So, wenn wir sowas jetzt von links an eine Matrix A heran
multiplizieren, machen wir es noch ein bisschen einfacher.
Sie multiplizieren den Karteneinheitsvektor.
Der Karteneinheitsvektor ist der, der überall Nullen stehen hat, nur
in der Kartenstelle hat er eine Eins stehen.
Den bringen Sie zum Liegen, indem Sie transponieren.
Und diesen liegenden Karteneinheitsvektor multiplizieren Sie an eine
Matrix A heran.
Was erhalten Sie?
Können Sie das im Kopf machen, nach dem Prinzip, Zeile mal Spalte,
Zeile mal Spalte.
Das Ergebnis hat welche Struktur?
Im Kopf, ja.
Wenn Sie jetzt, also ich kann es auch hier hinschreiben, dann haben
wir es vielleicht besser vor Augen.
So, wir nehmen den Karteneinheitsvektor, legen den hin und
multiplizieren den an eine Matrix A.
Was erhalten wir?
Ja, EK wissen Sie, es hat lauter Nullen, aber an der Kartenstelle
steht eine Eins.
Und den haben wir durch das Transponieren hingelegt.
Denken Sie kurz darüber nach, wie ist die Struktur der rechten Seite
des Ergebnisses?
Wie sieht das aus?
Und dann vielleicht konkret, welcher Teil von A ist das?
Ja, ganz hinten?
Die Kartezeile von A, genau.
Ja, also es muss auch ein Zeilenvektor rauskommen.
Sehen Sie, die Struktur ist der liegende Zeilenvektor mal die Matrix
und es gibt wieder einen liegenden Zeilenvektor.
Das ist die Struktur und Sie haben völlig recht, wenn ich an der
Kartenstelle eine Eins habe, dann picke ich mir sozusagen die
Kartezeile heraus.
Das wäre vielleicht eine ganz gute Geschichte, hier A zu nehmen mit
dem unteren Index K.
Was gemeint ist, ist die
Kartezeile von A.
Das ist nicht ganz unwichtig in allem, was wir heute machen, dass wir
diese Multiplikationen von links ein bisschen verstehen, von Vektoren
und nachher auch von ganzen Matrizen.
Was macht also jetzt eine Permutationsmatrix als Gesamtes?
Die besteht ja nicht nur aus einer Zeile, sondern eben, wenn wir in N
-Dimensionen sind, aus N-Zeilen.
Wenn wir die jetzt von links an das A dran multiplizieren, was macht
das?
Ja, ganz genau, vertauscht oder permutiert der lateinische Wort die
Zeilen von A eben genauso wie die Permutationsmatrix das möchte, das
was sie ausmacht.
Die Zeilen werden durchgemischt und wenn erst einmal die Zeilen
durchgemischt sind, dann also die Behauptung des Satzes, die wir heute
beweisen werden, ist folgende.
Es gibt so ein Durchmischen der Zeilen, so dass es ab diesem Zeitpunkt
möglich ist, eine Leerzerlegung zu finden, eine eindeutige.
Also wir müssen unter Umständen vorher die Zeilen oder in dem Prozess
die Zeilen ein bisschen tauschen.
Okay, das macht das P, wenn ich es von links auf das A drauf
multipliziere.
Wie können wir das jetzt benutzen, um das lineare Gleichungssystem zu
lösen?
Wir wollen A gleich B lösen.
Wir haben es am Ende der letzten Vorlesung zumindest für P gleich
Identität schon mal formuliert und jetzt wollen wir es unbedingt
wiederholen, weil es ein wichtiger Aspekt ist, aber für das allgemeine
P. P ist eine Permutationsmatrix.
Wie können Sie, wenn Sie so eine Zerlegung haben, PA ist gleich LR,
wie können Sie das investieren, um das lineare Gleichungssystem zu
lösen?
Ja?
Sehr schön.
Sie wollen die rechte Seite kleinen b mit P durchmultiplizieren, PB
berechnen.
Das ist genau richtig.
Das müssen wir.
Haben Sie völlig recht.
Wir wollen ja die LR-Zerlegung irgendwie investieren in das
Gleichungssystem und das geht noch nicht, weil da steht A mal X gleich
B.
Was können wir leicht machen, um, Sie haben schon gesagt, PB
berechnen.
Das ist schon mal ganz okay und richtig.
P mal B, das ist die rechte Seite, naja und auf der linken Seite
multiplizieren wir das P einfach auch drauf.
Dann haben wir P mal A mal X.
Wir nehmen einfach das Gleichungssystem, das lineare Gleichungssystem
und vertauschen die Gleichungen.
So geschickt, dass eben genau P mal A auf der linken Seite steht.
Das müssen wir natürlich dann auf der rechten Seite auch machen, mit
dem B.
Das müssen wir genauso vertauschen.
So, wenn wir das gemacht haben, dann ist es jetzt eigentlich alter
Kaffee, weil jetzt können wir was machen.
Genau, das war die Idee.
Jetzt erst können wir hier schreiben L mal R mal X gleich PB.
Und dann erinnern Sie sich an letzte Woche, dann würde man diesen Teil
für Moment mal Y nennen und löst in dem ersten Schritt LY gleich PB.
Das ist einfach.
PB zu berechnen ist schon einfach.
PB heißt nur, die Dinge in eine andere Reihenfolge zu schreiben.
Wenn Sie jetzt irgendwie an Speicher denken, brauchen Sie lediglich
den Zeiger irgendwie zu ändern.
Das geht ganz schnell.
Jetzt haben wir das geändert, haben PB ausgerechnet.
Jetzt können wir das Gleichungssystem leicht lösen, weil es ein
unteres Gleichungssystem ist.
Also L ist eine untere Dreiecksmatrix.
Das sage ich Ihnen jetzt noch, das werden wir heute sehen, dass es so
ist.
Und zu Schluss muss ich das Y noch ausrechnen.
Rx gleich Y.
Und wenn R eine obere Dreiecksmatrix ist, geht das auch leicht.
So, das ist die Motivation für heute.
Diesmal mit dem P berücksichtigt.
Wir müssen also unbedingt die rechte Seite B mit dem P
durchmultiplizieren, um dann durch LY PB und Rx gleich Y die Lösung
des linearen Gleichungssystems zu erhalten.
Gut, das müssen Sie sich merken.
Gehen wir zu dem Vortrag heute.
Gucken wir uns die Folie mal dazu an.
Ich will Sie erinnern an etwas, was Sie in der linearen Eigebrache
schon gemacht haben.
Da haben Sie die Gauss-Elimination schon kennengelernt.
Und ich habe hier mal eine Gauss-Elimination aus der linearen Eigebra
hergenommen, so wie Sie das vielleicht gemacht hätten.
Gucken Sie sich das mal kurz an.
Also, wie ging das?
Wissen Sie noch?
Wir schreiben die Matrix ab.
Also wir wollen jetzt hier, links steht das Problem Ax gleich B, was
wir lösen wollen.
Und wie haben wir das gemacht?
Oder so ähnlich zumindest.
Wir schreiben das A in so eine kompakte Form und die rechte Seite
einfach rechts daneben.
Die 2, 4 und die 14.
Und dann haben wir in irgendeiner Art und Weise die Matrix A
vereinfacht, so dass wir die Lösung irgendwann mehr oder weniger
leicht ablesen können.
Ein Vorschlag von mir wäre folgender.
Nehmen Sie das Minuszweifache der ersten Zeile und addieren Sie es
nach unten auf die zweite Zeile.
Gut, der Sinn davon ist Ihnen allen klar.
Wir können vorne eliminieren.
Deswegen heißt es auch Gauss-Elimination.
Wir erzeugen ganz vorne in der zweiten Zeile eine Null.
So, was haben wir sozusagen gemacht?
Was repräsentiert eigentlich die Null?
Die repräsentiert 0 mal x1.
Das heißt, wir haben die Variable x1 aus der zweiten Gleichung
eliminiert.
Die kommt nicht mehr vor.
In der zweiten Gleichung steht jetzt nur noch minus 2 mal x2 plus 1
mal x3 gleich 0.
Das ist die Bedingung, die in der zweiten Zeile kodiert ist und x1
taucht nicht mehr auf, ist eliminiert.
Gut, haben Sie schon immer so gemacht.
Und wenn wir jetzt noch das Minuszweifache der ersten Zeile auf die
letzte Zeile addieren, kriegen wir auch noch eine Elimination von x1
in der letzten Bedingung, in der letzten Gleichung.
Das heißt, wir haben in der ersten Spalte außer der 1 oben nur noch
Nullen.
So, das war sozusagen der erste Schritt.
Und ein zweiter Schritt könnte daran bestehen, die zweite Variable,
die ja natürlich in der ersten Gleichung vorkommt, in der zweiten
Gleichung vorkommt, in der darunter liegenden Gleichung, in der
dritten also, zu eliminieren.
Und da schlage ich vor, wir nehmen das Minus1-fache.
Das sind so schöne, einfache Zahlen, dass wir das wunderbar
überblicken können.
Das Minus1-fache der zweiten Zeile auf die letzten Zeile.
Und dann haben wir auch zwei Nullen in der letzten Zeile.
Die letzte Zeile ist nur noch von x3 abhängig.
Das heißt, bei drei Variablen können wir x3 wunderbar lösen.
Das ist 2 und das ist die Rückwärtssubstitution, die wir ja schon
letzte Woche kennengelernt haben und die sie auch schon immer
angewendet haben, wahrscheinlich intuitiv.
Da gehen sie rückwärts, rechnen x2 aus und x1.
Okay, so haben wir das in der Linie an Algebra gemacht.
Im Grunde genommen wollen wir das weiterhin so machen.
Die Idee ist, dass wir uns aber diese Faktoren, mit denen wir die
erste Zeile bzw.
unterliegende Zeilen multiplizieren, um sie dann nach unten zu
addieren, diese Faktoren, die hier am rechten Rand stehen, also
Minus2, Minus3 und auch die Minus1, die wollen wir uns merken.
Damit wir die LR-Zerlegung sozusagen einfach speichern, stellen Sie
sich vor, Sie haben jetzt noch eine andere rechte Seite, B.
Das A bleibt völlig identisch, aber B ändert sich.
Wenn Sie jetzt eine Rechnung gemacht hätten und hätten sich die nicht
gemerkt, die Faktoren, dann hätten Sie wieder die Matrix hinschreiben
müssen, wieder die rechte Seite und hätten alles nochmal gerechnet.
Und wir sagen, nein, nein, eigentlich ist die rechte Seite gar nicht
so interessant für uns.
Wir wollen vielmehr A zerlegen in L mal R.
Das heißt, für uns interessiert vielmehr die obere Dreiecksmatrix, die
hier unten steht und die Faktoren, die ich brauche, um die zu
erreichen.
Das sind eigentlich die Dinge, die ich speichern möchte.
Das wird nachher meine LR-Zerlegung werden und die rechte Seite, naja,
da können wir dann einsetzen, was wir wollen, nach dem Prozedere, wie
wir es eben gesagt haben.
Und jetzt wollen wir ganz kurz klären, deswegen war es gut, dass wir
am Anfang nochmal wiederholt haben, was es heißt, eine Zeile von links
an eine Matrix dran zu multiplizieren.
Ich will Ihnen mal zeigen, welche algebraische Operation dahinter
steckt, wenn wir ein Minus-Zweifaches zum Beispiel einer oberen Zeile
auf eine darunter liegende drauf multiplizieren, beziehungsweise das
Minus -Dreifache.
Was heißt das eigentlich aus dem Blick der Linie an Algebra?
Das heißt folgendes, das ist genau die Matrix aus dem Beispiel und
jetzt wollen wir eliminieren.
Wir wollen also Nullen erzeugen in der ersten Spalte.
Das klappt auch und sehen Sie, welche Matrix ich von links auf das A
drauf multiplizieren muss, damit ich das erreiche.
Ich habe sie Ihnen hier angegeben, diese L1-Matrix.
So, die hat in der ersten Zeile 1, 0, 0 stehen.
Das ist der erste Einheitsvektor.
Wir haben eben wiederholt, was es heißt, Einheitsvektor mal Matrix.
Wenn Sie das ausmultiplizieren, kommt die erste Zeile von A wieder
raus.
Passiert gar nichts.
Das sehen Sie auf der Folie.
Das Ergebnis hat die gleiche Zeile wie A.
Die oberste Zeile sind identisch.
So, jetzt gehen wir mal in die zweite Zeile von dem L1.
Wie sieht die aus, die 0?
Jetzt multiplizieren Sie das mal auf das A in Gedanken.
Machen Sie das mal.
Wie geht das?
Ja, wollen Sie mal erklären?
Ganz genau.
Das minus 2-fache der ersten Zeile plus das 1-fache der der zweiten
Zeile plus das 0-fache der letzten.
Interessiert nicht.
Genauso kommt es zustande und entsprechen natürlich, wenn wir uns die
dritte Zeile angucken, minus 301.
Das ist das minus 3-fache der ersten, das 0-fache der zweiten und das
1 -fache der untersten.
Also genauso kann man das realisieren, diese Gauss-Elimination durch
Multiplikation von links mit solchen Matrizen, von dieser Struktur.
Genauso, wenn wir jetzt eliminiert haben, das X1 und jetzt im nächsten
Schritt X2 eliminieren wollen, dann sage ich, erinnern Sie sich, in
dem Beispiel war das, gehen wir ganz kurz nochmal zurück, das minus 1
-fache, sehen Sie hier, der zweiten Zeile auf die letzte drauf
addiert.
Und schauen wir uns an, in der linearen Algebra wäre das kodiert in
der Multiplikation von so einem L2 noch zusätzlich obendrauf von
links.
Sehen Sie, die minus 1 steht jetzt in der allerletzten Zeile.
In der ersten Zeile steht der Einheitsvektor, der erste, in der
zweiten steht der zweite Einheitsvektor.
Das sind Vektoren, die machen nichts bei der Multiplikation.
Am Ende kommt wieder das gleiche raus.
Sehen Sie, diesmal hier an der Stelle, hier und hier, die beiden
Matrizen haben die identischen ersten beiden Zeilen.
Da tut sich nichts, wegen der Struktur von L2.
Aber in der allerletzten Zeile steht 0-1 1 hier.
Ja, wunderbar, so kann man ja auch ganz gut zeigen.
So, das heißt, ich nehme das 0-fache der ersten, die interessiert mich
ja nicht mehr, jetzt nehme ich das minus 1-fache der zweiten und lade
das auf die dritte.
So funktioniert es.
Können Sie sich jetzt schon vorstellen, das R definiere ich natürlich
als der Rest, der da übrig bleibt.
Diese obere Dreiecksmatrix, das haben wir hier.
Ja, wie komme ich jetzt zu einem L?
Schauen wir uns das mal kurz an.
Gucken Sie hier oben in die erste Zeile.
Insgesamt halten wir fest, dass wir herausgekriegt haben, wenn ich A
erstmal mit L1 multipliziere von links, dann L2 auch noch drauf
multipliziere, dann erhalte ich obere Dreiecksstruktur R.
Und das sind die beteiligten Matrizen.
Was wir jetzt machen können ist, diese Matrizen, die jetzt noch auf
der linken Seite stehen, auf der Seite, wo A vorkommt, da sollen Sie
ja nicht hin.
Wir wollen ja schreiben, A ist gleich L mal R.
Das soll ja auf die andere Seite.
Gut, das können wir durch Invertierung auf die andere Seite bringen.
Das heißt, wir multiplizieren, passen Sie auf, hier erst mit L2, mit
der Inversen durch und dann mit L1.
Aber hier ist eine Frage.
Okay, Frage an alle.
Gucken Sie sich mal die L1 und L2-Geschichten an.
Warum sind die invertierbar?
Ja?
Determinant ist ungleich 0, offensichtlich.
Das ist eine Äquivalenz der Invertierbarkeit.
Hat jemand eine andere Beschreibung?
Kann nicht schaden, dass wir ein paar wiederholen.
Hat vollen Rang, sieht man auch relativ leicht.
Ja, die Einsen auf der Hauptdiagonale, das macht ja die Determinante
aus.
Die Determinante wird ja berechnet durch das Produkt der
Hauptdiagonalelemente.
Da stehen nur Einsen.
Aber wir können auch ein bisschen mehr von dem Prozess denken, wie die
generiert worden sind.
Was haben wir denn gemacht?
Wir haben ein gewisses Vielfaches der ersten Zeile auf untere drauf
multipliziert.
Frage an Sie, kann man diesen Prozess umkehren, um wieder an die
Ausgangsposition zurückzukommen?
Na doch, kann man natürlich.
Wenn Sie das Minusfünffache der ersten Zeile nach unten addieren, dann
können Sie das rückgängig machen, indem Sie diesmal nicht das
Minusfünffache der ersten Zeile nach unten addieren, sondern das
Fünffache.
Dann sind Sie wieder da, wo Sie angekommen sind.
Da gucken Sie alle ein bisschen ungläubig.
Ich dachte, das wäre eine schöne Motivation, warum ich sagen kann,
dieser Prozess des Addierens einer oberen Zeile auf eine untere, den
kann ich rückgängig machen, indem ich genau das Vielfache dieser
Zeile, was ich vorher drauf addiert habe, nach unten diesmal abziehe.
Und dann ist es so, als ob ich gar nichts gemacht hätte.
Und deswegen ist der Prozess umkehrbar.
Und deswegen muss die Geschichte invertierbar sein.
Das ist eigentlich ganz schön.
Wie sähe denn dann die Inverse unter Umständen aus von dem L1?
Ach, das steht schon unten.
Ja, sehen Sie, das Inverse steht sogar direkt hier unten.
Und zwar ist das die Matrix.
Es ist im Grunde genommen L1, aber die Vorzeichen haben sich gedreht
in den Argumenten, die unter der Hauptdiagonal stehen.
Sehen Sie, hier steht minus 2, hier steht minus 3 und hier unten, das
ist die Inverse tatsächlich, da steht 2 und 3.
Das ist exakt genau das, was ich gerade gesagt habe.
Wenn Sie ein Zweifaches der ersten Zeile nach unten addieren, dann ist
der Umkehrprozess, ein Zweifaches der ersten Zeile zu subtrahieren.
Genau das Gegenteilige, gegenteilige Vorzeichen.
Und deswegen auf Ihre Frage, ja, die sind invertierbar.
Wir können argumentieren über die Determinante.
Wir können aber auch an dem Beispiel hier schön argumentieren und
sagen, diesen Prozess kann ich wieder umdrehen, als ob es am Ende
nichts passiert wäre.
Und zwar, das hilft dann sogar, die Inverse sozusagen anzugeben.
Von daher hoffe ich, dass es Ihnen jetzt plausibel ist, dass das die
Inverse ist, aber mit umgedrehten Vorzeichen hier unten.
Genauso die Inverse von dieser Matrix, von der L2-Matrix, die steht
hier und da ist es ganz genauso.
Wir können hier an der Stelle den Prozess umkehren.
Aber gucken Sie sich noch mal bitte diese Zeile hier in der Mitte an.
Hier steht A ist gleich.
Sehen Sie, die L-Matrizen haben wir auf die andere Seite gebracht
durch das Invertieren und wir haben gerade sehr stark motiviert, und
Sie müssen das in den Übungen beweisen, dass man die Inverse leicht
erhält, indem man einfach das Vorzeichen in den Elementen ändert, die
unter der Hauptdiagonal liegen.
Es ist also ganz leicht invertierbar.
Und jetzt noch eine Beobachtung.
Gucken Sie sich mal hier in der letzten Zeile das Produkt an.
Hier steht L2 hoch minus 1, hier steht L1 hoch minus 1 und hier hinten
steht das Ergebnis.
Haben Sie eine Idee?
Es kann ja nur eine Vermutung sein, wie das zustande kommt.
Ganz genau.
Auf der Hauptdiagonalen bleiben die Einsen, oben natürlich auch die
Nullen.
Sie haben vielleicht in der Linear Algebra gelernt, dass das
Modifizieren von unteren 3x-Matrizen immer wieder eine untere 3x
-Matrix ergibt.
Und jetzt haben Sie völlig recht.
Unten kann man sagen, additiv im Grunde genommen werden also die
einzelnen Spalten in den Faktoren im Ergebnis einfach reingeschrieben.
Man muss gar nicht rechnen bei der ganzen Geschichte.
Also die 2, die hier in dem Faktor steht, wird einfach hier
reingeschrieben.
Die 3, die hier steht, wird einfach reingeschrieben und die 1, die
hier steht, wird einfach reingeschrieben.
Also auch das Berechnen dieses Produktes von lauter Inversen ist, wenn
es genau so in der Reihenfolge vorkommt, das ist wichtig, kein
wirkliches Rechnen.
Es ist nur ein Reinschreiben von Faktoren und zwar genau den Faktoren,
die Sie benutzt haben in der Gauss-Elimination, um Nullen zu erzeugen.
Diese Faktoren, beziehungsweise das mit umgekehrten Vorzeichen,
schreiben Sie einfach da rein in das L.
So einfach ist das.
Hier habe ich die Dinge mal auf einer Folie zusammengefasst.
Beobachtungen, die ich schon motiviert habe.
Wie gesagt, der Beweis, den Beweis für diese Beobachtungen, den
müssten Sie in den Übungen durchziehen.
Wir haben gesagt, dass Inverse einer solchen Matrix, also die
Matrizen, die ich brauche zum Eliminieren, die haben diese Struktur.
Einsen auf der Hauptdiagonale und alles, was ich jetzt nicht
spezifiziert habe als Eintrag, soll Null sein.
Das ist besser, es ist übersichtlicher, wenn man alles weglässt, was
Null ist.
Aber Sie müssen das so lesen, alle Einträge, die jetzt nicht
spezifiziert worden sind in der Matrix sind Null.
Typischerweise haben die immer die Einsen auf der Hauptdiagonale und
in der Kartenspalte, das entspricht genau dem Karten-Eliminations
-Schritt, wo ich also die xk eliminieren will aus den
darunterliegenden Zeilen, in der Kartenspalte stehen Einträge und
genau die Faktoren, die sie brauchen, um zu eliminieren.
Und die Inverse steht da gar kein hoch minus eins, das ist auch wieder
ein strange, warum jetzt vor der Hochzahl kein Minus steht, aber da
müssen Sie ein Minus hindecken, das soll die Inverse sein.
Ich lerne immer wieder neue Dinge dazu, keine Ahnung, wie das Minus
verschluckt worden ist, es war definitiv da und ich kann es jetzt auch
nicht hinmalen, weil der Tablet-Computer nicht mitmacht.
Und das gleiche Zeichen fehlt auch noch.
Interessant.
Also die erste Zeile bitte so lesen, da steht LK, das ist diese
Matrix, die ich definitiv brauche zum Eliminieren und hinten sollte
eigentlich die Inverse stehen.
Also LK hoch minus eins ist gleich.
Okay, im unteren Teil denke ich, stimmt wieder alles, alles ist
vorhanden.
Die Frage war jetzt, wenn ich diese Eliminationsmatrizen eben alle
leicht invertiere und am Ende alle aufmultipliziere, wie funktioniert
das?
Ganz einfach, wir brauchen noch nicht mal rechnen, die Einträge werden
einfach alle in die Ergebnismatrix reingeschrieben, ohne zu rechnen.
Ja, das sind Beobachtungen, die Sie dann bitte in den Übungen mit ein
bisschen Hilfe, wie man das gut machen kann, relativ leicht beweisen
können.
So, jetzt war das ein einfaches Beispiel, was ich Ihnen eben gebracht
habe, weil das Beispiel nicht notwendigerweise eine Zeilenvertauschung
beinhaltet hat.
Jetzt haben wir mal ein anderes Beispiel, wo links oben eine Null
steht.
Das haben Sie auch schon in der Linie an Algebra gelernt, wenn Sie
jetzt eliminieren wollen, funktioniert das nicht, weil Sie können ein
Vielfaches der ersten Zeile so oft nach unten addieren, wie Sie
wollen.
Mit der Null klappt das nicht, das ist Ihnen klar.
Das heißt, ich muss irgendwie tauschen, Zeilentausch vornehmen und
jetzt gibt es da zwei Möglichkeiten, hier in dem Fall.
Und das ist schon diese Nichteindeutigkeit bezüglich der Permutation.
Wir können es auf den Standpunkt stellen, die zweite Zeile nach oben
zu tauschen.
Das werden wir heute und etwas später sogar noch mal motivieren, warum
wir das in der Regel machen sollten, im Computer zumindest.
Aber da ich kein Computer bin und Ihnen das nur vorrechnen möchte,
nehme ich lieber die letzte Zeile, weil die hat vorne eine Eins stehen
und mit der Eins kann man schön rechnen.
So, nehme ich also die letzte Zeile nach oben und ich habe Ihnen mal
in dieser Zeile vorgemacht, wie das geht.
Hier ist diese Permutationsmatrix, von der wir sprachen, die im Grunde
genommen die Einheitsmatrix ist, aber die Einheitsvektoren sind ein
bisschen durcheinander gekommen, wenn man mal so möchte.
Hier ist jetzt in der ersten Zeile der dritte Einheitsvektor.
In der zweiten der zweite, das wäre wie bei der Identität und in der
dritten ist der erste.
Was macht die Matrix?
Sie holt uns also die dritte Zeile in die erste.
Das sehen Sie hier.
Wenn Sie mal die 001 modifizieren mit der Matrix, kommt die Zeile 115
nach oben.
Das ist die Idee, die zweite Zeile bleibt an ihrer Stelle und dadurch,
dass wir hier eine Eins stehen haben, kommt die erste Zeile der Matrix
A in die letzte Zeile.
Also so laufen diese Permutationen ab.
Vielleicht an der Stelle mal den Hinweis, sowohl die
Permutationsmatrizen werden in keiner Form irgendwann im Computer mal
so abgespeichert.
Sie können sich vorstellen, dass das völlig ineffizient ist, wenn wir
lauter Nullen und Einsen aufblasen und in der Matrix irgendwie
abspeichern.
Sie werden nachher sehen, wie wir das wesentlich speichereffizienter
abspeichern können und organisieren können.
Und genau so denken diese Eliminationsmatrizen LK.
Das sind nur Sachen, die wir hier auf dem Papier machen.
In einer Realisierung im Computer würden wir auch nicht diese Matrizen
wirklich als Speichermedium oder als Speichertyp irgendwie verwenden.
Das ist einfach viel zu aufwendig.
Es stehen fast nur Nullen und Einsen drin und an einer Stelle stehen
ein paar Werte und zwar in der Kartenspalte stehen ein paar Werte und
gleich Null.
Die müssen wir irgendwie anders organisieren abzuspeichern.
Ich will Ihnen nur erklären, was die Linearalgebra dahinter ist.
Jetzt haben wir also die erste und die dritte Zeile getauscht.
Das Ergebnis steht jetzt hier und jetzt können wir wieder schön
eliminieren.
Jetzt könnten wir durch diese Eliminationsmatrix, die hier steht, das
Minuszweifache der ersten Zeile auf die zweite Zeile addieren und
erreichen hier eine Null.
Zufällig erreichen wir hier auch eine Null.
Das ist mehr Zufall, aber okay.
Warum habe ich das wohl genauso gewählt, das Beispiel?
Können Sie sich vorstellen?
Damit ich noch mal permutieren muss.
Ich habe jetzt hier eliminiert x1 und ich muss noch mal permutieren,
weil hier eine Null steht.
Und sehen Sie, das erreiche ich durch eine Permutationsmatrix, die in
der ersten Zeile bitteschön alles unberührt lässt, aber die zweite und
die dritte tauscht.
Und dann sehen Sie, aha, hier brauche ich ja gar nicht mehr weiter
eliminieren.
An der Stelle das ist jetzt schon mein R und schon habe ich es
gefunden.
Fassen wir mal die Dinge zusammen.
Was habe ich alles gemacht, um an das R ranzukommen?
Ich habe das A erst mit p1 multipliziert, um zu permutieren, damit ich
dann mit L1 eliminieren kann.
Dann konnte ich nicht mehr weitermachen und habe mit p2 noch mal
permutiert.
Jetzt könnte ich eliminieren, das war gar nicht mehr nötig, weil das
Ding jetzt schon eine obere 3x-Matrix ist, das Ergebnis.
Also das ist das, was ich gemacht habe, algebraisch.
Das waren die Matrizen p1, L1 und p2.
Die habe ich noch mal hier hingeschrieben.
So und jetzt ist die Idee und das steckt schon viel drin.
Das kann man vielleicht sogar mal markieren.
Ja, das ist schön.
Dann sieht man vielleicht auf der Aufnahme besser, worüber wir
sprechen.
Gucken Sie sich die Zeile jetzt mal an.
Was haben wir gemacht?
Wir haben das p2 auf die andere Seite gebracht durch Invertierung.
Indem ich von links mit p2 multipliziert habe, also mit p2 hoch minus
1 für den Moment mal streng genommen.
Dann fliegt das p2 weg auf der linken Seite und taucht auf der rechten
Seite als Inverse auf.
Dann habe ich mit L1 hoch minus 1 durch multipliziert und dann
erstaunlicherweise mit p2, weil ich will alle Permutationsmatrizen auf
der Seite von A sammeln, weil ich ja p mal a ist gleich L mal R
erzielen möchte.
So, jetzt gucken wir uns mal die rechte Seite an.
Also links ist das wunderbar.
Links, wenn ich jetzt diese Produkt p2 mal p1 als p definiere, dann
steht da p mal a.
Das ist schon mal schön.
Das ist das Ziel.
Auf der rechten Seite steht jetzt ziemlich viel.
p2 mal L1 hoch minus 1 mal p2 hoch minus 1.
Und jetzt behaupte ich, ich kann dieses Produkt als L definieren und
das wäre eine untere Dreiecksmatrix.
Und er ist ja offensichtlich eine obere Dreiecksmatrix.
Daran ändert sich sicher nichts.
Aber diese Aussage, dass das wirklich eine untere Dreiecksmatrix ist,
dieses Produkt, das müssen wir jetzt ein bisschen zusammen
diskutieren.
Erste Frage, wenn sie eine Permutationsmatrix hernehmen und zwei
Zeilen tauschen, was ist die Inverse dazu?
Nicht so schwer.
Nur Mut auch nachdenken und könnten sogar auf das Ergebnis kommen.
Ja,
die Matrix selbst, die gleiche Permutationsmatrix, wenn ich die Zeilen
nur wieder tausche, bin ich wieder da, wo ich vorher war.
Ich kann den Prozess leicht umkehren.
So, das heißt die P2, die Inverse von P2 ist P2 selbst.
Das wäre jetzt schön, wenn ich das hier hinschreiben könnte.
Müssen Sie dann irgendwie vornehmen auf Ihrem Blatt oder Ihrem PC
später.
Also P2 hoch minus 1 ist P2.
Ganz einfach.
Wir merken uns also, wir haben eine Permutationsmatrix, die von links
an das L1 hoch minus 1 drankommt und die gleiche kommt von rechts
dran.
Jetzt haben wir heute schon geklärt, was es heißt, dass ich eine
Permutationsmatrix von links an eine Matrix dran multipliziere.
Jetzt müssen wir uns Gedanken darüber machen, was es heißt, eine
Permutationsmatrix von rechts an eine Matrix dran zu multiplizieren.
Haben Sie eine Idee?
Das von rechts dran multiplizieren ist doch relativ geläufig.
Immer Matrix mal Spalte gibt Spalte.
Und stellen Sie sich mal vor, Sie haben eine Matrix und multiplizieren
das jetzt mit dem stehenden Karten-Einheitsvektor.
Was kommt denn dann raus?
Ja, die Karte Spalte von A.
Und wenn ich jetzt eine Permutationsmatrix von rechts auf eine Matrix
drauf multipliziere, was wird wohl passieren?
Ja, Sie vertauschen die Spalten.
Sie sagten zwei Spalten, hier in dem Fall zwei Spalten.
Sie haben völlig recht.
Ganz allgemein, wenn Sie eine beliebige Permutationsmatrix drauf
multiplizieren, würden eben entsprechend viele Spalten vertauscht.
Aber es ist nur ein Durchmischen der Spalten.
Einmal der Zeilen von links, einmal von Spalten von rechts.
Sie haben völlig recht.
In dem konkreten Fall werden nur zwei Zeilen getauscht, weil ich ja
von links drauf multipliziere das P2.
Und von rechts werden die entsprechenden Spalten getauscht, die mit
dem gleichen Index.
Wenn Sie vorher die I-Te und J-Te Zeile getauscht haben, wenn Sie von
links P2 drauf multiplizieren, wird jetzt genau die I-Te und J-Te
Spalte vertauscht.
Okay, jetzt müssen wir ein bisschen nachdenken.
Gehen wir mal zurück zu diesen Matrixen.
Kleinen Moment... Gucken Sie sich mal dieses LK links oder meinetwegen
diese Inverse rechts mal an.
Jetzt überlegen wir mal zusammen, wenn ich von links eine
Permutationsmatrix drauf multipliziere, die nur zwei Zeilen tauscht
und das gleiche von rechts mache, so dass die beiden entsprechenden
Spalten getauscht wird.
Wie sieht das Endprodukt aus?
Das ist die Frage.
Und eine zusätzliche Information.
Im Prozess werden nur Spalten beziehungsweise Zeilen getauscht, die
vom Index her streng größer sind als das K.
Sehen Sie, wenn Sie eliminieren und haben die ersten K-Variablen
eliminiert und wollen weitermachen und können nicht, weil irgendwo mal
eine Null steht und müssen jetzt tauschen, dann betrifft das nur
Zeilen, die ein Index haben, die größer sind als K.
Sie tauschen ja nur noch im unteren Bereich dieser Matrix.
Können Sie das nachvollziehen?
Es werden nur noch Zeilen von weiter unten getauscht.
Das ist eine wichtige Information.
Okay, ich fange nochmal zusammen.
Denken Sie sich bitte dieses LK hoch minus eins im Kopf vor.
Jetzt kommt von rechts eine Matrix drauf, die zwei Zeilen tauscht,
aber bitte schön nur noch zwei Zeilen mit dem Index streng größer als
K.
Was passiert?
Machen wir erst mal das.
Können Sie sich das im Kopf vorstellen?
Das ist ein bisschen Gedankenarbeit.
Zwei Zeilen tauschen bei der Matrix, wobei die Zeilen-Indizes beide
streng größer sind als K.
Was passiert?
Nicht so schwer.
Ich meine, in dieser Kartenspalte werden die Einträge getauscht.
In der Kartenspalte stehen die Einträge LK minus 1, K bis LN, K.
Und die beiden Einträge, die in den entsprechenden Zeilen stehen, die
getauscht werden, werden getauscht.
Dummerweise werden auch dann die Einsen, die schön auf der
Hauptdiagonalen standen, dann getauscht und liegen nicht mehr auf der
Hauptdiagonale nach diesem Tausch.
Können Sie sich das vorstellen?
Die Einsen stehen schön auf der Hauptdiagonale, jetzt tausche ich die,
zack, liegen die außerhalb der Hauptdiagonale.
So, aber jetzt kommt die Permutation von rechts dran.
Was macht die jetzt?
Ja,
ganz genau.
Die Einsen, die verrutscht waren, die sind so verrutscht, jetzt kommt
von rechts die Matrix, die die Spalten wieder permutiert.
Das heißt, die Einsen werden wieder genau auf die Hauptdiagonale
zurück abgebildet.
Aber den Tausch, den ich vorgenommen habe, in den Einträgen L, der
wird dadurch nicht wieder rückgängig gemacht.
Das heißt, wenn Sie so eine Matrix hernehmen und die von links und
rechts mit so einer Permutationsmatrix multiplizieren, hat die
Ergebnismatrix die komplett gleiche Struktur, nur die Einträge, die
wichtigen Einträge an dieser Kartenspalte, da sind zwei Stück
vertauscht worden.
Das ist eine wichtige Beobachtung, die wir noch mal aufgreifen werden.
Das heißt, für uns, das war sehr allgemein gerade motiviert, in
unserem Beispiel heißt das, hier noch immer bei der markierten Zeile,
da steht P2 mal L1 auf minus 1 mal P2 hoch minus 1.
Das P2 hoch minus 1 haben wir schon geklärt, da können Sie das hoch
minus 1 gedrohst weglassen, weil es ja P2 ist.
Und dieses L1 hoch minus 1 wird jetzt von links und rechts mit P2
multipliziert.
Die Ergebnismatrix hat die komplett gleiche Struktur, nur zwei Dinge
werden getauscht.
Das sehen Sie ganz schön hier.
Hier steht minus 2, wie Sie sehen, hier steht 0.
Wie kam die Inversematrix zustande?
Einfach nur das Minuszeichen drehen.
Das heißt, die Inverse davon hat hier eine 2 und hier eine 0 stehen
und jetzt gucken Sie sich mal das L an.
Das ist nicht 2 und 0, sondern 0 und 2.
Okay, die Einträge sind einfach getauscht.
Das ist nicht ganz unwichtig, auch wenn wir das realisieren im
Computer.
Wir müssen wissen, wie wir damit umgehen, wenn wir in unserem Prozess
permutieren müssen.
Wenn Sie in Ihrem Prozess permutieren müssen, etwas später, weiter
unten, müssen Sie bei dem, was Sie schon berechnet haben, bei den
Einträgen L bitte schon immer wieder noch mit permutieren.
Das wollte ich hier an der Stelle motivieren.
Okay, gut.
Praktische Durchführung, das ist wichtig für Sie, für eine Übung,
Klausur oder was auch immer.
Das ist die praktische Durchführung, die erst mal nur auf dem Papier
ist, weil es eine 3x3-Matrix ist.
Wie können wir das machen?
Schauen Sie her, wir haben hier die minus 3, multiplizieren Sie auf
die erste Zeile, um hier an der Stelle eine 0 zu generieren, zu
eliminieren.
Das Schöne ist, die 0, ich weiß, dass da eine 0 erzeugt wird, weil ich
eliminiere, die brauche ich nicht abspeichern im Computer, die 0.
Stattdessen nehme ich den Faktor, den ich dafür benutzt habe, in dem
Fall ist es auch die 3, weil in der ersten Zeile eine 1 stand, ist ein
bisschen unglücklich.
Gehe da gleich noch mal ganz kurz darauf ein.
Also die minus 3 ist der Faktor, ich nehme das minus weg, das ist im
Kopf das invertierende Matrix, jetzt ist der Faktor 3 und ich schreibe
ihn, jetzt ist er deswegen rot hier markiert, ich schreibe ihn an die
Stelle, von der ich weiß, dass jetzt eine 0 steht und speichere ihn da
ab.
Das ist speichereffizient.
Ich brauche nicht irgendwie noch einen zusätzlichen Container
aufmachen, wo ich die Dinge reinschiebe, sondern ich habe ja die
Matrix A sowieso gespeichert im Computer und die Matrix A wird jetzt
manipuliert, dass da eine 0 steht, durch den Faktor hier, diesen
Faktor 3 und dann schiebe ich den dahin.
Bitte passen Sie auf, ganz wichtig, die 3, die jetzt hier steht, hat
erst mal nichts mit der 3 zu tun, die hier steht.
Das ist nur zufällig so, das Beispiel sollte vielleicht mal abgeändert
werden, weil oben eine 1 steht.
Was wäre denn passiert, wenn oben eine 2 stünde?
Wenn hier eine 2 stünde, hier, das kann man ja schön markieren, zack.
Was würde dann passieren, wenn da eine 2 wäre?
Ja, irgendjemand anders noch?
Ja, Sie.
Ganz genau, dann würden wir 3 halbe hier reinschreiben, hier 3 halbe
reinschreiben.
Wunderbar, schön.
Wie kommt das immer zustande, diese Faktoren, die in das L reinkommen?
3 halbe ist völlig richtig.
Wie setzt sich der zusammen, dieser Faktor?
Wie setzt sich das 3 halbe zusammen?
Die 3 ist der Eintrag, den ich eliminieren will und die 2 ist der
Eintrag, den ich dazu benutze.
Die 2 ist dann entsprechend der Eintrag in der ersten Seile, an der
ersten Stelle.
Das sind immer Quotienten, aber ich habe mein Beispiel so einfach
gewählt, dass ich nicht so viel mit Quotienten rechnen muss, deswegen
ist der Nenner immer 1.
Das ist vielleicht ein bisschen unglücklich, aber ich glaube, Sie
haben das sowieso im Kopf von der linearen Algebra, dass das passieren
kann.
So, jetzt nehmen wir das Minus 2-fache der ersten Seile.
Sehen Sie hier die 2.
Sehen Sie hier.
Wird hier reingeschrieben wieder und jetzt wird es vielleicht ganz
schön.
Jetzt will ich eliminieren und zwar hier mit dieser Seile will ich die
letzte, also hier will ich eine 0 generieren und jetzt kommt ein Bruch
endlich zustande.
Minus 1 halb.
Also der Zahl, die ich mir merke, ist 1 halb.
Wegen dem Invertieren.
Wie kommt die zustande, die 1 halb?
Nochmal ganz wichtig an der Stelle, wie kommt die eigentlich zustande?
Ja,
genau.
Sie haben so argumentiert, Sie sagen, ich möchte bei der Minus 6 eine
0 generieren.
Mit was muss ich die Minus 12 multiplizieren, um sozusagen die 6
wegzukriegen und da sagen Sie mit Minus 1 halb.
Ich hätte es jetzt noch anders ausgedrückt.
Es ist immer das, was ich eliminieren möchte, die 6, geteilt durch den
Faktor, den ich benutze.
6 zwölftel.
Das ist natürlich genau das, was Sie gesagt haben, aber der Computer
kann nicht sich überlegen, mit was muss ich 12 multiplizieren, damit
ich das Umgekehrte von Minus 6 bekomme.
So geht es nicht.
Es ist ja ganz einfach.
Sie müssen einfach die 6 durch den Faktor teilen, mit dem Sie
eliminieren wollen.
Dann geht es.
Gut, okay, dann haben wir uns alle die Dinge gemerkt.
Hier steht die 3, hier steht die 2, hier die 1, wunderbar.
Sie können also hier aus dieser Matrix, schauen Sie, das ist das, was
wir im Computer gespeichert haben, können Sie sowohl das L rauslesen,
als auch das R.
Das R steht 1 zu 1 da und das L, das müssen Sie sich zusammen basteln,
weil bei L haben wir diese Einträge, die auf der Hauptdiagonale stehen
und lauter Einsen sind, die haben wir natürlich nicht abgespeichert.
Aber wenn Sie Lust haben und es wieder hinschreiben wollen als L und
R, dann müssen Sie hier auf der Hauptdiagonale wieder Einsen
hinschreiben.
Das ist wichtig.
Gut, gucken wir uns ein anderes Beispiel an.
Diesmal ist es eins, wo wir permutieren müssen.
Und jetzt sehen Sie, möchte ich Ihnen beibringen, wie man die
Permutationsmatrix gut kodieren kann.
Sie schreiben sich vorne oder hinten, wo Sie wollen, ein Vektor hin
mit den Zahlen 1 bis n, also in dem Fall 1 bis 3.
Und in diesem Vektor wollen Sie die Permutation kodieren.
Jetzt gucken Sie her, hier steht eine Null an der Stelle.
Okay, das ist ungünstig, damit kann ich nicht eliminieren.
Das heißt, ich tausche jetzt zum Beispiel hier die erste und die
dritte Zeile.
Was mache ich gleichzeitig in meinem Permutationsvektor, den ich vorne
habe?
Ich nehme die 3 in die erste Zeile und die 1 in die letzte Zeile.
Ich permutiere da einfach mit.
Dann eliminiere ich, wie ich das vorher gemacht habe, hier ein Minus
zweifaches der ersten Zeile kommt hier auf die zweite Zeile.
Dann kriege ich da eine Null.
Jetzt steht hier unten schon eine Null, da brauche ich gar nicht
eliminieren.
Brauche ich nichts zu tun, mache ich nichts.
Ich meine rein formal, nehmen Sie das Nullfache der ersten Zeile und
addieren es nach unten.
Das ist formale Geschichte.
Deswegen sind die Einträge in dem L sind jetzt 2 und 0.
Sehen Sie hier, 2 und 0.
Das sind die Faktoren, die Sie gebraucht haben, um X1 komplett zu
eliminieren.
Und Sie haben einmal permutiert.
Jetzt aufgepasst, jetzt steht hier eine Null an der Stelle hier.
Ich kann nicht eliminieren, dann permutiere ich wieder.
Und jetzt die Geschichte von eben.
Sehen Sie, die 2, 0 wird jetzt 0, 2 hier oben.
Das müssen Sie einfach mit berücksichtigen.
Alles, was Sie schon gemacht haben, müssen Sie dann auch mittauschen.
Das ist ganz einfach, weil Sie müssen ja sowieso die Einträge in den
Restmatrix A tauschen.
Und wenn Sie das L auch speichern in dem gleichen Array, brauchen Sie
im Grunde genommen keine Gedanken zu machen.
Sie tauschen die kompletten Zeilen.
Wobei die hintere Teil ist Teil von der Restmatrix A und der vordere
Teil sind die Einträge von L, die Sie schon abgespeichert haben.
Aber Sie müssen trotzdem beides tauschen.
Das ist das, was ich versuche, Ihnen heute auch mitzugeben, warum das
passiert.
Ich meine, man kann das schematisch auswendig lernen, dass man das so
macht.
Ich hatte gehofft, ein gewisses Gefühl dafür zu geben, warum das nötig
ist und das werden wir heute auch noch einmal aufgreifen.
Gut, wie komme ich jetzt zu der Permutationsmatrix hier, die untere
hier, diese P-Matrix, wenn ich die Permutation in diesem Vektor
kodiert habe?
Der Vektor hieß vorher 1, 2, 3.
Dann hieß er 3, 2, 1, weil ich die letzte und die erste Zeile
permutiert habe.
Jetzt im letzten Schritt habe ich noch die vorletzte und letzte
permutiert.
Das heißt, am Ende lautet dieser Vektor 3, 1, 2.
Haben Sie eine Idee, wie ich aus der 3, 1, 2 herauslesen kann, wie
meine Permutationsmatrix auf dem Papier aussieht?
Ich brauche das ja, weil ich nachher das PB ausrechnen möchte, dieses
B irgendwie permutieren muss.
Wie geht das?
Sehr schön, in jeder Zeile steht, in welcher Spalte die 1 steht, das
ist richtig.
Oben fangen wir mit der 3 an.
Oben steht eine 3.
Das heißt, ich weiß, in dieser Matrix steht in der ersten Zeile, weil
die 3 in der ersten Zeile steht, an der dritten Spalte eine 1.
Genauso ist es, und so weiter und so fort.
Das heißt, das ist eine gute Art, die Permutation abzuspeichern.
Wir haben halt nur einen Aufwand von n und nicht n².
Gut, aber auch, dass ich das L und R und P unten so hinschreibe, das
machen wir in den Übungen vielleicht, und wenn Sie programmieren, dass
Sie mal sehen, wie das aussieht, aber im Computer würde das natürlich
nie wirklich so benutzt.
Das L und R stünde in einer kompakten Matrix und das P wäre ein Vektor
und kodiert in dem Vektor.
Und so würden Sie dann damit weiterarbeiten.
So, jetzt eine Frage.
Warum haben wir eben permutiert?
Wir kamen an das Problem, dass da eine Null stand und ich mit einer
Null nicht eliminieren kann.
Das heißt, ich musste die Null wegtauschen.
Jetzt sage ich Ihnen hier, möchte Ihnen die sogenannte Spalten-Pivot
-Wahl nahe bringen, die auch permutiert, wenn es rein theoretisch
möglich wäre, zu eliminieren mit dem Faktor, der oben steht.
Also, selbst wenn oben an der Stelle, wo ich gerade bin, eine Nicht
-Null steht und ich mir dieser Nicht-Null nach unten hin eliminieren
könnte, trotzdem kann es sinnvoll sein, Zeilen zu tauschen, um ein
besseres Pivot, sagen wir, dieser Element, mit dem wir eliminieren,
heißt Pivot.
Unter Umständen können wir ein besseres Pivot bekommen.
Und hier wird ein Vorschlag gemacht, welches wir nehmen sollten.
Okay, wenn wir im Kartenschritt sind und wollen eliminieren, hier oben
dieser Index k-1, in dem a oben, soll heißen, ich habe das a jetzt
schon k-1 manipuliert.
Und das Ergebnis, was daraus kommt, heißt a oben k-1.
Jetzt gehen Sie in die Spalte und nehmen nicht das a, k, k-Element
unbedingt zum eliminieren, sondern Sie gehen die Spalte herunter und
gucken, wo steht das betragsmäßig größte Element.
Das ist das, was hier in der Zeile steht.
Sie gehen hier an der Stelle, da auf der rechten Seite, sehen Sie, der
Index läuft, der Index j soll das sein?
Oder ist es besser, der Index i oder was?
Genau, der Index, der Laufindex ist i.
Ich laufe von von der Kartenstelle die komplette Spalte runter bis zur
Endenstelle, gucke mir die alle an, bilde von allen den Betrag, das
sind endlich viele, und irgendeins davon, und jetzt habe ich hier
gesagt, das j ist das betragsmäßig größte, ohne j zu spezifizieren.
Das i läuft von der Stelle, wo ich bin, die komplette Spalte runter,
ich gucke, wo ist das betragsmäßig größte, das j ist es.
So, und was mache ich jetzt?
Deswegen, ich musste dem einen Namen geben, weil Sie jetzt in der
nächsten Zeile lesen, tausche dann j mit k-Zeile.
Wenn ich weiß, das betragsmäßig größte Element steht in der j-Zeile,
dann will ich bitteschön die Zeile nehmen, nach oben tauschen.
Das ist die sogenannte Spaltenpivotwahl, das führt auf eine bessere
Stabilität, das werden wir uns im gewissen Maße später noch mal
anschauen.
Hier steht, diese Spaltenpivotwahl führt auf Betrag lij kleiner gleich
1.
Die lij, das sind diese Einträge, die in diesen Eliminationsmatrizen
drin standen.
Wenn ich immer so tausche, immer so mein Pivot wähle, warum ist die
Konsequenz, dass lij von Betrag her immer kleiner gleich 1 ist?
Ja, Sie meinen das genau richtig.
Ich sehe schon, wie Sie fuchteln und das ist richtig.
Sehr schön, genau, Sie haben das richtig gemeint.
Wie kamen wir denn auf diese lij?
Diese lij kamen immer als Bruch daher, das haben wir eben schon
versucht zu motivieren.
Das, was ich eliminieren will, geteilt durch Pivot.
Und wenn ich jetzt garantiere, dass das Pivot aber in der Spalte das
betragsmäßig Maximale ist, dann ist der Betrag des Nenners immer
größer als der Betrag des Zählers.
Und dadurch ist das Ding kleiner gleich 1, der Bruch.
Ich hole mir das betragsmäßig Größte immer in meine erste Zeile.
Erste ist jetzt relativ gesehen zum Kartenschritt, wo ich gerade bin.
Dann eliminiere ich, indem ich ein Vielfaches dieser Zeile auf untere
drauf addiere und das funktioniert immer nach dem Prinzip, das was ich
eliminieren will, geteilt durch Pivot.
Das sind die Faktoren, mit denen ich die Zeile multiplizieren muss.
Und wenn der Nenner größer ist vom Betrag her, das ist hier der Fall,
sind die lij alle kleiner gleich 1 und das führt zu einer besseren
Stabilität.
Eine Sache, die wir unbedingt später noch mal aufgreifen müssen und
ein bisschen diskutieren werden im gewissen Rahmen.
Das heißt, sie permutieren auch dann, wenn sie theoretisch nicht
permutieren müssten, um den Algorithmus besser zu machen.
Das war jetzt zum Ersten, habe ich Sie erinnert an die Lineareigebra
und wir haben uns 3x3 Beispiele rausgenommen, so einfache Dinge, um zu
lernen, wie das funktionieren könnte.
Im Prinzip habe ich Ihnen die Spalten-Pivot-Wahl als Strategie mit an
die Hand gegeben, die Sie eigentlich wählen sollten.
Und jetzt möchte ich das formalisieren, die ganze Geschichte.
Das heißt, auf N-Dimensionen hinschreiben.
Das wird manchmal ein bisschen hässlich.
Gucken wir in die erste Zeile, wie läuft das?
Bestimmte Zeilenvertauschung P1, sodass P1 mal A, und dem müssen wir
dummerweise wieder einen neuen Namen geben, A-Quer oben, dass das eine
Matrix ist mit der Eigenschaft, dass A1, 1-Quer-Ungleich Null ist.
Also der allererste Schritt besteht darin, Sie kommen mit Ihrer Matrix
A daher.
Unter Umständen ist das Element links oben Null, dann müssen Sie
sowieso permutieren.
Aber selbst wenn es nicht Null ist und Sie die Spalten-Pivot-Wahl-
anwenden, dann gehen Sie die Spalte komplett runter, suchen das
betragsmäßig größte Element und bringen das bitte schön an die erste
Stelle.
Unter Umständen steht es schon an der Stelle ganz oben, da brauchen
Sie nichts machen, dann denken Sie sich P1 als Identität.
Die Identität ist auch eine Permutation in dem Sinne.
Wenn wir das gemacht haben, kann ich eliminieren, das habe ich Ihnen
ja eben schon versucht zu motivieren, ich eliminiere durch solche
Matrizen hier L1, sehen Sie, die haben diese Struktur.
Die heißen unipotente untere Frobenius-Matrizen.
Das ist der Name dafür.
Unipotent, weil Einsen auf der Hauptdiagonalen stehen, ist nur eine
Vokabel, ist nicht so ganz wichtig.
Aber die sehen so aus, das sind die Koeffizienten, die ich brauche,
diese L, I, J und die kommen zustande, wir haben eben darüber
gesprochen, immer als Quotient.
Sehen Sie, das, was ich eliminieren möchte, das ist jetzt die
Kartezeile, durch das, was ich benutze zum Eliminieren, das Pivot.
Das sind also immer so Quotienten und hier sehen Sie es nochmal schön,
wenn Sie Spalten-Pivot-Wahl angewendet haben, ist der Betrag von dem
unteren größer als der Betrag von dem oberen und deswegen kleiner
gleich 1.
Und die schreiben Sie, also in der Realisierung, im Computer schreiben
Sie dann hier an die Stelle, hier in die erste Spalte, aber jetzt um
aufzuräumen im Kopf und für die Theorie, schreiben wir die also in das
L1 herein.
Und bitte beachten Sie hier mit negativen Vorzeichen, weil es noch auf
der linken Seite steht.
Wir haben es noch nicht invertiert.
Okay, gut, das wäre der erste Eliminationsschritt, formal
aufgeschrieben.
Ich muss eventuell tauschen oder ich will tauschen, wenn ich Spalten
-Pivot -Wahl mache und dann eliminiere ich.
Das geht so, indem ich A erst mit P1 multipliziere und dann mit L1.
Fertig, jetzt der erste Schritt abgeschlossen.
Gucken Sie sich mal an, wenn der erste Schritt abgeschlossen ist, dem
Ergebnis gebe ich dann wieder neuen Namen, das nenne ich A oben 1.
Gucken Sie sich das Ergebnis mal an.
Was passiert dann?
Ich will jetzt eine Sicht der Dinge noch mal herausskizzeln, die es
sich lohnt, auch einmal angesprochen zu sein.
Wenn ich den ersten Eliminationsschritt durchgeführt habe und jetzt A
oben 1 habe, dann mache ich das Gleiche mit der Teilmatrix, sagten
Sie, die entsteht ohne die erste Zeile und ohne erste Spalte.
Die würde ich noch mit dazunehmen.
Haben Sie das auch gesagt?
Ja, wunderbar, super.
Dann habe ich das Problem reduziert um eine Dimension und mache das
Gleiche wieder.
Das ist also sozusagen eine iterative Geschichte, wie ich vorgehen
kann, um das zu lösen.
Im Prinzip sind wir damit also fertig.
Vom Programmiertechnischen her ist es ganz einfach.
Sie machen irgendeine Schleife, Sie müssen nur einmal kapieren, wie
Sie es realisieren im Fall n und dann zurückführen auf den Fall n-1.
Das lässt sich relativ schnell in den Code gießen und programmieren.
So, jetzt fehlt auch wieder ein bisschen was vom Gleichheitszeichen.
Der obere Teil zumindest.
Also wenn mir irgendjemand, Sie sind ja vielleicht fachkundig in der
Informatik, erklären kann, woran sowas liegt.
Ich wäre sehr offen, da was zuzulernen, damit ich in Zukunft
vielleicht solche Fehler vermeiden kann.
Warum passiert es, dass das nicht ordentlich angezeigt wird?
Das wird nicht auf meinem Bildschirm hier angezeigt.
Gut, wenn jemand eine Idee hat, kommen Sie nachher mal kurz auf mich
zu.
Das wäre ganz nett.
Vielleicht liegt es auch jetzt hier nur an der Software.
Diesmal ist es kein Windows-Gerät.
Versuchen Sie mal, die Folie zu erfassen.
Was haben wir gemacht?
Wir haben A hergenommen, mit P1 multipliziert und mit L1.
Das war das Eliminieren der ersten Variablen aus unteren Gleichungen.
Jetzt haben wir gesagt, machen wir das gleiche wieder mit der
Restmatrix.
Wir bleiben aber in der Dimension n.
Das heißt, mein P2, die nächste Permutation, die ich drauf
multipliziere, ist schon eine n-Kreuz-n-Matrix, aber die hat in jedem
Fall den ersten Einheitsvektor als Seile, weil das, was ich schon
erreicht habe, will ich nicht zerstören.
Ich permutiere nur noch weiter unten.
Das heißt, ab jetzt wird P2 drauf multipliziert, dann das
entsprechende L2, dann habe ich X2 eliminiert und so weiter und so
fort.
Hier haben wir jetzt also, ganz zum Schluss sehen Sie hier schon PK
und LK.
Ich habe jetzt also schon PK drauf multipliziert, wieder permutiert
und mit LK eliminiert.
Das heißt, ich habe die ersten K-Variablen eliminiert.
Sehen Sie, hier stehen ja Nullen.
Also in dieser Matrix, machen wir ruhig noch mal komplett, in dieser
Matrix sehen Sie hier in der Kartenspalte auch schon Nullen.
So, das heißt, bis hierhin sind wir gekommen.
Okay, und jetzt machen wir weiter mit dem Rest da unten, in gleicher
Art und Weise.
Ich gucke wieder in diese Matrix herein, in diese Matrix.
Ich weiß ja nicht, ob das Element, was hier steht, hier an der Stelle,
ich weiß noch nicht, ob das ungleich Null... Entschuldigung, dass das
Element, was hier steht, von dem weiß ich noch nicht, ob es ungleich
Null ist, beziehungsweise wenn ich die Strategie der Pivot-Wahl
anwende, weiß ich nicht, ob es betragsmäßig das Größte ist, was in der
Restspalte steht.
Unter Umständen muss ich also hier wieder permutieren.
In jedem Fall muss dann das Element des Ergebnisses, hier das hier,
muss ungleich Null sein, in jedem Fall.
Und dann mache ich weiter.
Und zwar, ich eliminiere wieder mit einer Matrix.
Hier steht wieder ein Gleich dazwischen.
Und diese Einträge in dem L kommen wieder als diese Quotienten
zustande.
Sieht ziemlich wild aus.
Das ist ein Formalismus für eine Idee, die eigentlich nicht ganz so
schwer ist.
Gehen Sie mit mir den Schritt, dass wir die allerletzte Zeile hier als
wahr annehmen.
Die allerletzte Zeile.
Haben Sie das Gefühl, ja, der Herr Weiß hat uns nichts gelogen,
sondern auch nichts vorgemacht.
Ich permutiere, eliminiere, permutiere, eliminiere, solange, indem ich
mit solchen gewissen Matrizen von links auf das A drauf modifiziere,
bis R rauskommt.
Das ist die Idee.
Was ist jetzt das Problem, wenn ich eigentlich zeigen will, dass es
eine Zerlegung von PA gibt, also von der Form PA ist gleich LR.
Das war ja eigentlich das Ziel.
Oder vielmehr, das ist das, was ich erreichen kann.
Was stört Sie jetzt hier eigentlich noch an diesem Ausdruck?
R ist gleich Eliminationsmatrix, Permutationsmatrix,
Eliminationsmatrix, Permutationsmatrix.
Das geht immer so hin und her.
Und zum Schluss steht A da.
Was stört noch ein bisschen?
Das Ziel ist eigentlich, P mal A ist gleich L mal R.
Irgend so was wollen wir eigentlich bekommen.
Haben Sie eine Idee?
Sehr schön.
Sie haben einen schönen Aspekt genannt.
Die Idee wäre natürlich, alle Ls irgendwie zusammenzufassen, alle Ps
irgendwie zusammenzufassen und das zu sortieren.
Sie geben schon eine Warnung mit uns auf den Weg.
Sie sagen, die Matrizmultiplikation ist nicht kommutativ.
Das ist völlig richtig.
Wir dürfen nicht einfach die Reihenfolge vertauschen.
Dann wäre das ja wunderbar.
Dann könnten wir alles sortieren und trennen und so weiter.
Das geht aber nicht.
Wir müssen aufpassen.
Wir können das nicht einfach sortieren.
Ich möchte Ihnen das kurz skizzieren, was wir machen können, um das zu
trennen.
Das ist auch ein bisschen hartes Brot.
Und die Idee ist, das zu tun in dem Beweis dieses Satzes.
Formulieren wir den noch mal ganz kurz.
Also A ist imitierbar, genau wie wir es haben.
Dann existiert eine nicht eindeutige Permutationsmatrix.
Das haben wir schon kennengelernt.
P selber muss nicht eindeutig sein.
Selbst bei der Spalten-Pi-Wohlwahl ist es nicht eindeutig.
Gehen Sie die Spalte runter und suchen nach dem betragsmäßig größten
Element in der Spalte.
Es könnte drei Stellen geben, fünf Stellen geben, wo ein betragsmäßig
gleicher Wert steht.
Jetzt haben Sie Ihr Programm so programmiert, dass die fünfte Stelle
nach oben getauscht wird.
Ich habe mein Programm so programmiert, dass die siebte Stelle nach
oben programmiert werden.
Wir haben beide die Spalten-Pi-Wohlwahl realisiert.
Also das P selber ist nicht eindeutig.
Das werden Sie nicht schaffen.
Aber wenn dann P erstmal gewählt ist und P mal A eine LR-Zelegung hat,
und die ist auch immer möglich, es existiert so ein P, dann ist das L
und das R eindeutig, wenn erst P mal gewählt ist.
Gut, R ist eine obere 3x-Matrix, L ist eine untere 3x-Matrix und L hat
auf der Hauptdiagonalen nur Einsen stehen.
Das ist die Behauptung.
Gucken wir uns das mal an und versuchen das mal zu beweisen.
Und zwar nur skizzenhaft, weil die Zeit auch schon ein bisschen
vorgeschritten ist und ich Ihnen noch einen anderen Aspekt heute
beibringen möchte.
So, gucken wir uns das mal an.
Wir stehen hier.
R ist gleich.
Was haben wir mit dem A gemacht?
Wir haben permutiert, eliminiert, permutiert, eliminiert und ganz zum
Schluss haben wir noch einmal unter Umständen permutiert und
eliminiert.
Warum nur bis N-1?
Naja, wenn Sie dann nur noch den 1x1 Kästchen unten übrig haben,
brauchen Sie nichts mehr zu machen.
Deswegen geht es nur bis N-1.
So, einen ersten Schritt machen wir mal folgendes.
Wir holen alles als Inverse auf die andere Seite.
Das heißt, wir schreiben nicht alles, das P1 lassen wir mal hier
stehen.
P1 mal A.
Was kommt dann rüber auf die andere Seite?
Nehmen das R hier hin.
Was muss ich als erstes auf die andere Seite bringen?
Ln-1.
Durch Multiplikation der Inversen bringe ich das auf die andere Seite.
Dann steht hier Ln-1 hoch minus 1.
Das ist dieser Faktor.
Jetzt bringe ich das Pn-1 auf die andere Seite.
Wir hatten schon gesagt, das Inverse einer Permutationsmatrix, die
zwei Zeilen tauscht, ist die Matrix selber.
Dann haben wir hier Ln-2 hoch minus 1 und so weiter und so fort.
Was haben wir hier noch?
Wir haben dann P2 und L1 hoch minus 1.
Kann das stimmen?
Sie müssen mal mitdenken.
Hier sind lauter Produkte.
Ich denke, so funktioniert es.
Wir haben alles mögliche auf die andere Seite gebracht.
Was wir jetzt machen ist, jetzt multiplizieren wir alle auftretenden
Permutationsmatrixen in richtiger Reihenfolge wieder auf die Gleichung
drauf.
In dieser Form.
Pn-1 mal Pn-2 mal P1 mal A.
Sehen Sie, P1 mal A stand schon da, links.
Und alle anderen kommen drauf.
Jetzt müssen wir das natürlich auf der rechten Seite mit
berücksichtigen.
Okay, dann steht hier Pn-1 mal Pn-2 mal P2.
Und jetzt kommt der Ausdruck, der da oben steht.
L1 hoch minus 1, P2 und so weiter.
Ich schreibe es mal nicht mehr alles hin.
Sehen Sie, wir haben einfach die Matrizen P2, P3, P4 nacheinander von
links auf die Gleichung drauf multipliziert.
Jetzt haben wir was erreicht.
Ich sage, wenn wir das hier schon mal P nennen, Gesamt-P, dann heißt
die linke Seite schon mal P mal A.
Das ist schön.
Also dann steht hier P mal A.
Die rechte Seite ist noch ganz schön kompliziert.
Da steht ganz hinten noch immer das R.
Und vorne steht ein wilder Ausdruck.
Machen wir mal kurz so.
Ja, wild.
Okay, und was ich jetzt motivieren möchte ist, das ist L.
Das ist wirklich eine untere Dreiecksmatrix mit Einsen auf der
Hauptdiagonale.
Wie kann man das einsehen?
Okay, gucken wir uns mal diesen Teil ein bisschen genauer an.
Was stand denn da auf der rechten Seite?
Das stand P n-1 mal P n-2 runter multipliziert bis P2.
Dann trifft es auf L1 und dann auf P2.
Und was ich hier oben unterschlagen habe, der nächste Faktor wäre L2
hoch minus 1.
Das wäre von der Struktur her der nächste Faktor da oben gewesen.
Was mache ich jetzt?
Ich füge jetzt Permutationsmatrizen ein.
In einer Art und Weise, dass sie ausmultipliziert die Identität
ergeben und dass nichts Böses passiert ist.
Also ich nehme jetzt einfach P3 hier hin und so weiter bis P n-1.
Das darf ich natürlich eigentlich nicht, weil die da nicht hingehören.
Aber wir haben doch gelernt, wenn ich eine Permutationsmatrix, die
zwei Zeilen miteinander tausche, wieder mit sich selber multipliziere,
dann ist das hier die Identität.
Wie schreiben Sie Identität?
Vielleicht I?
Einheitsmatrix?
Jetzt habe ich ja auch P n-2 eingeschmuggelt.
P n-2, das steht hier an der Stelle.
Das muss ich da auch hinschreiben.
All das, was ich hier links reingeschmuggelt habe, muss ich wieder
raus multiplizieren, bevor ich endlich zu dem Faktor komme, wo ich hin
möchte, der hier.
Können Sie das nachvollziehen?
Und jetzt, das ist die Hauptidee, machen wir es nur an diesem Faktor
uns klar.
Das machen wir bei allen anderen Faktoren, die hinten auch auftauchen.
Aber jetzt schauen Sie mal sich diesen Teil hier an, von hier bis
hier.
Was sagen Sie dazu?
Sie nehmen L1 hoch minus 1, multiplizieren das mit P2 von rechts, mit
P2 von links, dann mit P3 von rechts und mit P3 von links, dann mit P4
und so weiter und so fort.
Können Sie sich erinnern, was wir eben schon mal motiviert haben?
Was passiert nur hier innen?
Was passiert nur hier?
Wie sieht diese Matrix aus?
Ganz genau.
Jetzt werden die Zeilen vertauscht und dann die entsprechenden
Spalten.
Das heißt, diese Einsatzstruktur auf der Hauptdiagonalen wird nicht
zerstört und es wird lediglich unten in dem Bereich, hier in dem Fall
in der ersten Spalte etwas getauscht.
Weiter unten.
Und dann kommt das mit P3 auch, P4 auch, P4, P5.
Also alle diese P´s bewirken kaum eine Veränderung.
Sie bewirken letztlich nur eine Permutation der Einträge in der ersten
Spalte.
Aber selber ist das wieder eine Matrix dieser Form.
Und wir geben mal Namen.
Dach 1 und meinetwegen auch R hoch minus 1 brauchen wir, glaube ich,
gar nicht.
Mit dem Pn-1.
Das ist wichtig.
Nicht mit dem zweiten.
Dreimal.
Oh, pfui.
Dankeschön.
Hier kommt natürlich ein Pn-2.
Danke.
Das würde ja alles durcheinander bringen.
Es war ärgerlich.
Dann haben Sie vielleicht den Faden an der Stelle verloren.
Also das eine Pn-1 habe ich eingeschmuggelt und durch das zweite
wollte ich es sozusagen wieder in die Luft auflösen lassen.
Ich habe davor ein Pn-2 eingeschmuggelt, was ich auch durch den Faktor
Pn -2 wieder auflösen möchte.
Danke für den Hinweis.
Also das war natürlich sehr wichtig, dass da Pn-2 steht.
Sehen Sie, und jetzt habe ich eine Permutation weniger.
Jetzt kann ich das gleiche Spielchen hier auf der rechten Seite von
dem Faktor L2 hoch minus 1 auch machen und so weiter und so fort.
Das ist die Hauptidee, dass man diese Matriz inbeweist und dass man
diese Dinger da einschmuggelt.
Und letztlich kommen Sie also nachher auf ein Produkt von L1 Dach und
L2 Dach ist analog definiert bis Ln-1 Dach.
Was sich herausstellt ist genau Ln-1, bei dem letzten Faktor kommen
keine Permutationen mehr vor.
Das sehen Sie hier, wenn Sie das bis zum Schluss machen, dann steht
hier L hoch n-1 hoch minus 1 mal R.
Und das allerletzte, dieses hier, hat keine Permutationen mehr rechts
stehen und dann auch keine mehr links.
Aber das ist die grobe Idee und das sind alles wieder solche Matrizen,
wenn Sie das ausmodifizieren, müssen Sie wieder nicht rechnen, sondern
nur die Ergebnisse in die einzelnen Spalten reinschreiben.
Gut, soviel zum Beweis für diesen Satz.
Ich hoffe, Sie haben ein Geschmäckle gekriegt, wie das funktioniert.
Wichtig für die Praxis ist einfach nur, wenn Sie das programmieren,
alle Einträge, die Sie schon berechnet haben im L, das haben wir ja
eben schon mal gesagt, müssen, wenn Sie später noch mal permutieren,
bitteschön mit permutiert werden.
Das ist alles.
Gut, also Beweis ist geschafft.
Okay, den Aufwand.
Den Aufwand machen wir mündlich, ist gar nicht so schwer.
Wir können jetzt diese Beobachtung investieren, dass wir, wenn wir
einmal eliminiert haben, dann das gleiche Prozedere auf die
Teilmatrix, auf die n-1 x n-1 Teilmatrix wieder anwenden können.
Das heißt, wenn wir uns nur klar werden darüber, welchen Aufwand wir
haben in einem einzigen Eliminationsschritt, wissen wir schon, wie der
Aufwand für die komplette Geschichte ist.
Haben Sie eine Idee?
Wie groß ist der Aufwand in Operationen gemessen?
Und Operationen waren eine Addition und eine Multiplikation.
Wie aufwendig ist es wohl, diese Nullen zu erzeugen in der ersten
Spalte?
Die Nullen zu erzeugen ist nicht sehr aufwendig.
Wenn wir richtig eliminieren, dann wissen wir ja, dass da Null
rauskommt.
Das heißt, das ist eigentlich ein Aufwand Null, aber wir müssen dabei
ja was tun.
Wir addieren Vielfaches der oberen Zeile auf untere.
Das heißt, diese Teilmatrix, die unten übrig bleibt, diese n-1 x n-1
Dimensionale, die wird natürlich in jedem Eintrag verändert.
Im schlechtesten Fall in jedem Eintrag.
Haben Sie eine Idee?
Sehr schön.
Der Aufwand ist n-1².
Warum?
Wir haben n-1 viele untere Zeilen.
Machen wir uns doch mal Gedanken nur für die allererste Zeile.
Wenn der Aufwand da n-1 wäre, wir haben n-1 viele Zeilen, dann wäre es
n -1².
Überlegen wir mal kurz, warum ist der Aufwand, um die allererste Null
zu erzeugen, warum ist dieser Aufwand n-1?
Diese Null hier, geht das zu markieren?
Ne, geht nicht, ist klar.
Aber diese Null hier will ich erzeugen.
Das sind n-1 viele restliche Elemente in der Zeile, die verändert
werden müssen, weil ein Vielfaches dieser Elemente hier drauf addiert
wird.
Ist nicht so schwer.
Sie haben einen Faktor, diesen L2-1 Faktor, das ist der erste
Eliminationsfaktor, mit dem Sie die obere Zeile multiplizieren und
dann auf die untere addieren.
Mit dem müssen Sie jedes Element multiplizieren aus der ersten Zeile,
also die n-1 restlichen, und dann nach unten addieren,
komponentenweise auf die Zeile drunter.
Das heißt, es ist exakt eine Multiplikation und eine Addition pro
Element und es gibt n-1 viele in der Zeile.
Also ist der Aufwand tatsächlich n-1 viele Operationen.
Ja?
Okay, Sie haben recht, der Aufwand berücksichtigt zusätzlich eine
Division.
Vielen Dank.
Jetzt diskutieren wir das mal ganz kurz.
Wie viele Multiplikationen und Additionen haben wir ausgerechnet?
Genau, und eine Division.
Jetzt rechnen Sie das mal auf den kompletten Eliminationsschritt.
Dann haben wir n-1² viele Operationen und n viele Divisionen.
Was sagen Sie dazu?
Auch jemand anders noch?
Sie haben es gut bemerkt, wir haben n Divisionen unter den Tisch
fallen lassen.
Warum sage ich, ist es okay?
Es ist immer noch O von n, es ist was Lineares und das andere wächst
quadratisch.
Fällt also in dem Sinne nicht ins Gewicht.
Aber danke für den Hinweis, der war gut.
Also wir haben den dominanten Teil hier diskutiert und das wäre n-1 in
Klammern zum Quadrat.
Das war ein einziger Eliminationsschritt.
Jetzt haben wir das ganze Problem reduziert auf ein n-1-Kreuz-n-1
-Matrix.
Welchen Aufwand haben wir im nächsten Schritt?
n-2², das ist eine Symmetrieüberlegung.
Wenn das erste richtig war, dann muss es jetzt hier n-2² sein und im
nächsten Schritt n-3² usw.
Das führt also auf die Summe der ersten n-1² Zahlen.
Der Gesamtaufwand führt auf die Summe der ersten n-1² Zahlen.
Können Sie das mitmachen im Kopf?
Dafür gibt es Formeln.
Sie kennen ja die Summe der ersten n-Zahlen, da gibt es der kleine
Gauss.
Dann hat man irgendwie so eine abkürzende Schreibweise.
Das haben Sie dann wahrscheinlich mit vollständiger Induktion mal
beweisen müssen in Ihrer Laufbahn.
Die Formel für die Summe der ersten n-1² Zahlen lautet...
ich schreibe es mal hier hin...
Summe über j gleich 1 bis n-1j² Wenn ich mich nicht täusche, ist das
so etwas der Form n-1.
Kleinen Moment...
Sieht gut aus.
Diese Formel sollte stimmen, aber die weiß ich morgen auch wieder
nicht mehr.
Die brauchen Sie nicht auswendig lernen.
Aber was ist entscheidend an der Formel, wenn sie denn stimmt?
Ich bin zu 95% sicher, dass sie stimmt.
Für die, die zuhören, die Formel heißt...
n-1 mal n mal 2n-1 durch 6.
Das alles durch 6.
Aber was ist jetzt das Entscheidende, wenn wir uns diese Formel
angucken, wenn wir über Aufwand reden?
Wir würden den dominanten Term davon rauskitzeln.
Das heißt, Sie würden das hier in Gedanken ausmultiplizieren.
Aber wenn wir an dem dominanten Term interessiert sind, dann ist das
offensichtlich ein kubischer Term.
Und hier haben wir 2 mal n hoch 3 und das Sechstel.
Das heißt, der eigentliche Aufwand, sagen wir, ist ein Drittel n hoch
3.
Plus Terme kleinerer Ordnung, die uns nicht interessieren.
Das ist der Hauptaufwand.
Haben Sie noch Fragen?
Vielleicht nehmen wir uns noch eine Minute oder zwei für mögliche
Fragen.
Okay, das ist nicht der Fall.
Ich hoffe, Sie haben ein bisschen verstanden, wie die LR-Zerlegung
funktioniert.
Wenn Sie möchten, programmieren Sie es bitte auch zu Hause.
Das freiwillig.
Da lernen Sie dann noch unwahrscheinlich viel dazu.
Wir haben über den Aufwand gesprochen.
Nächsten Mittwoch reiche ich noch ein bisschen was nach, was Sie für
die Übungen brauchen, was ich heute nicht mehr geschafft habe.
Aber das ist kein Beinbruch, das ist nur ein kleiner Teil.
Okay, ich wünsche Ihnen einen schönen Tag und bis nächste Woche.