Jaka jest zasada zbieżności metod podprzestrzeni Kryłowa do rozwiązywania liniowych układów równań?

Jak rozumiem, istnieją dwie główne kategorie iteracyjnych metod rozwiązywania liniowych układów równań:

Metody stacjonarne (Jacobi, Gauss-Seidel, SOR, Multigrid)
Metody podprzestrzeni Kryłowa (Gradient sprzężony, GMRES itp.)

Rozumiem, że większość metod stacjonarnych działa poprzez iteracyjne relaksowanie (wygładzanie) trybów błędu Fouriera. Jak rozumiem, metoda gradientu sprzężonego (metoda podprzestrzeni Kryłowa) działa poprzez „przechodzenie” przez optymalny zestaw kierunków wyszukiwania z mocy macierzy zastosowanej do $n$ tego reszty. Czy ta zasada jest wspólna dla wszystkich metod podprzestrzeni Kryłowa? Jeśli nie, to jak ogólnie scharakteryzujemy zasadę konwergencji metod podprzestrzeni Kryłowa?

— Paweł
źródło

Twoja analiza metod stacjonarnych jest obciążona przez proste problemy modelowe, ponieważ można je analizować pod kątem trybów Fouriera. Ignoruje także ukryty kierunek naprzemienny (ADI) i wiele innych metod. Celem większości „metod stacjonarnych” jest połączenie wielu prostych „przybliżonych częściowych” solverów w jeden iteracyjny solver. Celem metod Kryłowa jest przyspieszenie (lub nawet wymuszenie) zbieżności danej stacjonarnej iteracji liniowej.

— Thomas Klimpel

Artykuł, który, jak sądzę, został napisany, aby odpowiedzieć na twoje pytania, to Ipsen i Meyer. Pomysł krystalicznych metod, Amer. Matematyka Monthly 105 (1998) s. 889–899. To cudownie dobrze napisany i wyjaśniający artykuł, dostępny tutaj .

— Andrew T. Barker,

@ AndrewT.Barker: Awesome! Dzięki Andrew! :)

— Paweł

Odpowiedzi:

Ogólnie rzecz biorąc, wszystkie metody Kryłowa zasadniczo szukają wielomianu, który jest mały, gdy jest oceniany na widmie macierzy. W szczególności ta reszta metody Kryłowa (z zerowym początkowym domysłem) może być zapisana w formie $n$

r_{n} = {P.}_{n} (ZA) b

$r_n = P_n (A) b$

gdzie to jakiś monomiczny wielomian stopnia . $P_n$ $n$

Jeśli jest diagonalizowalne, przy , mamy $A$ $A=V\Lambda V^{-1}$

\begin{array}{rcl} ‖ r_{n} ‖ & \leq & ‖ V. ‖ \cdot ‖ {P.}_{n} (Λ) ‖ \cdot ‖ {V.}^{- 1} ‖ \cdot ‖ b ‖ \\ = & κ (V.) \cdot ‖ {P.}_{n} (Λ) ‖ \cdot ‖ b ‖ . \end{array}

$\begin{eqnarray*} \|r_n\| &\leq& \|V\|\cdot \|P_n(\Lambda)\|\cdot \|V^{-1}\|\cdot \|b\|\\ &=& \kappa(V) \cdot \|P_n(\Lambda)\| \cdot \|b\|. \end{eqnarray*}$

W przypadku, gdy jest normalny (np. Symetryczny lub jednostkowy) wiemy, że GMRES konstruuje taki wielomian poprzez iterację Arnoldiego, podczas gdy CG konstruuje wielomian przy użyciu innego produktu wewnętrznego (szczegóły w tej odpowiedzi ) . Podobnie, BiCG konstruuje swój wielomian poprzez niesymetryczny proces Lanczosa, podczas gdy iteracja Czebyszewa wykorzystuje wcześniejsze informacje o widmie (zwykle szacunki największych i najmniejszych wartości własnych dla symetrycznych określonych macierzy). $A$ $\kappa(V) = 1.$

Jako fajny przykład (motywowany przez Trefethen + Bau), rozważ macierz o spektrum:

Widmo macierzy

W MATLAB zbudowałem to z:

A = rand(200,200);
[Q R] = qr(A);
A = (1/2)*Q + eye(200,200);

Jeśli weźmiemy pod uwagę GMRES, który konstruuje wielomianów, które faktycznie minimalizują resztki na wszystkich wielomianach monicznych stopnia , możemy łatwo przewidzieć historię resztkową, patrząc na kandydujący wielomian $n$

{P.}_{n} (z) = (1 - z)^{n}

$P_n (z) = (1-z)^n$

co w naszym przypadku daje

| {P.}_{n} (z) | = \frac{1}{{2)}^{n}}

$|P_n(z)| = \frac{1}{2^n}$

do w widmie . $z$ $A$

Teraz, jeśli uruchomimy GMRES na losowym RHS i porównamy resztkową historię z tym wielomianem, powinny one być dość podobne (potencjalne wartości wielomianowe są mniejsze niż resztkowe GMRES, ponieważ ): $\|b\|_2 > 1$

Historia szczątkowa

— Reid.Atcheson
źródło

Czy możesz wyjaśnić, co rozumiesz przez „mały w spektrum macierzy”?

— Paweł

Traktować jako złożoną wielomianu wielomian

ma mały moduł sprężystości w obszarze płaszczyzny zespolonej, które obejmuje zakres

. Wyobraź sobie wykres konturowy nałożony na wykres rozproszenia wartości własnych. Jak mały jest mały? Zależy to od problemu, czy

jest normalne, a od prawej

Podstawową ideą jest jednak to, że sekwencja wielomianów

dąży do stopniowego zmniejszania się widma, tak że resztkowa wartość szacunkowa w mojej odpowiedzi wynosi

P_{n}

$P_n$

A

$A$

A

$A$

b .

$b.$

(P_{n})

$(P_n)$

0

$0$ .

— Reid.Atcheson

@ Reid.Atcheson: Bardzo dobrze powiedziane. Czy mogę polecić napisanie

jako

i wspomnienie, że jest to jeden dla normalnych matryc?

‖ V ‖ ‖ V^{- 1} ‖

$\|V\|\|V^{-1}\|$

κ (V)

$\kappa(V)$

— Jack Poulson

Laplacian wstępnie przygotowany przez optymalną SOR ma widmo bardzo podobne do tej przykładowej matrycy. Szczegóły tutaj: scicomp.stackexchange.com/a/852/119

— Jed Brown

Ściśle mówiąc, CGNE jest niezależny od widma, ponieważ zależy tylko od pojedynczych wartości.

— Jed Brown

W sprawie norm

Jako uzupełnienie odpowiedzi Reid.Atcheson chciałbym wyjaśnić niektóre kwestie dotyczące norm. W iteracji GMRES znajduje wielomianu $n^{\mathrm{th}}$ $P_n$ $2$

r_{n} = ZA x_{n} - b = ({P.}_{n} (ZA) - 1) b - b = {P.}_{n} (ZA) b .

$r_n = A x_n - b = \big(P_n(A) - 1 \big)b - b = P_n(A) b .$

$A$ $A$ $A^{-1}$

\begin{aligned} ‖ r_{n} ‖_{{ZA}^{- 1}} & = r_{n}^{T.} {ZA}^{- 1} r_{n} \\ = (ZA {mi}_{n})^{T.} {ZA}^{- 1} ZA {mi}_{n} \\ = {mi}_{n}^{T.} ZA {mi}_{n} \\ = ‖ {mi}_{n} ‖_{ZA} \end{aligned}

$\begin{align*} \lVert r_n \rVert_{A^{-1}} &= r_n^T A^{-1} r_n \\ &= (A e_n)^T A^{-1} A e_n \\ &= e_n^T A e_n \\ &= \lVert e_n \rVert_{A} \end{align*}$

gdzie użyliśmy błędu

{mi}_{n} = x_{n} - x_{*} = x_{n} - {ZA}^{- 1} b = {ZA}^{- 1} r_{n}

$e_n = x_n - x_* = x_n - A^{-1} b = A^{-1} r_n$

$A$ $A^{-1}$ $A$ $2$ $A^T A$ $A$

Ostrość granic konwergencji

Wreszcie, istnieje interesująca literatura na temat różnych metod Kryłowa i subtelności konwergencji GMRES, szczególnie dla nietypowych operatorów.

Nachtigal, Reddy i Trefethen (1992) Jak szybkie są niesymetryczne iteracje macierzy? (pdf autora) podaje przykłady macierzy, dla których jedna metoda pokonuje wszystkie inne dużym czynnikiem (przynajmniej pierwiastek kwadratowy z rozmiaru matrycy).
Embree (1999) Jak opisowe są granice konwergencji GMRES? daje wnikliwą dyskusję na temat pseudospektr, które dają ostrzejsze granice, a także odnoszą się do matryc niediagonalnych.
Embree (2003) Żółw i zając restartują GMRES (autor pdf)
Greenbaum, Pták i Strakoš (1996) Dla GMRES możliwa jest dowolna nie rosnąca krzywa konwergencji

— Jed Brown
źródło

— Zrezygnowałeś

Metody iteracyjne w pigułce:

Metody stacjonarne są w istocie iteracjami stałymi punktami : do rozwiązania $Ax=b$ , wybierasz odwracalną macierz $C$ i znajdź stały punkt
$x = x + do b - do ZA x$ $x = x + Cb- CAx$ Jest to zbieżne z twierdzeniem Banacha o punkcie stałym if $\|I-CA\|<1$ . Różne metody odpowiadają konkretnemu wyborowi $C$ (np. w przypadku iteracji Jacobi, $C=D^{-1}$ , gdzie $D$ jest matrycą ukośną zawierającą elementy ukośne $A$ ).
Metody Kryłowa Metody podprzestrzeni są w istocie metodami projekcji : wybierasz podprzestrzenie $U,V\subset \mathbb{C}^n$ i poszukaj $\tilde x \in U$ tak, że resztkowe $b-A\tilde x$ jest prostopadły do $V$ . W przypadku metod Kryłowa $U$ oczywiście jest to przestrzeń rozpięta przez moce $A$ zastosowane do początkowej pozostałości. Różne metody odpowiadają następnie konkretnym wyborom $V$ (na przykład, $V=U$ dla CG i $V=AU$ dla GMRES).

Właściwości zbieżności tych metod (i ogólnie metod projekcji) wynikają z faktu, że ze względu na odpowiedni wybór $V$ , $\tilde x$ są optymalne $U$ (np. minimalizują błąd w normie energetycznej dla CG lub resztkowy dla GMRES). Jeśli zwiększysz wymiar $U$ w każdej iteracji masz gwarancję (dokładnie arytmetyki), aby znaleźć rozwiązanie po skończonej liczbie kroków.

Jak zauważył Reid Atcheson, używając spacji Kryłowa dla $U$ pozwala udowodnić wskaźniki konwergencji pod względem wartości własnych (a tym samym liczby warunków) $A$ . Ponadto mają one kluczowe znaczenie dla uzyskania wydajnych algorytmów do obliczania projekcji $\tilde x$ .

Jest to dobrze wyjaśnione w książce Youcefa Saada na temat metod iteracyjnych .

— Christian Clason
źródło