QR-Zerlegung

Die QR-Zerlegung bringt eine Matrix durch orthogonale Transformationen in obere Dreiecksform. Anders als elementare Zeilenoperationen bewahren diese Transformationen Längen und Winkel und sind numerisch gut konditioniert.

Sei $A \in \mathbb{R}^{m \times n}$ eine rechteckige Matrix mit $m \geq n$ und $\text{Rang}A = n$ . Dann gibt es eine orthogonale Matrix $Q \in \mathbb{R}^{m \times m}$ mit $Q^T Q = I$ und eine obere Dreiecksmatrix $R \in \mathbb{R}^{m \times n}$ mit Diagonalelementen $r_{ii} > 0$ für $i = 1, \ldots, n$ , so dass:

Diese Darstellung wird als QR-Zerlegung von $A$ bezeichnet.

Die Spalten $a_j$ für $j = 1, \ldots, n$ der Matrix $A$ können mit dem Gram-Schmidt-Prozess orthonormalisiert werden:

\tilde{q}_j := a_j - \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k

Wir erhalten Orthonormalvektoren $q_j$ für $j = 1, \ldots, n$ als Spalten der orthogonalen Matrix $Q_1 \in \mathbb{R}^{m \times n}$ . Umgekehrt:

a_j = \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \tilde{q}_j

Also $A = Q_1 R_1$ mit oberer Dreiecksmatrix $R_1 \in \mathbb{R}^{n \times n}$ , deren Diagonalelemente $r_{ii} = \|\tilde{q}_i\|_2 > 0$ sind.

Wenn $Q_1$ mit $m - n$ zusätzlichen Spalten vervollständigt wird, um zur orthogonalen Matrix $Q = (Q_1 \quad Q_2) \in \mathbb{R}^{m \times m}$ zu werden, und $R_1$ zu $R = \begin{pmatrix} R_1 \\ 0 \end{pmatrix} \in \mathbb{R}^{m \times n}$ wird, dann $A = Q_1 R_1 = QR$ .

Wenn wir eine Matrix $A \in \mathbb{R}^{m \times n}$ mit $m \geq n$ haben, Es gibt zwei Möglichkeiten, die QR-Zerlegung darzustellen. Der Unterschied liegt in der Größe der verwendeten Matrizen.

Bei der vollständigen QR-Zerlegung werden Matrizen in voller Größe verwendet:

wobei $Q \in \mathbb{R}^{m \times m}$ eine orthogonale Matrix voller Größe ist und $R \in \mathbb{R}^{m \times n}$ ist eine obere Dreiecksmatrix.

Da der untere Teil der Matrix $R$ nur Nullen enthält, können wir Speicherplatz und Rechenaufwand sparen. Bei der reduzierten QR-Zerlegung werden nur die benötigten Blöcke verwendet:

A = Q \cdot R = (Q_1 \quad Q_2) \cdot \begin{pmatrix} R_1 \\ 0 \end{pmatrix} = Q_1 \cdot R_1

Hier übernimmt $Q_1 \in \mathbb{R}^{m \times n}$ nur die erste bis $n$ -te Spalte aus $Q$ und $R_1 \in \mathbb{R}^{n \times n}$ ist eine quadratische obere Dreiecksmatrix.

Die reduzierte Form spart Speicher und Rechenzeit. Anstelle der vollständigen Matrix $Q$ der Größe $m \times m$ benötigen wir nur $Q_1$ der Größe $m \times n$ .

Die nicht verwendeten Spalten der Matrix $Q_2 \in \mathbb{R}^{m \times (m-n)}$ bilden eine Orthonormalbasis von $\text{Kern}A^T$ :

A^T Q_2 = R_1^T Q_1^T Q_2 = 0

Der Kern von $A^T$ enthält genau die Vektoren $x$ , die $A^T x = 0$ erfüllen.

Die reduzierte QR-Zerlegung $A = Q_1 \cdot R_1$ mit der Bedingung $r_{ii} > 0$ für alle $i = 1, \ldots, n$ ist eindeutig für die Matrix $A$ das hat vollen Rang.

A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}=(a_1\ \,a_2)

Gram-Schmidt liefert zunächst

q_1=\frac{a_1}{\|a_1\|_2}=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}

Q_1=\begin{pmatrix}1/\sqrt2&1/\sqrt6\\1/\sqrt2&-1/\sqrt6\\0&2/\sqrt6\end{pmatrix}

Das klassische Gram-Schmidt-Verfahren liefert eine klare Herleitung, kann aber in Gleitkommaarithmetik bei nahezu linear abhängigen Spalten Orthogonalität verlieren. Das modifizierte Gram-Schmidt-Verfahren verbessert dieses Verhalten. Householder-QR ist die übliche dichte, numerisch stabile Implementierung, weil es orthogonale Reflektoren direkt anwendet.

Das Householder-Verfahren vermeidet dieses Problem durch orthogonale Spiegelungen. Eine weitere stabile Möglichkeit sind Givens-Rotationen.

Für einen Vektor $v \in \mathbb{R}^m$ mit $\|v\|_2 = 1$ , definieren wir die Householder-Matrix:

S = I - 2vv^T \in \mathbb{R}^{m \times m}

Dabei ist $vv^T$ ein dyadisches Produkt, also das Produkt des Spaltenvektors $v \in \mathbb{R}^{m \times 1}$ mit Zeilenvektor $v^T \in \mathbb{R}^{1 \times m}$ . Das Ergebnis dieser Multiplikation ist eine $m \times m$ -Matrix mit dem Rang $1$ für $v \neq 0$ . Verwechseln Sie dies nicht mit der Skalarmultiplikation $v^T v \in \mathbb{R}$ .

Sei $S = I - 2vv^T \in \mathbb{R}^{m \times m}$ eine Householder-Transformationsmatrix für Vektor $v \in \mathbb{R}^m$ mit $\|v\|_2 = 1$ . Dann gilt:

$S$ ist symmetrisch: $S^T = S$
$S$ ist eine orthogonale Matrix: $S^T S = I$
Der Ausdruck $S \cdot x$ beschreibt die Linksmultiplikation von $S$ mit dem Vektor $x \in \mathbb{R}^m$ und spiegelt $x$ am Unterraum , das heißt, in der Hyperebene mit Normalenvektor
$\text{cond}_2(S) = 1$

Für eine Matrix $A \in \mathbb{R}^{m \times n}$ mit $m \geq n$ und $\text{Rang}A = n$ wird die Matrix $A$ Spalte für Spalte durch Householder-Spiegelungen in obere Dreiecksform überführt.

Wir beginnen mit $A_1 = A$ und spiegeln die erste Spalte von $A_1$ auf ein Vielfaches des ersten Einheitsvektors:

\tilde{a}_1 \text{erste Spalte von} A_1

u_1 = \tilde{a}_1 \mp \|\tilde{a}_1\|_2 \cdot e_1

Mit der Householder-Matrix $S_1 = I_m - 2v_1v_1^T \in \mathbb{R}^{m \times m}$ erhalten wir:

A_2 = S_1 \cdot A_1 = \begin{pmatrix} r_{11} & * \\ 0 & \tilde{A}_2 \end{pmatrix}

mit $r_{11} = \pm\|\tilde{a}_1\|_2$ und $\tilde{A}_2 \in \mathbb{R}^{m-1 \times n-1}$ .

Im nächsten Schritt spiegeln wir die erste Spalte der verbleibenden Untermatrix:

\tilde{a}_2 \text{erste Spalte von} \tilde{A}_2

u_2 = \tilde{a}_2 \mp \|\tilde{a}_2\|_2 \cdot \tilde{e}_1

Die zugehörige Transformationsmatrix lautet:

\tilde{S}_2 = I_{m-1} - 2v_2v_2^T \in \mathbb{R}^{m-1 \times m-1}

A_3 = S_2 \cdot A_2 = \begin{pmatrix} r_{11} & * & * \\ 0 & r_{22} & * \\ 0 & 0 & \tilde{A}_3 \end{pmatrix}

mit $r_{22} = \pm\|\tilde{a}_2\|_2$ und $\tilde{A}_3 \in \mathbb{R}^{m-2 \times n-2}$ usw. bis:

\tilde{A}_n = \begin{pmatrix} \tilde{a}_{nn} \\ \vdots \\ \tilde{a}_{mn} \end{pmatrix} \in \mathbb{R}^{m-(n-1) \times 1}

Schließlich erhalten wir die obere Dreiecksmatrix:

A_{n+1} = R = \begin{pmatrix} r_{11} & & * \\ & \ddots & \\ 0 & & r_{nn} \\ 0 & \cdots & 0 \\ \vdots & & \vdots \\ 0 & \cdots & 0 \end{pmatrix} = S_n \cdot \ldots \cdot S_1 \cdot A = Q^T \cdot A

Somit erhalten wir die Faktorisierung:

Q = (S_n \cdot \ldots \cdot S_1)^T = S_1 \cdot \ldots \cdot S_n

wobei $Q$ eine orthogonale Matrix ist.

Das Householder-Verfahren lässt sich direkt als Iteration formulieren.

Für $i = 1, \ldots, n$ :

\tilde{a}_i = \begin{pmatrix} a_{ii} \\ \vdots \\ a_{mi} \end{pmatrix} := \begin{pmatrix} (A_i)_{ii} \\ \vdots \\ (A_i)_{mi} \end{pmatrix} \in \mathbb{R}^{m-i+1}

\sigma := \|\tilde{a}_i\|_2

\beta := \frac{2}{u_i^Tu_i}=\frac{1}{\sigma(\sigma+|\tilde a_{ii}|)}

v_i=\frac{u_i}{\|u_i\|_2}

A_{i+1} := S_i A_i = (I_m - \beta \hat{u}_i \hat{u}_i^T) A_i = A_i - \hat{u}_i (\beta \hat{u}_i^T A_i)

Schließlich erhalten wir:

Für $m\ge n$ benötigt Householder-QR ungefähr

2mn^2-\frac{2}{3}n^3\text{ Gleitkommaoperationen}

Aufgrund der orthogonalen Transformation gilt $\text{cond}_2(R) = \text{cond}_2(A)$
Die Diagonalelemente von $R$ sind die Zahlen $\pm\|\tilde{a}_i\|_2$ ab dem $i$ -ten Schritt. Wenn man die Transformation so wählt, dass alle positiv sind, erhält man die QR-Zerlegung. Wenn $\|\tilde{a}_i\|_2 = 0$ , hat $A$ nicht den vollen Rang und die Eindeutigkeitsaussage für vollen Rang gilt nicht mehr. Eine QR-Zerlegung existiert weiterhin; wenn der numerische Rang wichtig ist, eignet sich eine rangoffenbarende QR-Zerlegung mit Spaltenpivotisierung besser.

Das Vorzeichen wird so gewählt, dass numerische Auslöschung vermieden wird:
$u_i = \tilde{a}_i + s_i\|\tilde{a}_i\|_2e_1$
Statt $Q$ vollständig zu konstruieren, genügt es, die für jede Spiegelung benötigten Informationen zu speichern:

$\text{Speichere den Householder-Vektor }u_i$

Dieser Vektor passt in den freien Bereich von $A$ unterhalb der Diagonale; die Diagonalelemente werden separat gespeichert.
Für die reduzierte QR-Zerlegung werden die nicht benötigten Spalten von $Q$ und die zugehörigen Nullzeilen von $R$ weggelassen.

\text{Span}(v)^{\perp}

s_i=1\text{ für }\tilde a_{ii}\ge0,\qquad s_i=-1\text{ sonst}

QR-Zerlegung

Existenzsatz der QR-Zerlegung

QR-Zerlegung

Existenzsatz der QR-Zerlegung

Beweis mit Gram-Schmidt

Vollständige und reduzierte QR-Zerlegung

Vollständige QR-Zerlegung

Eökonomische QR-Zerlegung

Eindeutigkeit

Beispiel einer dünnen QR-Zerlegung

Householder-Methode zur QR-Zerlegung

Householder-Transformation

Eigenschaften der Householder-Transformation

Householder-Verfahren

Iterativer Transformationsprozess

Implementierungsalgorithmus

Numerische Eigenschaften und Aufwand

Rechenkomplexität

Numerische Eigenschaften