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

Dies ist eine alte Version des Dokuments!

  • Prüfer: Prof. Dr. Ulrich Rüde
  • Beisitzer: Simon Bogner
  • Note: 2.7
  • Prüfungsfragen:
  • Prüfer: Die erste Einstiegsfrage 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 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.
  • Atmosphäre: Ich danke den Prüfern für diese Lektion. Sie zeigt mir meine Grenzen. Ich sehe ein, dass ich für eine Masterarbeit im Bereich der Systemsimulation nicht reif bin, und konzentriere mich auf diejenigen Bereiche, für die ich geeigneter bin.
  • Vorbereitung: Größtenteils habe ich mich analog zu kili vorbereitet. Ebenfalls habe ich mir die Protokolle im CE-Repository angeschaut. Für mich war diese Vorbereitung allerdings falsch, da ich Defizite in der Ausdrucksweise zeigte und nicht jede Frage sofort exakt beantwortet habe. Bloßes Verständnis reicht den Prüfern nicht aus.