Explication intuitive de la raison pour laquelle le Gram-Schmidt modifié est plus stable que le classique?

Question

Cela peut être une vieille question, et il y a certainement des articles connexes que je mentionnerai ci-dessous. Cependant, il ne me semble pas encore de réponse claire. La question est: existe-t-il un moyen intuitif d'expliquer pourquoi le processus modifié de Gram-Schmidt (MGS) pour faire la factorisation QR d'une matrice$A\in\mathbb{C} ^{m\times n}$ donne un $Q$matrice qui est "plus orthogonale" que celle du processus classique de Gram-Schmidt (CGS)? Par «intuitif», j'espère que l'explication peut être liée à la différence de procédure entre MGS et CGS de manière transparente.

Dans l' algèbre linéaire numérique de Trefethen , la distinction entre le CGS et le MGS est la suivante:

Au $j$ème étape, les deux processus GS calculent $q_j$ comme $$ q_j=\frac{P_j a_j }{\|| P_j a_j \|| } $$ tandis que pour CGS, $$ P_j=I-Q_{j-1}Q_{j-1}^* $$ mais pour MGS, $$ P_j=(I-q_{j-1}q_{j-1}^* )...(I-q_2q_2^* )(I-q_1q_1^* ) $$

Trefethen n'explique pas pourquoi cette différence de procédure conduit à une meilleure stabilité numérique de MGS.

@AlgebraicPavel a donné ici des limites quantitatives sur les facteurs d'orthogonalité:$\||I-Q^* Q\||\leq O(\epsilon \kappa(A))$ pour MGS, tandis que $\||I-Q^* Q\||\leq O(\epsilon \kappa^2(A))$pour CGS. Ces résultats sont suffisamment quantitatifs. Cependant, comme mentionné ci-dessus, je voudrais un raisonnement plus intuitif sur la façon dont cela se produit.

@Ian a dit ici que:

"Le Gram-Schmidt classique, dans lequel vous soustrayez les projections du (k + 1) ème vecteur sur les k premiers vecteurs, est assez instable, en particulier dans les grandes dimensions, car vous vous assurez essentiellement que votre nouveau vecteur est orthogonal à l'entrée vecteur en question, mais ne vous assurez pas que les vecteurs que vous obtenez à la fin du processus sont orthogonaux les uns aux autres. Combinez cela avec le fait que vous pouvez finir par soustraire des nombres presque égaux et vous obtenez une mauvaise situation. "

Cela ressemble à une explication intuitive et qualitative du problème du CGS. Cependant, pour entrer dans les détails, je ne me sens pas à l'aise avec ce raisonnement. Plus précisément, dire que "le nouveau vecteur est orthogonal au vecteur d'entrée en question" ne semble pas être en accord avec ce que fait CGS. Pour CGS et MGS, le nouveau vecteur ($a_j$) est soustrait pour tenter de le rendre orthogonal à l'existant $q_i, i=1,...,j-1$. Il n'est peut-être pas approprié d'appeler ces$q_i$ "vecteur d'entrée", et cela ne résout pas la principale différence de procédure entre MGS et CGS.

Dans cet article, le$4\times 3$La matrice de Lauchli est utilisée comme exemple pour démontrer les différents résultats entre MGS et CGS. Bien qu'il n'y ait toujours pas d'explication intuitive à la question non plus, je remarque que pour cet exemple de Lauchli, le résultat$q_3^{CGS}$ ne parvient pas à être orthogonal à $q_2^{CGS}$ est parce que le $r_{23}^{CGS}$est mal calculé, avec une erreur relative de 100%. Cependant, je ne peux pas comprendre pourquoi la procédure MGS peut atténuer ce problème de manière significative.

J'apprécie beaucoup vos commentaires.

Answer 1

Dans CGS et MGS, l'étape d'orthogonalisation consistant à soustraire des projections sur les colonnes de $Q$qui ont déjà été calculés introduit des erreurs dues à l'arithmétique de précision finie. Chaque colonne$\mathbf{q}_i$ de $Q$ a donc une composante d'erreur dans la direction des colonnes précédemment calculées $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$. L'erreur s'accumule lorsque le numéro de colonne augmente$i$, ce qui est une faiblesse inhérente aux deux algorithmes.

Dans CGS, l'orthogonalisation d'une colonne $n$ contre colonne $\mathbf{q}_{i}$ ($i<n$) est réalisée en projetant la colonne d'origine de $A$ (appelle ça $\mathbf{a}_n$) sur $\mathbf{q}_{i}$ et soustraire. $$ \begin{split} \mathbf{p}_{n} &\equiv \mathbf{a_n} - \sum_{i=1}^{n-1}(\mathbf{q_i^T}\cdot \mathbf{a_n})\mathbf{q_i} \\ \mathbf{q}_{n} &= \frac{\mathbf{p}_{n}}{\|\mathbf{p}_{n}\|} \end{split} $$ Dans MGS, en revanche, les composants le long de chaque $\mathbf{q}_i$ sont immédiatement soustraits du reste des colonnes à droite de la colonne $i$ aussi tôt que le $\mathbf{q}_i$sont calculés. Par conséquent, l'orthogonalisation de la colonne$n$ contre $\mathbf{q}_{i}$ n'est pas réalisée en projetant $\mathbf{q}_{i}$ contre la colonne originale de $A$ comme dans CGS, mais plutôt contre un vecteur obtenu en soustrayant de cette colonne de $A$ les composants en travée ($\mathbf{q}_1….\mathbf{q}_{i-1}$). Ceci est important en raison des composants d'erreur de$\mathbf{q}_i$, qui s'étendent $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$.

Plus précisément, dans MGS l'orthogonalisation de colonne $n$ contre $\mathbf{q}_{i}$ est effectuée en soustrayant la composante de $\mathbf{q}_{i}$ du vecteur $\mathbf{v}_n^{i-1}$, où $\mathbf{v}_n^0\equiv \mathbf{a}_n$ et $\mathbf{v}_n^i$ ($0<i<n$) est défini comme $$ \begin{split} \mathbf{v}_n^{i}&\equiv \mathbf{v}_n^{i-1} -(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})\mathbf{q}_{i}, \\ \mathbf{q}_n &= \frac{\mathbf{v}_n^{n-1}}{\|\mathbf{v}_n^{n-1}\|} \end{split} $$ Notez la différence dans les facteurs de projection entre parenthèses dans l'expression ci-dessus, $(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})$, et celui correspondant pour CGS, ($\mathbf{q_i^T}\cdot \mathbf{a_n}$). Le vecteur$\mathbf{q}_i$ a des composants d'erreur dans l'étendue ($\mathbf{q}_1….\mathbf{q}_{i-1}$) qui introduira une erreur dans ce facteur de projection. Alors que le vecteur$\mathbf{a}_n$ peut en général avoir de grands composants en portée ($\mathbf{q}_1….\mathbf{q}_{i-1}$), le vecteur $\mathbf{v}_n^{i-1}$ n'a que des composants d'erreur dans l'étendue ($\mathbf{q}_1….\mathbf{q}_{i-1}$) parce qu'en informatique $\mathbf{v}_n^{i-1}$ ces composants de $\mathbf{a}_n$ en span ($\mathbf{q}_1….\mathbf{q}_{i-1}$) ont déjà été soustraites. En conséquence, l'erreur de ce facteur multiplicatif due à l'orthogonalité imparfaite entre$\mathbf{q}_i$ et $\{\mathbf{q}_1...\mathbf{q}_{i-1}\}$ est beaucoup plus petit dans MGS que dans CGS.

En raison de l'erreur beaucoup plus petite dans ce facteur de projection, le MGS introduit moins d'erreur d'orthogonalisation à chaque étape de soustraction que le CGS.