LR-Algorithmus

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

Der LR-Algorithmus formt die gegebene quadratische Matrix A=:A0 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.

A0:=A
for k=1,2,… do
Ak−1=:LkRk (LR-Zerlegung)
Ak:=RkLk
end for

Da Ak=RkLk=Lk−1Ak−1Lk ähnlich ist zu Ak−1 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 A 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:

Probleme im LR-Algorithmus

Der entscheidende Nachteil des LR-Algorithmus besteht darin, dass die einfache LR-Zerlegung der Matrizen LkRk=Ak−1 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 Ak−1=PkLkRk mit einer Permutationsmatrix Pk führen. Die entsprechende Modifikation des Verfahrens ist Ak=RkPkLk=Lk−1(PkTAk−1Pk)Lk, welche wieder auf eine zu Ak−1 ähnliche Matrix führt. Allerdings ist dann die Konvergenz nicht mehr gesichert, es gibt Beispiele, wo die modifizierte Iteration zur Ausgangsmatrix A=A0 zurückkehrt. Daher bevorzugt man den QR-Algorithmus, der dieses Problem nicht hat.