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 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.
- Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A_{0}:=A}
- for do
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{k-1}=:L_kR_k} (LR-Zerlegung)
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_k:=R_kL_k}
- end for
Da ähnlich ist zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{k-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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:
- für Hessenbergmatrizen kostet jeder LR-Schritt nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^2)} 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
Der entscheidende Nachteil des LR-Algorithmus ist aber, dass die einfache LR-Zerlegung der Matrizen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_kR_k=A_{k-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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_{k-1}=P_kL_kR_k} mit einer Permutationsmatrix führen. Die entsprechende Modifikation des Verfahrens ist Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A_{k}=R_{k}P_{k}L_{k}=L_{k}^{-1}(P_{k}^{T}A_{k-1}P_{k})L_{k}} , welche wieder auf eine zu Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A_{k-1}} ähnliche Matrix führt. Allerdings ist dann die Konvergenz nicht mehr gesichert, es gibt Beispiele, wo die modifizierte Iteration zur Ausgangsmatrix Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle A=A_{0}} zurückkehrt. Daher bevorzugt man den QR-Algorithmus, der dieses Problem nicht hat.
Literatur
- 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.
