Matrice de Householder

Illustration de l'application d'une matrice de Householder : c'est la matrice de la réflexion par rapport à l'hyperplan orthogonal au vecteur n

En algèbre linéaire, la matrice de Householder associée à un vecteur non nul v∈ℝn est la matrice définie par :

Hv=In−2vvT‖v‖2

où In est la matrice identité de taille n.

Dans la suite, ∀x,y∈ℝn,x⋅y=⟨x,y⟩, le produit scalaire euclidien.

Propriétés

Ainsi, Hv est la matrice de la symétrie orthogonale par rapport à l'hyperplan orthogonal au vecteur v.

Applications

Optique géométrique

En optique géométrique, la réflexion spéculaire peut être exprimée en termes de matrice de Householder.

Algèbre linéaire numérique

En remarquant que la définition d'une matrice de Householder ne nécessite que la connaissance d'un seul vecteur et non d'une matrice entière (qui pour les calculs n'est jamais explicitement donnée), on peut aisément minimiser le stockage et la mémoire nécessaire pour leur utilisation.

Ainsi, la multiplication d'une matrice de Householder et d'un vecteur ne nécessite pas l'opération complète d'un produit matrice-vecteur, mais seulement un produit scalaire, puis une transformation affine, soit deux opérations de niveau BLAS-1. Ceci rend les matrices de Householder extrêmement efficaces en termes de coût de calcul

Ainsi, en notant ⋅̂ la valeur calculée et ⋅ la valeur exacte, alors pour une matrice de Householder donnée P de taille n,

Pb^=(P+ΔP)b

avec ||ΔP||F≤γn~:=cnu1−cnu (où u désigne un arrondi d'unité, et c une constante). Ainsi, les multiplications par des matrices de Householder sont extrêmement inversement stables.

Comme les transformations de Householder sont de stockage mémoire minimal, de complexité arithmétique basse, et stables numériquement, elles sont souvent utilisées en algèbre linéaire numérique, par exemple, pour trianguler une matrice, calculer des décompositions QR ou dans la première étape de l'algorithme QR. On les utilise aussi pour établir la forme de Hessenberg d'une matrice. Pour les matrices symétriques ou hermitiennes, on peut conserver la symétrie, résultant en une tridiagonalisation,.

Décomposition QR

Les transformations de Householder peuvent être utilisées pour calculer la décomposition QR d'une matrice. En considérant une matrice triangularisée jusqu'à la colonne i, alors l'objectif est de construire des matrices de Householder qui agissent comme les sous-matrices principales d'une matrice donnée :

[a11a12⋯a1n0a22⋯a1n⋮⋱⋮0⋯0x1=aii⋯ain0⋯0⋮⋮0⋯0xn+1−i=ani⋯ann]

par la matrice

[Ii−100Pv].

On peut rappeler qu'il a été établi supra que les matrices de Householder sont des matrices unitaires, et puisque le produit de deux matrices unitaires est également unitaire, on a la matrice unitaire de la décomposition QR.

Si on peut trouver un vecteur v→ tel que Pvx→=αe1→ on peut mener ce calcul. D'un point de vue géométrique, on cherche un hyperplan tel que la réflexion par ce plan envoie sur le vecteur de base, soit :

x→−2⟨x→,v→⟩v→=αe→1

 

 

 

 

(1)

pour une constante α. Ceci implique d'avoir v→∝x→−αe→1. Et puisque v→ est unitaire, il faut que

v→=±x→−αe→1‖x→−αe→1‖2

 

 

 

 

(2)

En réinjectant l'équation (2) dans l'équation (1), on obtient x→−αe→1=2⟨x→,x→−αe→1‖x→−αe→1‖2⟩x→−αe→1‖x→−αe→1‖2 Ou, en d'autres termes, en comparant les scalaires facteurs du vecteur x→−αe→1 on a ‖x→−αe→1‖22=2⟨x→,x→−αe1⟩. soit ‖x→‖22−2αx1+α2=2(‖x→‖22−αx1) La résolution en α donne α=±‖x→‖2 On a ainsi la construction complète ; cependant, en pratique, on veut éviter l'annulation catastrophique dans l'équation (2). Ainsi, on choisit le signe de α avec α=−sgn⁡(Re(x1))‖x→‖2

Tridiagonalisation et réduction de Hessenberg

Cet algorithme, présenté dans Numerical Analysis par Burden et Faires, fonctionne si la matrice est symétrique. Dans le cas non-symétrique, un calcul similaire peut donner une matrice de Hessenberg.

On doit utiliser une définition modifiée de la fonction sgn avech sgn⁡(0)=1. Pour la première étape, pour former la matrice de Householder à chaque étape, on doit déterminer α et r, tels que :

α=−sgn⁡(a21)∑j=2naj12;r=12(α2−a21α);

À partir de α et r, on construit le vecteur v :

v→(1)=[v1v2⋮vn],

où v1=0, v2=a21−α2r, et

vk=ak12r pour tout k=3,4…n

On calcule ensuite :

P1=I−2v→(1)(v→(1))𝖳A(2)=P1AP1

On a alors trouvé P1 et calculé A(2), le processus est répété pour k=2,3,…,n−2 comme suit :

α=−sgn⁡(ak+1,kk)∑j=k+1n(ajkk)2r=12(α2−ak+1,kkα)v1k=v2k=⋯=vkk=0vk+1k=ak+1,kk−α2rvjk=ajkk2r pour j=k+2, k+3, …, nPk=I−2v→(k)(v→(k))𝖳A(k+1)=PkA(k)Pk

On obtient de cette façon la matrice symétrique tridiagonale voulue.

Exemples

Dans cet exemple, tiré de Burden et Faires, la matrice donnée est transformée en une matrice tridiagonale similaire A3 par la méthode de Householder.

𝐀=[41−221201−203−221−2−1],

Par la méthode de Householder, on obtient :

  • étape 1 :
Q1=[10000−1323−2302323130−231323],A2=Q1AQ1=[4−300−31031430153−43043−43−1],
  • étape 2 :
Q2=[1000010000−35−4500−4535],A3=Q2A2Q2=[4−300−3103−5300−53−3325687500687514975],

On a bien au final une matrice tridiagonale symétrique similaire à la première. Le processus s'interrompt après deux étapes.

Calcul quantique

Illustration de l'interprétation géométrique de la première itération de l'algorithme de Grover. Le vecteur d'état |s⟩ subit une rotation autour du vecteur cible |ω⟩.

Comme les matrices unitaires sont utiles en calcul quantique, les transformations de Householder y sont tout à fait adaptées. Un des algorithmes où elles présentent un grand intérêt est celui de Grover, où l'on cherche à calculer une fonction oracle représentée dans ce qui s'avère être une transformation de Householder :

{Uω|x⟩=−|x⟩pour x=ω, soit f(x)=1,Uω|x⟩=|x⟩pour x≠ω, soit f(x)=0.

(avec |x⟩ une partie de la notation bra-ket, analogue à x→ utilisée auparavant).

On l'obtient par un algorithme qui itère par la fonction oracle Uω et un autre opérateur Us connu comme l'opérateur de diffusion de Grover défini par

|s⟩=1N∑x=0N−1|x⟩. et Us=2|s⟩⟨s|−I.

Voir aussi

Articles connexes