exo7 2230

Montrer que $$\mbox{Im} A= \mbox{span} \{q_1, \cdots , q_n\} .$$

Montrer que $$q_k=\frac{1}{r_{kk}} \left( a_k -\sum_{i=1}^{k-1}r_{ik}q_i\right) \ \ \ k=1, \cdots , n$$

En déduire un algorithme pour le calcul récursif des $q_i$ (algorithme de Gram–Schmidt).

Algorithme de Gram–Schmidt modifié L’algorithme précédent est instable numériquement dû à la perte d’orthogonalité dans le calcul des $q_i$. On va reformuler l’algorithme pour le rendre stable. Pour $k=1, \cdots , n-1$, on définit $A^{(k)}\in\Rr^{m\times (n-k+1)}$ de la façon suivante: $$[0 , A^{(k)}] =A-\sum_{i=1}^{k-1} q_ir_i^T = \sum_{i=k}^n q_ir_i^T$$ et on va décrire l’étape $k$ de l’algorithme.

Montrer que si on pose $$A^{(k)} =[z,B] ,\ \ \ z\in\Rr^m , \ \ \ B\in\Rr^{m\times (n-k)}$$ alors $$r_{kk}=\|z\|_2, \ \ \ q_k=z/r_{kk}.$$

Comment peut–on calculer la ligne $k$ de $R$ à partir de $A^{(k)}$?

Calculer $A^{(k+1)}$.

A partir des questions précédentes, décrire l’algorithme qui permet le calcul de la factorisation $A=Q_1R_1$, $Q_1\in\Rr^{m \times n}$ orthonormale, $R_1\in\Rr^{n\times n}$ triangulaire supérieure (Gram–Schmidt modifié). Le calcul de $Q_1$ doit se faire sur place.

Quelle est la complexité de l’algorithme précédent?