Intuitive Erklärung, warum der modifizierte Gram-Schmidt stabiler ist als der klassische?
Dies mag eine alte Frage sein, und es gibt sicherlich einige verwandte Beiträge, die ich unten erwähnen werde. Es scheint mir jedoch noch keine klare Antwort zu geben. Die Frage ist: Gibt es eine intuitive Möglichkeit zu erklären, warum der modifizierte Gram-Schmidt (MGS) -Prozess zur QR-Faktorisierung einer Matrix durchgeführt wird?$A\in\mathbb{C} ^{m\times n}$ gibt ein $Q$Matrix, die "orthogonaler" ist als die des klassischen Gram-Schmidt (CGS) -Prozesses? Durch "intuitiv" hoffe ich, dass die Erklärung auf transparente Weise mit dem Verfahrensunterschied zwischen MGS und CGS in Verbindung gebracht werden kann.
In Trefethens numerischer linearer Algebra wird zwischen CGS und MGS wie folgt unterschieden:
Bei der $j$Im Schritt werden beide GS-Prozesse berechnet $q_j$ wie $$ q_j=\frac{P_j a_j }{\|| P_j a_j \|| } $$ während für CGS, $$ P_j=I-Q_{j-1}Q_{j-1}^* $$ aber für MGS, $$ P_j=(I-q_{j-1}q_{j-1}^* )...(I-q_2q_2^* )(I-q_1q_1^* ) $$
Trefethen diskutiert nicht, warum dieser Verfahrensunterschied zu einer besseren numerischen Stabilität von MGS führt.
@AlgebraicPavel hat quantitative Grenzen gegeben hier auf die Orthogonalität Faktoren:$\||I-Q^* Q\||\leq O(\epsilon \kappa(A))$ für MGS, während $\||I-Q^* Q\||\leq O(\epsilon \kappa^2(A))$für CGS. Diese Ergebnisse sind quantitativ genug. Wie oben erwähnt, möchte ich jedoch eine intuitivere Begründung dafür, wie dies herauskommt.
@ Ian sagte hier, dass:
"Das klassische Gram-Schmidt, bei dem Sie die Projektionen des (k + 1) -ten Vektors auf die ersten k Vektoren subtrahieren, ist besonders in hohen Dimensionen ziemlich instabil, da Sie im Wesentlichen sicherstellen, dass Ihr neuer Vektor orthogonal zur Eingabe ist Der betreffende Vektor stellt jedoch nicht sicher, dass die Vektoren, die Sie am Ende des Prozesses erhalten, orthogonal zueinander sind. Kombinieren Sie dies mit der Tatsache, dass Sie nahezu gleiche Zahlen subtrahieren können und eine schlechte Situation erhalten. "
Dies klingt nach einer intuitiven und qualitativen Erklärung für das Problem von CGS. Wenn ich jedoch ins Detail gehe, fühle ich mich bei dieser Argumentation nicht wohl. Insbesondere scheint die Aussage, dass der "neue Vektor orthogonal zum fraglichen Eingabevektor ist", nicht mit dem übereinzustimmen, was CGS tut. Sowohl für CGS als auch für MGS ist der neue Vektor ($a_j$) wird subtrahiert, um es orthogonal zum Bestehenden zu machen $q_i, i=1,...,j-1$. Es ist möglicherweise nicht richtig, diese zu nennen$q_i$ "Eingabevektor", und dies spricht nicht den Hauptprozedurunterschied zwischen MGS und CGS an.
In diesem Beitrag wird die$4\times 3$Die Lauchli-Matrix wird als Beispiel verwendet, um die unterschiedlichen Ergebnisse zwischen MGS und CGS zu demonstrieren. Obwohl es auch keine intuitive Erklärung für die Frage gibt, stelle ich fest, dass für dieses Lauchli-Beispiel das Ergebnis ist, dass$q_3^{CGS}$ ist nicht orthogonal zu $q_2^{CGS}$ liegt daran, dass die $r_{23}^{CGS}$wird falsch berechnet, mit einem relativen Fehler von 100%. Ich kann jedoch nicht herausfinden, warum das MGS-Verfahren dieses Problem erheblich lindern kann.
Ich freue mich über Kommentare.
Antworten
Sowohl in CGS als auch in MGS ist der Orthogonalisierungsschritt das Subtrahieren von Projektionen auf die Spalten von $Q$die bereits berechnet wurden, führen aufgrund der Arithmetik mit endlicher Genauigkeit zu Fehlern. Jede Spalte$\mathbf{q}_i$ von $Q$ hat daher eine Fehlerkomponente in Richtung zuvor berechneter Spalten $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$. Der Fehler summiert sich zur Erhöhung der Spaltennummer$i$Dies ist eine inhärente Schwäche beider Algorithmen.
In CGS die Orthogonalisierung einer Spalte $n$ gegen Spalte $\mathbf{q}_{i}$ (($i<n$) wird ausgeführt, indem die ursprüngliche Spalte von projiziert wird $A$ (Nenn das $\mathbf{a}_n$) auf zu $\mathbf{q}_{i}$ und subtrahieren. $$ \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} $$ In MGS hingegen die Komponenten entlang jeder $\mathbf{q}_i$ werden sofort von den restlichen Spalten rechts von der Spalte abgezogen $i$ sobald $\mathbf{q}_i$berechnet werden. Daher die Orthogonalisierung der Säule$n$ gegen $\mathbf{q}_{i}$ wird nicht durch Projektion ausgeführt $\mathbf{q}_{i}$ gegen die ursprüngliche Spalte von $A$ wie es in CGS ist, sondern gegen einen Vektor, der durch Subtrahieren von dieser Spalte von erhalten wird $A$ die Komponenten in span ($\mathbf{q}_1….\mathbf{q}_{i-1}$). Dies ist wegen der Fehlerkomponenten von wichtig$\mathbf{q}_i$, welche Spanne $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$.
Genauer gesagt, in MGS die Orthogonalisierung der Säule $n$ gegen $\mathbf{q}_{i}$ wird durch Subtrahieren der Komponente von durchgeführt $\mathbf{q}_{i}$ aus dem Vektor $\mathbf{v}_n^{i-1}$, wo $\mathbf{v}_n^0\equiv \mathbf{a}_n$ und $\mathbf{v}_n^i$ (($0<i<n$) ist definiert als $$ \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} $$ Beachten Sie den Unterschied in den Projektionsfaktoren in Klammern im obigen Ausdruck. $(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})$und die entsprechende für CGS, ($\mathbf{q_i^T}\cdot \mathbf{a_n}$). Der Vektor$\mathbf{q}_i$ hat Fehlerkomponenten in span ($\mathbf{q}_1….\mathbf{q}_{i-1}$), die Fehler in diesen Projektionsfaktor einführen. Während der Vektor$\mathbf{a}_n$ kann im Allgemeinen große Komponenten in der Spanne haben ($\mathbf{q}_1….\mathbf{q}_{i-1}$), der Vektor $\mathbf{v}_n^{i-1}$ hat nur Fehlerkomponenten in span ($\mathbf{q}_1….\mathbf{q}_{i-1}$) weil beim Rechnen $\mathbf{v}_n^{i-1}$ diese Komponenten von $\mathbf{a}_n$ in span ($\mathbf{q}_1….\mathbf{q}_{i-1}$) wurden bereits abgezogen. Infolgedessen ist der Fehler in diesem multiplikativen Faktor aufgrund der unvollständigen Orthogonalität zwischen$\mathbf{q}_i$ und $\{\mathbf{q}_1...\mathbf{q}_{i-1}\}$ ist in MGS viel kleiner als in CGS.
Aufgrund des viel kleineren Fehlers in diesem Projektionsfaktor führt das MGS bei jedem Subtraktionsschritt weniger Orthogonalisierungsfehler ein als das CGS.