Bisektions-Verfahren/Inverse Iteration

• Im Folgenden wird stets A reell symmetrisch angenommen.
• Um alle Eigenwerte und Eigenvektoren einer reell-symmetrischen Matrix A zu bestimmen, kann man sich des Trägheitssatzes von Sylvester bedienen, um alle Eigenwerte zu finden. Danach bestimmt man die einzelnen Eigenvektoren durch inverse Iteration. Dies macht aber nur Sinn, wenn man zuvor die Matrix auf Dreibandform ähnlichtkeitstransformiert hat. Eine allgemeine symmetrische Matrix wird daher zunächst durch eine vorgeschaltete Householdertransformation auf Dreibandform T gebracht.
  
• Ist mu eine Eigenwertnäherung, dann ist die Anzahl der Eigenwerte von T kleiner als mu identisch mit der Anzahl der Pivots in der LR-Zerlegung mit der natürlichen Pivotwahl, die kleiner sind als null. Wird ein Pivot null, ändert man ihn in eps ab, was die Eigenwerte maximal um eps verändert. Durch Auswertung dieser Anzahl an zwei Grenzen eines Intervalls und Reduktion der Intervallbreite kann man so jeden Eigenwert beliebig genau eingrenzen. Man beachte, dass eine Tridiagonalmatrix, deren Nebendiagonalelemente alle ungleich null sind, nur einfache Eigenwerte haben kann. (Die können aber dennoch extrem dicht liegen!)
• Ist ein Eigenwert genügend genau angenähert, kann man den zugehörigen Eigenvektor durch inverse Iteration bestimmen. Die so erhaltenen Eigenvektoren sind häufig nur ungenügend orthogonal, insbesondere bei dicht benachbarten Eigenwerten, weshalb es empfehlenswert ist, während der inversen Iteration zusätzlich eine Orthogonalisierung bezüglich der bereits bestimmten Eigenvektoren durchzuführen, was aber den Aufwand noch einmal beträchtlich erhöht.
• Die Eigenvektoren der Tridiagonalmatrix werden dann mittels der Householdertransformation in die der Ausgangsmatrix überführt. Diese Operation beeinflusst die Orthogonalität der Eigenvektoren nicht.

Die Eingaben

• Die Matrix kann aus fünf Fällen ausgewählt werden:
  1. Eine 8x8-Matrix mit bekannter Eigenwertverteilung.
  2. Eine 5-Bandmatrix, die bei der Diskretisierung des Balkenbiegungs-Problems entsteht. Dimension variabel, Eigenwerte bekannt.
  3. Eine eigene Eigenwertverteilung kann angegeben werden, aus der mit Hilfe einer festen Eigenvektormatrix die Matrix A erzeugt wird.
  4. Das untere Dreieck einer eigenen Matrix A. Einträge zeilenweise, durch Kommata oder Leerzeichen getrennt.
  5. Direkte Eingabe einer Tridiagonalmatrix in Form von Diagonale und Superdiagonale. Dann entfällt natürlich die Vortransformation und Rücktransformation der Eigenvektoren.
• Die Dimension n der Matrix, falls der Fall 2,3,4,5 gewählt wurde. Im Falle der Matrix 2 muß 3 <= n <= 30 sein, sonst 2 <= n <= 30 !
• Ist die Ausgabe der Matrix A erwünscht ?
• Ist die Ausgabe der approximierten Eigenvektoren erwünscht ?
• Ist die Nachorthogonalisierung der Eigenvektoren in der inversen Iteration gewünscht?

Die Ausgaben

• Ausgegeben wird die Matrix A, falls dies gewünscht war.
• Die approximativen Eigenwerte (falls kein Programmabbruch aufgetreten ist), und die Abweichung zu den echten Eigenwerten, falls diese bekannt sind.
• Die approximativen Eigenvektoren, falls dies gewünscht war.
• Die Abweichung der Eigenvektormatrix von der Orthogonalität gemessen in der Frobeniusnorm.
• Eine Grafik, die den Verlauf der Testwerte mu während der Bisektion zeigt. Da wir hier bis nahe an die Maschinengenauigkeit gehen, sieht man ca 50 Schritte pro Eigenwert.

Fragen ?!

• Hängt die Konvergenz von der Eigenwertverteilung ab ?
• Wie ist die Sensitivität der Eigenwerte und Eigenvektoren gegen Änderungen in der Matrix ?
• Wie wirkt sich die Unterlassung der Nachorthogonalisierung aus, abhängig von der Eigenwertverteilung?

Das Eingabeformular

Zurück: Eigenwertprobleme