Décomposition QR et Gram-Schmidt

Construire une base orthonormée

Les colonnes orthonormées sont les mieux élevées qu'une matrice puisse avoir : $Q^{T}Q=I$ , donc $Q$ conserve longueurs et angles et n'amplifie jamais les erreurs. Gram-Schmidt transforme toutes colonnes indépendantes $\mathbf{a}_1,\dots,\mathbf{a}_n$ en colonnes orthonormées : prenez $\mathbf{q}_1=\mathbf{a}_1/\|\mathbf{a}_1\|$ , puis, pour chaque colonne suivante, retranchez ses projections sur les $\mathbf{q}$ déjà trouvés et normalisez ce qui reste.

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)

Conserver les nombres employés donne la décomposition QR : $Q$ porte les colonnes orthonormées et $R$ est triangulaire supérieure, avec $R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j$ et les longueurs $R_{jj}$ sur la diagonale. Pour les moindres carrés, $\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|$ est minimisée par $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$ , un système triangulaire résolu par substitution arrière, sans jamais former $A^{T}A$ . C'est pourquoi $\kappa(R)=\kappa(A)$ au lieu de $\kappa(A)^2$ .

Gram-Schmidt sur deux colonnesPrenons

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

, de colonnes

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

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

. Alors

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

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

. Ensuite

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

, et

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

a pour longueur

R_{22}=0{,}4

, donc

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

. Ainsi

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

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

. Vérification :

\det A=2=\det R

Q : colonnes orthonormées, $Q^{T}Q=I$ , aucune amplification d'erreur.
R : triangulaire supérieure ; sa diagonale contient les longueurs restantes après retrait des directions précédentes.
Gram-Schmidt modifié (ou réflexions de Householder dans les bibliothèques) garde $Q$ orthogonale en virgule flottante ; la version classique perd l'orthogonalité sur des colonnes presque dépendantes.

Pourquoi les bibliothèques utilisent QR pour la régressionLes régresseurs en finance sont souvent presque colinéaires (nombreux facteurs corrélés, termes polynomiaux). Les équations normales mettraient ce conditionnement au carré et renverraient discrètement n'importe quoi, alors que QR (ou la SVD) s'en sort. C'est l'algorithme derrière les routines de moindres carrés de NumPy et statsmodels, et celui que vous construirez dans le projet final.

Lab : ce qui est noté

Le premier terme diagonal10 pts
La matrice Q20 pts
La matrice R20 pts
Un déterminant à partir de R15 pts
Moindres carrés avec QR15 pts
Pourquoi QR est plus précis20 pts

Construire une base orthonormée

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 sur deux colonnesPrenons

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

, de colonnes

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

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

. Alors

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

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

. Ensuite

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

, et

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

a pour longueur

R_{22}=0{,}4

, donc

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

. Ainsi

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

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

. Vérification :

\det A=2=\det R

Q : colonnes orthonormées, $Q^{T}Q=I$ , aucune amplification d'erreur.
R : triangulaire supérieure ; sa diagonale contient les longueurs restantes après retrait des directions précédentes.
Gram-Schmidt modifié (ou réflexions de Householder dans les bibliothèques) garde $Q$ orthogonale en virgule flottante ; la version classique perd l'orthogonalité sur des colonnes presque dépendantes.

Lab : ce qui est noté

Le premier terme diagonal10 pts
La matrice Q20 pts
La matrice R20 pts
Un déterminant à partir de R15 pts
Moindres carrés avec QR15 pts
Pourquoi QR est plus précis20 pts

Décomposition QR et Gram-Schmidt

Construire une base orthonormée

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

Décomposition QR et Gram-Schmidt

Construire une base orthonormée

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.