AlgèbreMéthode · Glossaire
méthode de Householder
La méthode de Householder est un algorithme permettant de calculer la décomposition QR d'une matrice A, c'est-à-dire de l'écrire sous la forme A = QR, où Q est une matrice orthogonale et R une matrice triangulaire supérieure. Cette décomposition est fondamentale en algèbre linéaire numérique, notamment pour la résolution de systèmes linéaires et le calcul des valeurs propres. Dans la méthode de Householder, la matrice orthogonale Q est construite comme un produit successif de matrices orthogonales élémentaires appelées réflexions de Householder (ou réflecteurs), chaque réflexion annulant les éléments sous-diagonaux d'une colonne de la matrice.
Sommaire
Ce que vous allez apprendre
- Relier géométriquement une réflexion de Householder à l’annulation des coefficients sous-diagonaux.
- Construire les réflecteurs successifs et retrouver les facteurs Q et R.
- Vérifier sur une matrice 3 × 2 un calcul sans arrondi.
- Reconnaître les cas de vecteur nul, de rang déficient et de matrice large.
En clair
Imaginez les nombres d’une colonne comme une flèche. Une réflexion bien choisie rabat cette flèche sur le premier axe : sa longueur est conservée, mais tous les nombres situés au-dessous du premier deviennent nuls. La méthode de Householder répète ce geste colonne après colonne.
À la fin, les zéros dessinent une matrice triangulaire supérieure R. La suite des réflexions fournit une matrice orthogonale Q, qui conserve longueurs et angles. La matrice de départ s’écrit alors A = QR.
Définition
La méthode de Householder calcule une décomposition QR d’une matrice réelle A. Elle construit une matrice orthogonale Q, dont les colonnes préservent les produits scalaires, et une matrice R triangulaire supérieure telles que . Pour une matrice rectangulaire ayant au moins autant de lignes que de colonnes, la forme réduite donne une matrice Q aux colonnes orthonormées et une matrice R carrée.
Le calcul élémentaire repose sur un vecteur non nul v. Le réflecteur associé est la matrice , où I désigne l’identité et vT le vecteur v transposé. Cette matrice est symétrique et orthogonale : et . Elle réalise une réflexion par rapport à l’hyperplan perpendiculaire à v.
À chaque étape, le réflecteur agit seulement sur la partie encore non réduite de A et annule les coefficients sous la diagonale dans la colonne courante. Si R est obtenue par , alors .
Le principe
Pour la colonne active, on note x le vecteur formé par le coefficient diagonal et ceux placés au-dessous. On choisit , avec la convention sign(0) = 1, puis , où e1 est le premier vecteur de la base canonique.
On forme et on applique H à la partie active.
Comme , les coefficients visés deviennent nuls. On recommence sur la colonne suivante jusqu’à obtenir R.
On forme et on applique H à la partie active.
Comme , les coefficients visés deviennent nuls. On recommence sur la colonne suivante jusqu’à obtenir R.
Quand l'utiliser
La version réelle s’applique à une matrice A à coefficients réels. Pour obtenir la décomposition QR réduite usuelle, A possède m lignes et n colonnes avec m ≥ n. Chaque réflecteur est calculé à partir de la partie de colonne située sur la diagonale et sous elle ; les colonnes déjà traitées ne doivent plus être modifiées. Le procédé fournit encore une décomposition si les colonnes sont dépendantes, mais R comporte alors un coefficient diagonal nul et la factorisation n’est plus unique.
Si le vecteur actif x est exactement nul, la formule ne doit pas conduire à une division par vTv = 0 : on saute cette réflexion. Pour une matrice complexe, la transposée simple et le signe réel ne conviennent pas ; il faut employer la version complexe, avec transposée conjuguée et choix de phase.
Un exemple, pas à pas
Considérons une matrice A de trois lignes et deux colonnes. Les données sont ses deux colonnes (4, 3, 0)T et (0, 5, 3)T :
1. La norme de la première colonne vaut 5. Le vecteur v1 = (9, 3, 0)T donne le premier réflecteur :
2. La multiplication annule les deux nombres sous le premier coefficient :
3. Dans la seconde colonne, la partie active est (4, 3)T, encore de norme 5. Le second réflecteur agit seulement sur les deux dernières lignes :
4. On obtient la matrice triangulaire supérieure R :
Le schéma des trois états de la matrice rend visibles les zéros créés successivement.
Le produit est orthogonal. Le contrôle est direct : en multipliant Q par R, on retrouve exactement les colonnes (4, 3, 0)T et (0, 5, 3)T de A.
En pratique
Pour résoudre un problème de moindres carrés, on transforme d’abord la matrice des données en QR. Après multiplication par QT, les n premières équations forment, si les colonnes sont indépendantes, un système triangulaire supérieur qui se résout par remontée ; les lignes restantes décrivent le résidu. Quand les colonnes sont presque alignées, les réflexions de Householder sont généralement préférées à la méthode classique de Gram-Schmidt, plus sensible aux erreurs d’arrondi.
Dans les algorithmes de valeurs propres, les réflexions servent aussi à préparer une matrice sous une forme plus simple avant les itérations QR. Elles sont adaptées aux matrices denses, car une seule transformation traite d’un coup toute la partie basse d’une colonne.
Pour une matrice très creuse ou une modification portant sur quelques coefficients, les rotations de Givens peuvent mieux préserver la structure. En programmation, on conserve souvent les vecteurs des réflecteurs au lieu de former explicitement Q, puis on applique ces vecteurs dans l’ordre voulu.
À ne pas confondre
Décomposition QR. La décomposition A = QR est le résultat recherché ; la méthode de Householder est l’un des algorithmes qui la calculent. Une même factorisation peut aussi être obtenue par Gram-Schmidt ou par rotations de Givens.
Procédé de Gram-Schmidt. Gram-Schmidt orthogonalise directement une suite de colonnes par projections. Householder transforme toute une partie de matrice par réflexion. Sur une matrice dense calculée en précision finie, ce second geste conserve généralement mieux l’orthogonalité.
Rotations de Givens. Une rotation de Givens annule typiquement un coefficient à la fois dans un plan de coordonnées. Un réflecteur de Householder annule en une opération tous les coefficients visés d’une colonne ; Givens devient intéressant lorsque la matrice est creuse ou localement modifiée.
Limites et pièges
Vecteur actif nul. Si sa norme vaut exactement 0, aucun coefficient n’est à annuler et le calcul de v créerait une division par zéro. Il faut conserver cette partie inchangée et passer à la colonne suivante.
Choix du signe. Prendre α avec le même signe que le premier coefficient peut soustraire deux nombres presque égaux lors du calcul de v. Le choix α = −sign(x1)‖x‖2 évite cette annulation numérique.
Rang déficient. Un coefficient diagonal nul dans R signale qu’une nouvelle direction indépendante n’a pas été créée. La décomposition existe encore, mais résoudre ensuite par division diagonale échoue ; il faut traiter le rang ou utiliser une factorisation avec pivotement.
Matrice large. Si le nombre de lignes m est inférieur au nombre de colonnes n, la forme réduite standard avec R carrée de taille n n’est pas disponible. Il faut adapter les dimensions de la factorisation ou travailler sur une formulation transposée selon le problème.
Pour aller plus loin
Décomposition QR. Situez la factorisation obtenue, ses formes et les problèmes linéaires qu’elle simplifie.
matrice orthogonale. Approfondissez la conservation des longueurs et des angles qui rend les réflecteurs numériquement utiles.
valeur propre. Reliez la préparation des matrices aux algorithmes qui approchent leur spectre.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres