QR-Zerlegung

Die QR-Zerlegung oder QR-Faktorisierung beschreibt die Zerlegung einer Matrix \(\displaystyle A\) in das Produkt
\(\displaystyle A = Q\cdot R\)
zweier anderer Matrizen, wobei \(\displaystyle Q\) eine orthogonale \(\displaystyle (QQ^T=I)\) bzw. unitäre Matrix \(\displaystyle (QQ^*=I)\) und \(\displaystyle R\) eine obere Dreiecksmatrix ist.
Eine solche Zerlegung existiert stets und kann mit verschiedenen numerischen Algorithmen berechnet werden, wie z.B.:
 
 

Definition

Eine Matrix \(\displaystyle A \in \R^{m\times n},\, m \geq n\) besitzt eine (fast - siehe weiter unten) eindeutige reduzierte QR-Zerlegung
\(\displaystyle A=\hat{Q}\cdot\hat{R}\)
als Produkt einer in den Spalten orthogonalen Matrix \(\displaystyle \hat{Q} \in \R^{m\times n}\) und einer oberen Dreiecksmatrix \(\displaystyle \hat{R} \in \R^{n\times n}\).
Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung
\(\displaystyle A = Q\cdot R\),
indem man \(\displaystyle \hat{Q}\) mit weiteren orthogonalen Spalten \(\displaystyle \tilde{Q}\) zu einer quadratischen \(\displaystyle m \times m\)-Matrix erweitert, und an \(\displaystyle \hat{R}\) unten Nullen anfügt, so dass eine \(\displaystyle m\times n\)-Matrix entsteht:
\(\displaystyle Q\cdot R = (\hat{Q} \tilde{Q}) \cdot \begin{pmatrix} \hat{R} \\ 0 \end{pmatrix} = \hat{Q}\cdot\hat{R}\)
Die QR Zerlegung ist eindeutig für \(\displaystyle m \geq n\) und \(\displaystyle \rang(A)=n\) wenn man die Vorzeichen der Diagonalelemente von \(\displaystyle R, \hat{R}\) 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 eines linearen Gleichungssystems

Um die Lösung \(\displaystyle x\in\R^n\) eines linearen Gleichungssystems
\(\displaystyle Ax = b\)
zu bestimmen, sind folgende drei Schritte durchzuführen:
  1. Bestimme eine \(\displaystyle QR\)-Zerlegung der Matrix \(\displaystyle A\).
  2. Berechne \(\displaystyle z = Q^Tb\).
  3. Löse \(\displaystyle Rx = z\) durch Rückwärtseinsetzen.

Alle Pädagogen sind sich darin einig: man muß vor allem tüchtig Mathematik treiben, weil ihre Kenntnis fürs Leben größten direkten Nutzen gewährt.

Felix Klein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel QR-Zerlegung aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе