Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 10 » anla-2016-03-02-2   (Übersicht)

  • 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 <zeichnet Kreise für Matrix auf>
  • 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 <implementiert erst 2 For-Schleifen und die typische Elimination ohne Pivotisierung, allerdings wurde das Normieren falsch implementiert>
  • Prüfer <korrigiert den Studenten>
  • 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.