QR-Zerlegung
Die QR-Zerlegung oder QR-Faktorisierung ist ein Begriff aus den mathematischen Teilgebieten der linearen Algebra und Numerik. Man bezeichnet damit die Zerlegung einer Matrix in das Produkt
zweier anderer Matrizen, wobei eine orthogonale () bzw. unitäre Matrix () und eine obere Dreiecksmatrix ist. Die QR-Zerlegung ist ein Spezialfall der Iwasawa-Zerlegung.
Eine solche Zerlegung existiert stets und kann mit verschiedenen Algorithmen berechnet werden. Die bekanntesten davon sind
Das letztere wird üblicherweise in der linearen Algebra benutzt, ist aber in seiner Standardform numerisch instabil. Man kann das Verfahren aber erweitern und numerisch stabilisieren.
Definition
Eine Matrix , besitzt eine (fast – siehe weiter unten) eindeutige reduzierte QR-Zerlegung
als Produkt einer in den Spalten orthogonalen Matrix und einer oberen Dreiecksmatrix
Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung
- ,
indem man mit weiteren orthogonalen Spalten zu einer quadratischen -Matrix erweitert, und an unten Nullen anfügt, so dass eine -Matrix entsteht:
Die QR-Zerlegung ist eindeutig für und , wenn man die Vorzeichen der Diagonalelemente von vorgibt – üblicherweise wählt man alle positiv.
Anwendung
Die QR-Zerlegung spielt in vielen Verfahren der numerischen Mathematik eine wichtige Rolle, beispielsweise um eine orthogonale oder unitäre Basis zu bestimmen oder um lineare Ausgleichsprobleme zu behandeln. Sie ist integraler Bestandteil des QR-Algorithmus zur Berechnung aller Eigenwerte einer Matrix.
Lösung regulärer oder überbestimmter Gleichungssysteme
Um die Lösung eines linearen Gleichungssystems mit Matrix ,
- von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:
- Bestimme eine QR-Zerlegung der Matrix .
- Berechne , üblicherweise unter Benutzung der Faktorisierung von aus Schritt 1.
- Löse durch Rückwärtseinsetzen.
Für ist dies eine Alternative zur LR-Zerlegung, sie hat den doppelten Aufwand der LR-Zerlegung, ist aber möglicherweise numerisch stabiler.
Im Fall gibt es im Gleichungssystem mehr Gleichungen als Variablen und es liegt ein überbestimmtes Gleichungssystem vor. Hier wird durch Lösung des Ausgleichproblems nach der Methode der kleinsten Quadrate (s. auch Regressionsanalyse) bestimmt:
- Minimiere .
In diesem Fall ist die Moore-Penrose-Pseudoinverse von und für die berechnete Kleinste-Quadrate-Lösung gilt die Beziehung , die die übliche Darstellung des regulären Falls verallgemeinert.
Lösung unterbestimmter Gleichungssysteme
Für hat die Matrix einen nichttrivialen Kern. Bei vollem Rang von bilden die Lösungen des Gleichungssystems daher einen affinen Unterraum. Diejenige Lösung mit kleinster Norm liegt im orthogonalen Komplement des Kerns und man bekommt sie mit Hilfe einer QR-Zerlegung von :
- Bestimme eine QR-Zerlegung der Matrix .
- Löse durch Vorwärtseinsetzen.
- Berechne .
Auch hier ist wieder die Moore-Penrose-Pseudoinverse von und für die berechnete Lösung kleinster Norm gilt die Beziehung .
Basierend auf einem Artikel in: Wikipedia.de Seite zurück© biancahoegel.de
Datum der letzten Änderung: Jena, den: 17.02. 2021