Intuicyjne wyjaśnienie, dlaczego zmodyfikowany Gram-Schmidt jest bardziej stabilny niż klasyczny?
To może być stare pytanie i na pewno jest kilka powiązanych postów, o których wspomnę poniżej. Jednak wydaje mi się, że nie ma jeszcze jasnej odpowiedzi. Pytanie brzmi: czy istnieje intuicyjny sposób wyjaśnienia, dlaczego zmodyfikowany proces Grama-Schmidta (MGS) do przeprowadzania faktoryzacji QR macierzy$A\in\mathbb{C} ^{m\times n}$ daje $Q$macierz, która jest „bardziej ortogonalna” niż ta z klasycznego procesu Grama-Schmidta (CGS)? Mam nadzieję, że dzięki „intuicyjności” wyjaśnienie będzie można powiązać z różnicą proceduralną między MGS i CGS w przejrzysty sposób.
W numerycznej algebrze liniowej Trefethena rozróżnienie między CGS i MGS jest następujące:
Na $j$W tym kroku oba procesy GS obliczają $q_j$ tak jak $$ q_j=\frac{P_j a_j }{\|| P_j a_j \|| } $$ podczas gdy dla CGS, $$ P_j=I-Q_{j-1}Q_{j-1}^* $$ ale dla MGS, $$ P_j=(I-q_{j-1}q_{j-1}^* )...(I-q_2q_2^* )(I-q_1q_1^* ) $$
Trefethen nie omawia, dlaczego ta różnica proceduralna prowadzi do lepszej stabilności numerycznej MGS.
@AlgebraicPavel podał tutaj ilościowe granice współczynników ortogonalności:$\||I-Q^* Q\||\leq O(\epsilon \kappa(A))$ dla MGS, podczas gdy $\||I-Q^* Q\||\leq O(\epsilon \kappa^2(A))$dla CGS. Te wyniki są wystarczająco ilościowe. Jednak, jak wspomniano powyżej, chciałbym mieć bardziej intuicyjne uzasadnienie tego, jak to się dzieje.
@Ian powiedział tutaj, że:
„Klasyczna metoda Gram-Schmidta, w której odejmujesz rzuty (k + 1)-tego wektora na pierwsze k wektorów, jest dość niestabilna, szczególnie w dużych wymiarach, ponieważ zasadniczo upewniasz się, że nowy wektor jest prostopadły do wejścia ale nie gwarantujemy, że wektory, które otrzymujesz na końcu procesu, są względem siebie ortogonalne. Połącz to z faktem, że możesz skończyć odejmując prawie równe liczby, a otrzymasz złą sytuację. "
Brzmi to jak intuicyjne i jakościowe wyjaśnienie problemu CGS. Jednak wchodząc w szczegóły, nie czuję się komfortowo w tej linii rozumowania. W szczególności stwierdzenie, że „nowy wektor jest prostopadły do rozpatrywanego wektora wejściowego” nie wydaje się zgadzać z tym, co robi CGS. Zarówno dla CGS, jak i MGS, nowy wektor ($a_j$) jest odejmowana, aby uczynić ją ortogonalną do istniejącej $q_i, i=1,...,j-1$. Nazywanie ich może nie być właściwe$q_i$ „wektor wejściowy” i nie rozwiązuje głównej różnicy proceduralnej między MGS i CGS.
W tym poście$4\times 3$Macierz Lauchli jest używana jako przykład do demonstracji różnych wyników między MGS i CGS. Chociaż nadal nie ma intuicyjnego wyjaśnienia tego pytania, zauważam, że w tym przykładzie Lauchli wynik, że$q_3^{CGS}$ nie jest ortogonalny do $q_2^{CGS}$ jest ponieważ $r_{23}^{CGS}$jest błędnie obliczona, z względnym błędem 100%. Jednak nie mogę zrozumieć, dlaczego procedura MGS może znacząco złagodzić ten problem.
Bardzo doceniam wszelkie komentarze.
Odpowiedzi
Zarówno w CGS, jak i MGS, krok ortogonalizacji polegający na odejmowaniu rzutów na kolumny $Q$które zostały już obliczone, wprowadzają błędy z powodu arytmetyki o skończonej precyzji. Każda kolumna$\mathbf{q}_i$ z $Q$ dlatego ma pewien składnik błędu w kierunku poprzednio obliczonych kolumn $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$. Błąd narasta wraz ze wzrostem numeru kolumny$i$, co jest nieodłączną słabością obu algorytmów.
W CGS: ortogonalizacja kolumny $n$ przeciwko kolumnie $\mathbf{q}_{i}$ ($i<n$) jest wykonywana przez rzutowanie oryginalnej kolumny $A$ (nazwij to $\mathbf{a}_n$) na $\mathbf{q}_{i}$ i odejmowanie. $$ \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} $$ Z drugiej strony w MGS komponenty wzdłuż każdego $\mathbf{q}_i$ są natychmiast odejmowane od pozostałych kolumn na prawo od kolumny $i$ tak szybko jak $\mathbf{q}_i$są obliczane. Dlatego ortogonalizacja kolumny$n$ przeciwko $\mathbf{q}_{i}$ nie jest wykonywana przez projekcję $\mathbf{q}_{i}$ w stosunku do oryginalnej kolumny $A$ jak to jest w CGS, ale raczej w stosunku do wektora otrzymanego przez odjęcie od tej kolumny $A$ komponenty w rozpiętości ($\mathbf{q}_1….\mathbf{q}_{i-1}$). Jest to ważne ze względu na składniki błędów$\mathbf{q}_i$, który rozpiętość $\{\mathbf{q}_1….\mathbf{q}_{i-1}\}$.
Dokładniej, w MGS ortogonalizacja kolumny $n$ przeciwko $\mathbf{q}_{i}$ jest wykonywana przez odjęcie składnika $\mathbf{q}_{i}$ z wektora $\mathbf{v}_n^{i-1}$, gdzie $\mathbf{v}_n^0\equiv \mathbf{a}_n$ i $\mathbf{v}_n^i$ ($0<i<n$) jest zdefiniowany jako $$ \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} $$ Zwróć uwagę na różnicę współczynników projekcji w nawiasach w powyższym wyrażeniu, $(\mathbf{q}_{i}^T\cdot \mathbf{v}_n^{i-1})$i odpowiedni dla CGS, ($\mathbf{q_i^T}\cdot \mathbf{a_n}$). Wektor$\mathbf{q}_i$ zawiera komponenty błędu w rozpiętości ($\mathbf{q}_1….\mathbf{q}_{i-1}$), które wprowadzą błąd do tego współczynnika projekcji. Natomiast wektor$\mathbf{a}_n$ może ogólnie mieć duże komponenty w rozpiętości ($\mathbf{q}_1….\mathbf{q}_{i-1}$), wektor $\mathbf{v}_n^{i-1}$ ma tylko komponenty błędów w rozpiętości ($\mathbf{q}_1….\mathbf{q}_{i-1}$) ponieważ w informatyce $\mathbf{v}_n^{i-1}$ te składniki $\mathbf{a}_n$ w rozpiętości ($\mathbf{q}_1….\mathbf{q}_{i-1}$) zostały już odjęte. W rezultacie błąd w tym mnożniku z powodu niedoskonałej ortogonalności między$\mathbf{q}_i$ i $\{\mathbf{q}_1...\mathbf{q}_{i-1}\}$ jest znacznie mniejszy w MGS niż w CGS.
Ze względu na znacznie mniejszy błąd w tym współczynniku projekcji MGS wprowadza mniejszy błąd ortogonalizacji na każdym kroku odejmowania niż CGS.