LR-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der LR-Algorithmus, auch Treppeniteration, LR-Verfahren oder LR-Iteration, ist ein Verfahren zur Berechnung aller Eigenwerte und eventuell auch Eigenvektoren einer quadratischen Matrix und wurde 1958 vorgestellt von Heinz Rutishauser. Er ist der Vorläufer des gängigeren QR-Algorithmus von John G. F. Francis und Wera Nikolajewna Kublanowskaja. Beide basieren auf dem gleichen Prinzip der Unterraumiteration, verwenden im Detail aber unterschiedliche Matrix-Faktorisierungen, die namensgebende LR-Zerlegung bzw. QR-Zerlegung. Obwohl der LR-Algorithmus sogar einen geringeren Aufwand als der QR-Algorithmus aufweist, verwendet man heutzutage für das vollständige Eigenwertproblem eher den letzteren, da der LR-Algorithmus weniger zuverlässig ist.

Ablauf des LR-Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Der LR-Algorithmus formt die gegebene quadratische Matrix in jedem Schritt um, indem zuerst ihre LR-Zerlegung berechnet wird, sofern diese existiert, und dann deren beide Faktoren in umgekehrter Reihenfolge wieder multipliziert werden, d. h.

for do
(LR-Zerlegung)
end for

Da ähnlich ist zu bleiben alle Eigenwerte erhalten. Der LR-Algorithmus hat wie der QR-Algorithmus den Vorteil, am Platz durchführbar zu sein, d. h. durch Überschreiben der Matrix und weist im Vergleich zum QR-Algorithmus sogar geringere Kosten auf, da die bei der LR-Zerlegung verwendeten Gauß-Transformationen (vgl. Elementarmatrix) jeweils nur eine Zeile ändern, während Givens-Rotationen jeweils auf 2 Zeilen operieren. Zusätzlich sind beim LR-Algorithmus auch die vom QR-Algorithmus bekannten Maßnahmen zur Beschleunigung der Rechnung einsetzbar:

  • für Hessenbergmatrizen kostet jeder LR-Schritt nur Operationen
  • die Konvergenz lässt sich durch Spektralverschiebung wesentlich beschleunigen
  • durch Deflation kann die Iteration auf eine Teilmatrix eingeschränkt werden, sobald sich einzelne Eigenwerte abgesondert haben.

Probleme im LR-Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Der entscheidende Nachteil des LR-Algorithmus ist aber, dass die einfache LR-Zerlegung der Matrizen eventuell nicht existiert oder durch kleine Pivotelemente zu großen Rundungsfehlern führen kann. In diesem Fall sind Zeilenvertauschungen erforderlich, welche auf eine modifizierte Zerlegung mit einer Permutationsmatrix führen. Die entsprechende Modifikation des Verfahrens ist , welche wieder auf eine zu ähnliche Matrix führt. Allerdings ist dann die Konvergenz nicht mehr gesichert, es gibt Beispiele, wo die modifizierte Iteration zur Ausgangsmatrix zurückkehrt. Daher bevorzugt man den QR-Algorithmus, der dieses Problem nicht hat.

  • Heinz Rutishauser (1958): Solution of eigenvalue problems with the LR transformation. Nat. Bur. Stand. App. Math. Ser. 49, 47–81.
  • J. G. F. Francis (1961): The QR Transformation: A Unitary Analogue to the LR Transformation—Part 1. The Computer Journal Vol. 4(3), S. 265–271. doi:10.1093/comjnl/4.3.265
  • Josef Stoer, Roland Bulirsch: Numerische Mathematik 2. 5. Auflage, Springer-Verlag Berlin 2005, ISBN 978-3-540-23777-8.