Matrices de Householder

(Exercice d’oral Centrale Mp)
On munit {\mathbb{R}^n} de son produit scalaire canonique.
Pour {v\in\mathbb{R}^n}, on note {[v]} la matrice-colonne associée à {v} dans la base canonique.
Si {v\ne0}, soit {h(v)} la réflexion de {\mathbb{R}^n} par rapport l’hyperplan {(\mathbb{R} v)^{\bot}}.
Soit {H(v)} la matrice de {h(v)} dans la base canonique {(e)}.
On complète cette définition en posant {h(0)=\text{Id}}, donc {H(0)=\text{I}_{n}}.

  1. Montrer que, pour {v\ne0} dans {\mathbb{R}^n}, on a {H(v)=\text{I}_{n}-2\dfrac{[v]{[v]}^{\top}}{\left\|{v}\right\|^2}}.
  2. Soit {u=(a_{1},\ldots,a_{n})} un élément de {\mathbb{R}^n}.

    Soit {j} dans {[[ 1,n]]}. On note {u_{j}=(0,\ldots,0,a_{j},\ldots,a_{n})}. On pose : {\begin{array}{rl}v_{j}&=u_{j}+\varepsilon \left\|u_{j}\right\|\,e_{j}\\\\&=(0,\ldots,0,a_{j}+\varepsilon\left\|u_{j}\right\|,a_{j+1},\ldots,a_{n})\end{array}\text{\ où\ }\begin{cases}\varepsilon=1\text{\ si\ }a_{j}\ge0\cr \varepsilon=-1\text{\ sinon}\end{cases}}

    • Montrer que {v_{j}} est nul si et seulement si {u_{j}} est nul.
    • Si {u_{j}\ne0}, soit {h_{j}} la réflexion par rapport à {(\mathbb{R} v_{j})^\bot} (sinon {h_{j}=\text{Id}}).

      Montrer que {h_{j}(u)=u-v_{j}=(a_{1},\ldots,a_{j-1},-\varepsilon\left\|u_{j}\right\|,0,\ldots,0)}.

  3. Soit {M} une matrice réelle, carrée d’ordre {n}, inversible.

    • En s’inspirant de ce qui précède, montrer qu’il existe une famille {v_{1},v_{2},\ldots,v_{n-1}} de vecteurs de {\mathbb{R}^n} tels que, pour tout {k} de {[[ 1,n-1]]}, les coefficients sous-diagonaux des {k} premières colonnes de la matrice {T_{k}=H(v_{k})\cdots H(v_{2})H(v_{1})M} soient nuls.
    • En déduire l’existence d’une matrice orthogonale {\Omega} et d’une matrice triangulaire supérieure {T} telles que {M=\Omega T}.

Cliquer ici pour voir (ou cacher) le corrigé

  1. Soit {v} un vecteur non nul de {\mathbb{R}^n}.

    La projection orthogonale {p} de {\mathbb{R}^n} sur {\mathbb{R} v} est définie par {u\mapsto p(u)=\dfrac{(v\mid u)}{\left\|v\right\|^2}v}.

    Soit {P} sa matrice dans {(e)}. Pour tout {u} de {\mathbb{R}^n}, on a : {P[u]=\dfrac{(v\mid u)}{\;\left\|v\right\|^2}[v]=\dfrac{1}{\;\left\|v\right\|^2}[v](v\mid u)=\dfrac{1}{\;\left\|v\right\|^2}[v]{[v]}^{\top}[u]=\dfrac{[v]{[v]}^{\top}}{\;\left\|v\right\|^2}[u]}Ainsi {P=\dfrac{[v]{[v]}^{\top}}{\;\left\|v\right\|^2}}. Du fait que {h(v)=\text{Id}-2p}, il vient : {H(v)=\text{I}_{n}-2\dfrac{[v]{[v]}^{\top}}{\;\left\|v\right\|^2}}.

    • On a {v_{j}=u_{j}+\varepsilon \left\|u_{j}\right\|\,e_{j}}, et il en résulte : {\left\|v_j\right\|^2=2\left\|u_{j}\right\|^2+2\varepsilon\left\|u_{j}\right\|a_{j}=2\left\|u_{j}\right\|(\left\|u_{j}\right\|+\left|a_{j}\right|)}Le vecteur {v_{j}} n’est nul que si {u_{j}=0}, c’est-à-dire si {u\in\text{Vect}(e_{1},\ldots,e_{j-1})}.
    • Supposons {v_{j}\ne0} (sinon il n’y a rien à démontrer).

      Le vecteur {v'_{j}=u_{j}-\varepsilon\left\|u_{j}\right\|e_{j}} est orthogonal à {v_{j}=u_{j}+\varepsilon\left\|u_{j}\right\|e_{j}}.

      Le vecteur v'_j est donc invariant par {h_{j}}.

      Ainsi {\begin{cases}h_{j}(u_{j}-\varepsilon\left\|u_{j}\right\|e_{j})=u_{j}-\varepsilon\left\|u_{j}\right\|e_{j}\cr h_{j}(u_{j}+\varepsilon\left\|u_{j}\right\|e_{j})=-u_{j}-\varepsilon\left\|u_{j}\right\|e_{j}\end{cases}} donc {h_{j}(u_{j})=-\varepsilon\left\|u_{j}\right\|e_{j}}.

      La réflexion {h_{j}} laisse invariants l’orthogonal de {\mathbb{R}v_{j}} et en particulier {u-u_{j}}.

      On en déduit : {\begin{array}{rl}h_{j}(u)&=h_{j}(u-u_{j})+h_{j}(u_{j})=u-u_{j}-\varepsilon\left\|u_{j}\right\|e_{j}\\\\&=u-v_{j}=(a_{1},\ldots,a_{j-1},-\varepsilon\left\|u_{j}\right\|,0,\ldots,0)\end{array}}Remarque: puisque le résultat est donné dans l’énoncé, on peut aussi se contenter de remarquer (toujours avec {u_{j}\ne0}) que les vecteurs distincts {u} et {u-v_{j}} ont la même norme. Comme leur différence est proportionnelle à {v_{j}}, ils sont échangés par {h_{j}}.

    1. Soit {u\in\mathbb{R}^n}, dont les composantes forment la première colonne de {M}.

      On applique (2a) avec {j=1} et on définit encore l’application {h_{1}}.

      Il existe donc un vecteur {v_{1}} tel que {h_{1}(u)} appartienne à {\mathbb{R} e_{1}}.

      La sous-diagonale de la première colonne de {T_{1}=H(v_{1})M} est donc nulle.

      Soit {k} dans {[[ 2,n-1]]}. On suppose que les vecteurs {v_{1},\ldots,v_{k-1}} ont été construits, ainsi donc que les matrices {H(v_{1}),\ldots,H(v_{k-1})}. Les coefficients sous-diagonaux des {k-1} premières colonnes de {T_{k-1}=H(V_{k-1})\cdots H(v_{2})H(v_{1})M} sont donc nuls.

      Soit {u\in\mathbb{R}^n}, dont les composantes forment la {k}-ième colonne de {T_{k-1}}.

      On applique (2a) avec {j=k} et on définit l’application {h_{k}}.

      Il existe donc un vecteur {v_{k}} tel que {h_{k}(u)\in\text{Vect}(e_{1},\ldots,e_{k})}.

      Par construction, les vecteurs {e_{1},\ldots,e_{k-1}} sont invariants par {h_{k}}.

      La matrice {T_{k}=H(v_{k})T_{k-1}} a donc les mêmes {(k-1)} premières colonnes que {T_{k-1}}, et les coefficients sous-diagonaux de sa {k}-ème colonne sont nuls également.

      Ainsi {HM=T}{H=H(v_{n-1})\cdots H(v_{1})} (orthogonale) et {T} triangulaire supérieure.

      Il suffit de poser {\Omega={H}^{\top}} pour avoir l’écriture {M=\Omega T}.