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 ${\displaystyle A}$ in das Produkt

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

zweier anderer Matrizen, wobei ${\displaystyle Q}$ eine orthogonale bzw. unitäre Matrix und ${\displaystyle R}$ 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

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

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

Jede reelle Matrix ${\displaystyle A\in \mathbb {R} ^{m\times n}}$, ${\displaystyle 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 \mathbb {R} ^{m\times n}}$ und einer oberen Dreiecksmatrix ${\displaystyle {\hat {R}}\in \mathbb {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 Nullzeilen anfügt, so dass als Matrixprodukt eine ${\displaystyle m\times n}$-Matrix entsteht:

${\displaystyle Q\cdot R={\begin{pmatrix}{\hat {Q}}&{\tilde {Q}}\end{pmatrix}}\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 \operatorname {Rang} (A)=n}$, wenn man die Vorzeichen der Diagonalelemente von ${\displaystyle R,{\hat {R}}}$ vorgibt – üblicherweise wählt man alle positiv.

Anmerkungen: Eine reelle Matrix ${\displaystyle Q}$ heißt orthogonal, wenn das Matrixprodukt mit ihrer transponierten Matrix ${\displaystyle Q^{T}}$ die Einheitsmatrix ${\displaystyle I}$ ergibt, also ${\displaystyle Q^{T}Q=I}$ ist. Im allgemeineren Fall einer komplexen Matrix ${\displaystyle A}$ ist die Matrix ${\displaystyle Q}$ eine unitäre Matrix, das heißt, das Matrixprodukt mit ihrer adjungierten Matrix ${\displaystyle Q^{H}={\overline {Q}}^{T}={\overline {Q^{T}}}}$ ergibt die Einheitsmatrix ${\displaystyle I}$, also ${\displaystyle Q^{H}Q=I}$.

Beispiel

Für die reelle Matrix ${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}$ ergibt sich die QR-Zerlegung

${\displaystyle Q={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}}$, ${\displaystyle R={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}}$,

denn es gilt:

${\displaystyle QR={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}{\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}=A}$

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 und der Unterraumiteration zur Berechnung von Eigenwerten einer Matrix.

Lösung regulärer oder überbestimmter Gleichungssysteme

Um die Lösung ${\displaystyle x\in \mathbb {R} ^{n}}$ eines linearen Gleichungssystems ${\displaystyle Ax=b}$ mit Matrix ${\displaystyle A\in \mathbb {R} ^{m\times n},\ m\geq n}$ von vollem Rang zu bestimmen, sind folgende drei Schritte durchzuführen:

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

Für ${\displaystyle 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 ${\displaystyle m>n}$ gibt es im Gleichungssystem mehr Gleichungen als Variablen und es liegt ein überbestimmtes Gleichungssystem vor. Hier wird ${\displaystyle x}$ durch Lösung des Ausgleichproblems nach der Methode der kleinsten Quadrate (s. auch Regressionsanalyse) bestimmt:

Minimiere ${\displaystyle \|Ax-b\|^{2}=\sum _{j=1}^{m}\left(\sum _{k=1}^{n}a_{jk}x_{k}-b_{j}\right)^{2}}$.

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

Lösung unterbestimmter Gleichungssysteme

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

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

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

Literatur

• Martin Hermann: Numerische Mathematik, Band 2: Analytische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065765-4.
• Gene H. Golub and Charles F. van Loan: Matrix Computations. 3. Auflage. The Johns Hopkins University Press, Baltimore and London 1996.
• G. W. Stewart: Matrix Algorithms, Vol. 1: Basic Decompositions. Society for Industrial and Applied Mathematics, Philadelphia 1998.
• Lloyd N. Trefethen and David Bau, III: Numerical Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia 1997.

Weblinks

• QR-Zerlegungs-Rechner: Berechnet die QR-Zerlegung einer Matrix mittels Householdertransformation
• LP: QR-Zerlegung für lineare Ausgleichsprobleme, Georg-August-Universität Göttingen
• taramath Online-Tool zur Berechnung der QR-Zerlegung reeller Matrizen.