QR-Zerlegung und Gram-Schmidt

Eine Orthonormalbasis bauen

Orthonormale Spalten sind die bravsten, die eine Matrix haben kann: $Q^{T}Q=I$ , also erhält $Q$ Längen und Winkel und verstärkt Fehler nie. Gram-Schmidt macht aus beliebigen unabhängigen Spalten $\mathbf{a}_1,\dots,\mathbf{a}_n$ orthonormale: Nehmen Sie $\mathbf{q}_1=\mathbf{a}_1/\|\mathbf{a}_1\|$ , ziehen Sie dann von jeder weiteren Spalte ihre Projektionen auf die bereits gefundenen $\mathbf{q}$ ab und normieren Sie den Rest.

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Hält man die verwendeten Zahlen fest, erhält man die QR-Zerlegung: $Q$ trägt die orthonormalen Spalten, $R$ ist obere Dreiecksmatrix mit $R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j$ und den Längen $R_{jj}$ auf der Diagonale. Für kleinste Quadrate wird $\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|$ durch $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$ minimiert, ein Dreieckssystem, das per Rückwärtseinsetzen gelöst wird, ohne je $A^{T}A$ zu bilden. Darum gilt $\kappa(R)=\kappa(A)$ statt $\kappa(A)^2$ .

Gram-Schmidt mit zwei SpaltenSei

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

mit den Spalten

\mathbf{a}_1=(3,4)

und

\mathbf{a}_2=(1,2)

. Dann ist

R_{11}=\|\mathbf{a}_1\|=5

und

\mathbf{q}_1=(0{,}6;\ 0{,}8)

. Weiter

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2{,}2

, und

\mathbf{a}_2-2{,}2\,\mathbf{q}_1=(-0{,}32;\ 0{,}24)

hat die Länge

R_{22}=0{,}4

, also

\mathbf{q}_2=(-0{,}8;\ 0{,}6)

. Somit

Q=\begin{pmatrix}0{,}6&-0{,}8\\0{,}8&0{,}6\end{pmatrix}

und

R=\begin{pmatrix}5&2{,}2\\0&0{,}4\end{pmatrix}

. Probe:

\det A=2=\det R

Q: orthonormale Spalten, $Q^{T}Q=I$ , keine Fehlerverstärkung.
R: obere Dreiecksmatrix; ihre Diagonale enthält die Längen, die nach Abzug früherer Richtungen bleiben.
Modifiziertes Gram-Schmidt (oder Householder-Spiegelungen in Bibliotheken) hält $Q$ in Gleitkommazahlen orthogonal; die Lehrbuchversion verliert bei fast abhängigen Spalten die Orthogonalität.

Warum Bibliotheken QR für die Regression nutzenRegressoren in der Finanzwelt sind oft nahezu kollinear (viele korrelierte Faktoren, Polynomterme). Die Normalgleichungen würden diese Konditionszahl quadrieren und stillschweigend Unsinn liefern, während QR (oder die SVD) damit zurechtkommt. Das ist der Algorithmus hinter den Kleinste-Quadrate-Routinen von NumPy und statsmodels und der, den Sie im Abschlussprojekt bauen.

Lab: Was bewertet wird

Der erste Diagonaleintrag10 Pkt.
Die Matrix Q20 Pkt.
Die Matrix R20 Pkt.
Eine Determinante aus R15 Pkt.
Kleinste Quadrate mit QR15 Pkt.
Warum QR genauer ist20 Pkt.

Eine Orthonormalbasis bauen

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

Gram-Schmidt mit zwei SpaltenSei

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

mit den Spalten

\mathbf{a}_1=(3,4)

und

\mathbf{a}_2=(1,2)

. Dann ist

R_{11}=\|\mathbf{a}_1\|=5

und

\mathbf{q}_1=(0{,}6;\ 0{,}8)

. Weiter

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2{,}2

, und

\mathbf{a}_2-2{,}2\,\mathbf{q}_1=(-0{,}32;\ 0{,}24)

hat die Länge

R_{22}=0{,}4

, also

\mathbf{q}_2=(-0{,}8;\ 0{,}6)

. Somit

Q=\begin{pmatrix}0{,}6&-0{,}8\\0{,}8&0{,}6\end{pmatrix}

und

R=\begin{pmatrix}5&2{,}2\\0&0{,}4\end{pmatrix}

. Probe:

\det A=2=\det R

Q: orthonormale Spalten, $Q^{T}Q=I$ , keine Fehlerverstärkung.
R: obere Dreiecksmatrix; ihre Diagonale enthält die Längen, die nach Abzug früherer Richtungen bleiben.
Modifiziertes Gram-Schmidt (oder Householder-Spiegelungen in Bibliotheken) hält $Q$ in Gleitkommazahlen orthogonal; die Lehrbuchversion verliert bei fast abhängigen Spalten die Orthogonalität.

Lab: Was bewertet wird

Der erste Diagonaleintrag10 Pkt.
Die Matrix Q20 Pkt.
Die Matrix R20 Pkt.
Eine Determinante aus R15 Pkt.
Kleinste Quadrate mit QR15 Pkt.
Warum QR genauer ist20 Pkt.

Eine Orthonormalbasis bauen

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.

QR-Zerlegung und Gram-Schmidt

Eine Orthonormalbasis bauen

Lab: Was bewertet wird

Melde dich an, um deinen Code auszuführen.