* **Prüfer:** Prof. Dr. Ulrich Rüde * **Beisitzer:** Simon Bogner * **Note:** 2.7 * **Prüfungsfragen:** * Prüfer: Die erste Frage beschäftigt sich mit den Normen. Wie definieren Sie eine Norm? * Student: Positivität, Absolut-Homogenität und Dreiecksungleichung erklärt * Prüfer: Wie definiert man ausgehend davon eine Matrixnorm? * Student: sup_(x != 0) (||Ax|| / ||x||) = sup_(x mit ||x|| = 1) ||Ax|| * Prüfer: Für die Matrixnormen gibt es eine weitere Ungleichung. Wie lautet sie? * Student: Erst ||AB|| = ||A|| * ||B|| hingeschrieben, dann aber auf <= korrigiert, da der Dozent nach einer Ungleichung gefragt hat. * Prüfer: Können Sie ein Beispiel konstruieren, wieso die Gleichheit nicht immer gilt? * Student (peinlich nach Überlegung): Stimmt, die Gleichheit gilt nicht immer, denn sonst müsste ja die Norm von ||A|| * ||A^-1|| = ||1|| sein, womit ja jedes Problem die Konditionszahl von 1 hätte. Das wäre zu schön, um wahr zu sein. * Prüfer: Kommen wir nun zu einer Klausuraufgabe aus 2011, Gershgorins Theorem. Was ist die Aussage von Gershgorins Theorem? * Student: Eigenwerte liegen in den Kreisen, deren Mittelpunkt durch die Diagonalelemente der Matrix und deren Radius durch die Summe der Beträge der Nichtdiagonalelemente derselben Zeile liegt. * Prüfer (zeigt eine Matrix): Zeichnen Sie die Kreise für diese Matrix! * Student * Prüfer: Wenn sich wie in diesem Fall Kreise überlappen, können Sie da eine Aussage treffen, wo die Eigenwerte liegen? * Student (verwirrt): Liegen hier zwei Eigenwerte nicht in der Schnittmenge des Kreises? * Prüfer: Nein, das ist falsch. Generell kann man nur eine Aussage treffen, dass die Eigenwerte in der Vereinigungsmenge der Kreise liegen. Eine letzte Frage zu dem Kapitel: Können die Eigenwerte auch am Rand des Kreises liegen? * Student: Ja, insofern gilt für diese Matrix, dass 0 ein Eigenwert sein kann. * Prüfer: Können Sie dieser Matrix auch ohne Gershgorins Theorem ansehen, ob sie singulär ist? * Student: Nach Gauß-Elimination erkennt man, dass diese Matrix singulär ist. * Prüfer: Betrachten wir nun die Least-Squares-Verfahren: Was ist denn die generelle Rechnung bei Least Squares? * Student: ||Ax-b|| —> min, was man benötigt, um Ax=b zu lösen. * Prüfer: ||Ax-b|| stimmt aber nicht für jede beliebige Norm. Welche Norm muss das sein? * Student: Das muss die euklidische Norm sein. * Prüfer: Das stimmt. Jetzt ist aber A nicht quadratisch. Können Sie eine Aussage über die Dimension von A angeben? * Student: A sei eine Matrix mit n Spalten und m Zeilen, … * Prüfer: Nein, ich meine, wie verhält sich m zu n? * Student (nach einiger Überlegung): Das Gleichungssystem ist überbestimmt. * Prüfer: Das wollte ich hören. Welche Verfahren haben Sie kennengelernt, um das Least Squares Problem zu lösen? * Student: SVD, QR, Cholesky. * Prüfer: OK, fangen wir nun mit SVD an. Wie lösen Sie das Problem mit SVD? * Student: Wir haben die Gleichung U*Sigma*V^* * x = b, insofern können wir erst U invertieren, was durch eine Transposition und eine komplexe Konjugation erfolgt. Anschließend müssen wir noch die Pseudoinverse von Sigma ausrechnen. * Prüfer: Wofür brauchen wir hier eine Pseudoinverse? * Student: Na ja, Sigma ist im Allgemeinen keine quadratische Matrix und insbesondere nicht immer invertierbar. * Prüfer: Aber wie rechnen wir die Pseudoinverse für Sigma aus? * Student: Durch 1/sigma_i für sigma_i != 0 und 0 sonst. * Prüfer: OK, jetzt haben wir eine Matrix mit zahlreichen Nullzeilen. Sind jetzt die unteren Einträge des Vektors b egal und wieso? * Student: SVD hat ja die Eigenschaft, dass man damit die minimale Rang-n-Approximation ausrechnen kann. * Prüfer: Genau, dementsprechend wird b durch eine Multiplikation mit U so transformiert, dass die untersten Einträge am wenigsten beitragen. Der Vollständigkeit halber: was muss man als letzten Schritt machen? * Student: Man muss noch mit V auf beiden Seiten multiplizieren. * Prüfer: Kommen wir nun zur Cholesky-Zerlegung, wie Sie gesagt haben. Wie sieht da die Formel für Least Squares aus? * Student: Wir haben nun eine symmetrisch positiv definite Matrix A gegeben, für die A = R^*R gilt (hier hat der Student etwas überlegt, ob nun R^*R oder RR^* genommen werden soll, am Ende aber R^*R genommen, damit R eine rechte obere Dreiecksmatrix ist). * Prüfer: Im Allgemeinen ist aber A nicht positiv definit, welche Matrix wäre es denn? * Student: Wir können beide Seiten mit A^* multiplizieren, also erhalten wir die Gleichung A^*A = A^*b. * Prüfer: Wie heißt denn diese Art von Gleichung? * Student: Normalengleichung * Prüfer: OK, wie würden Sie jetzt diese Normalengleichungen lösen? * Student: Wir können jetzt zunächst die Cholesky-Zerlegung von A^*A berechnen, dann A^*b ausrechnen und anschließend die Inverse von R^*R berechnen und erneut an A^*b multiplizieren. * Prüfer: Wenn Sie mir eine Inverse anbieten würden, würde ich Sie entlassen, denn eine Inverse ist immer ineffizient. Wie genau würden Sie da invertieren? * Student: Wir haben ja eine Cholesky-Zerlegung, also können wir ja erst R und dann R^* invertieren, was wegen Tridiagonalgestalt ja in quadratischer Laufzeit analog zur LR-Zerlegung funktioniert. * Prüfer: Wie genau sieht aber diese Invertierung aus? * Student: Das funktioniert über die Elimination R\b bzw. R^*\b. * Prüfer: Und was machen Sie, wenn Sie z. B. in eingebetteten Systemen arbeiten und kein Matlab haben, wo schlauere Leute als Sie diesen Backslash-Operator implementiert haben? * Student * Prüfer * Prüfer: Kommen wir nun zu den Eigenwertalgorithmen. Aus welchen 2 Phasen bestehen diese? * Student: Erst reduzieren wir eine quadratische Matrix A auf die Hessenberg-Normalform QHQ^* und dann lösen wir das Problem auf H, was ein einfacheres Problem als das Finden von Eigenwerten auf H darstellt. * Prüfer: Wie können wir denn die Reduktion auf die Hessenberg-Normalform durchführen? Wie konstruieren wir also Q? * Student: Im Prinzip können wir das z. B. mit Arnoldi machen. * Prüfer: Wir wollen jetzt aber keine iterativen Algorithmen besprechen, sondern uns lieber mit den klassischen Algorithmen befassen. Wie kann man denn Q elementar finden? * Student (verwirrt): Evtl. mit Gram-Schmidt bzw. Householder. * Prüfer: OK, wie findet man mit Householder die richtige Matrix Q? * Student (auch hier nach viel Überlegung): Man kann ja Q über Aneinanderreihungen von I - 2 * vv^* / v^*v ausrechnen. * Prüfer: Und wie sieht hier denn v aus? * Student: Im Gegensatz zu QR muss hier nach einem Schritt nicht jedes Element unterhalb der Hauptdiagonalen 0 sein, sondern alle bis auf das oberste. * Prüfer: Aber warum nehmen wir hier nicht einfach die Schur-Zerlegung? Hat das einen Grund? * Student (hat keine Ahnung): Evtl. ist die Berechnung von Schur nicht so stabil wie Hessenberg? * Prüfer: Nein. Damit wir zu einem runden Abschluss kommen: Hier multiplizieren wir mit Q von links und mit Q^* von rechts. Wenn wir also mit Q^* immer wieder multiplizieren, dann werden die durch Q auf 0 veränderten Einträge wieder zurückgeändert. Deshalb wäre hier falsch, die Elemente der beiden Nebendiagonalen auf 0 zu transformieren.