AlgèbreMéthode · Glossaire
Décomposition QR
Pour une matrice réelle A de taille m × n, avec m ≥ n et des colonnes linéairement indépendantes, la décomposition QR réduite est son écriture sous la forme A = QR, où Q est une matrice m × n à colonnes orthonormées et R une matrice n × n triangulaire supérieure. Lorsque Q est carrée, elle est orthogonale. Cette décomposition peut être calculée par le procédé de Gram-Schmidt ou par des réflexions de Householder. Elle est utilisée pour résoudre les systèmes linéaires, calculer les valeurs propres par l'algorithme QR itératif, et résoudre les problèmes de moindres carrés de manière numériquement stable.
Sommaire
Ce que vous allez apprendre
- Distinguer les rôles du facteur orthonormé Q et du facteur triangulaire R.
- Construire pas à pas la QR de la matrice de colonnes (1, 1) et (1, 0).
- Vérifier exactement le produit QR et l'orthonormalité des colonnes de Q.
- Choisir entre Gram-Schmidt, Householder, QR pivotée et SVD selon le rang et la stabilité.
- Relier la factorisation aux systèmes linéaires, aux moindres carrés et aux valeurs propres.
En clair
Imaginez deux flèches qui donnent les colonnes d'une matrice. La décomposition QR les remplace par des directions perpendiculaires de longueur 1, puis garde dans une matrice triangulaire les nombres nécessaires pour reconstruire les flèches de départ.
La lettre Q rassemble les nouvelles directions orthonormées. La lettre R indique comment les combiner. Rien n'est perdu : leur produit redonne exactement la matrice initiale. Ce changement de repère rend notamment les calculs de moindres carrés plus directs et évite de former certains produits qui amplifient les erreurs numériques.
Définition
Soit A une matrice réelle à m lignes et n colonnes, avec m au moins égal à n. Une décomposition QR réduite est une factorisation dans laquelle les n colonnes de Q sont orthonormées et R est une matrice carrée triangulaire supérieure de taille n. Autrement dit, , où In est la matrice identité. Si Q est carrée, cette relation signifie que Q est une matrice orthogonale.
Lorsque les colonnes de A sont linéairement indépendantes, les termes diagonaux de R sont non nuls. En imposant qu'ils soient positifs, Q et R sont uniques. Sans cette convention, changer simultanément le signe d'une colonne de Q et de la ligne correspondante de R donne une autre factorisation.
Le procédé de Gram-Schmidt construit Q colonne après colonne par projections. Les réflexions de Householder transforment plutôt A en matrice triangulaire par des transformations orthogonales ; elles sont généralement préférées en calcul numérique. Une factorisation QR existe aussi pour une matrice de rang déficient, mais la diagonale de R contient alors des zéros et l'unicité précédente disparaît.
Le principe
Pour une matrice réelle dont les colonnes a1, …, an sont indépendantes, orthogonalisez-les dans cet ordre. À l'étape j, retirez de aj ses projections sur les directions q1, …, qj−1 déjà obtenues, puis normalisez le vecteur restant pour former qj.
Les coefficients de projection et les normes remplissent R :
Le procédé s'arrête après la n-ième colonne et fournit .
Quand l'utiliser
Dans le cadre réduit décrit ici, A est réelle, possède au moins autant de lignes que de colonnes et ses colonnes sont linéairement indépendantes. Ces conditions donnent n directions orthonormées, une matrice R carrée à diagonale non nulle et, si cette diagonale est positive, une factorisation unique.
Si une colonne est combinaison des précédentes, le vecteur que Gram-Schmidt doit normaliser devient nul : la division par sa norme bloque. Une QR avec zéros sur la diagonale reste possible, mais il faut employer une méthode adaptée, souvent Householder avec pivotement, et ne plus conclure à l'unicité. Pour une matrice complexe, la transposée doit être remplacée par la transposée conjuguée.
Un exemple, pas à pas
Prenons la matrice A dont les colonnes sont a1 = (1, 1) et a2 = (1, 0). Elles sont indépendantes. Nous allons construire Q et R par Gram-Schmidt. Une représentation des deux colonnes initiales et des directions orthonormées rend visible le changement de repère.
1. La norme de a1 vaut √2. La première direction est donc q1 = (1/√2, 1/√2), et le premier coefficient diagonal vaut r11 = √2.
2. La projection de a2 sur q1 a pour coefficient r12 = 1/√2. Après soustraction, il reste (1/2, −1/2), de norme 1/√2. Ainsi q2 = (1/√2, −1/√2) et r22 = 1/√2.
3. Les deux facteurs sont alors :
4. Le contrôle refaisable consiste à multiplier les facteurs :
De plus, les colonnes de Q ont chacune une norme égale à 1 et leur produit scalaire est nul.
En pratique
Pour résoudre un système carré Ax = b lorsque A est inversible, la factorisation transforme le problème en . Comme R ne possède alors aucun pivot nul, il reste une substitution remontante. Si A est très grande et creuse, une méthode itérative peut toutefois éviter de stocker les facteurs.
Pour un problème de moindres carrés avec plus d'équations que d'inconnues et des colonnes indépendantes, la même relation fournit l'unique solution sans former la matrice ATA. Cette voie est préférable aux équations normales lorsque les colonnes sont presque dépendantes, car celles-ci aggravent le conditionnement numérique.
Pour approcher les valeurs propres d'une matrice carrée, l'algorithme QR répète une factorisation puis inverse l'ordre des facteurs. Dans un logiciel numérique, les réflexions de Householder sont le choix courant pour une factorisation dense ; Gram-Schmidt reste précieux pour comprendre la construction et pour certaines mises à jour de bases.
À ne pas confondre
Avec une diagonalisation. Une décomposition QR produit un facteur triangulaire R et s'applique à une matrice qui n'est pas nécessairement carrée. Une diagonalisation cherche une matrice diagonale liée aux vecteurs propres et peut ne pas exister. Une matrice rectangulaire de rang plein admet donc une QR réduite, mais aucune diagonalisation au sens usuel.
Avec la décomposition LU. LU combine une matrice triangulaire inférieure et une matrice triangulaire supérieure, souvent avec pivotement. QR se reconnaît au facteur dont les colonnes sont orthonormées. Pour les moindres carrés, QR évite les équations normales ; pour de nombreux systèmes carrés bien conditionnés, LU coûte moins d'opérations.
Avec la décomposition en valeurs singulières. La SVD place une matrice diagonale de valeurs singulières entre deux facteurs orthogonaux. Elle révèle directement le rang et traite mieux les déficiences de rang, mais son calcul est plus coûteux. Si R possède une diagonale nulle, la distinction devient décisive.
Limites et pièges
Rang déficient. Si le rang de A est strictement inférieur au nombre n de ses colonnes, au moins un terme diagonal de R peut être nul. Gram-Schmidt rencontre alors un vecteur nul à normaliser. Il faut recourir à une QR avec pivotement ou à une décomposition en valeurs singulières selon l'objectif.
Unicité conditionnelle. Une QR n'est pas unique tant que le signe de la diagonale de R n'est pas fixé. Le symptôme est que deux logiciels renvoient des colonnes de Q opposées. Avec des colonnes indépendantes, imposer rjj > 0 pour tout indice j lève cette ambiguïté.
Gram-Schmidt classique en précision finie. Pour des colonnes presque dépendantes, les colonnes calculées de Q peuvent ne plus être suffisamment orthogonales. Le contrôle consiste à mesurer l'écart de QTQ à l'identité. Gram-Schmidt modifié ou les réflexions de Householder réduisent ce défaut.
Forme réduite ou complète. Pour une matrice à m lignes et n colonnes avec m > n, la forme réduite utilise une matrice Q de taille m × n. La forme complète prolonge cette base et donne une matrice Q carrée de taille m. Il faut vérifier les dimensions avant toute multiplication.
Pour aller plus loin
La fiche matrice orthogonale précise les propriétés du facteur Q et les transformations qui préservent longueurs et angles.
La fiche Droite des moindres carrés montre une application concrète où la factorisation QR évite de résoudre directement les équations normales.
La fiche valeur propre donne le cadre spectral auquel mène l'algorithme QR itératif.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres
