Hallo, ich begrüße Sie ganz herzlich zur Vorlesung Numerische
Mathematik für die Fachrichtungen Informatik und Ingenieurwesen.
Als erstes wollte ich Ihnen die Homepage vorstellen, wo Sie
Informationen finden können zur Vorlesung und zur Übung.
Ich wollte Ihnen da ein bisschen was zeigen.
Gut, dass die Vorlesung mittwochs morgens zur ungnädigen Zeit von 8
Uhr beginnt, haben Sie schon festgestellt.
Schön, dass Sie alle hier sind.
Der Termin ist nicht ganz unproblematisch für Sie, wahrscheinlich auch
für mich.
Die Stimme ist noch ein bisschen belegt, aber ich würde Sie bitten,
Sie sind heute so zahlreich da wie wahrscheinlich im ganzen Semester
nicht mehr und möchte die Gelegenheit nutzen, Sie einzuladen, sich
jetzt zu entscheiden, die Vorlesungen zu besuchen.
Auch wenn es mittwochs morgens um 8 Uhr ist, Sie müssen nur 14 mal
früh aufstehen und einmal haben Sie schon.
Das sind nur noch 13 mal, das ist kein schlechtes Omen, das ist
machbar.
Ich denke grundsätzlich, ich werde da nicht so viel Zeit drauf
verlieren, aber ein klein bisschen werde ich was dazu sagen.
Sie sind ja nicht nur hier, um Ihr Studium zu absolvieren und auch
sich Wissen anzueignen, sondern was ich Ihnen beibringen möchte, ist
neben diesen Dingen, die natürlich auch wichtig sind, dass ich Ihnen
Fähigkeiten beibringen kann.
Das ist vielleicht viel wichtiger als der Inhalt, den ich Ihnen
vermitteln kann.
Das werden nicht so viele von Ihnen brauchen.
Das geht nur, wenn Sie hier sind.
Das gilt für die Vorlesungen wie auch für die Übungen.
Ich denke, es ist eine Gelegenheit, die zwei Semesterwochenstunden in
der Woche hier hinzukommen und ein ganz kleines bisschen geprägt zu
werden vor der Mathematik.
Nicht so viel, aber ein klein bisschen.
Und das kann nicht schaden.
Das mathematische Denken kann Ihnen als Informatiker sehr, sehr
nützlich sein.
Ich meine, abgesehen davon, dass Sie das in manchen anderen
Vorlesungen auch brauchen.
Ich selber habe schon in der Wirtschaft gearbeitet, bei der Allianz,
eine Zeit lang, bevor ich dann wieder zur Universität zurückgegangen
bin und bin dort angestellt worden, neben zwölf anderen Mathematikern
und einem Physiker, Dinge zu programmieren.
Es war kein Informatiker bei uns da.
Wir haben ein großes Programm geschrieben, es war ein großes Projekt,
aber hauptsächlich wurden Mathematiker eingestellt, um das zu
programmieren.
Und wenn es dann Schwierigkeiten gab, weil wir an unsere Grenzen kamen
mit der Programmierung, dann haben wir uns extern Informatiker
eingeladen.
Die haben für uns, dann weiß ich nicht, irgendwelche
Datenbankkommunikationen programmiert.
Die haben gut verdient, das ist keine Frage.
Ich wollte Ihnen nur sagen, hauptsächlich waren in diesem Team nur
Mathematiker.
Gut, Sie werden auch einen Arbeitsplatz finden, aber ich sage, die
Mathematik kann Ihnen sehr helfen, Dinge von einem anderen Licht zu
sehen und vielleicht anders zu durchdringen, auch in der
Programmierung vielleicht ein bisschen mehr Struktur reinzubringen in
das Programm.
Von daher lade ich Sie ganz herzlich ein, sich mal einzulassen auf die
Vorlesung.
Gut, die Übungen wird der Herr Maurer übernehmen.
Die Übungen finden statt, freitags, 9.45 Uhr.
In Klammern steht 14-tägig, aber Sie wissen, dass viele Freitage wegen
dem verlängerten Wochenende eher ungünstig sind, weil viele von Ihnen
vielleicht nicht da sind, sodass wir die Termine exakt festgelegt
haben.
Die Termine finden Sie also auch auf der Homepage.
Die erste Übung wäre erst am 9.
Mai.
Und die Übungen finden auch hier statt, in diesem Hörsaal.
Okay, nächste Woche wird das erste Übungsblatt für Sie zur Verfügung
stehen.
Wir haben uns entschieden, das Übungsblatt nur noch online zur
Verfügung zu stellen.
Das werden wir hier auf dieser Homepage tun.
Und ab nächste Woche, Mittwoch, ist es online verfügbar für Sie.
Sie haben relativ viel Zeit für das erste Übungsblatt.
Im Gegensatz zum letzten Semester, ich sehe einige bekannte Gesichter
hier, die vielleicht die Sachen nochmal sich anhören müssen, haben wir
es jetzt so, dass wir das Übungsblatt nur alle zwei Wochen
entsprechend in Übungen stellen.
Das heißt, es werden am Ende nur sieben Übungsblätter werden.
Die Übungsblätter sind etwas umfangreicher dadurch.
Wir haben in der Vergangenheit auf dem Übungsblatt zwei Aufgaben
gemacht und werden dementsprechend jetzt vier Aufgaben bringen.
Aber Sie haben etwas länger Zeit für die Aufgaben.
Ab nächsten Mittwoch haben Sie dann online das Übungsblatt zur
Verfügung.
Und müssen es dann bis zu dem Donnerstag, dem 8.
Mai, also einen Tag vor dem Freitag, dem 9.
Mai, abgegeben haben.
Und dazu besteht die Möglichkeit, im Allianzgebäude, werden wir in dem
ersten OG einen Briefkasten einrichten.
Und da steht dann der Name der Vorlesung drauf und da können Sie die
Übungen einfach einschmeißen.
Das Allianzgebäude ist beim Kronenplatz und da gehen Sie dann in die
erste Etage, die ist im Gebäudeteil C.
Aber diese Information sollten wir hier auch nochmal vielleicht
draufschreiben, steht aber insbesondere auf dem Übungsblatt.
Auf dem Übungsblatt steht ganz genau, bis wann Sie das abgegeben haben
müssen und wo Sie es abgeben können.
Also auch im Unterschied zum letzten Jahr, die Übungen werden nicht
mehr hier in der Übungsgruppe vorher abgegeben, sondern müssen bis
einen Tag vorher in diesen Briefkasten geworfen werden.
Was brauchen Sie überhaupt?
Sie brauchen diesen Übungsschein.
Sie brauchen A, ein erfolgreiches Bestehen der Klausur und den
Übungsschein.
Den Übungsschein bekommen Sie, wenn Sie 50% der Übungspunkte erreicht
haben.
Wenn Sie den Übungsschein schon erworben haben in einer der vorigen
Semester, brauchen Sie das nicht nochmal tun.
Sie können dann direkt bei der Klausur mitschreiben.
Ansonsten, oder vielleicht in jedem Fall, sollten Sie sich anmelden in
unserem Verwaltungssystem.
Da finden Sie hier einen kleinen Link.
Da melden Sie sich an mit Ihrer KIT-Adresse, um die Vorlesung ein
bisschen zu verfolgen.
Da gibt es einen E-Mail-Verteiler.
Und wenn irgendetwas Interessantes zur Vorlesung eine Frage aufkommt
und wir die Antwort geben wollen, dann würde ich diesen E-Mail
-Verteiler nutzen.
Zudem können Sie genau einsehen, wie viele Punkte Sie haben.
Für die einzelnen Übungsblätter, sogar für jede einzelne Aufgabe.
Das wird da eingetragen von den Tutoren.
Und Sie können sich an jeder Zeit einloggen und schauen, wie ist mein
Punktestand.
Also von unserer Seite her würden wir empfehlen, dass Sie sich da
anmelden.
Alles andere macht uns nur mehr Arbeit.
Wenn Sie sich nicht anmelden, müssen wir separat irgendwie Ihre Punkte
verwalten.
Und für uns wäre es... wir würden Sie dann sowieso händisch da
anlegen, ohne dass Sie Zugriff hätten dann.
Es macht uns nur viel mehr Arbeit.
Also Einladung, gehen Sie in dieses Verwaltungssystem und melden Sie
sich bitte an.
Okay, was gibt es noch zu sagen?
Die Prüfung, ja, auch unfristige Uhrzeit, 8 bis 10 Uhr, aber da haben
Sie sich ja schon dran gewöhnt dann.
Das ist am 16.09.
Also gucken Sie einfach mal auf der Homepage vorbei.
Hier wird immer irgendwas Aktuelles, also alles Aktuelle wird hier
veröffentlicht.
Haben Sie noch Fragen?
Ich gucke gleich.
So, Sie sehen, ich male hier ein bisschen rum.
Das ist der Versuch zum ersten Mal...
Ich werde die Vorlesung also nicht mehr an der Tafel halten, wie
letztes Jahr, sondern mit PDFs.
Und nebenbei versuchen Erklärungen hier mit diesem Stift an die Wand
zu beamen.
Das mache ich zum ersten Mal.
Sie müssen ein bisschen gnädig sein.
Auch die Nutzung von Windows ist mir sehr, sehr neu.
Und das mache ich jetzt erst seit anderthalb Wochen und bin da immer
noch blutiger Anfänger.
Es könnte also passieren, dass Dinge passieren, die ich nicht unter
Kontrolle habe.
So war es in der Vorlesung gestern.
Haben Sie noch Fragen zur Vorlesung, zum Ablauf?
Die Folien, ja, das ist gar kein Problem.
Die gibt es in jedem Fall online.
Und ich würde auch die Folien online stellen mit den Notizen, die ich
da noch reinschreibe.
Dann haben Sie es immer doppelt, aber es ist Ihnen überlassen.
Sie müssen es ja nicht nutzen.
Es gibt auch ein Skript zu der Vorlesung.
Das ist auf dem Stand vom letzten Jahr.
Das würde ich gerne ein bisschen überarbeiten.
Und das Problem ist, dass ich das vielleicht nicht mehr zeitnah
schaffe.
Insbesondere werde ich es nicht schaffen, im Vorfeld der Vorlesung das
fertig zu haben.
Also ich denke, eine Woche, zwei Wochen später werden Sie das Skript
zur Verfügung haben.
Und das steht dann auch online.
Vielleicht bei diesen sensiblen Daten, wie die Folien und auch das
Skript, die würde ich dann eher in dem Verwaltungssystem
veröffentlichen.
Und da können Sie es dann auch versuchen, die Vorlesung aufzunehmen.
Deswegen war eben der Herr Fischer hier.
Also alles, was ich jetzt gerade sage, wird aufgenommen, auch mit dem
Bildschirm.
Die ganze Information wird auch irgendwie veröffentlicht.
Das werde ich mir aber vorher anschauen, ob ich damit zufrieden bin
und wie das läuft.
Das ist erstmal ein Start und ein Versuch.
Und die Idee ist natürlich, alle Ihnen das zur Verfügung zu stellen,
die Mittwoch morgens nicht können.
Wir stellen es dafür, dass wenn hier am Ende nur noch 30 Leute sitzen,
dass wir das dann einstellen.
Also das würde ich dann einstellen wollen, ja.
Also es ist das eine...
...was nicht verstanden hat, um es dann nochmal zu wiederholen, als
von vornherein zu sagen, ich brauche ja gar nicht zu kommen, ich
kriege sowieso alles online.
Sie werden sich die Zeit nicht nehmen, das anzuschauen.
Das kann ich Ihnen jetzt schon versprechen.
Das ist doch klar, das ist doch immer so.
Sie sammeln alles, Material, und die Zeit, sich das anzuschauen, ist
dann nicht mehr da.
Das ist bei mir auch so.
Und deswegen nehmen Sie sich doch von Anfang an vor, hier hinzukommen.
Dann reden wir anderthalb Stunden pro Woche über Mathematik und Sie
haben schon unwahrscheinlich viel von dem verstanden, was wir
überhaupt machen wollen.
Das ist schon gut investierte Zeit.
Ja?
Weitere Fragen?
Grundsätzlich möchte ich gerne die Vorlesung so gestalten, dass man
sie eigentlich nicht aufnehmen kann.
Also alles, was man aufnehmen kann und einfach nur ins Netz stellen
kann, dann brauche ich die Vorlesung nur noch einmal zu halten und die
nächsten zehn Jahre gucken wir uns das im Netz an.
Die Idee ist natürlich, das so zu gestalten, dass ich in Ihre
Gesichter gucke, schaue, haben Sie es verstanden, nicht, werde Sie
auch fragen, versuche das so interaktiv wie möglich zu machen.
Alle die Stärken, die wir haben, dass wir wirklich hier beieinander
sind, die müssen ausgespielt werden bis zum Letzten, damit es
überhaupt Sinn macht, dass wir uns hier treffen.
Deswegen habe ich auch ein bisschen ein mulmiges Gefühl, wenn der Herr
Fischer schöne Grüße an Sie das jetzt hier aufnimmt.
Weil eigentlich sollte das nicht gehen.
Die Vorlesung, die ich halte, sollte nicht aufgenommen werden können.
Gut, umso schneller Sie die Hemmungen verlieren und auch ein bisschen
mit mir in Kontakt kommen und auch Fragen und Antwortspielchen
zulassen, wäre gut.
Und sich auch trauen, die Fragen zu stellen.
Ja, das wird dann im Internet in dem Verwaltungssystem veröffentlicht.
Aber da gibt es noch nichts.
Weil ich angefangen habe, es zu verändern und jetzt ist es eine
Baustelle.
Jetzt kommen die Osterfeiertage, meine Kinder haben Ferien und ich
finde keine Zeit.
Nach Ostern setze ich mich dann hin und mache das ordentlich und
bemühe mich, dass Sie sehr zeitnah das Skript zur Verfügung haben.
Weitere Fragen?
Okay, wenn das nicht der Fall ist, dann gehe ich mal davon aus, dass
wir an alles gedacht haben.
Und wir fangen an.
Okay, das erste große Thema, wir haben ja nur noch 14 Vorlesungen und
drei bis vier Vorlesungen werden wir uns mit linearen
Gleichungssystemen beschäftigen.
Das haben Sie schon kennengelernt in der linearen Algebra.
Das ist eigentlich nichts Neues.
Von der Struktur her ist vielleicht ganz schön sich zu merken, A x
gleich B.
Und so wie ich es aufgezeichnet habe, werden wir es auch genau
verwenden.
Das A ist eine quadratische Matrix, das wird im Grunde genommen immer
unsere Situation sein.
Wir werden sogar noch mehr fordern von dem A, aber das machen wir ja
in einer Minute.
Schauen wir uns das mal an.
Also lineare Gleichungssysteme, gesucht ist die Lösung eben von A x
gleich B, wobei A eine quadratische Matrix ist und das B irgendeine
rechte Seite.
Und wir fragen uns jetzt, welches x löst diese Gleichung?
Warum ist das ein lineares Gleichungssystem?
Na ja, Sie haben vielleicht noch in Erinnerung, wie das funktioniert
mit Matrix mal Vektor.
Wie geht das nochmal?
Wir multiplizieren immer Zeile mal Spalte.
Und dann kommt jeder Eintrag von dem x, die einzelnen Komponenten, in
linearer Weise vor.
Also x 1 bis x n, wenn wir mal in n Dimensionen denken.
Und wenn Sie das ausmultiplizieren, kommen alle diese x i wirklich nur
in linearer Art und Weise vor.
Es kommen keine Quadrate vor oder hoch 3 oder Wurzel, kommt nicht vor.
Deswegen heißen die Dinger hier lineare Gleichungssysteme.
So, was ist die Situation, die wir vor Augen haben?
Ich sagte schon, wir haben die quadratische Matrix.
Wir werden gleich noch tiefer erklären, warum.
Und das, was wir vor Augen haben, sind riesige Systeme.
Das Dilemma ist, dass wir uns in den Übungen permanent mit 3x3 und 4x4
Systemen rumärgern, weil alles andere nervig ist und auch nicht
machbar ist auf dem Papier.
Aber das sollten Sie von Anfang an im Kopf haben.
Wir sind interessiert an Systemen, wo A riesengroß ist.
Und wir wollen Algorithmen entwickeln, um das effektiv zu lösen.
Und diese Algorithmen auch ein bisschen untersuchen.
Auf Aspekte, die Sie vielleicht bisher noch nicht kennen.
Also haben Sie das im Kopf, A ist riesengroß, alles das, was wir in
den Übungen und Klausuren machen, ist eher Spielerei.
Damit wir sehen, Sie haben das Prinzip verstanden.
Gut, man kann das Ganze jetzt ausführlich schreiben.
Das einfach ausmultipliziert.
Und hier sehen Sie jetzt, wie jedes einzelne Komponente von einem X in
linearer Art und Weise vorkommt.
Aber wenn es nötig ist, werden wir diese Schreibweise benutzen, mit
diesen Indizes.
Aber in der Regel haben wir das als Matrixmalvektor im Kopf.
Die Indizes an diesen kleinen a, das sind natürlich die Einträge von
der Matrix A.
Und wir haben zwei Indizes, auch wenn die scheinbar so daherkommen,
als ob da elf und zwölf und so weiter steht.
Dann meine ich ein eins und eins.
Immer wenn es nötig ist, dass wir zwischen den Zahlen wirklich
unterscheiden müssen können, werde ich einen Komma dazwischen machen.
Aber in der Schreibweise hier ist es eindeutig, der erste Index gibt
uns an, in welcher Spalte ich zu suchen habe.
Und der zweite Index gibt uns an, in welcher Zeile.
Und der zweite Index gibt uns an, in welcher Spalte dieser Eintrag zu
finden ist.
Also a11 wäre der Eintrag links oben in der Matrix.
Warum nur quadratische Matrizen?
An was sind wir interessiert?
Sie können sich ein bisschen zurücklehnen, das sind Dinge, die Sie
kennen aus der linearen Algebra oder kennen sollten.
Werden wir auch hier nicht beweisen, aber der Satz über die Existenz
einer eindeutigen Lösung.
Naja, wenn ich eine quadratische Matrix habe, A x gleich b, also auch
ein lineares Gleichungssystem A x gleich b, dann kann ich das, wenn
das A invertierbar ist, von links durch multiplizieren mit der
Inversen.
Sehen Sie hier unten als kleine Wiederholung, was die Inverse ist.
Die Inverse einer Matrix, mit A hoch minus 1 bezeichnet, ist genau die
Matrix, wenn ich sie von links oder von rechts an A ran multipliziere,
dass ich die Identität bekomme.
Die Identität ist jetzt hier in der Vorlesung mit I bezeichnet.
Das sind Kritzeleien, die mache ich nachher wieder raus, bevor ich das
online stelle.
Nur wenn wir Text hinschreiben, dann lasse ich das stehen.
So, also kann ich die Matrix invertieren, dann kann ich A x gleich b
von links mit A hoch minus 1 multiplizieren und habe meine Lösung x
Stern dastehen.
Wichtige Bemerkung, das wird in der Praxis nicht gemacht.
Das habe ich schon noch letztes Jahr sehr vehement vertreten, dass wir
die Inverse nie berechnen.
Ist gar nicht nötig, bringt gar keinen Vorteil.
Tatsächlich habe ich gelernt, dass es einen Lehrstuhl in der
Informatik gibt, der sich gerade sehr intensiv damit beschäftigt, die
Inverse parallel schnell zu berechnen.
Und eine Bachelorarbeit ist tatsächlich aus der Vorlesung letztes Jahr
entstanden und wir werden mal schauen, ob wir das sinnvoll nutzen
können, die Inverse.
Also schwäche ich das ein bisschen ab.
Aber in der Tendenz, sage ich Ihnen, werde ich Ihnen auch noch
belegen, wir haben überhaupt keinen Vorteil davon, dass wir die
Inverse kennen.
Die Inverse sollten wir nicht berechnen.
Vielleicht können wir uns mal kurz zusammen überlegen, was meinen Sie,
wenn wir jetzt die Inverse kennen und hier die rechte Seite a hoch
minus 1 mal b berechnen wollen.
Das ist ja x-Stern, das wäre ja die Lösung.
Und jetzt sind Sie in der vielleicht vermeintlich tollen Lage, dass
Sie a hoch minus 1 kennen.
Können wir mal darüber nachdenken, wie ist der Aufwand, a hoch minus 1
mal b auszurechnen?
Gut, das geht nach dem Prinzip, Zeile mal Spalte.
Das heißt, wir machen uns das am besten erstmal die Gedanken darüber,
wie der Aufwand ist, eine einzige Zeile mit dem Vektor x zu
multiplizieren.
Dann müssen wir diesen Aufwand nun mal n nehmen, mal n wie Norbert,
wenn wir n Zeilen haben.
So, wie ist das?
Eine Zeile mal Spalte, was ist der Aufwand?
Das ist ein euklidisches Skalarprodukt.
So funktioniert das, wenn Sie Zeile mal Spalte nehmen.
Wir nehmen immer die einzelnen Komponenten miteinander mal und
addieren das Ganze auf.
Okay, das heißt, wenn wir jede Komponente miteinander multiplizieren,
haben wir n Multiplikationen.
Und dann addieren wir alles auf, dann haben wir n minus 1 Additionen,
weil zwischen jedem Term steht ein Plus, deswegen haben wir ein Plus
weniger als Terme.
Also gut, das sind n minus 1 Additionen und n Multiplikationen.
Und jetzt, wo Sie alle da sind, ist es vielleicht auch eine gute
Gelegenheit, dass wir uns einigen darauf, wie wir...
Ich schlage vor, dass wir so zählen.
Multiplikationen und Divisionen sind für uns ein und dasselbe.
Teure sind im Computer, aber wir werden sehen, alle die Algorithmen,
die wir untersuchen, haben immer eine Größenordnung weniger Divisionen
als Multiplikationen.
Von daher braucht uns das nicht so zu interessieren.
Wir packen die Divisionen einfach mit zu den Multiplikationen und
Additionen und Subtraktionen fassen wir zusammen.
Und wir sprechen dann von einer Operation, wenn wir immer pärchenweise
eine Multiplikation und eine Addition zusammenfassen.
Dann sprechen wir von einer Operation.
Das wäre einfach ein Sprachgebrauch, an dem wir uns ein Semester lang
gemeinsam gewöhnen könnten.
Da kann man relativ präzise sagen, wie viele Operationen so ein
Algorithmus braucht.
Also hier nochmal zusammenfassend für das Skalarprodukt.
Das waren n Multiplikationen und n-1 Additionen.
Da kommen das minus 1 Schenken bei uns.
Das sind so gut wie n Additionen.
Dann nehmen wir die pärchenweise zusammen, das sind n Operationen, die
wir durchzuführen haben.
Nur um ein Skalarprodukt auszurechnen.
n Operationen ist auch das, was wir vermuten.
Hat die Länge n?
n Operationen, also dass es linear in der Länge ist, das ist sinnvoll.
So, n Operationen.
Jetzt machen wir dafür jede Zeile.
Wir haben n Zeilen.
Zeile mal Spalte waren n Operationen, also n².
Können wir uns ja vielleicht mal hier hinschreiben.
n² Operationen.
Und vielleicht schreiben wir es an die Stelle auch mal.
Hier drüben irgendwo hin.
Eine Operation gleich eine Multiplikation und eine Addition.
Gut, das müssen wir unbedingt im Kopf behalten.
Weil ich will Ihnen ja heute auch weismachen und motivieren, warum wir
die Inverse nicht unbedingt gebrauchen können.
Wir haben noch gar nicht darüber gesprochen, wie wir sie berechnen.
Aber wenn wir sie hätten, hätten wir n² viele Operationen auszuführen,
um x Stern zu bekommen.
Das müssen wir im Kopf behalten und werden wir auf jeden Fall gleich
noch mal anschauen.
Gut, das ist aber alter Kaffee, das kennen Sie ja.
Und das nächste kennen Sie auch.
Ich habe mal ein Beispiel genommen, wie Sie das vielleicht in der
Linie an Algebra kennengelernt haben.
Schon relativ formal und schön aufgeschrieben.
Als Musterlösung sozusagen.
Wir suchen die Lösung von...
Naja, hier links steht es.
Matrix mal Vektor gleich rechte Seite.
So, und wie ging das nochmal?
Was haben Sie kennengelernt in der Linie an Algebra?
Natürlich die Gauss-Elimination haben Sie kennengelernt.
Wie ging das nochmal?
Die Idee ist, vielfaches von oberen Zeilen auf untere Zeilen zu
addieren, um möglichst viele Nullen zu generieren.
Und das kann man hier relativ schön machen.
Das liegt daran, dass die Zahl hier, die 1, schon ungleich Null ist.
Und wir an der Stelle diese 1 als sogenanntes Pivot-Element benutzen
können.
Haben Sie das vielleicht auch so genannt.
Aber das wäre jetzt die Vokabel, die wir benutzen wollen.
Das ist unser Pivot-Element.
Und wenn wir das gleich auf die untere drauf addieren, was passiert
dann?
Dann wird aus der 2, die wir hier sehen, da können Sie es relativ
leicht nachvollziehen, wird eine Null.
Gut, das war genau der Sinn und Zweck der Geschichte, dass wir das
genau mit Minus 2 modifiziert haben.
Machen wir mal die Sachen hier wieder weg, damit es nicht so
unübersichtlich wird.
Natürlich müssen wir die anderen Einträge auch verändern.
Wir nehmen ein Minus 2-faches der ersten Zeile auf die mittlere Zeile
für den Eintrag, aber wichtig ist, wir haben so multipliziert, dass
vorne eine Null entsteht.
Das ist das entscheidende Ziel gewesen.
Genauso werden wir dann ein Minus 3-faches der ersten Zeile auf die
untere addieren, um nochmal eine Null zu generieren.
Das heißt, am Ende haben wir hier...
zwei Nullen.
Man sagt, wir haben x1, die Variable x1 entspricht der ersten Spalte,
die haben wir aus den unteren Gleichungen eliminiert.
Das ist der Grund, warum das Eliminationsverfahren heißt.
Und hier in dem 3x3-Beispiel passiert nicht mehr viel.
Als nächstes ist die Idee, auf das Untersystem...
Jetzt schreiben wir es mal kurz hin.
Das nochmal weg.
Hier auf dieses untere System jetzt.
Auf diese 2x2-Matrix.
Ist ja fast albern, aber ich will Ihnen ja nur das Prinzip erklären.
Machen wir das gleiche wieder.
Das Ziel ist jetzt, die Variable x2 zu eliminieren aus unteren
Gleichungen.
Das heißt, wir nehmen jetzt in dem Fall die mittlere Gleichung mit
minus 1.
Und zack, haben wir dann hier unten wieder eine Null.
Gut, das kennen Sie.
Wollen wir nicht so lange daran rumdoktern.
Was machen Sie, wenn Sie dann die Geschichte
in dieser Dreiecksform haben?
Wir haben jetzt Nullen generiert, links unten in der Matrix.
Und die Matrix selber hat jetzt obere Dreiecksstruktur.
Das, was unten rausgekommen ist.
Das ist ja leicht lösbar.
Das können Sie alle.
Sie haben vielleicht in den letzten Jahren Algebra gelernt.
Wir machen das Gaussen so lange, bis links die Inverse steht.
Und dann steht rechts der Lösungsvektor.
Aber das will ich Ihnen ja heute beibringen, dass wir das nicht mehr
machen.
Weil das viel zu aufwendig ist.
Und keinen Vorteil bringt, wenn wir die Inverse kennen.
Das heißt, an der Stelle hören wir auf.
Wir verändern nicht weiter.
Wir verändern die obere Dreiecksgestalt.
Weil das reicht aus, um jetzt von unten die Lösungen peu à peu sehr
leicht auszurechnen.
Wenn wir in die untere Gleichung gehen, dann haben wir hier die 4 und
hier haben wir die 8.
Naja gut, x3 ist 2.
Das ist einfach.
2 mal 4 gibt 8.
Wenn wir erstmal x3 kennen, können wir dann hier in die zweite
Gleichung gehen und ziehen von der Null 2 mal die 1 ab.
Das ist minus 2.
Das muss 2, 1 sein.
Oh ja, das passt.
Das passiert mir sicher noch häufiger.
Ich muss immer erst den Stift nach unten bewegen.
Dann gehen wir in die obere Gleichung und lösen die obere Gleichung
nach x1.
Das nennt man dieses Prozedere, das neue Vokabel.
Das ist die sogenannte Rückwärts-Substitution.
Wir kommen von unten und lösen von hinten die Variablen auf.
Das ist unser Ziel.
Diese Struktur bringt eben Vorteil.
Ich möchte Ihnen jetzt kurz was sagen zu solchen 3x-Systemen.
Gehen wir mal für einen kurzen Moment davon aus, dass wir unser
Gleichungssystem irgendwie umgeformt haben, sodass wir diese 3x
-Struktur haben.
Das kann man sich eigentlich ganz schön merken, hier unten durch das
Bildchen.
Jetzt machen wir genau das, was wir eben im Fall von 3x3 gemacht
haben.
Wir gehen hier erst zur unteren Gleichung und lösen das nach xn auf,
indem wir einfach durch rnn teilen.
Warum meinen Sie, kann ich durch rnn teilen?
rnn könnte ja 0 sein.
Warum nicht?
Was meinen Sie?
Ja, Sie hier vorne.
Doch, das wäre dann schon ein 3x-Gestalt.
Das wäre es schon.
Aber es gibt einen Aspekt, den habe ich ein bisschen nebenbei eben
gesagt.
Genau, dann wäre es eine Nullzeile und wäre nicht mehr invertierbar
gewesen.
Jetzt wollen wir uns mit invertierbaren Matrizen beschäftigen.
Wir brauchen eine eindeutige Lösung.
Wir sind nicht interessiert an dem Fall, den Sie auch aus der Linie an
Algebra kennen, dass wir eine Lösungsmenge haben, die einem ganzen
Kern entspricht und all so Dinge.
Das haben wir nicht.
Ab jetzt haben wir eine quadratische Matrix, das hätte ich eben besser
betonen müssen, und die ist invertierbar.
Und was heißt das für ein oberes 3x-System, die Invertierbarkeit?
Sie haben es gesagt mit der Nullzeile.
Wir könnten auch mal über die Determinante argumentieren.
Wie ist es mit der Determinante einer Matrix?
Es ist genau dann Null, wenn die Matrix singulär ist.
Oder anders formuliert, es ist genau dann ungleich Null, wenn die
Matrix invertierbar ist oder regulär ist.
Wie ist es mit der Determinante einer 3x-Matrix?
Wie kann man die ausrechnen?
Man multipliziert die Diagonale durch.
Wunderbar.
Deswegen müssen die Diagonalelemente alle ungleich Null sein, bei
einer invertierbaren oberen 3x-Matrix.
Das haben wir hier wirklich vorausgesetzt.
Wir können durch das Rnn teilen.
Jetzt kennen wir also das Yn.
Damit kennen wir auch diesen Ausdruck hier.
Wenn wir den Ausdruck kennen, können wir eine ganz einfache
Manipulation mit Minus auf die andere Seite bringen.
Und was machen wir dann noch, um an das Xn-1 zu kommen?
Dieser Vorfaktor Rn-1 N-1, den müssen wir einfach auf die andere Seite
bringen, die Formel steht hier.
Für die vorletzte Zeile.
Kein Problem.
Wir bringen alle die Terme, die wir mittlerweile kennen, auf die
andere Seite, und das sind die hinteren i-1-Terme.
Und von dem vorderen, den wir nicht kennen, müssen wir einfach nur
noch durch Rii teilen.
Das ist dann hier die allgemeine Formel.
Jetzt müssen wir uns gleich mal Gedanken über den Aufwand machen.
Auf der nächsten Folie.
Ich gebe Ihnen mal einen Vorschlag, wie man das implementieren kann.
Das kann man leicht implementieren.
Der Input sind also die obere Dreiecksmatrix R.
Wir haben eine rechte Seite Y.
In dem Fall nenne ich die rechte Seite mal Y.
Das hat einen ganz bestimmten Grund, den sehen Sie auch gleich noch.
Und der Output soll eben die Lösung X sein.
Gut.
Hier in der dritten Zeile von dem Code haben wir nach der letzten
Variablen aufgelöst, nach dem Xn.
So, wie geht das dann?
Wir müssen so eine Summe bilden.
Das machen wir hier in dieser Zeile hier.
In diesen vier Zeilen.
Das ist all das, was wir schon kennen.
Das ist die Summe von Produkten, die wir ausgerechnet haben.
Und die bringen wir dann auf die andere Seite.
Das ist hier dieses Minus.
Und müssen dann noch durch das Diagonalelement teilen.
Okay.
Ich initialisiere diese Summe immer mit dem ganz rechts stehenden
Produkt.
Ich zeige es Ihnen nochmal.
Das wäre jetzt genau das Umkringelte.
Oder auch das hier oben Umkringelte.
Das sind ja die Produkte, die ich bereits kenne, nachdem ich Xn
aufgelöst habe.
Sobald ich Xn kenne, kenne ich alle diese Produkte.
Und damit initialisiere ich meine Variable Summe.
Und addiere dann einfach den Rest auf, den ich bereits kenne.
Und zum Schluss muss ich die Differenz noch durch Ri teilen.
Was können wir zum Aufwand sagen von der Geschichte?
Gut, schauen wir mal ein bisschen.
Wir haben in der dritten Zeile eine Division.
Dann haben wir eine Vorschleife, die über i läuft.
Die wird n-1 mal durchlaufen.
Und jedes Mal am Ende, ich will erstmal die Division ein bisschen in
den Blick nehmen, wird nochmal dividiert.
Das heißt, wir haben insgesamt n Divisionen.
Schreiben wir es trotzdem mal für den Moment noch als Division auf.
n Divisionen.
Gut.
Wie ist das mit den
Multiplikationen und der Additionen?
Im Grunde genommen haben wir die Multiplikationen in der fünften
Zeile.
Schreiben wir es nochmal hin.
Hier ist die 5.
Da haben wir eine Multiplikation.
Und dann haben wir in der siebten Zeile, das war klar, jeweils eine
Addition und eine Multiplikation.
Und sehen Sie, in der neunten Zeile, die Division haben wir ja schon
gerechnet, aber da haben wir noch eine Subtraktion.
Die kommt auch in jeder Vorschleife von dem i genau einmal vor.
Das heißt, immer Addition und Multiplikation kommen tatsächlich
paarweise vor.
Also die Multiplikation in Zeile 5 wird mit der Subtraktion in Zeile 9
kombiniert.
Und in Zeile 7 stehen die sowieso schon direkt nebeneinander.
Die Addition und die Multiplikation.
Wie oft durchlaufen wir eigentlich die innere Schleife?
Die innere Schleife läuft von i von j gleich i plus 1 bis n minus 1.
Gucken wir uns das mal an.
Also wenn i n minus 1 ist, was ist dann die innere Schleife?
Die innere Schleife läuft dann von j gleich n bis n minus 1.
Das geht nicht.
Also zumindest nicht, wenn wir sagen, dass wir unser j immer um 1
erhöhen, weil wir dann von n bis n minus 1 laufen.
Das ist eine leere Schleife und wird nicht durchlaufen.
Das ist auch gut so, das soll es auch gar nicht tun.
Das heißt, diese Schleife wird für i gleich n minus 1 nicht
durchlaufen.
Gut, jetzt reduzieren wir das n.
n minus 1 war die vorletzte Zeile.
Jetzt gehen wir auf n minus 2.
Wenn i n minus 2 ist, ist also das i plus 1 n minus 1.
Und dann läuft das j von n minus 1 bis n minus 1.
Durchlauf.
Das heißt, eine Multiplikation, eine Addition.
Eine Operation.
Und jetzt gehen wir mit dem i weiter runter.
i geht auf n minus 3.
Wenn i auf n minus 3 geht, wird diese innere Schleife zweimal
durchlaufen und nachher wird sie dreimal durchlaufen.
Na ja, auf was läuft das hinaus?
Das läuft auf sowas hinaus.
Nehmen wir hier mal den Index k.
Von gepaarten Multiplikationen und Additionen.
Beim ersten Durchlauf wird die Vorschleife nicht durchlaufen.
Dann einmal, dann zweimal, dann dreimal.
Deswegen diese Summe.
Und die Frage ist, bis wohin?
Na ja, wenn wir i gleich 1 wählen, dann fängt j bei 2 an.
Und geht von 2 bis n minus 1.
Das heißt, wir müssen hier...
Das sind n minus 2 Durchläufe.
Deswegen addieren wir hier bis n minus 2.
Gut.
Das ist fast komplizierter, als es eigentlich ist.
Das sieht komplizierter aus, als es eigentlich ist.
Gut.
Jetzt nehmen wir noch die in Zeile 9 und Zeile 5 dazu.
Und das sind wie viele?
Plus n minus 1.
Immer gepaart.
Eine Addition, eine Multiplikation.
Sprich, wir reden gleich hier über Operationen, wie wir das machen
wollen in dem Semester.
Ja, wie können wir das ausrechnen?
Das ist wieder so ein kleiner Gauss.
Das wäre also n minus 2 halbe.
Mal n minus 1 in Klammern.
Plus n minus 1.
Das können wir ausklammern.
Dann haben wir n minus 2.
Also was ich machen möchte ist...
n minus 1 halbe ausklammern.
Ach, das kommt hier ja nur einmal vor.
Das heißt, ich muss hier eine 2 hinschreiben.
Und ein Plus dazwischen.
Und am Ende haben wir, weil ich das weghebe, die 2.
n mal n minus 1 halbe.
Okay, das ist der Aufwand.
Die Anzahl von Operationen...
die wir durchführen müssen, um so ein Dreieckssystem zu berechnen.
Die n Divisionen haben wir ein bisschen vernachlässigt.
Aber denken Sie daran, wir reden hier über riesige Matrizen.
Sprich, n Quadrat.
Und der Term hier unten ist ja ein quadratischer Term.
Weil da wird n mit n minus 1 modifiziert.
Das heißt, das da unten ist ein quadratischer Term.
Der übersteigt natürlich den Aufwand von diesen linear vielen
Divisionen.
Das können Sie vernachlässigen.
Das interessiert nicht.
Also, was wir uns merken, ist...
naja, modifizieren wir das nochmal in der Form aus.
Das sind 1 halb n Quadrat...
plus irgendwas.
Der dominante Term ist 1 halb n Quadrat.
Als nächstes käme minus n halbe.
Aber das ist wieder ein linearer Term, der interessiert uns nicht.
Wir merken uns nur die dominanten Terme vorne.
Merken Sie das?
Das lösen eines Dreieckssystems durch die Rückwärtssubstitution...
hat den Aufwand n Quadrat halbe Operation.
Das wäre die erste Botschaft.
Sie können sich vorstellen, dass es nicht so sehr davon abhängig war,
dass wir ein oberes Dreieckssystem haben.
Nehmen wir ein unteres Dreieckssystem L.
L mal Y gleich B.
Da sollte das relativ ähnlich verlaufen.
Was ändert sich?
Es ändert sich die Reihenfolge, mit der ich das System löse.
Wenn ich ein unteres Dreieckssystem habe, wie hier angedeutet, was
löse ich zuerst?
Na ja, Y1.
Ich nehme die erste Gleichung und löse Y1.
Hier würden Sie dann in die erste Gleichung gehen...
und Y1 lösen.
Dann gehen Sie von da aus zu Y2, Y3.
Das ist relativ klar, wie wir das nennen.
Das ist eine Vorwärtssubstitution.
Sehen Sie, der Aufwand ist natürlich auch n Quadrat halbe Operation.
Das sind mehr oder weniger die gleichen Formeln.
Da dürfen Sie sich in den Übungen mit beschäftigen.
Dass Sie da mal einen Algorithmus schreiben, in ähnlicher Form, im
Pseudocode wie hier.
Und dass Sie auch genau mal schauen, wie aufwendig ist das.
Dass Sie das mal argumentieren.
Okay, vielleicht wäre es jetzt an der Zeit, Ihnen schon mal ein erstes
Geschmäckle zu geben,
warum das mit der Inversen keinen Vorteil bringt.
Schauen wir mal ganz kurz.
Das Ziel der Vorlesung heute ist folgendes.
Ein bisschen vereinfacht.
Das Ziel ist, das A zu zerlegen.
Das A, was die Matrix unseres linearen Gleichungssystems zu zerlegen,
in L mal R.
Ein bisschen reduziert.
A ist gleich L mal R.
Und was meine ich mit L und R?
Das hier soll natürlich eine obere Dreiecksmatrix sein.
Und das hier eine untere.
Entschuldigung, das eine untere.
Und das ist eine obere Dreiecksmatrix.
Genau wie wir es eben hatten.
Wie würden wir jetzt A x gleich B lösen?
A x gleich B ist zu L und R.
Ich werde Ihnen gleich zeigen, wie wir das berechnen können.
Das heißt, wir können das A ersetzen.
Durch L mal R mal x gleich B.
Dann ersetzen wir R mal x durch Y.
Und haben unser Problem zerlegt.
In zwei leichte Probleme, die Sie eben kennengelernt haben, wie wir
sie lösen würden.
Wir würden als erstes lösen...
Wir lösen L Y gleich B.
B ist die rechte Seite, die gegeben ist.
L kommt aus der Zerlegung.
Wir reden gleich darüber, wie wir sie bekommen.
Ich behaupte jetzt schon mal, das sind 1,5 n² viele Operationen.
Ich bin schon richtig gut.
Das ist gestern noch viel häufiger passiert.
Ich übe und übe.
Aber Sie müssen auch gnädig sein.
L ist gleich Y zu lösen.
In dem ersten Schritt haben wir dann Y ausgerechnet.
Wir können dann mit dem unteren System, was wieder einfacher ist, weil
R eine obere 3x-Matrix ist, das x ausrechnen.
Die Anzahl der Operationen ist auch 1,5 n².
Zusammen haben wir n² viele Operationen.
So ist das mit der Inversen auch.
Denken Sie daran, auf der anderen Seite, wenn wir a hoch minus 1
kennen würden und x ausrechnen würden als a hoch minus 1 mal b, haben
wir auch n² viele Operationen.
Bisher habe ich noch nicht darüber gesprochen, wie teuer es ist, L und
R zu berechnen und wie teuer es wäre, a hoch minus 1 zu berechnen.
Aber hätten wir beides zur Verfügung, wäre das Berechnen der Lösung
einmal ein ledigliches Matrix-mal-Vektor-Produkt genauso teuer, wie
zunächst eine Vorwärts-Substitution durchzuführen und dann eine
Rückwärts -Substitution durchzuführen.
Beides kostet uns n² viele Operationen.
Also der erste Eindruck davon, selbst wenn ich a hoch minus 1 kenne,
haben Sie keinen großen Vorteil gegenüber demjenigen, der L und R
kennt.
Aber wie können wir das jetzt berechnen?
Also das a hoch minus 1 wollen wir natürlich nicht berechnen, das
werde ich Ihnen nicht vormachen.
a hoch minus 1 ist sogar teurer zu berechnen als L und R und, das
werden wir noch ein bisschen genauer untersuchen, numerisch
instabiler.
Das heißt, es bringt keinen Vorteil, es zu kennen und es ist auch noch
teurer.
Also a hoch minus 1 in dem Sinne über konventionelle Rechnungen
zu finden.
Es gibt gewisse Strukturen von a, wo man vielleicht mit einem
Parallelrechner was schaffen kann.
Das ist, wie gesagt, Gegenstand der Bachelorarbeit, die wir jetzt
gemeinsam haben mit Herrn Sanders hier in der Informatik.
Gut.
Gehen wir weiter.
Also die Idee ist tatsächlich, a zu zerlegen in ein Produkt L mal R,
wenn es denn möglich ist.
Ja, ich habe es hier nochmal aufgeschrieben.
Wir haben gesucht, ist die Lösung a x gleich b und der Unterschied zu
dem, was ich mit Ihnen eben gemacht habe, ist folgender.
Sehen Sie, vor dem a steht noch dieses p.
Weil, gucken wir uns das mal an, hier diese Geschichte.
Da steht p mal a ist gleich L mal R.
Das Problem ist nämlich, dass eine beliebige invertierbare Matrix a
sich nicht immer zerlegen lässt in L mal R.
Und das p steht für Permutation.
Das ist nichts anderes als eine Vertauschung der Zeilen.
Nachdem ich bei einer invertierbaren Matrix die Zeilen geschickt
vertauscht habe, kann ich sie immer in L und R zerlegen, in das
Produkt L mal R zerlegen.
Das werden wir heute noch beweisen sogar.
Also so eine Permutation muss ich unter Umständen mit einbeziehen.
Wie wirkt sich das aus, dass vor dem a ein p steht?
Schauen wir uns das an.
Ganz wichtig, wird gerne vergessen.
Der
Reader...
Diese Wischerei ist, wenn man so aufgeregte Hände hat wie ich, relativ
schwierig.
So.
Sehen Sie, das ist ganz wichtig, sollten Sie sich merken.
Die rechte Seite muss vorher, bevor wir loslegen und eine Vorwärts-
und Rückwärts-Substitution durchführen, mit p durchmodifiziert werden.
Die Rechnung dazu ist relativ simpel, das ist Ihnen klar.
Was müssen wir machen mit a x gleich b, um diese Zerlegung anwenden zu
können?
Die Zerlegung gilt ja nur für p mal a.
Also, was machen wir mit der Gleichung?
Wir modifizieren die von links mit groß p durch.
Erst jetzt...
können wir hier unsere LR-Zerlegung einsetzen.
Aber Sie sehen, auf der rechten Seite steht nicht mehr b, sondern p
mal b.
Wir müssen vorher die Komponenten in b entsprechend permutieren.
Aber wenn wir das gemacht haben, ist das Prozedere genau wie vorher.
Wir lösen eine Vorwärts-Substitution, eine Rückwärts-Substitution.
Also n² viele Operationen.
Gut.
Haben Sie soweit Fragen?
Irgendwas unklar bis hierhin.
Okay.
Was ich Ihnen heute noch beibringen möchte, ist a, wie setzen wir das
wirklich um?
Das sind Übungsaufgaben, die dummerweise eben, wie gesagt, nur für 3x3
- oder 4x4-Matrizen gelten.
Und wie könnten wir das im Computer dann auch umsetzen?
Das ist das eine.
Und wir werden einen theoretischen Beweis führen, warum so eine
Dreiecks -Zerlegung existiert.
So, jetzt wird es ein bisschen kompliziert.
Ich möchte Ihnen für den Moment beibringen, wie Elimination eigentlich
funktioniert.
Das ist etwas, was Sie unter Umständen auch sehen können.
So, wie funktioniert das?
Wir haben jetzt eine Matrix A gegeben.
Das ist genau die gleiche von vorher, denke ich.
1, 4, minus 1 und so weiter.
Und die Idee ist doch jetzt, dass wir aus den unteren Gleichungen x1
eliminieren.
Das hatten wir eben in einer sehr kompakten Schreibweise schon
hingeschrieben.
Was ich jetzt mache, ist, das ein bisschen umständlich aufzuplänen,
damit Sie verstehen, was dahinter steckt.
Das ist nichts anderes, als das Multiplizieren einer Elementarmatrix,
so wird das Ding genannt, L1, von links an die Matrix ran.
So, vielleicht ist es ganz hilfreich, nochmal kurz zu überlegen, wie
werden eigentlich Matrizen von links an andere ran multipliziert?
Was passiert denn da?
Schauen wir uns das mal an.
Nehmen wir mal diese Zeile hier.
Das geht ja immer nach dem Prinzip Zeile mal Spalte.
So werden Matrizen ausmultipliziert.
Was heißt es jetzt, dass ich von links einen Zeilenvektor an eine
Matrix multipliziere?
Eine andere Interpretation.
Was ist das Ergebnis davon?
Liegender Vektor, also Zeilenvektor mal Matrix.
Wie können Sie das Ergebnis interpretieren?
Hatten Sie eine Idee?
Nein?
Okay.
Zeilenvektor mal Matrix.
Das Ergebnis ist wieder ein Zeilenvektor.
Das Ergebnis ist wieder ein Zeilenvektor, aber es geht mir nicht nur
um das Format des Ergebnisses, sondern wie kommt denn das Ergebnis
eigentlich zustande?
Wie geht das?
Gucken wir uns mal diesen Vektor hier an.
Auf was trifft denn die Minus 3?
Im Ergebnisvektor.
Können wir den Ergebnisvektor hier drüben irgendwo zeigen?
Ja, der Ergebnisvektor steht hier.
Das ist die Zeile.
Und wenn Sie das mal machen mit dem Prinzip Zeile mal spalten, dann
trifft die Minus 3 immer auf die Elemente in der ersten Zeile der
Matrix A.
Auf die 1, auf die 4 und auf die Minus 1.
Hier trifft immer die Minus 3 drauf.
Die 1, das mittlere Element trifft immer auf die erste Zeile und hier
in dem Fall eben die 0 auf die untere.
Das ist eine Linearkombination der Zeilen in der Matrix A.
Das ist vielleicht ganz hilfreich, das zu wissen.
Wie ist es, wenn Sie jetzt einen Vektor von rechts, einen
Spaltenvektor von rechts an eine Matrix ran multiplizieren?
Also das ist eine sehr, sehr wichtige Geschichte, das zu verstehen.
Wenn Sie einen Matrix, einen Spaltenvektor von rechts an eine Matrix
multiplizieren, genau, das ist eine Linearkombination der Spalten der
Matrix.
Also was rauskommt, ist wieder ein Spaltenvektor diesmal.
Wenn Sie von rechts einen Spaltenvektor drauf multiplizieren, also
vielleicht machen wir das mal
Matrix haben und multiplizieren da einen Vektor dran, dann ist das
Ergebnis wieder ein Vektor.
Das ist uns klar, von der Struktur her, von den Dimensionen her.
Aber es ist gut zu wissen, dass im Grunde genommen das hier hinten,
der Ergebnisvektor nichts anderes ist als eine Linearkombination der
Spalten.
Das ist eine ganz gute Interpretation.
Wenn Sie jetzt einen liegenden Vektor haben, also einen Zeilenvektor,
und multiplizieren den von links, geht ja nur von links, von rechts
können Sie den ja gar nicht drauf multiplizieren, dann ist das
Ergebnis tatsächlich wieder ein liegender Vektor.
Und es ist gut zu wissen, also die Bilder sollten Sie im Kopf haben,
aber was ist der liegende Zeilenvektor?
Es ist eine Linearkombination der Zeilen von A.
Das sind verschiedene Interpretationen von diesem Vektor-Matrix
-Produkt, die, denke ich, ganz hilfreich sind.
Das heißt, wenn wir jetzt eine Matrix von links auf eine andere Matrix
dran multiplizieren, ist die Ergebnismatrix nichts anderes als
zeilenweise Linearkombinationen von Zeilen in A.
Und die Koeffizienten für die Kombinationen stehen in der Matrix
links.
Also hier in dem Fall in dem L1.
Also das war wichtig, dass Sie diesen Aspekt verstanden haben, weil
jetzt können Sie vielleicht verstehen, warum das mit dem Eliminieren
so klappt.
Machen wir uns mal für einen kleinen Moment wieder diesen Ausdruck
hier weg.
Sehen Sie, die erste Zeile besteht ja nur aus 1, 0, 0.
Also das ist ein Einheitsvektor, ein liegender, erster Einheitsvektor.
Das heißt, Sie nehmen einmal diese hier, 0 mal die zweite und 0 mal
die dritte und diese Linearkombinationen schreiben Sie oben hin.
Na gut, das ist natürlich die Zeile selber, die erste Zeile.
Also 1, 4, minus 1.
Die obere Zeile hat sich nicht verändert.
Wenn das so ist, dass tatsächlich das Multiplizieren von links mit
einem Zeilenvektor eine Linearkombination der Zeilen ist, dann brauche
ich nur darauf achten, dass bei der Linearkombination bitteschön ganz
vorne eine 0 rauskommt.
Das ist ja die Idee von eliminieren.
Deswegen sollten Sie verstehen, dass hier eine minus 3 steht und hier
eine 1.
Das ist wichtig.
Jetzt trifft nämlich die minus 3 auf die erste Zeile.
Also Sie müssen wissen, das ist echt großer Stress für mich.
Ich weiß, wie nerven das ist, wenn man da unten sitzt.
Ich hätte mich auch schon lange lustig gemacht.
Aber wir ziehen das durch.
Und am Ende bin ich ein Fachmann da drin.
Also die minus 3 trifft auf die erste Zeile.
Hier.
Die 1 auf die zweite.
Und jetzt sehen Sie, warum ich da minus 3 hingeschrieben habe.
Die minus 3 trifft ja dann auf die 1 und die 1 auf die 3 und in der
Summe kommt 0 raus.
Das war das Ziel.
Und genauso machen wir das mit dem unteren.
Hier schreiben wir eine minus 2 hin.
Hier eine 1.
Warum?
Weil die minus 2 auf die 1 trifft.
Und die 1 auf die 2.
Die 0 bleibt bitte schön da, damit die 3 keinen Einfluss hat.
Jetzt sind schon relativ viele Kritzeleien da.
Aber am Ende wollen wir garantieren, dass hier drüben die 0 entsteht
und hier die 0 entsteht.
Jetzt ist angebracht, wieder ein bisschen Platz zu schaffen.
Das ist ein bisschen murksig.
Aber was ich wollte, dass Sie verstehen, ist, dass Elimination im
Sinne von Links mit der Eliminationsmatrix zu multiplizieren, mit
einer Elementarmatrix zu multiplizieren.
Wenn wir das gemacht haben, haben wir die erste Variable
offensichtlich, das sehen Sie auf der rechten Seite, eliminiert.
Ganz oben steht die 1 und darunter stehen nur noch Nullen.
Wunderbar.
Und jetzt ist die Idee, die zweite Variable zu eliminieren.
Und Sie können sich vorstellen, das schaffen wir
mit der Elementarmatrix L2.
Diesmal stehen hier vorne bitte keine Einträge.
Also die Nullen bleiben erhalten.
Weil wir ja nicht mehr eliminieren wollen in der ersten Spalte.
Wir eliminieren jetzt in der zweiten Spalte.
Deswegen steht hier die Minus 2.
Warum steht da die Minus 2?
Können Sie sich vorstellen.
Wir wollen, dass von der Minus 12, die müssen wir durch Minus 1
halb...
nein, falsch.
Jetzt wollen wir mal ruhig bleiben.
Und nochmal das Prinzip ein bisschen besser machen.
Hier diese Zeile, wird mit der Matrix multipliziert.
Das heißt, die Minus 1 halb trifft auf die mittlere Zeile in A.
Also doch auf das Minus 12.
Und wenn ich das mit Minus 1 halb multipliziere, ich habe dividieren
gesagt und mich selber dadurch durcheinander gebracht.
Ich multipliziere es mit Minus
2, dann trifft die 1 auf die Minus 6 und wir haben hier hinten eine
wunderschöne Null generiert.
Die Idee ist, solche Matrizen von links drauf zu multiplizieren.
Das machen wir jetzt nur in der Theorie.
Das machen Sie in der Praxis natürlich nicht.
In der Praxis machen wir das viel effizienter.
Aber in der Theorie heißt eliminieren von links mit Elementarmatrizen
dieser Form drauf zu multiplizieren.
Das ist eine Dreiecksform.
Wir haben so lange eliminiert, bis wir eine obere Dreiecksmatrix
haben.
Und die nennen wir dann R.
Das ist unser R.
Das haben wir schon gefunden.
Sehen Sie, es ist auch nicht sehr schwer, diese Elementarmatrizen zu
bekommen.
Was lernen wir denn bei den Elementarmatrizen?
Sehen Sie, die haben immer Einsen auf der Hauptdiagonale.
Hier und hier.
Die sind von der Struktur R immer gleich.
Und die
geben als Quotienten von Einträgen in der A.
Das schauen wir uns gleich nochmal genauer an.
Das heißt, auch die Elementarmatrizen kann man ganz gut berechnen.
Fassen wir mal zusammen bei diesem Beispiel ohne Zeilentausch.
Wir haben erst die Matrix A mit L1 multipliziert, dann mit L2
multipliziert und am Ende kam ein R raus.
Wie kommen wir jetzt zu der Zerlegung LR?
Im Übrigen sind das die Matrizen L1 und L2 von der Zerlegung LR.
Was wir jetzt machen, ist einfach das durch Invertieren auf die andere
Seite bringen.
Und das ist eine wichtige Beobachtung.
Das Invertieren dieser Elementarmatrizen ist furchtbar denkbar
einfach.
Gucken Sie sich das mal an hier unten.
Wie unterscheidet sich diese Matrix und diese Matrix von den
entsprechenden Matrizen da oben?
Das Invertieren solcher Matrizen geschieht dadurch, dass man in die
Matrizen vertauscht.
Das ist alles.
Sehen Sie, oben steht Minus 3, Minus 2, unten steht 3, 2 und schon ist
das die Inverse.
Das müssen Sie mal ausprobieren zu Hause.
Das klappt.
Das ist tatsächlich die Inverse.
Die nächste wichtige Beobachtung ist folgende.
Wenn Sie diese Elementarmatrizen invertiert haben, hier unten, und das
Produkt bilden, lässt sich das Produkt ganz leicht ausrechnen.
Wenn Sie die nämlich sehen, auf der rechten Seite sind einfach die
Einträge der Elementarmatrizen spaltenweise reingeschrieben.
Das ist die zweite wichtige Beobachtung.
Die erste wichtige Beobachtung, also diese Elementarmatrizen lassen
sich ganz leicht invertieren.
Wir brauchen einfach nur ein Minus vor die einzelnen Koeffizienten
schreiben.
Nicht die Einsen auf der Hauptdiagonal.
Die bleiben Einsen.
Aber alles was in den Einträgen steht, ist lediglich nichts anderes
als die Einträge spaltenweise in eine Ergebnismatrix zu schreiben.
Das sind zwei ganz wichtige Beobachtungen, die ja auch im Computer
ganz leicht zu realisieren sind.
Sie ahnen schon jetzt, wir werden im Computer nie und nimmer mal diese
Elementarmatrizen hinschreiben.
Das Blödsinn, was wir brauchen, das sind unter Umständen
Riesenmatrizen mit vielen, vielen Nullen
und Einsen.
Warum sollten wir Nullen und Einsen speichern?
Wir brauchen nur die Einträge.
Von den Einträgen brauchen wir auch eigentlich nur genau das mit dem
umgekehrten Vorzeichen.
Und diesen Eintrag können wir gerne gleich in eine Sammelmatrix, in
diese Ergebnismatrix hinten reinschreiben.
Was letztlich auch das L wird.
So werden wir das im Computer machen und auf dem Papier auch nachher.
Also die Elementarmatrizen
und die Riesenmatrizen.
Bevor wir dazu kommen, machen wir noch ein Beispiel mit Permutation.
Schauen Sie, das ist so ein simples Beispiel.
Hier oben steht eine Null.
Wie soll ich denn die unteren Zeilen eliminieren, also das X1 aus den
unteren Zeilen zu addieren, um in der ersten Spalte Nullen zu
erzeugen?
Wie soll das gehen?
Ein Vielfaches der ersten Zeile hat immer ganz links ein Null stehen,
okay.
Wir schaffen es also gar nicht.
Das heißt, das ist jetzt mal so ein Trivial.
Wir müssen die Zeilen tauschen, sonst werden wir mit dem Gauss
-Algorithmus nicht vorwärts kommen.
Aber das haben Sie ja auch schon in der Linie an Algebra gemacht.
Ich schlage vor, das ist im Übrigen nicht eindeutig, das können Sie
anders machen als ich.
Ich schlage vor, dass wir uns die letzte Zeile in die erste holen und
die erste in die letzte.
Und das macht diese Permutationsmatrix.
Wenn ich die von links drauf multipliziere und wir haben eben gelernt,
das sind nichts anderes als Linearkombinationen von Zeilen.
Ich fange nochmal anders an.
Was ist eigentlich eine Permutationsmatrix?
Das haben Sie vielleicht in der Linie an Algebra kennengelernt.
Eine Permutationsmatrix ist eine Matrix, wo die Einheitsvektoren alle
vorkommen, spaltenweise oder auch zeilenweise, wie Sie wollen.
Und jeder Einheitsvektor kommt genau einmal vor.
Das ist eine schöne Definition für eine Permutationsmatrix.
Gucken wir uns die erste Zeile an.
Die erste Zeile dieser Matrix hier ist der Einheitsvektor E3.
Darunter kommt dann E2 und darunter kommt E1.
Jeder Einheitsvektor kommt als Zeile genau einmal vor oder als Spalte.
Können Sie denken, wenn Sie so eine Matrix also von links auf eine
andere drauf multiplizieren, was passiert?
Nachdem was wir uns eben überlegt haben, dass das Multiplizieren einer
Zeile von links auf eine Matrix nichts anderes ist als eine
Linearkombination der Spalten, der Zeilen, aber jetzt die Zeilen
Einheitsvektoren sind, ist klar, eine einzige Zeile kommt einmal vor,
alle anderen werden mit 0 multipliziert.
Das ist nur ein Vertauschen der Zeilen.
Im Übrigen, was meinen Sie ist die Inverse von so einer Matrix, die
die zwei Zeilen miteinander vertauscht?
Also Permutationsmatrizen sind viel allgemeiner.
Permutationsmatrizen können alle Zeilen miteinander kombinieren und
vertauschen.
Nicht nur zwei.
Was wir hier machen, wir nehmen eine gewisse Klasse von
Permutationsmatrizen.
Wir nehmen nur solche, die genau zwei Zeilen miteinander vertauscht.
Das reicht.
Das reicht, um diese 0 da oben wegzukriegen.
Wir vertauschen immer nur zwei Zeilen miteinander.
Und hier in dem Fall habe ich vorgeschlagen, lassen Sie uns die erste
und die letzte Zeile miteinander tauschen.
Wir hätten auch die zweite nehmen können und die erste.
Aber die 1 ist so schön zum Rechnen, deswegen habe ich die nach oben
geholt.
So, was meinen Sie ist die Inverse einer solchen Permutationsmatrix,
die nur zwei Zeilen vertauscht?
Ja?
Genau, die Matrix selbst wieder, weil wenn wir sie wieder dran
multiplizieren, vertauschen wir die beiden wieder am ursprünglichen
Platz.
Das ist eine wichtige Erkenntnis.
Die Inverse einer Matrix, die zwei Zeilen vertauscht, ist sie selber.
Ja?
Das werden wir gleich nochmal brauchen.
Okay.
Also das erste, was wir machen, ist also hier oben eine 1 zu erzeugen.
Hier.
Durch Zeilen tauschen.
Und jetzt können wir eliminieren, das haben wir eben schon gemacht,
indem wir hier jetzt mit so einer Matrix...
Okay.
Wollen Sie Kontakt haben mit mir?
Jetzt kommt das wahrscheinlich gleich wieder, weil ich diese App
geöffnet habe.
Jetzt können Sie live miterleben, wie man Apps schließt bei Windows 8.
Oder auch nicht.
Ich glaube, das wäre hier das.
Ein bisschen komisch.
Windows.
Also gut.
Hier.
Nachdem ich jetzt also permutiert habe, wäre jetzt die Idee, zu
eliminieren.
Also Nullen zu erzeugen.
Sehen Sie, unten steht ja schon ein Null.
Also Entschuldigung.
Hier steht ja schon ein Null.
Das heißt, hier haben wir keinen Eintrag.
Hier in der Ergebnismatrix haben wir jetzt eliminiert.
So.
Jetzt haben wir eliminiert.
Und Sie können sich vorstellen, warum ich das Beispiel so gewählt
habe.
Was ist passiert, wenn Sie sich das Ergebnis da anschauen?
Was sehen Sie jetzt an dem Ergebnis?
Ich habe wirklich X1 eliminiert aus den unteren Gleichungen.
Aber ich habe das so gebastelt, dass hier in dieser Restmatrix ein
Null links oben steht.
Das heißt, wir sind wieder gezwungen, zu vertauschen.
Weil dieses Element kann wieder nicht als Pivot-Element benutzt
werden, um nach unten zu eliminieren.
So.
Das machen wir jetzt durch so eine Matrix P2.
Eine weitere Permutationsmatrix.
Aber da ist es wichtig zu erkennen, welche Struktur die Matrix hat.
P2 soll jetzt die untere Zeile mit der vorletzten Zeile wieder
vertauschen, damit wir wieder ein Pivot-Element bekommen, was ungleich
Null ist.
Ja, das wäre hier die 4.
Die wollen wir haben.
Aber was Sie hier sehen können, ist, dass P, diese Permutationsmatrix,
weil sie sich ja nur noch auf ein unteres System bezieht, ist es
wichtig, dass Sie erkennen, dass links oben immer eine 1 stehen muss,
bei dieser Permutationsmatrix.
Der erste Einheitsvektor muss spaltenweise in der ersten Spalte und
zeilenweise in der ersten Zeile stehen.
Also 1, 0, 0, 1, 0, 0.
Das ist wichtig, damit nicht das zerstört wird, was wir schon erreicht
haben.
Wir arbeiten ja jetzt nur noch auf einem System, einem Untersystem,
ein N-1, in diesem Fall eben zweidimensionalen System.
So, das heißt die Permutationsmatrix, die eigentliche
Permutationsmatrix steht hier als 2x2-Matrix.
Gut, jetzt haben wir permutiert und was sich herausstellt, ich meine,
das musste ja jetzt so sein, ist dass das Ergebnis hier schon als
Dreiecksform dasteht.
Okay, haben Sie Fragen zu der Geschichte?
Ja?
Okay, also hier war der Vorschlag, wie sieht es aus, wir haben jetzt
die erste und die dritte vertauscht und das hatte zwangsläufig zur
Konsequenz, dass wir dann nachher noch mal vertauschen mussten.
Kann man nicht von Anfang an so geschickt vertauschen, damit man sich
das erspart?
Die Antwort ist für dieses Beispiel, ja, das können Sie mit dem 3x3
-System, Sie könnten ein bisschen Arbeit reinstecken, Sachen
ausprobieren, testen und verstehen.
Es wäre besser gewesen, wir hätten die erste und die zweite Zeile
getauscht, dann hätten wir nachher nicht mehr tauschen müssen.
Wie ist das mit dem Computer?
Im Computer machen wir das nicht.
Sie werden eine Strategie von mir kennen lernen, wie wir vertauschen,
die uns numerische Vorteile verspricht oder bringt.
Das werde ich noch erklären, warum.
Und dann macht der Computer das und fertig.
Der wird sich nicht Gedanken machen darüber, ob es noch was
Geschickteres gibt.
Das funktioniert sehr, sehr gut.
Vielleicht kann ich es an der Stelle mal erklären, wie das
funktioniert.
Die Geschichte ist jetzt die, wir mussten tauschen, weil das Pivot
-Element null war und nicht als Pivot-Element dienen kann, weil wir in
der Null können wir nicht nach unten eliminieren.
Ja, geht nicht.
Wenn da aber auch eine Zahl ungleich null gestanden hätte, hätte der
Computer ein geschicktes Programm vielleicht trotzdem Zeilen
vertauscht und zwar in folgender Art und Weise.
Der Computer guckt die Spalte komplett nach unten, alle Elemente durch
und schaut, wo das betragsmäßig größte Element steht.
Und dieses Element, diese Zeile, wo das betragsmäßig größte Element
steht, wird nach oben getauscht.
Das ist die sogenannte Spalten-Pivot-Wahl oder Spalten-Pivot-Wahl, so
heißt es.
Das hat numerische Vorteile, bringt eine Stabilität des Algorithmus,
aber das schauen wir uns nochmal genau an.
Aber Sie haben jetzt schon mal kennengelernt oder ich habe Ihnen
mündlich gesagt, wie das funktioniert.
Der Computer tauscht im Grunde genommen immer.
Jeden Schritt eigentlich.
Er guckt immer, wo ist das betragsmäßig größte Element und das wird
nach oben getauscht.
In der Regel ist es nämlich nicht an der Stelle oben.
Also das Permutieren macht er im Grunde genommen fast bei jedem
Schritt.
Aber das bringt Stabilität und bringt nachher dem Algorithmus einen
Vorteil.
Das heißt, wir werden uns dem anvertrauen, das ist das Beste, was wir
machen können und werden uns nicht noch zusätzliche Strategien
ausdenken, um möglichst wenig zu permutieren.
Vielleicht noch eine Frage zur Permutation.
Ist das für den Computer eine große Anstrengung, zu permutieren?
Nein, nein, nicht.
Haben Sie C++ schon programmiert?
Änder ich ein paar Zeiger, fertig.
Ich brauche noch nicht mal den Speicherplatz ändern von irgendwas.
Das ist überhaupt kein Problem.
Also permutieren ist überhaupt kein Problem.
Abgesehen davon, was meinen Sie, wie wird der Computer Permutationen,
wie werden wir dem Computer Permutationen beibringen?
Wie sollten wir das speichern?
Haben Sie da eine Idee?
Permutationsmatrix, wir reden hier wieder über riesige Matrizen.
Denken Sie an eine 10.000 kreuz 10.000 Matrix.
Das ist die Ausgangsmatrix A.
Was können Sie über die Permutationsmatrix P sagen?
Die hat hauptsächlich Nullen drin stehen und irgendwo ein paar Einsen.
Wie speichern Sie sowas?
Was haben Sie für Möglichkeiten?
Ja,
ganz genau.
Also der Vorschlag war, man sollte immer nur Zahlen-Tupel speichern,
den Zeilenindex und gucken, wo steht in der Zeile die 1 und dann den
Spaltenindex und diese Tupel speichern.
Es geht noch ein bisschen einfacher.
Das ist schon ein guter Schritt, ja?
Ja, das ist richtig.
Die Antwort war, wir wissen ja, dass das Ding quadratisch ist.
Wir wissen, wie viele Zeilen es gibt.
Wir brauchen ja doch eigentlich immer nur den Spaltenindex uns zu
merken, weil die Zeilen werden von 1 bis N durchnummeriert.
Diesen Index können wir auf den Müll schmeißen.
Sie nehmen einfach einen Vektor und in den Vektor schreiben Sie immer
rein, an welcher Stelle steht die 1.
Ja, das würde reichen.
Das heißt, die komplette Permutationsmatrix, eine Riesenmatrix, wird
einfach nur als ein einziger Vektor abgespeichert.
Das werden Sie auch gleich sehen.
Das machen wir auch so.
Weitere Fragen?
Ja,
am Ende brauchen wir die Information, also es werden immer nur zwei
Zeilen vertauscht, aber in dem Algorithmus wird das sehr häufig
gemacht.
Und das Endprodukt ist eine Matrix, das hätte ich vielleicht noch mal
deutlicher machen müssen, das Endprodukt ist eine Matrix, die nicht
nur zwei Zeilen vertauscht, sondern wo alles drin kodiert ist.
Ich zeige Ihnen mal die nächste Folie, da wird das vielleicht
deutlich.
Dieses Beispiel hier, Sie haben jetzt ein bisschen gesehen, ich musste
permutieren, eliminieren, permutieren.
Das war das Kochrezept bei der Aufgabe.
Und schauen Sie, jetzt können Sie es vielleicht besser verstehen.
Schauen Sie, das ist das, was wir drüben gemacht haben auf der anderen
Folie.
Permutiert, eliminiert, permutiert.
Und das Endprodukt ist R, eine obere Dreiecksmatrix.
Wie kriege ich das jetzt in diesen formalen Ansatz mit dem P mal A ist
gleich L mal R.
Also schauen Sie sich mal diese wilde Zeile hier an.
Das Ziel ist, P mal A ist gleich L mal R.
Ich will die L, R Zerlegung haben.
Bisher stehen da noch diese L1 und P1 und P2 auf der falschen Seite.
Zumindestens das L.
Was ich mache ist, ich modifiziere mit dem Inversen durch.
Gucken Sie, als allererstes hier wird mit dem Inversen von P2
durchmodifiziert.
Wir haben eben schon miteinander gesprochen, das ist nichts anderes
als P2 selber.
Eine Matrix, die zwei Zeilen vertauscht, ist inverse zu sich selber.
Schreiben wir das mal hier hin.
Ohne hier gleich wieder irgendwelche anderen Programme aufzumachen.
Das ist gleich P2.
Sehr ungünstige Position.
Aber das kriegen wir weg.
Also, die Inverse ist P2 selber.
Wir modifizieren mit P2 hoch minus 1 durch.
Dann modifizieren wir mit L1 hoch minus 1 durch.
Wir haben eben festgestellt, das ist einfach.
Ich brauche nur Minuszeichen an der richtigen Stelle zu machen.
Und was wir als nächstes machen, jetzt steht das P1 auch noch auf der
linken Seite.
Jetzt modifizieren wir nochmal mit P2 durch.
Und dann haben wir hier die Ergebnismatrix P. Das ist jetzt die
Gesamtpermutationsmatrix, die alle Permutationen in sich vereint.
Und die wollen wir als diesen Spaltenvektor repräsentieren.
So, was ist auf der rechten Seite passiert in diesem einfachen
Beispiel?
Ich denke, hier ist es wichtig, dass Sie das nochmal verstehen.
Ich schreibe es mal hier kurz hin.
L ist gleich P2 mal L1 hoch minus 1 mal P2.
Weil P2 hoch minus 1 ist P2 selber.
Was passiert mit so einer Matrix L1 oder L1 hoch minus 1?
Das hoch minus 1 können wir für den Moment vergessen.
Die Inverse ist genauso einfach und hat die gleiche Struktur wie L1
selber.
Hatten wir schon geklärt.
Es wird lediglich ein gewisse Stelle geschrieben.
Ansonsten sind das identische Matrizen.
Also vergessen Sie das hoch minus 1 für den Moment.
Was passiert, wenn ich an so einer Matrix von links P2 dran
multipliziere und von rechts P2 dran multipliziere?
Was meinen Sie?
Ja?
Doch.
Fast.
Ja, ein bisschen was passiert.
Vielleicht sage ich mal kurz, wie L1 aussieht.
Wo haben wir es stehen?
Ach, hier steht es hier oben.
Sehen Sie, L1 steht hier und wie gesagt L1 hoch minus 1 ist einfach
die gleiche Matrix, wo Sie minus 2 durch 2 ersetzt haben.
Was passiert bei der Matrix?
Nochmal?
Nee, wird nicht transponiert.
Das ist wirklich gut, das lineare Algebra jetzt.
Was passiert, das haben wir vorher schon miteinander diskutiert, was
passiert, wenn ich eine Permutationsmatrix von links dran
multipliziere?
Was ist die Funktion?
Funktionsweise, was ist das Ergebnis?
Ja?
Vertauschen von was?
Von Zeilen.
Sehr gut.
Und wenn ich das von rechts dran multipliziere?
Genau, dann werden Spalten vertauscht.
Das ist schon mal ganz wichtig.
Jetzt ist P2 eine Matrix, die genau zwei Zeilen vertauscht und einmal
multipliziere ich die von links und einmal von rechts drauf.
Was passiert denn da?
Ja?
Zeilentausch und Spaltentausch.
Fangen wir mal mit den Einsen an, die auf der Hauptdiagonalen stehen.
Wenn wir jetzt zwei Zeilen vertauschen, was passiert denn?
Diese Struktur der Einsen auf der Hauptdiagonalen wird zerstört.
Wir nehmen einfach zwei Zeilen und tauschen die dann wandert eine
Eins, die vorher auf der Diagonalen ist, irgendwie ins Off und eine
andere auch.
Können Sie sich vorstellen?
Und jetzt kommt aber von rechts wieder ein Spaltentausch.
Und es werden zwei Spalten getauscht und es werden exakt die gleichen
Spalten getauscht wie vorher Zeilen.
Also meinetwegen, vorher wurde die erste und die fünfte Zeile
vertauscht, dann wird auch jetzt die erste und fünfte Spalte
vertauscht.
Was passiert also mit den Einsen?
Die waren vorher auf der Hauptdiagonalen.
Jetzt nehmen sie aus dieser Struktur einfach zwei Zeilen und
vertauschen die.
Dann wandern die von der Hauptdiagonale irgendwo in die Matrix rein.
Aber jetzt kommt die Permutationsmatrix von rechts.
Und was passiert mit den Einsen?
Die stehen jetzt in den super entsprechenden Spalten und wenn die
vertauschen, dann wandern sie wieder auf die Hauptdiagonale.
Das ist in der Tendenz das, was Sie sagten.
An der Hauptdiagonalen passiert nichts.
Am Ende besteht die Hauptdiagonale wieder aus lauter Einsen.
Aber in dem Prozedere gibt es ja noch andere Einträge in dem L.
Nein?
Okay, das kann sogar richtig sein, was Sie jetzt sagen.
Ich muss aber noch eine Zusatzinformation geben und das ist vielleicht
für Sie auch interessant.
Was für Zeilen werden denn überhaupt getauscht?
Machen wir es mal konkret für das Beispiel.
Wir reden über L1.
L1 ist eine Matrix mit Einsen auf der Hauptdiagonalen und in der
ersten Spalte stehen diese Eliminationskoeffizienten, so nenne ich sie
mal.
Die stehen in der ersten Spalte.
Was ist jetzt P2 für eine Matrix?
Ganz wichtig an der Stelle, hätte ich vielleicht besser sagen sollen,
es ist eine Permutationsmatrix, die nur noch Zeilen vertauscht, die
größer sind als 1.
Sehen Sie, P2 kommt ja nur noch ins Spiel, nachdem ich schon die
eliminiert habe.
Das heißt, die obere Struktur darf nicht zerstört werden.
Gehen wir mal in die Matrix selber.
Hier sehen Sie, ganz wichtig, hier oben steht eine 1.
Die Permutation findet nur noch in unteren Zeilen statt.
Das ist ganz, ganz wichtig.
Es wird jetzt hier in dem Fall, weil es ein Drei-Kreuz-Drei-Fall ist,
wird die zweite und die dritte Zeile werden vertauscht.
Die erste wird nicht mehr angepackt, weil das schon perfekt ist.
Da haben wir schon eliminiert.
Das wird nicht mehr angepackt im Algorithmus.
Das waren wichtige Zusatzinformationen.
Okay, wir bringen das nachher auf den Punkt, den Sie sich merken
können, auch wenn Sie nachher sagen, worin diese ganzen Gedanken
resultieren und was wichtig für Sie ist.
Vielleicht denken jetzt nur noch 10% mit.
Aber versuchen wir es trotzdem zu Ende zu bringen.
Permutationsmatrix von links und von rechts dran modifiziert.
Einmal werden die Zeilen vertauscht, einmal Spalten.
Wichtig, es werden nur noch weiter unterliegende Zeilen und Spalten
vertauscht.
Was hat das jetzt mit der ersten Spalte zu tun?
Die erste Spalte in dieser L-Matrix,
weiter unterliegende, und dann die Spalten vertauschen.
Machen Sie ruhig die Augen zu und stellen Sie sich das vor.
Sehr schön, das ist wichtig, die bleiben in der gleichen Spalte.
Sehr schön haben Sie den Punkt erfasst, weil ja nur noch untere Zeilen
und Spalten getauscht werden.
Die Elemente in der ersten Spalte werden vertauscht, weil ja Zeilen
vertauscht werden und die Zeilen über die komplette Matrix beinhalten
auch die erste Spalte.
Das heißt, es werden Zeilen vertauscht.
Dadurch werden in der ersten Spalte Elemente vertauscht.
Dann werden Spalten vertauscht, aber nur hintere.
Das heißt, die erste Spalte bleibt die erste Spalte.
Aber das ist ein ganz wichtiger Aspekt.
Diese Koeffizienten, diese Eliminations- koeffizienten, das ist ein
gutes Wort für den Moment, die werden getauscht.
Das ist wichtig, auch für den Algorithmus.
Okay, gucken wir mal ein bisschen weiter.
Hier sind diese wichtigen Beobachtungen, die wir heute schon
ausführlich diskutiert haben.
Können Sie das erfassen?
Das sind Riesenmatrizen.
Können Sie das ein bisschen sehen?
Im Karten- Eliminationsschritt haben Sie eine Matrix dieser Struktur.
Sie sehen, sie ist ein bisschen verschoben, aber das soll eine
Hauptdiagonale sein mit Einsen.
Und in der Kartenspalte haben Sie diese Eliminations- koeffizienten,
nennen wir sie mal so.
Und dann behaupte ich, die Inverse, na die Inverse kriegen Sie ganz
klar.
Das lässt sich leicht ausrechnen.
Nehmen Sie es einfach mit.
Das würden Sie auch nachvollziehen, wenn Sie das zu Hause rechnen.
Und die nächste wichtige Beobachtung steht hier unten.
Wenn Sie diese Produkte alle bilden, heißt das nichts anderes als die
Koeffizienten spaltenweise reinzuschreiben.
Das hatten wir ja heute schon als Ergebnis festgehalten, aber das
schadet nicht, das nochmal als Zwischenergebnis festzuhalten.
Das heißt, diese L-Matrix lässt sich sehr leicht herstellen, wenn wir
wissen, was die Eliminations-Koeffizienten sind.
Wir brauchen sie dann nur an die entsprechende Stelle von L
reinzuschreiben.
Und kommt dann irgendwann später nochmal eine Permutation, taucht
nochmal auf, müssen wir nach dem, was wir uns gerade überlegt haben,
die Einträge entsprechend vertauschen in L.
Mehr nicht.
Entsprechend der Permutation, die aufgetaucht ist.
Hier gebe ich Ihnen mal ein Beispiel.
Das war jetzt vielleicht ein bisschen viel.
Jetzt kommen wir wieder, Sie haben das verstanden.
Idee ist auch folgende.
Gucken Sie mal noch kurz zu mir, aber noch nicht auf die Folie.
Was machen wir denn im Computer?
Ich will mit Ihnen kurz darüber sprechen, wie wir Speicherplatz sparen
können.
Das sind riesige Matrizen.
Das macht dem Computer schon Probleme, sowas überhaupt in den
Arbeitsspeicher zu laden.
Das heißt, wir müssen uns Gedanken machen, das ordentlich
abzuspeichern.
Wie ist das denn?
Ja gut, die R-Matrix kommt irgendwie im Laufe des Prozesses raus.
Aber was machen wir mit der Matrix A?
Wir eliminieren permanent nach unten und erzeugen Nullen.
Wir machen das so geschickt, dass da eben eine Null rauskommt.
Die Null brauchen wir uns nicht speichern im Computer.
Was könnten wir da hinschreiben an die Stelle, wo die Null steht?
Wir könnten genau in die Stelle, wo die Null steht, den
Eliminationskoeffizienten, den Eintrag aus L, könnten wir da
reinschreiben.
Das ist doch wunderbar.
Da brauchen wir nur ein Array, nur eine Matrix.
Und die Hauptdiagonale können wir leider nicht verwenden von der
Matrix A, weil die Hauptdiagonale bleibt relevant.
Aber die Hauptdiagonale von der Matrix L besteht sowieso nur aus
Einsen.
Die brauchen wir auch nicht speichern.
Wir speichern also alle unteren Nebendiagonalen von L und die
schreiben wir sofort da rein, wo wir vorher eliminiert haben.
Das heißt, wir haben ein und dieselbe Matrix A, die, wenn wir richtig
vorgehen, am Ende oben R enthält und unten L.
Das ist die Idee.
So, gucken wir uns das mal an.
Schauen Sie, wir starten hier mit der Matrix, diese hier, ja?
Ist die gleiche wie vorher.
Ich will Ihnen nur beibringen, so sollten Sie es aufschreiben, weil so
ist es auch schon relativ nah an dem, was im Computer gemacht wird.
So, ich eliminiere.
Die Minus 3 ist der Koeffizient, der Eliminationskoeffizient, mit dem
ich die erste Zeile multiplizieren muss, um die zweite zu addieren, um
eine Null zu schreiben.
Sie sehen hier an der Stelle, ganz wichtig, hier, schreibe ich nicht
eine Null hin.
Ich weiß ja, dass da eine Null steht in der Matrix A.
Was ich hinschreibe ist den Eintrag, der nachher in L drin steht.
Und der ist, nach dem, was wir uns eben überlegt haben, nichts anderes
als das vom Vorzeichen umgekehrte von Minus 3, sprich 3.
Den schreibe ich einfach da rein.
Geht ganz einfach, ja?
Jetzt gehen wir zur nächsten Geschichte.
Jetzt multipliziere ich die erste Zeile mit Minus 2.
Wir sind hier.
Und wiederum speichere ich hier den Koeffizienten.
Nicht Minus 2, sondern wieder einfach mit dem Mindestzeichen umdrehen,
die 2.
Und sehen Sie, jetzt habe ich in Rot hier schon die ersten Einträge
von der Matrix L abgespeichert.
Und so würde der Computer das auch machen.
Und dann machen Sie das Gleiche.
Jetzt eliminieren Sie hier noch die Variable x2 aus der untersten
Zeile und schreiben das schön auch hier gleich rein.
So, und das Ergebnis können Sie dann abschreiben.
L und R.
Einmal der obere Teil mit der Hauptdiagonalen, einmal der untere Teil
ohne die Hauptdiagonale, aber dann müssen wir die Einsen
reinschreiben.
Nochmal, im Computer würden Sie nie schreiben L und R.
Im Computer haben Sie nur eine n-Kreuz-n-Matrix, sprich ein Array.
Aber wir hier schreiben am Ende dann wieder hin L und R.
So, okay, ich sehe, die Zeit geht ein bisschen vorwärts.
Jetzt ganz wichtig, achten Sie, wie immer, achten Sie noch einmal die
drei, vier Minuten, die wir noch haben, auf das letzte Beispiel, weil
jetzt kommt noch mal die Vorgehensweise mit Permutationen.
Ich würde vorschlagen, links, ganz links, aber das können Sie auch
rechtschreiben, ist völlig egal, ein Vektor mit den Zeilen nochmal hin
zu schreiben.
1, 2, 3 in dem Fall.
Sehen Sie hier, ja, hier ist einfach dieser Vektor und wann immer Sie
jetzt permutieren, verändern Sie nur die Reihenfolge in diesem
Permutationsvektor und am Ende haben Sie in diesem Permutationsvektor
die komplette Permutation kodiert.
Gehen wir es mal zusammen durch, das Beispiel.
Hier, erstens, was wird da gemacht?
Da wird die erste Zeile mit der dritten Zeile vertauscht.
Das sehen Sie jetzt schön in dem Permutationsvektor, der dann hier
entsteht.
Die 3 steht jetzt oben und die 1 steht jetzt unten.
Soll heißen, in der ersten Zahl haben wir an der dritten Position die
1, in der zweiten Zeile haben wir an der zweiten Position die 1 und in
der letzten Zeile an der ersten.
Das ist das, was Sie eben auch vorgeschlagen hatten.
Jetzt eliminieren wir, jetzt kommt die minus 2 hier als
Eliminationsfaktor und den schreiben wir hier rein.
Wunderbar.
Sehen Sie, die 0 unten hat sich sofort auch ergeben, die 0 hat sich
auch sofort ergeben, weil schon hier oben, jetzt wird es wieder ein
bisschen kritisch und grenzwertig, hier steht schon eine 0.
Ich brauche also nicht mehr eliminieren und immer wenn ich nicht
eliminieren muss, weil da schon ein Ergebnis steht, was ich möchte,
heißt der entsprechende Eintrag in L 0.
Und deswegen kann ich ihn da reinschreiben, als 0.
Okay, jetzt sehen Sie leider nicht mehr ordentlich, weil ich schon so
viel reingemalt habe.
Machen wir mal wieder weg.
Jetzt sehen Sie, haben Sie ja eben auch schon das Gefühl, ich muss
also wieder eliminieren.
A, muss ich eliminieren.
B, hatte ich Ihnen schon erklärt, der Computer macht eigentlich
sowieso immer eine Spalten-Pivot-Wahl.
Der würde in erster Linie nicht vertauschen, weil da eine 0 steht,
sondern er würde in erster Linie vertauschen, weil hier eine 4 steht
und die betraglich größer ist.
Das ist der eigentliche Grund, warum er tauschen würde.
So, können Sie sehen, wie das sich auswirkt in dem Permutationsvektor
hier.
Der heißt jetzt nicht mehr 3, 2, 1, sondern 3, 1, 2.
Wir haben die unteren beiden Einträge getauscht.
Aber ganz wichtig, das habe ich versucht eben mit Ihnen
herauszuarbeiten, sehen Sie die Einträge hier unten, ich schmal es
nochmal hin, hier die 2 und die 0.
Ganz wichtig, heißen jetzt hier in der neuen Matrix 0, 2.
Sehen Sie, Sie müssen die Einträge in L auch tauschen, wenn Sie
permutieren.
Das ist wichtig.
Okay, das ist eigentlich alles.
Dann haben Sie jetzt hier L, R und P stehen.
Wie Sie auf P kommen ist klar.
Sie gucken in Ihren Vektor, den Sie oben haben und an der dritten
Stelle steht die 1, an der ersten Stelle steht die 1, an der zweiten
Stelle steht die 1.
Da können Sie einfach wieder generieren diese Permutationsmatrix.
Aber im Computer würden Sie das sowieso nicht machen.
So, ich will Sie auch nicht mehr lange aufhalten.
Ich glaube, vom Prinzip her haben Sie das verstanden.
Ja.