Problemy, w których gradient sprzężony działa znacznie lepiej niż GMRES

Interesują mnie przypadki, w których gradient sprzężony działa znacznie lepiej niż metoda GMRES.

Ogólnie rzecz biorąc, CG jest lepszym wyborem w wielu przypadkach SPD (symetrycznie-dodatnio-określony), ponieważ wymaga mniej pamięci, a teoretyczna granica szybkości konwergencji dla CG jest dwukrotnie wyższa niż GMRES. Czy są jakieś problemy z faktycznym obserwowaniem takich stawek? Czy istnieje jakakolwiek charakterystyka przypadków, w których GMRES działa lepiej lub porównywalnie do CG dla tej samej liczby spmv (rzadkie mnożenie macierzy-wektora).

Jedną rzeczą, która CG ma na jej korzyść jest to, że nie jest zminimalizowanie dyskretną $l^2$ normę dla swoich szczątkowych wielomianów (co robi GMRES). Zamiast tego minimalizuje normę indukowaną macierzą i bardzo często ta norma indukowana macierzą jest bardzo zbliżona do normy energetycznej dla dyskretyzacji problemów fizycznych, i często jest to znacznie bardziej rozsądna norma do pomiaru błędu z powodu nadchodzących właściwości konserwujących z fizyki.

Tego rodzaju efekt można osiągnąć również za pomocą GMRES, jeśli przeprowadzenie rozkładu Cholesky'ego na macierz masy nie jest zbyt drogie, można zmusić produkty wewnętrzne do uzyskania produktów energii wewnętrznej, które chcesz.

Wtedy przypadki, w których należy oczekiwać, że CG będzie działać bardzo inaczej niż GMRES, to wtedy, gdy stałe implikowane w równoważności norm są bardzo różne. To może być prawdą, na przykład w sposobie wysokiej celu widmowego Galerkina gdzie dyskretne $l^2$ normy stosowane w GMRES traktuje wszystkich stopni swobody za równe, choć w rzeczywistości wielomianowe gradienty najostrzejsze blisko granic (stąd węzeł klasterów), a więc stałe normą równoważności pomiędzy tą normą, a mówiąc ciągłe $L^2$ normą podane przez matrycę masa może być bardzo duża.

Podejrzewam, że ogólnie nie ma dużej różnicy między GMRES i CG dla matrycy SPD.

Powiedzmy, że mamy do rozwiązywania x = b z A symetrycznego dodatnia określony i przypuszczenie począwszy x 0 = 0 oraz generowanie iteruje z CG i GMRES, nazywamy je x c k i x g k . Obie metody iteracyjne będą budować x k z tej samej przestrzeni Kryłowa K k = { b , b , 2 b , ... } . Zrobią to na nieco inne sposoby.$Ax = b$$A$$x_0 = 0$$x_k^c$$x_k^g$$x_k$$K_k = \{ b, Ab, A^2b, \ldots \}$

CG charakteryzuje się minimalizacją błędu w normie energetycznej indukowanej przez A , tak że ( A e c k , e c k ) = ( A ( x - x c k ) , x - x c k ) = min y ∈ K ( A ( x - y ) , x $e_k^c = x - x_k^c$$A$

$$\begin{equation} (A e_k^c, e_k^c) = (A (x - x_k^c), x - x_k^c) = \min_{y \in K} (A (x-y), x-y). \end{equation}$$

GMRES minimalizuje natomiast resztkowe , i robi to w dyskretnej normie ℓ 2 , tak że ( r k , r k ) = ( b - A x g k , b - A x g k ) = minimum y ∈ K ( b - r , b - Y ) $r_k = b - A x^g_k$$\ell^2$

$$\begin{equation} (r_k, r_k) = (b - A x_k^g, b - A x_k^g) = \min_{y \in K} (b - Ay, b - Ay). \end{equation}$$ Teraz, korzystając z równania błędu , możemy również zapisać GMRES jako minimalizujące ( r k , r k ) = ( A e g k , A e g k ) = ( A 2 e g k , e g k ) gdzie Chcę podkreślić, że dotyczy to tylko macierzy A SPD . Następnie mamy CG minimalizującą błąd w odniesieniu do $A e_k = r_k$ $$\begin{equation} (r_k, r_k) = (A e_k^g, A e_k^g) = (A^2 e_k^g, e_k^g) \end{equation}$$ $A$$A$normą i GMRES minimalizuje błędów w odniesieniu do 2 normy. Jeśli chcemy, aby zachowywały się zupełnie inaczej, intuicyjnie potrzebowalibyśmy A, tak że te dwie normy są bardzo różne. Ale dla SPD A normy te będą zachowywać się dość podobnie.$A^2$$A$$A$

Się jeszcze dokładniej, w pierwszej wersji z przestrzenią Kryłowa , zarówno CG i GMRES skonstruuje w przybliżeniu formy x 1 = α b . CG wybierze α = ( b , b $K_1 = \{ b \}$$x_1 = \alpha b$ i GMRES wybierze α=(Ab,b

$$\begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation}$$ Jeślijest diagonalna z wejściami(ε,1,1,1,...)ib=(1,1,0,0,0,...),a następnie jakoε→0pierwszy etap CG będzie dwukrotnie większe niż pierwsze GMRES krok. Prawdopodobnie możesz zbudowaćAi $$\begin{equation} \alpha = \frac{ (Ab,b) }{ (A^2b,b) }. \end{equation}$$ $A$$(\epsilon,1,1,1,\ldots)$$b = (1,1,0,0,0,\ldots)$$\epsilon \rightarrow 0$$A$$b$ tak, że ten współczynnik dwóch różnic utrzymuje się przez całą iterację, ale wątpię, żeby stało się jeszcze gorzej.

Jedną rzeczą jest to, że GMRES nigdy nie jest stosowany wszędzie tam, gdzie można zastosować CG. Nie sądzę, żeby porównywanie tych dwóch miało sens. W przypadku matryc SPD CG jest zdecydowanie zwycięzcą ze względu na wymagania dotyczące pamięci i powody wspomniane powyżej. Ciekawym pytaniem byłoby znalezienie rozszerzenia CG, które ma zastosowanie do problemów, w których nie można zastosować CG. Istnieją metody takie jak BiCG-stab, które nie wymagają liniowego zwiększania pamięci, jak GMRES, ale zbieżność nie jest tak dobra jak GMRES (czasami nawet przy zrestartowanym GMRES).