« Algèbre linéaire/Devoir/Décomposition QR » : différence entre les versions
Contenu supprimé Contenu ajouté
début de solution |
fin du corrigé |
||
Ligne 55 :
iii) <math>\langle v,x\rangle=\|x\|^2+\alpha\langle e,x\rangle=\alpha^2+\alpha\langle e,x\rangle</math> et
<math>\|v\|^2=\|x\|^2+2\alpha\langle x,e\rangle+\alpha^2=2(\alpha^2+\alpha\langle e,x\rangle)</math> donc <math>2\langle v,x\rangle/\|v\|^2=1</math> donc
<math>s_v(x)=x-v=-\alpha e</math>. Soient <math>e</math> le premier vecteur de la base canonique de <math>\R^n</math> et <math>x</math> le premier vecteur colonne de <math>A</math> (non nul puisque <math>A</math> est inversible). Si <math>x=\|x\|e</math>, on choisit <math>\alpha=\|x\|</math> ; si <math>x=-\|x\|e</math>, on choisit <math>\alpha=-\|x\|</math> ; si <math>x</math> n'est pas colinéaire à <math>e</math> on choisit indifféremment <math>\alpha=\pm\|x\|</math>. De cette manière, on a toujours <math>v:=x+\alpha e\
iv) Supposons construites <math>Q_1,\ldots,Q_k</math> telles que <math>Q_k\dots Q_1 A</math> soit de la forme <math>\begin{pmatrix}T_k&U_k\\0&A_k\end{pmatrix}</math> avec <math>T_k</math> triangulaire supérieure de taille <math>k</math> et <math>A_k</math> de taille <math>n-k</math> (inversibles).
*Si <math>k=n-1</math>, <math>A_k</math> est de taille <math>1</math> donc <math>Q_k\dots Q_1A</math> est triangulaire. Donc <math>t=n-1</math>.
*Si <math>k<n-1</math>, il existe une matrice de Householder <math>Q'_{k+1}</math> de taille <math>n-k</math> telle que <math>Q'_{k+1}A_k</math> soit de la forme <math>\begin{pmatrix}-\alpha_k&L_k\\0&A_{k+1}\end{pmatrix}</math>, avec <math>A_{k+1}</math> de taille <math>n-k-1</math>, d'où (par ii) une matrice de Householder <math>Q_{k+1}</math> telle que <math>Q_{k+1}\dots Q_1A=\begin{pmatrix}T_{k+1}&U_{k+1}\\0&A_{k+1}\end{pmatrix}</math> avec <math>T_{k+1}</math> triangulaire supérieure.
v) Par définition de <math>R</math> et <math>Q</math> et d'après i, <math>A=Q_1^{-1}\dots Q_t^{-1}R=Q_1\ldots Q_tR=QR</math>.
'''c)'''
i) Si <math>R</math> est triangulaire (par exemple supérieure) et orthogonale, les termes diagonaux sont égaux à <math>\pm 1</math> donc les autres termes sont <math>0</math>. S'il y a <math>k</math> termes diagonaux égaux à <math>-1</math>, <math>R</math> est le produit de <math>k</math> matrices diagonales dont chacune comporte une fois <math>-1</math> et <math>n-1</math> fois <math>1</math>, donc <math>R</math> est produit de <math>k</math> matrices de réflexion. Si l'on applique b à une matrice de départ <math>A</math> qui est orthogonale, la matrice triangulaire <math>R=Q^TA</math> sera orthogonale donc de cette forme, donc sera (comme <math>Q</math>) produit de réflexions, donc <math>A=QR</math> aussi.
ii) D'après ce qui précède, la seule matrice qui soit à la fois triangulaire et orthogonale et à termes diagonaux <math>>0</math> est <math>\rm I</math>. Si l'on améliore b.iv en choisissant simplement <math>Q_{k+1}=\rm I</math> lorsque <math>A_k</math> est déjà de la forme <math>\begin{pmatrix}\lambda_k&L_k\\0&A_{k+1}\end{pmatrix}</math> avec <math>\lambda_k>0</math>, on peut dans tous les autres cas choisir <math>\alpha_k<0</math>, si bien que la matrice triangulaire <math>R</math> obtenue aura tous ses termes diagonaux <math>>0</math> sauf peut-être le dernier, ce que l'on peut corriger en complétant si nécessaire par un <math>Q_n</math> supplémentaire. Si l'on était partis d'une matrice <math>A</math> orthogonale, on aura alors <math>R=\rm I</math> donc <math>A=Q=Q_1\dots Q_n</math>, où chaque <math>Q_i</math> est soit <math>\rm I<math>, soit une matrice de réflexion.
}}
| |||