Algèbre linéaire/Devoir/Décomposition QR

Soit $A$ une matrice réelle inversible de taille $n$. $\mathbb {R} ^{n}$ est muni de sa structure euclidienne canonique.

a) Méthode de Schmidt

Soient ${\cal {B}}'$ de matrice $A$ dans la base canonique ${\cal {B}}$ de $\mathbb {R} ^{n}$, ${\cal {B}}''$ la b.o.n. de $\mathbb {R} ^{n}$ construite à partir de ${\cal {B}}'$ par l'algorithme de Gram-Schmidt, $R$ la matrice de ${\cal {B}}'$ dans ${\cal {B}}''$ et $Q$ la matrice de ${\cal {B}}''$ dans ${\cal {B}}$.

i) Montrer que $Q$ est orthogonale.

ii) Montrer que $R$ est triangulaire supérieure.

iii) Quelle équation relie $A,Q,R$ ?

b) Méthode de Householder

Pour tout vecteur non nul $v$, on pose $s_{v}(x)=x-{2\langle v,x\rangle \over \|v\|^{2}}v$, et $H_{v}=$ la matrice de $s_{v}$ dans la base canonique. Les matrices $H_{v}$ ainsi obtenues sont appelées matrices de Householder de taille $n$.

i) Démontrer que $s_{v}$ est une réflexion.

ii) Démontrer que si $H$ est une matrice de Householder de taille $n-k$ alors ${\begin{pmatrix}{\rm {I}}_{k}&0\\0&H\end{pmatrix}}$ est une matrice de Householder de taille $n$.

iii) Soient $e$ un vecteur unitaire et $x$ un vecteur non nul. On pose $v=x+\alpha e$ avec $\alpha =\pm \|x\|$. Montrer que $s_{v}(x)=-\alpha e$. En choisissant convenablement $e$, $x$ et $\alpha$, montrer qu'il existe une matrice de Householder $Q_{1}$ (de taille $n$) telle que $Q_{1}A$ soit de la forme ${\begin{pmatrix}-\alpha &L\\0&A_{1}\end{pmatrix}}$, avec $A_{1}$ matrice inversible de taille $n-1$.

iv) En déduire (en précisant $t$) un algorithme permettant de construire des matrices de Householder $Q_{1},\ldots ,Q_{t}$ (de taille $n$) telles que $R:=Q_{t}\ldots Q_{1}A$ soit triangulaire supérieure.

v) Quelle équation relie alors $A,R$, et $Q:=Q_{1}\ldots Q_{t}$ ?

c)

i) Quelles matrices sont à la fois triangulaires et orthogonales ? Montrer qu'elles sont produits de matrices de réflexions. En déduire (par b) que tout endomorphisme orthogonal est un produit de réflexions.

ii) Quelles matrices sont à la fois triangulaires et orthogonales et à termes diagonaux $>0$ ? En déduire (en améliorant b.iv) que tout endomorphisme orthogonal est produit d'un nombre $\leq n$ de réflexions.

Corrigé

a) Méthode de Schmidt

i) $Q$ est la matrice d'une b.o.n. ${\cal {B}}''$ dans une b.o.n. ${\cal {B}}$.

ii) En notant ${\cal {B}}'=(u_{1},\ldots ,u_{n})$ et ${\cal {B}}''=(v_{1},\ldots ,v_{n})$, $Vect(u_{1},\ldots ,u_{k})$ contient les vecteurs $v_{1},\ldots ,v_{k}$ donc contient le sous-espace qu'ils engendrent, et est de même dimension, donc égal, en particulier $u_{k}\in {\rm {Vect}}(v_{1},\ldots ,v_{k})$, donc $R$ est triangulaire supérieure.

iii) Pour tout $j$, $\sum _{i}A_{i,j}e_{i}=u_{j}=\sum _{k}R_{k,j}v_{k}=\sum _{k}R_{k,j}(\sum _{i}Q_{i,k}e_{i})$ donc pour tous $i,j$, $A_{i,j}=\sum _{k}Q_{i,k}R_{k,j}$ donc $A=QR$.

b) Méthode de Householder

i) $x\mapsto {\langle v,x\rangle \over \|v\|^{2}}v$ est la projection orthogonale sur $\mathbb {R} v$ donc $s_{v}$ est la réflexion d'hyperplan $v^{\perp }$.

ii) Si $H$ est la matrice de $s_{u}$ avec $u=(u_{k+1},\dots ,u_{n})$ alors ${\begin{pmatrix}{\rm {I}}&0\\0&H\end{pmatrix}}$ est la matrice de $s_{v}$ avec $v=(0,\ldots ,0,u_{k+1},\ldots ,u_{n})$.

iii) $\langle v,x\rangle =\|x\|^{2}+\alpha \langle e,x\rangle =\alpha ^{2}+\alpha \langle e,x\rangle$ et $\|v\|^{2}=\|x\|^{2}+2\alpha \langle x,e\rangle +\alpha ^{2}=2(\alpha ^{2}+\alpha \langle e,x\rangle )$ donc $2\langle v,x\rangle /\|v\|^{2}=1$ donc $s_{v}(x)=x-v=-\alpha e$. Soient $e$ le premier vecteur de la base canonique de $\mathbb {R} ^{n}$ et $x$ le premier vecteur colonne de $A$ (non nul puisque $A$ est inversible). Si $x=\|x\|e$, on choisit $\alpha =\|x\|$ ; si $x=-\|x\|e$, on choisit $\alpha =-\|x\|$ ; si $x$ n'est pas colinéaire à $e$ on choisit indifféremment $\alpha =\pm \|x\|$. De cette manière, on a toujours $v:=x+\alpha e\neq 0$, et en prenant pour $Q_{1}$ la matrice de $s_{v}$, $Q_{1}A$ a pour première colonne $s_{v}(x)=-\alpha e$ donc est de la forme voulue.

iv) Supposons construites $Q_{1},\ldots ,Q_{k}$ telles que $Q_{k}\dots Q_{1}A$ soit de la forme ${\begin{pmatrix}T_{k}&U_{k}\\0&A_{k}\end{pmatrix}}$ avec $T_{k}$ triangulaire supérieure de taille $k$ et $A_{k}$ de taille $n-k$ (inversibles).

• Si $k=n-1$, $A_{k}$ est de taille $1$ donc $Q_{k}\dots Q_{1}A$ est triangulaire. Donc $t=n-1$.
• Si $k<n-1$, il existe une matrice de Householder $Q'_{k+1}$ de taille $n-k$ telle que $Q'_{k+1}A_{k}$ soit de la forme ${\begin{pmatrix}-\alpha _{k}&L_{k}\\0&A_{k+1}\end{pmatrix}}$, avec $A_{k+1}$ de taille $n-k-1$, d'où (par ii) une matrice de Householder $Q_{k+1}$ telle que $Q_{k+1}\dots Q_{1}A={\begin{pmatrix}T_{k+1}&U_{k+1}\\0&A_{k+1}\end{pmatrix}}$ avec $T_{k+1}$ triangulaire supérieure.

v) Par définition de $R$ et $Q$ et d'après i, $A=Q_{1}^{-1}\dots Q_{t}^{-1}R=Q_{1}\ldots Q_{t}R=QR$.

c)

i) Si $R$ est triangulaire (par exemple supérieure) et orthogonale, les termes diagonaux sont égaux à $\pm 1$ donc les autres termes sont $0$. S'il y a $k$ termes diagonaux égaux à $-1$, $R$ est le produit de $k$ matrices diagonales dont chacune comporte une fois $-1$ et $n-1$ fois $1$, donc $R$ est produit de $k$ matrices de réflexion. Si l'on applique b à une matrice de départ $A$ qui est orthogonale, la matrice triangulaire $R=Q^{T}A$ sera orthogonale donc de cette forme, donc sera (comme $Q$) produit de réflexions, donc $A=QR$ aussi.

ii) D'après ce qui précède, la seule matrice qui soit à la fois triangulaire et orthogonale et à termes diagonaux $>0$ est ${\rm {I}}$. Si l'on améliore b.iv en choisissant simplement $Q_{k+1}={\rm {I}}$ lorsque $A_{k}$ est déjà de la forme ${\begin{pmatrix}\lambda _{k}&L_{k}\\0&A_{k+1}\end{pmatrix}}$ avec $\lambda _{k}>0$, on peut dans tous les autres cas choisir $\alpha _{k}<0$, si bien que la matrice triangulaire $R$ obtenue aura tous ses termes diagonaux $>0$ sauf peut-être le dernier, ce que l'on peut corriger en complétant si nécessaire par un $Q_{n}$ supplémentaire. Si l'on était partis d'une matrice $A$ orthogonale, on aura alors $R={\rm {I}}$ donc $A=Q=Q_{1}\dots Q_{n}$, où chaque $Q_{i}$ est soit <math>\rm I<math>, soit une matrice de réflexion.