A stable cubically convergent GR algorithm and Krylov subspace methods for non-Hermitian matrix eigenvalue problems

Abstract

In dieser Dissertation werden Krylov-Verfahren und Zerlegungsalgorithmen (GR-Algorithmen) zur Eigenwertberechnung von beliebigen Matrizen untersucht. Es wird gezeigt, dass das allgemeine restarted Krylov-Verfahren mathematisch äquivalent zum allgemeinen GR-Algorithmus ist. Ausgehend von diesem Ergebnis wird ein neues, numerisch stabiles GR-Verfahren entwickelt. Es wird bewiesen, dass dieses Verfahren, angewandt auf eine beliebig gegebene Matrix mit paarweise verschiedenen Eigenwerten, unter sehr schwachen Voraussetzungen kubisch konvergiert. Man beachte, dass das QR-Verfahren unter diesen Voraussetzungen i.a. nur quadratisch konvergiert.

In this thesis Krylov methods and algorithms of decomposition type (GR algorithms) for the eigenvalue computation of arbitrary matrices are discussed. It is shown that the general restarted Krylov method is mathematically equivalent to the general GR algorithm. Using this connection, a new, numerical stable GR algorithm is developed. It is proved that this algorithm converges cubically under mild conditions, when applied to any given matrix with distinct eigenvalues. Notice, that the QR algorithm converges typically quadratically under these conditions.