Etant donnés \(n\) vecteurs linéairement indépendants de \(\Rr^m\), \(\{a_1, \cdots , a_n\}\), on veut calculer une base orthonormale pour span\(\{a_1, \cdots , a_n\}\).
On pose \(A=[ a_1, a_2, \cdots , a_n] \in \Rr^{m\times n}\) et on considère la factorisation QR de \(A\), \[A=QR,\ \ \ Q=[q_1, \cdots , q_n] ,\ \ r_i^T, i=1, \cdots , n \mbox{ les lignes de }R\]
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?