QR-Zerlegung

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

Definition

Eine Matrix A∈Rm×n, m≥nA \in \R^{m\times n},\, m \geq n besitzt eine (fast - siehe weiter unten) eindeutige reduzierte QR-Zerlegung
A=Q^⋅R^A=\hat{Q}\cdot\hat{R}
als Produkt einer in den Spalten orthogonalen Matrix Q^∈Rm×n\hat{Q} \in \R^{m\times n} und einer oberen Dreiecksmatrix R^∈Rn×n\hat{R} \in \R^{n\times n}.
Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung
A=Q⋅RA = Q\cdot R,
indem man Q^\hat{Q} mit weiteren orthogonalen Spalten Q~\tilde{Q} zu einer quadratischen m×mm \times m-Matrix erweitert, und an R^\hat{R} unten Nullen anfügt, so dass eine m×nm\times n-Matrix entsteht:
Q⋅R=(Q^Q~)⋅(R^0)=Q^⋅R^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 m≥nm \geq n und rang⁡(A)=n\rang(A)=n wenn man die Vorzeichen der Diagonalelemente von R,R^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 x∈Rnx\in\R^n eines linearen Gleichungssystems
Ax=bAx = b
zu bestimmen, sind folgende drei Schritte durchzuführen:
  1. Bestimme eine QRQR-Zerlegung der Matrix AA.
  2. Berechne z=QTbz = Q^Tb.
  3. Löse Rx=zRx = z durch Rückwärtseinsetzen.

Man darf nicht das, was uns unwahrscheinlich und unnatürlich erscheint, mit dem verwechseln, was absolut unmöglich ist.

Carl Friedrich Gauß

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е
Datenschutzerklärung

 

Numerische Verfahren