# QR-Zerlegung
> For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`.
URL: https://nakafa.com/de/faecher/ki-und-data-science/lineare-methoden-der-ki/qr-zerlegung
Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/qr-decomposition/de.mdx
QR-Zerlegung mit Gram-Schmidt- und Householder-Verfahren. Volle und reduzierte Faktorisierung, numerische Stabilität und Rechenaufwand werden hergeleitet.
---
## Existenzsatz der 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:
Visible text: Sei eine rechteckige Matrix mit und . Dann gibt es eine orthogonale Matrix mit und eine obere Dreiecksmatrix mit Diagonalelementen für , so dass:
```math
A = Q \cdot R
```
Diese Darstellung wird als QR-Zerlegung von $$A$$ bezeichnet.
Visible text: Diese Darstellung wird als QR-Zerlegung von bezeichnet.
### Beweis mit Gram-Schmidt
Die Spalten $$a_j$$ für $$j = 1, \ldots, n$$ der Matrix $$A$$ können mit dem Gram-Schmidt-Prozess orthonormalisiert werden:
Visible text: Die Spalten für der Matrix können mit dem Gram-Schmidt-Prozess orthonormalisiert werden:
Component: MathContainer
Children:
```math
\tilde{q}_j := a_j - \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k
```
```math
q_j := \frac{\tilde{q}_j}{\|\tilde{q}_j\|_2}
```
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:
Visible text: Wir erhalten Orthonormalvektoren für als Spalten der orthogonalen Matrix . Umgekehrt:
Component: MathContainer
Children:
```math
a_j = \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \tilde{q}_j
```
```math
= \sum_{k=1}^{j-1} \langle a_j, q_k \rangle \cdot q_k + \|\tilde{q}_j\|_2 \cdot q_j
```
```math
= \sum_{k=1}^{j-1} q_k \cdot r_{kj} + q_j \cdot r_{jj}
```
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.
Visible text: Also mit oberer Dreiecksmatrix , deren Diagonalelemente 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$$.
Visible text: Wenn mit zusätzlichen Spalten vervollständigt wird, um zur orthogonalen Matrix zu werden, und zu wird, dann .
## Vollständige und reduzierte QR-Zerlegung
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.
Visible text: Wenn wir eine Matrix mit haben,
Es gibt zwei Möglichkeiten, die QR-Zerlegung darzustellen. Der Unterschied liegt in der Größe der verwendeten Matrizen.
### Vollständige QR-Zerlegung
Bei der vollständigen QR-Zerlegung werden Matrizen in voller Größe verwendet:
```math
A = Q \cdot R
```
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.
Visible text: wobei eine orthogonale Matrix voller Größe ist und
ist eine obere Dreiecksmatrix.
### Eökonomische QR-Zerlegung
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:
Visible text: Da der untere Teil der Matrix nur Nullen enthält, können wir Speicherplatz und Rechenaufwand sparen.
Bei der reduzierten QR-Zerlegung werden nur die benötigten Blöcke verwendet:
```math
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.
Visible text: Hier übernimmt nur die erste bis -te Spalte
aus und 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$$.
Visible text: Die reduzierte Form spart Speicher und Rechenzeit.
Anstelle der vollständigen Matrix der Größe
benötigen wir nur der Größe .
Die nicht verwendeten Spalten der Matrix $$Q_2 \in \mathbb{R}^{m \times (m-n)}$$ bilden
eine Orthonormalbasis von $$\text{Kern}A^T$$:
Visible text: Die nicht verwendeten Spalten der Matrix bilden
eine Orthonormalbasis von :
```math
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.
Visible text: Der Kern von enthält genau die Vektoren , die erfüllen.
### Eindeutigkeit
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.
Visible text: Die reduzierte QR-Zerlegung mit der Bedingung
für alle ist eindeutig für die Matrix
das hat vollen Rang.
## Beispiel einer dünnen QR-Zerlegung
Sei
```math
A=\begin{pmatrix}1&1\\1&0\\0&1\end{pmatrix}=(a_1\ \,a_2)
```
Gram-Schmidt liefert zunächst
Component: MathContainer
Children:
```math
q_1=\frac{a_1}{\|a_1\|_2}=\frac1{\sqrt2}\begin{pmatrix}1\\1\\0\end{pmatrix}
```
```math
r_{12}=q_1^Ta_2=\frac1{\sqrt2}
```
```math
\widetilde q_2=a_2-r_{12}q_1=\begin{pmatrix}1/2\\-1/2\\1\end{pmatrix}
```
```math
q_2=\frac1{\sqrt6}\begin{pmatrix}1\\-1\\2\end{pmatrix}
```
Damit gilt
Component: MathContainer
Children:
```math
Q_1=\begin{pmatrix}1/\sqrt2&1/\sqrt6\\1/\sqrt2&-1/\sqrt6\\0&2/\sqrt6\end{pmatrix}
```
```math
R_1=\begin{pmatrix}\sqrt2&1/\sqrt2\\0&\sqrt6/2\end{pmatrix}
```
```math
Q_1^TQ_1=I,\qquad Q_1R_1=A
```
## Householder-Methode zur QR-Zerlegung
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.
### Householder-Transformation
Für einen Vektor $$v \in \mathbb{R}^m$$ mit $$\|v\|_2 = 1$$,
definieren wir die Householder-Matrix:
Visible text: Für einen Vektor mit ,
definieren wir die Householder-Matrix:
```math
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}$$.
Visible text: Dabei ist ein dyadisches Produkt, also das Produkt des Spaltenvektors
mit Zeilenvektor .
Das Ergebnis dieser Multiplikation ist eine -Matrix mit dem Rang für .
Verwechseln Sie dies nicht mit der Skalarmultiplikation .
## Eigenschaften der Householder-Transformation
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:
Visible text: Sei eine Householder-Transformationsmatrix
für Vektor mit . Dann gilt:
1. $$S$$ ist symmetrisch: $$S^T = S$$
2. $$S$$ ist eine orthogonale Matrix: $$S^T S = I$$
3. Der Ausdruck $$S \cdot x$$ beschreibt die Linksmultiplikation von $$S$$ mit dem Vektor $$x \in \mathbb{R}^m$$ und
spiegelt $$x$$ am Unterraum $$\text{Span}(v)^{\perp}$$,
das heißt, in der Hyperebene mit Normalenvektor $$v$$
4. $$\text{cond}_2(S) = 1$$
Visible text: 1. ist symmetrisch:
2. ist eine orthogonale Matrix:
3. Der Ausdruck beschreibt die Linksmultiplikation von mit dem Vektor und
spiegelt am Unterraum ,
das heißt, in der Hyperebene mit Normalenvektor
4.
## Householder-Verfahren
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.
Visible text: Für eine Matrix mit
und wird die Matrix 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:
Visible text: Wir beginnen mit und spiegeln die erste Spalte von
auf ein Vielfaches des ersten Einheitsvektors:
Component: MathContainer
Children:
```math
\tilde{a}_1 \text{erste Spalte von} A_1
```
```math
\pm\|\tilde{a}_1\|_2 \cdot e_1 \in \mathbb{R}^m \text{Zielvektor}
```
```math
v_1 = u_1/\|u_1\|_2 \text{mit} \text{Span}(v_1)^{\perp}
```
```math
u_1 = \tilde{a}_1 \mp \|\tilde{a}_1\|_2 \cdot e_1
```
### Iterativer Transformationsprozess
Mit der Householder-Matrix $$S_1 = I_m - 2v_1v_1^T \in \mathbb{R}^{m \times m}$$ erhalten wir:
Visible text: Mit der Householder-Matrix erhalten wir:
```math
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}$$.
Visible text: mit und .
Im nächsten Schritt spiegeln wir die erste Spalte der verbleibenden Untermatrix:
Component: MathContainer
Children:
```math
\tilde{a}_2 \text{erste Spalte von} \tilde{A}_2
```
```math
\pm\|\tilde{a}_2\|_2 \cdot \tilde{e}_1 \in \mathbb{R}^{m-1}
```
```math
v_2 = u_2/\|u_2\|_2
```
```math
u_2 = \tilde{a}_2 \mp \|\tilde{a}_2\|_2 \cdot \tilde{e}_1
```
Die zugehörige Transformationsmatrix lautet:
Component: MathContainer
Children:
```math
\tilde{S}_2 = I_{m-1} - 2v_2v_2^T \in \mathbb{R}^{m-1 \times m-1}
```
```math
S_2 = \begin{pmatrix} I_1 & 0 \\ 0 & \tilde{S}_2 \end{pmatrix} \in \mathbb{R}^{m \times m}
```
Wir erhalten:
```math
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:
Visible text: mit und usw. bis:
```math
\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:
```math
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:
Component: MathContainer
Children:
```math
A = Q \cdot R
```
```math
Q = (S_n \cdot \ldots \cdot S_1)^T = S_1 \cdot \ldots \cdot S_n
```
wobei $$Q$$ eine orthogonale Matrix ist.
Visible text: wobei eine orthogonale Matrix ist.
## Implementierungsalgorithmus
Das Householder-Verfahren lässt sich direkt als Iteration formulieren.
Initialisierung:
Component: MathContainer
Children:
```math
A_1 := A
```
```math
Q_1 := I
```
Für $$i = 1, \ldots, n$$:
Visible text: Für :
```math
\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}
```
Berechnung:
Component: MathContainer
Children:
```math
\sigma := \|\tilde{a}_i\|_2
```
```math
s_i:=\begin{cases}1,&\tilde a_{ii}\ge0,\\-1,&\tilde a_{ii}<0,\end{cases}
```
```math
u_i := \tilde{a}_i+s_i\sigma e_1 \in \mathbb{R}^{m-i+1}
```
```math
\hat{u}_i := \begin{pmatrix} 0 \\ \vdots \\ 0 \\ u_i \end{pmatrix} \in \mathbb{R}^m
```
und:
```math
\beta := \frac{2}{u_i^Tu_i}=\frac{1}{\sigma(\sigma+|\tilde a_{ii}|)}
```
Dann:
Component: MathContainer
Children:
```math
v_i=\frac{u_i}{\|u_i\|_2}
```
```math
\tilde{S}_i = I_{m-i+1} - 2v_i v_i^T = I_{m-i+1} - \beta u_i u_i^T
```
```math
S_i = I_m - \beta \hat{u}_i \hat{u}_i^T
```
Wir erhalten also:
Component: MathContainer
Children:
```math
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)
```
```math
Q_{i+1} := Q_i S_i = Q_i (I_m - \beta \hat{u}_i \hat{u}_i^T) = Q_i - (Q_i \hat{u}_i) \beta \hat{u}_i^T
```
Schließlich erhalten wir:
Component: MathContainer
Children:
```math
R := A_{n+1}
```
```math
Q := Q_{n+1}
```
## Numerische Eigenschaften und Aufwand
### Rechenkomplexität
Für $$m\ge n$$ benötigt Householder-QR ungefähr
Visible text: Für benötigt Householder-QR ungefähr
Component: MathContainer
Children:
```math
2mn^2-\frac{2}{3}n^3\text{ Gleitkommaoperationen}
```
```math
\frac{4}{3}n^3\text{ Gleitkommaoperationen für }m=n
```
### Numerische Eigenschaften
1. Aufgrund der orthogonalen Transformation gilt $$\text{cond}_2(R) = \text{cond}_2(A)$$
2. 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:
```math
u_i = \tilde{a}_i + s_i\|\tilde{a}_i\|_2e_1
```
```math
s_i=1\text{ für }\tilde a_{ii}\ge0,\qquad s_i=-1\text{ sonst}
```
3. Statt $$Q$$ vollständig zu konstruieren, genügt es, die für jede Spiegelung benötigten Informationen zu speichern:
```math
\text{Speichere den Householder-Vektor }u_i
```
Dieser Vektor passt in den freien Bereich von $$A$$ unterhalb der Diagonale; die Diagonalelemente werden separat gespeichert.
4. Für die reduzierte QR-Zerlegung werden die nicht benötigten Spalten von $$Q$$ und die zugehörigen Nullzeilen von $$R$$ weggelassen.
Visible text: 1. Aufgrund der orthogonalen Transformation gilt
2. Die Diagonalelemente von sind die Zahlen
ab dem -ten Schritt. Wenn man die Transformation so wählt, dass alle positiv sind, erhält man die QR-Zerlegung.
Wenn , hat 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:
3. Statt vollständig zu konstruieren, genügt es, die für jede Spiegelung benötigten Informationen zu speichern:
Dieser Vektor passt in den freien Bereich von unterhalb der Diagonale; die Diagonalelemente werden separat gespeichert.
4. Für die reduzierte QR-Zerlegung werden die nicht benötigten Spalten von und die zugehörigen Nullzeilen von weggelassen.