QR-Faktorisierung

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 (QQ^T = I) bzw. unitäre Matrix (QQ ^* = I) und R eine obere Dreiecksmatrix ist.

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

• Householdertransformationen
• Givens-Rotationen
• Gram-Schmidtsches Orthogonalisierungsverfahren.

Das letztere wird üblicherweise in der linearen Algebra benutzt, ist aber numerisch instabil. Man kann das Verfahren aber erweitern und numerisch stabilisieren.

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 $m \geq n$ und Rang(A) = n wenn man die Vorzeichen der Diagonalelemente von $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 regulärer oder überbestimmter Gleichungssysteme

Um die Lösung $x\in\R^n$ eines linearen Gleichungssystems mit Matrix $A\in\R^{m\times n},\ m\ge n$,

Ax = b von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:

1. Bestimme eine QR-Zerlegung der Matrix A.
2. Berechne $z = Q^Tb\in\R^n$, üblicherweise unter Benutzung der Faktorisierung von Q aus Schritt 1.
3. Löse Rx = z durch Rückwärtseinsetzen.

Für m = n ist dies eine Alternative zur LR-Zerlegung, sie hat den doppelten Aufwand der LR-Zerlegung, ist aber möglicherweise numerisch stabiler. Im Fall m > n gibt es im Gleichungssystem mehr Gleichungen als Variablen und x ist die Lösung des Ausgleichproblems nach der Methode der kleinsten Quadrate (s. auch Regressionsanalyse):

Minimiere $\|Ax-b\|^2=\sum_{j=1}^m\left(\sum_{k=1}^n a_{jk}x_k-b_j\right)^2$.

In diesem Fall ist A ⁺ = R ^{− 1}Q^T die Moore-Penrose-Pseudoinverse von A und für die berechnete Kleinste-Quadrate-Lösung x gilt die Beziehung x = A ⁺ b, die die übliche Darstellung x = A ^{− 1}b des regulären Falls m = n verallgemeinert.

Lösung unterbestimmter Gleichungssysteme

Für m < n hat die Matrix A einen nichttrivialen Kern. Bei vollem Rang von A bilden die Lösungen des Gleichungssystems Ax=b 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 A^T:

1. Bestimme eine QR-Zerlegung der Matrix A^T = QR.
2. Löse $R^T z = b\in\R^m$ durch Vorwärtseinsetzen.
3. Berechne $x = Qz\in\R^n$.

Auch hier ist wieder A ⁺ = Q(R^T) ^{− 1} die Moore-Penrose-Pseudoinverse von A und für die berechnete Lösung kleinster Norm gilt die Beziehung x = A ⁺ b.