Logo ZeTeM

Zentrum für Technomathematik

ZeTeM > Forschung und Anwendungen > Projekte > Kontrolltheoretische Analyse von Eigenwertverfahren

Kontakt Sitemap Impressum [ English | Deutsch ]

Kontrolltheoretische Analyse von Eigenwertverfahren

Leitung: Prof. Dr. Diederich Hinrichsen (E-Mail: dh@math.uni-bremen.de)
Bearbeiter: Prof. Dr. Fabian Wirth
Projektpartner:
Laufzeit: 01.08.1999 - 31.10.2003
Bild des Projekts Kontrolltheoretische Analyse von Eigenwertverfahren Effiziente numerische Eigenwertverfahren wie der QR-Algorithmus oder allgemeiner definierte FG-Algorithmen beruhen wesentlich auf der Verwendung von Spektralverschiebungen (sogenannten "Shifts"). Diese sind notwendig, um z.B. quadratische oder kubische Konvergenzgeschwindigkeiten zu erzielen. Das globale Konvergenzverhalten derartiger Eigenwertverfahren ist komplex und trotz intensiver Untersuchungen bisher nur partiell verstanden, hauptsächlich für den Fall normaler Matrizen.

Die Literatur in der numerischen linearen Algebra bietet derzeit keine wirklich überzeugenden Argumente, welche Shift-Strategien verwendet werden sollten oder vielleicht sogar optimal sind. Es fehlt daher ein systematischer Zugang zu solchen Fragen. Betrachtet man Eigenwertverfahren als diskrete dynamische Systeme, so sind Spektralverschiebungen als Kontrollparameter zu interpretieren und die zugehörigen Algorithmen damit als nichtlineare Kontrollsysteme auf homogenen Räumen. Dies legt es nahe, nach kontrolltheoretischen Ansätzen zur Analyse von Eigenwertverfahren zu suchen und sich dabei die Fortschritte der nichtlinearen Kontrolltheorie zu Nutze zu machen.

Eine grundlegende Frage in diesem Zusammenhang ist die der Kontrollierbarkeit der entstehenden Systeme. Derartige systemtheoretische Untersuchungen in der numerischen linearen Algebra sind bisher kaum durchgeführt worden (eine prominente Ausnahme bilden dabei allerdings die Arbeiten von Absil, Sepulchre und Van Dooren aus Belgien). Insbesondere fehlt eine Untersuchung der Kontrollierbarkeit von QR-ähnlichen Eigenwertverfahren.

In dem Projekt wurde zunächst die Kontrollierbarkeit der inversen Iteration mit Shift untersucht und diese Ergebnisse dann auf den Fall des geshifteten QR-Algorithmus ausgeweitet. Dabei wurde eine Charakterisierung von Kontrollierbarkeit für die inverse Iteration erzielt und es konnte gezeigt werden, dass der Standard-QR-Algorithmus in allen interessanten Fällen nicht kontrollierbar ist. Diese Erkenntnis hat zur Entwicklung von QR-ähnlichen Algorithmen mit "Multishifts" durch Helmke und Hüper geführt, die eine Kontrollierbarkeitseigenschaft haben.