QR-Zerlegung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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 $A$ in das Produkt

$A = Q\cdot R$

zweier anderer Matrizen, wobei Q eine orthogonale ( $Q Q T = I$ ) bzw. unitäre Matrix ( $Q Q * = I$ ) und R eine obere Dreiecksmatrix ist.

Eine solche Zerlegung existiert stets und kann mit verschiedenen numerischen Algorithmen berechnet werden. Die bekanntesten davon sind

Das letztere ist nur von theoretischer Bedeutung, weil es numerisch instabil ist. Man kann das Verfahren aber erweitern und numerisch stabilisieren.

[Bearbeiten] Definition

Eine Matrix $A \in \R^{m\times n}$ , $m \geq n$ besitzt eine (fast - siehe weiter unten) eindeutige reduzierte QR-Zerlegung

$A=\hat{Q}\cdot\hat{R}$

als Produkt einer in den Spalten orthogonalen Matrix $\hat{Q} \in \R^{m\times n}$ und einer oberen Dreiecksmatrix $\hat{R} \in \R^{n\times n}$ .

Diese Lösung ist erweiterbar zu einer vollständigen QR-Zerlegung

$A = Q\cdot R$ ,

indem man $\hat{Q}$ mit weiteren orthogonalen Spalten $\tilde{Q}$ zu einer quadratischen $m \times m$ -Matrix erweitert, und an $\hat{R}$ unten Nullen anfügt, so dass eine $m\times n$ -Matrix entsteht:

$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 $n \geq m$ und Rang(A)=m wenn man die Vorzeichen der Diagonalelemente von $R, \hat{R}$ vorgibt. (Üblicherweise wählt man alle positiv)

[Bearbeiten] 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.