Matrice de Householder

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'à a colonne ${\displaystyle i}$, alors l'objectif est de construire des matrices de Householder qui agissent comme les sous-matrices principales d'une matrice donnée :

${\displaystyle {\begin{bmatrix}a_{11}&a_{12}&\cdots &&&a_{1n}\\0&a_{22}&\cdots &&&a_{1n}\\\vdots &&\ddots &&&\vdots \\0&\cdots &0&x_{1}=a_{ii}&\cdots &a_{in}\\0&\cdots &0&\vdots &&\vdots \\0&\cdots &0&x_{n}=a_{ni}&\cdots &a_{nn}\end{bmatrix}}}$

par la matrice

${\displaystyle {\begin{bmatrix}I_{i-1}&0\\0&P_{v}\end{bmatrix}}}$.

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 ${\displaystyle {\vec {v}}}$ tel que $${\displaystyle P_{v}{\vec {x}}=\alpha {\vec {e_{1}}}}$$ on peut mener ce calcul. D'un point de vue géométrique, on cherche un plan tel que la réflexion par ce plan envoie sur le vecteur de base, soit :

${\displaystyle {\vec {x}}-2\langle {\vec {x}},{\vec {v}}\rangle {\vec {v}}=\alpha {\vec {e}}_{1}}$

(1)

pour une constante ${\displaystyle \alpha }$. Ceci implique d'avoir $${\displaystyle {\vec {v}}\propto {\vec {x}}-\alpha {\vec {e}}_{1}{\text{.}}}$$ Et puisque ${\displaystyle {\vec {v}}}$ est unitaire, il faut que

${\displaystyle {\vec {v}}=\pm {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}}$

(2)

En réinjectant l'équation (2) dans l'équation (1), on obtient $${\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}=2\left\langle {\vec {x}},{\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}\right\rangle {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}}$$ Ou, en d'autres termes, en comparant les scalaires facteurs du vecteur ${\displaystyle {\vec {x}}-\alpha {\vec {e}}_{1}}$ on a $${\displaystyle \|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}^{2}=2\langle {\vec {x}},{\vec {x}}-\alpha e_{1}\rangle {\text{.}}}$$ soit $${\displaystyle \|{\vec {x}}\|_{2}^{2}-2\alpha x_{1}+\alpha ^{2}=2(\|{\vec {x}}\|_{2}^{2}-\alpha x_{1})}$$ La résolution en ${\displaystyle \alpha }$ donne $${\displaystyle \alpha =\pm \|{\vec {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^[1] le signe de ${\displaystyle \alpha }$ avec $${\displaystyle \alpha =-\operatorname {sgn}(\mathrm {Re} (x_{1}))\|{\vec {x}}\|_{2}}$$

Tridiagonalisation (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 Hessenbeer.

On doit utiliser une définition modifié de la fonction ${\displaystyle \operatorname {sgn} }$ avech ${\displaystyle \operatorname {sgn} (0)=1}$^[6]. Pour la première étape, pour former la matrice de Householder à chaque étape, on doit déterminee ${\textstyle \alpha }$ et ${\textstyle r}$, tels que :

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}}$

À partir de ${\textstyle \alpha }$ et ${\textstyle r}$, on construit le vecteur ${\textstyle v}$ :

${\displaystyle {\vec {v}}^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},}$

où ${\textstyle v_{1}=0}$, ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$, et

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$ pour tout ${\displaystyle k=3,4\ldots n}$

On calcule ensuite :

${\displaystyle {\begin{aligned}P^{1}&=I-2{\vec {v}}^{(1)}\left({\vec {v}}^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}}$

On a alors trouvé ${\textstyle P^{1}}$ et calculé ${\textstyle A^{(2)}}$, le process est répété pour ${\textstyle k=2,3,\ldots ,n-2}$ comme suit :

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ pour }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2{\vec {v}}^{(k)}\left({\vec {v}}^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}}$

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

Exemples

Dans cet exemple, tiré de Bruden et Faires^[6], la matrice donnée est transformée en une matrice tridiagonale similaire A₃ par la méthode de Householder.

${\displaystyle \mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},}$

Par la méthode de Householder, on a :

• étape 1 :

${\displaystyle {\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}}$

• étape 2 :

${\displaystyle {\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}}$

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

Calcul quantique

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

${\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{pour }}x=\omega {\text{, soit }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{pour }}x\neq \omega {\text{, soit }}f(x)=0.\end{cases}}}$

(avec ${\displaystyle |x\rangle }$ une partie de la notation bra-ket, analogue à ${\displaystyle {\vec {x}}}$ utilisée auparavant).

On l'obtient par un algorithme qui itère par la fonction oracle ${\displaystyle U_{\omega }}$ et un autre opérateur ${\displaystyle U_{s}}$ connu comme l'opérateur de diffusion de Grover défini par

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$ et ${\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}$.