Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Apprendre Introduction à la Décomposition de Matrices | Fondements de l'Algèbre Linéaire
Mathématiques pour la Science des Données

bookIntroduction à la Décomposition de Matrices

La résolution de systèmes tels que Ax⃗=b⃗A \vec{x} = \vec{b} peut être coûteuse en calcul, en particulier pour les grands systèmes.

La décomposition matricielle simplifie ce processus en découpant la matrice AA en parties plus simples – que l’on peut ensuite résoudre par étapes.

LU vs QR

On décompose la matrice AA en d’autres matrices structurées.

Décomposition LU

Décomposer AA en une matrice triangulaire inférieure et supérieure :

  • Construite à l’aide de l’élimination de Gauss ;
  • Fonctionne mieux pour les matrices carrées.
A=LUA = LU

Décomposition QR

Décomposer AA en une matrice orthogonale et une matrice supérieure :

  • Souvent utilisée pour les matrices non carrées ;
  • Idéale pour les problèmes des moindres carrés ou lorsque la décomposition LU échoue.
A=QRA = QR

Décomposition LU

Commencer avec une matrice carrée :

A=[4363]A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

L’objectif est d’écrire ceci comme :

A=LUA = LU

Où :

L=[10l211],  U=[u11u120u22]L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Cette décomposition est possible si A est carrée et inversible.

Points importants :

  • Les matrices triangulaires inférieures ont toutes les entrées au-dessus de la diagonale nulles, ce qui simplifie la substitution avant ;
  • Les matrices triangulaires supérieures ont des zéros sous la diagonale, ce qui rend la substitution arrière directe ;
  • Une matrice orthogonale possède des colonnes qui sont des vecteurs orthonormés (vecteurs de norme 1 et perpendiculaires) ;
  • Cette propriété préserve la longueur et les angles des vecteurs, ce qui est utile pour résoudre les moindres carrés et améliorer la stabilité numérique.

Élimination de Gauss

Appliquer l'élimination de Gauss pour éliminer l'entrée sous le pivot en haut à gauche :

R2→R2−64R1R_2 \rarr R_2 - \frac{6}{4}R_1

Cela donne :

R2′=[0,−1.5]R'_2 = [0, -1.5]

Les matrices mises à jour deviennent donc :

U=[430−1.5]U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Et à partir de notre opération sur les lignes, nous savons :

L=[101.51]L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Points importants :

  • L'élimination de Gauss élimine systématiquement les entrées sous l'élément pivot de chaque colonne en soustrayant des versions multipliées de la ligne pivot aux lignes en dessous ;
  • Ce processus transforme A en une matrice triangulaire supérieure U ;
  • Les multiplicateurs utilisés pour éliminer ces entrées sont stockés dans L, ce qui permet de représenter A comme le produit LU.

Résultat de la décomposition LU

Nous vérifions :

A=LU=[101.51][430−1.5]=[4363]A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Le système Ax⃗=b⃗A \vec{x} = \vec{b} peut maintenant être résolu en deux étapes :

  1. Résoudre Ly⃗=b⃗L \vec{y} = \vec{b} par substitution avant ;
  2. Résoudre Ux⃗=y⃗U \vec{x} = \vec{y} par substitution arrière.

Décomposition QR

On souhaite exprimer une matrice AA comme le produit de deux matrices :

A=QRA = QR

Où :

  • AA est la matrice d'entrée (par exemple, données, coefficients, etc.) ;
  • QQ est une matrice orthogonale (ses colonnes sont des vecteurs orthonormés) ;
  • RR est une matrice triangulaire supérieure.

Exemple de décomposition :

A=[a1a2a3a4]=[q1q2q3q4][r11r120r22]A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Cette décomposition est souvent utilisée lorsque :

  • La matrice A n'est pas carrée ;
  • Résolution de problèmes des moindres carrés ;
  • La décomposition LU n'est pas stable.

Que sont les vecteurs orthonormés ?

Vecteurs orthogonaux

Deux vecteurs u,vu, v sont orthogonaux si leur produit scalaire est nul :

u⋅v=0u \cdot v = 0

Vecteur normalisé

Un vecteur uu est normalisé lorsque ∣u∣=1|u| = 1.

Ensemble orthonormé

Un ensemble de vecteurs {q1,q2,...,qk}\{q_1, q_2, ..., q_k\} est orthonormé si chacun est de norme unitaire et s'ils sont mutuellement orthogonaux :

qi⋅qj={1, si  i=j,0, si  i≠j.q_i \cdot q_j = \begin{cases} 1,\ \text{si}\ \ i = j,\\ 0,\ \text{si}\ \ i \neq j. \end{cases}

Importance : des colonnes orthonormées dans QQ préservent la géométrie, simplifient les projections et améliorent la stabilité numérique.

Définir la matrice A

Commençons par cet exemple :

A=[4363]A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nous allons utiliser le procédé de Gram-Schmidt pour trouver les matrices QQ et RR telles que A=QRA=QR. Le procédé de Gram-Schmidt crée un ensemble orthonormé de vecteurs à partir des colonnes de AA.

Cela signifie que les vecteurs de QQ sont tous perpendiculaires (orthogonaux) entre eux et de norme unitaire (normalisés). Cette propriété simplifie de nombreux calculs et améliore la stabilité numérique lors de la résolution de systèmes.

L'objectif ici est donc de :

  • Rendre les colonnes de QQ orthonormées ;
  • Créer la matrice RR qui va encoder les projections.

Calcul du premier vecteur de base

Nous extrayons la première colonne de AA :

a1=[46]a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Pour la normaliser, nous calculons la norme :

∣a1∣=42+62=16+36=52|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Puis :

q1=152[46]=[452652]q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Ceci est le premier vecteur orthonormé pour QQ.

Comment normaliser un vecteur

Étant donné un vecteur :

v=[v1v2⋮vn]v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Nous calculons sa norme :

∣v∣=v12+v22+...+vn2|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Puis nous normalisons :

v^=1∣v∣v\hat{v} = \frac{1}{|v|}v

Exemple :

v=[34],  ∣v∣=32+42=5v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Ainsi, notre vecteur normalisé est :

v^=15[34]=[0.60.8]\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Une fois que l'on sait normaliser et orthogonaliser des vecteurs, on peut appliquer le procédé de Gram-Schmidt pour former la matrice QQ, puis l'utiliser pour calculer RR dans la décomposition QR.

Calcul de q2q_2 avec Gram-Schmidt

Pour calculer q2q_2, on commence par la deuxième colonne de AA :

a2=[33]a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Ensuite, on projette a2a_2 sur q1q_1 :

r12=q1Ta2=152(4⋅3+6⋅3)=152⋅30r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

On retire la projection de a2a_2 :

u2=a2−r12q1u_2 = a_2 - r_{12}q_1

Puis on normalise (comme montré ci-dessus) :

q2=u2∣u2∣q_2 = \frac{u_2}{|u_2|}

Maintenant, q1q_1 et q2q_2 forment la base orthonormée pour QQ. On assemble alors le résultat final :

Q=[q1q2],  R=[r11r120r22]Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Ce qui satisfait :

A=QRA = QR
question mark

Quelle est la première étape du processus de Gram-Schmidt pour la décomposition QR ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 8

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Awesome!

Completion rate improved to 1.96

bookIntroduction à la Décomposition de Matrices

Glissez pour afficher le menu

La résolution de systèmes tels que Ax⃗=b⃗A \vec{x} = \vec{b} peut être coûteuse en calcul, en particulier pour les grands systèmes.

La décomposition matricielle simplifie ce processus en découpant la matrice AA en parties plus simples – que l’on peut ensuite résoudre par étapes.

LU vs QR

On décompose la matrice AA en d’autres matrices structurées.

Décomposition LU

Décomposer AA en une matrice triangulaire inférieure et supérieure :

  • Construite à l’aide de l’élimination de Gauss ;
  • Fonctionne mieux pour les matrices carrées.
A=LUA = LU

Décomposition QR

Décomposer AA en une matrice orthogonale et une matrice supérieure :

  • Souvent utilisée pour les matrices non carrées ;
  • Idéale pour les problèmes des moindres carrés ou lorsque la décomposition LU échoue.
A=QRA = QR

Décomposition LU

Commencer avec une matrice carrée :

A=[4363]A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

L’objectif est d’écrire ceci comme :

A=LUA = LU

Où :

L=[10l211],  U=[u11u120u22]L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

Cette décomposition est possible si A est carrée et inversible.

Points importants :

  • Les matrices triangulaires inférieures ont toutes les entrées au-dessus de la diagonale nulles, ce qui simplifie la substitution avant ;
  • Les matrices triangulaires supérieures ont des zéros sous la diagonale, ce qui rend la substitution arrière directe ;
  • Une matrice orthogonale possède des colonnes qui sont des vecteurs orthonormés (vecteurs de norme 1 et perpendiculaires) ;
  • Cette propriété préserve la longueur et les angles des vecteurs, ce qui est utile pour résoudre les moindres carrés et améliorer la stabilité numérique.

Élimination de Gauss

Appliquer l'élimination de Gauss pour éliminer l'entrée sous le pivot en haut à gauche :

R2→R2−64R1R_2 \rarr R_2 - \frac{6}{4}R_1

Cela donne :

R2′=[0,−1.5]R'_2 = [0, -1.5]

Les matrices mises à jour deviennent donc :

U=[430−1.5]U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

Et à partir de notre opération sur les lignes, nous savons :

L=[101.51]L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Points importants :

  • L'élimination de Gauss élimine systématiquement les entrées sous l'élément pivot de chaque colonne en soustrayant des versions multipliées de la ligne pivot aux lignes en dessous ;
  • Ce processus transforme A en une matrice triangulaire supérieure U ;
  • Les multiplicateurs utilisés pour éliminer ces entrées sont stockés dans L, ce qui permet de représenter A comme le produit LU.

Résultat de la décomposition LU

Nous vérifions :

A=LU=[101.51][430−1.5]=[4363]A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Le système Ax⃗=b⃗A \vec{x} = \vec{b} peut maintenant être résolu en deux étapes :

  1. Résoudre Ly⃗=b⃗L \vec{y} = \vec{b} par substitution avant ;
  2. Résoudre Ux⃗=y⃗U \vec{x} = \vec{y} par substitution arrière.

Décomposition QR

On souhaite exprimer une matrice AA comme le produit de deux matrices :

A=QRA = QR

Où :

  • AA est la matrice d'entrée (par exemple, données, coefficients, etc.) ;
  • QQ est une matrice orthogonale (ses colonnes sont des vecteurs orthonormés) ;
  • RR est une matrice triangulaire supérieure.

Exemple de décomposition :

A=[a1a2a3a4]=[q1q2q3q4][r11r120r22]A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Cette décomposition est souvent utilisée lorsque :

  • La matrice A n'est pas carrée ;
  • Résolution de problèmes des moindres carrés ;
  • La décomposition LU n'est pas stable.

Que sont les vecteurs orthonormés ?

Vecteurs orthogonaux

Deux vecteurs u,vu, v sont orthogonaux si leur produit scalaire est nul :

u⋅v=0u \cdot v = 0

Vecteur normalisé

Un vecteur uu est normalisé lorsque ∣u∣=1|u| = 1.

Ensemble orthonormé

Un ensemble de vecteurs {q1,q2,...,qk}\{q_1, q_2, ..., q_k\} est orthonormé si chacun est de norme unitaire et s'ils sont mutuellement orthogonaux :

qi⋅qj={1, si  i=j,0, si  i≠j.q_i \cdot q_j = \begin{cases} 1,\ \text{si}\ \ i = j,\\ 0,\ \text{si}\ \ i \neq j. \end{cases}

Importance : des colonnes orthonormées dans QQ préservent la géométrie, simplifient les projections et améliorent la stabilité numérique.

Définir la matrice A

Commençons par cet exemple :

A=[4363]A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Nous allons utiliser le procédé de Gram-Schmidt pour trouver les matrices QQ et RR telles que A=QRA=QR. Le procédé de Gram-Schmidt crée un ensemble orthonormé de vecteurs à partir des colonnes de AA.

Cela signifie que les vecteurs de QQ sont tous perpendiculaires (orthogonaux) entre eux et de norme unitaire (normalisés). Cette propriété simplifie de nombreux calculs et améliore la stabilité numérique lors de la résolution de systèmes.

L'objectif ici est donc de :

  • Rendre les colonnes de QQ orthonormées ;
  • Créer la matrice RR qui va encoder les projections.

Calcul du premier vecteur de base

Nous extrayons la première colonne de AA :

a1=[46]a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

Pour la normaliser, nous calculons la norme :

∣a1∣=42+62=16+36=52|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Puis :

q1=152[46]=[452652]q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

Ceci est le premier vecteur orthonormé pour QQ.

Comment normaliser un vecteur

Étant donné un vecteur :

v=[v1v2⋮vn]v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

Nous calculons sa norme :

∣v∣=v12+v22+...+vn2|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Puis nous normalisons :

v^=1∣v∣v\hat{v} = \frac{1}{|v|}v

Exemple :

v=[34],  ∣v∣=32+42=5v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

Ainsi, notre vecteur normalisé est :

v^=15[34]=[0.60.8]\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Une fois que l'on sait normaliser et orthogonaliser des vecteurs, on peut appliquer le procédé de Gram-Schmidt pour former la matrice QQ, puis l'utiliser pour calculer RR dans la décomposition QR.

Calcul de q2q_2 avec Gram-Schmidt

Pour calculer q2q_2, on commence par la deuxième colonne de AA :

a2=[33]a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Ensuite, on projette a2a_2 sur q1q_1 :

r12=q1Ta2=152(4⋅3+6⋅3)=152⋅30r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

On retire la projection de a2a_2 :

u2=a2−r12q1u_2 = a_2 - r_{12}q_1

Puis on normalise (comme montré ci-dessus) :

q2=u2∣u2∣q_2 = \frac{u_2}{|u_2|}

Maintenant, q1q_1 et q2q_2 forment la base orthonormée pour QQ. On assemble alors le résultat final :

Q=[q1q2],  R=[r11r120r22]Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

Ce qui satisfait :

A=QRA = QR
question mark

Quelle est la première étape du processus de Gram-Schmidt pour la décomposition QR ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 8
some-alt