Kryteria zatrzymania iteracyjnych solverów liniowych stosowanych w układach prawie pojedynczych

$Ax=b$ $A$ $\lambda_0$ $A$ $r_n:=b-Ax_n$ $\|r_n\|/\|r_0\|<tol$ $n$ $v$ $\lambda_0$ $Av=\lambda_0v$ . Załóżmy, że początkowa wartość rezydualna jest duża, to może się zdarzyć, że zatrzymamy się na ale błąd jest nadal duży. Jaki jest lepszy wskaźnik błędu w tym przypadku? Czydobry kandydat? $r_0$ $\|r_n\|/\|r_0\|<tol$ $x_n-x$ $\|x_{n}-x_{n-1}\|$

linear-algebra Hui Zhang
źródło

Możesz pomyśleć o swojej definicji „prawie pojedynczej”. Macierz (z i to matryca tożsamości) ma bardzo małą wartość własną, ale jest tak daleka od liczby pojedynczej, jak to tylko możliwe.

I \cdot ϵ

$I \cdot \epsilon$

ϵ ≪ 1

$\epsilon\ll 1$

I

$I$

David Ketcheson

Równieżwygląda na niewłaściwy zapis. jest bardziej typowy, nie?

| | r_{n} / r_{0} | |

$||r_n/r_0||$

| | r_{n} | | / | | r_{0} | |

$||r_n||/||r_0||$

Bill Barth

Tak, masz rację, Bill! Naprawię ten błąd.

Hui Zhang

Co z? a jaki dokładnie jest twój algorytm?

‖ b - A x ‖ / ‖ b ‖

$\| b - Ax \| / \| b \|$

shuhalo

Dodatek: Myślę, że poniższy artykuł dotyczy w dużej mierze źle kondycjonowanych systemów, o które się martwisz, przynajmniej jeśli używasz CG: Axelson, Kaporin: Szacowanie normy błędu i kryteria zatrzymania w wstępnie przygotowanych iteracjach gradientu sprzężonego. DOI: 10.1002 / nla.244

shuhalo

Odpowiedzi:

Proszę nie używać różnicę pomiędzy kolejnymi iteruje aby zdefiniować kryteria zatrzymania. To błędnie diagnozuje stagnację dla konwergencji. Większość niesymetrycznych iteracji macierzy nie jest monotoniczna, a nawet dokładna arytmetyka GMRES bez restartów może zastygać w przypadku dowolnej liczby iteracji (aż do wymiaru macierzy) przed nagłym zbiegiem. Zobacz przykłady w Nachtigal, Reddy i Trefethen (1993) .

Lepszy sposób na zdefiniowanie zbieżności

Zazwyczaj interesuje nas dokładność naszego rozwiązania, a nie wielkość reszty. W szczególności chcielibyśmy zagwarantować, że różnica między przybliżonym rozwiązaniem a dokładnym rozwiązaniem wystarczająca dla niektórych określonych przez użytkownika . Okazuje się, że można to osiągnąć przez znalezienie takiego, że gdzie jest najmniejszą liczbą pojedynczą ze względu na $x_n$ $x$

| x_{n} - x | < c

$|x_n - x| < c$

c

$c$

x_{n}

$x_n$

| A x_{n} - b | < c ϵ

$|A x_n - b| < c\epsilon$

ϵ

$\epsilon$

A

$A$

\begin{aligned} | x_{n} - x | & = | A^{- 1} A (x_{n} - x) | \\ \leq \frac{1}{ϵ} | A x_{n} - A x | \\ = \frac{1}{ϵ} | A x_{n} - b | \\ < \frac{1}{ϵ} \cdot c ϵ = c \end{aligned}

$\begin{align} |x_n - x| &= |A^{-1} A (x_n - x)| \\ & \le \frac 1 \epsilon |A x_n - A x| \\ & = \frac 1 \epsilon |A x_n - b| \\ & < \frac 1 \epsilon \cdot c \epsilon = c \end{align}$

gdzie zastosowaliśmy, że jest największą liczbą pojedynczą (druga linia) i że dokładnie rozwiązuje (trzecia linia). $1/\epsilon$ $A^{-1}$ $x$ $A x = b$

Oszacowanie najmniejszej liczby pojedynczej $\epsilon$

Dokładne oszacowanie najmniejszej pojedynczej wartości zwykle nie jest bezpośrednio dostępne na podstawie problemu, ale można je oszacować jako produkt uboczny gradientu sprzężonego lub iteracji GMRES. Należy zauważyć, że chociaż szacunki największych wartości własnych i wartości osobliwych jest zazwyczaj dość dobre po kilku iteracjach, dokładne oszacowanie najmniejszego EIGEN / wartość pojedynczej jest zwykle tylko uzyskane po osiągnięciu zbieżności. Przed konwergencją szacunek będzie zasadniczo znacznie większy niż wartość rzeczywista. To sugeruje, że musisz rozwiązać równania, zanim będziesz mógł zdefiniować prawidłową tolerancję . Automatyczna tolerancja zbieżności, która wymaga dokładności podanej przez użytkownika $\epsilon$ $c\epsilon$ $c$ dla rozwiązania i oszacowań najmniejsza liczba pojedyncza z obecnym stanem metody Kryłowa może zbiegać się zbyt wcześnie, ponieważ oszacowanie było znacznie większe niż wartość rzeczywista. $\epsilon$ $\epsilon$

Notatki

Powyższa dyskusja działa również z zastąpionym przez wstępnie kondycjonowany operator i wstępnie kondycjonowany pozostały lub z odpowiednio kondycjonowanym operatorem i błędem . Jeśli $A$ $P^{-1}A$ $P^{-1} (A x^n - b)$ $A P^{-1}$ $P (x_n - x)$ $P^{-1}$ jest dobrym kondycjonerem, kondycjonowany operator będzie dobrze kondycjonowany. W przypadku wstępnego kondycjonowania z lewej strony oznacza to, że wstępnie kondycjonowana reszta może być mała, ale prawdziwa reszta może nie być. Na prawej kondycjonowania jest łatwo zrobić mały, ale prawdziwy błąd Nie może być. To wyjaśnia, dlaczego wstępne kondycjonowanie z lewej strony jest lepsze do zmniejszania błędów, podczas gdy wstępne kondycjonowanie z prawej strony jest lepsze do zmniejszania pozostałych (i do debugowania niestabilnych warunków wstępnych). $|P(x_n - x)|$ $|x_n-x|$
Zobacz tę odpowiedź, aby uzyskać więcej informacji na temat norm zminimalizowanych przez GMRES i CG.
Szacunki ekstremalnych wartości pojedynczych można monitorować za -ksp_monitor_singular_valuepomocą dowolnego programu PETSc. Zobacz KSPComputeExtremeSingularValues (), aby obliczyć pojedyncze wartości z kodu.
Podczas korzystania z GMRES do szacowania pojedynczych wartości, bardzo ważne jest, aby nie uruchamiać ponownie (np. -ksp_gmres_restart 1000W PETSc).

Jed Brown
źródło

„” działa również z A zastąpionym przez kondycjonowany operator ”” - Jednak wówczas stosuje się tylko do wstępnie kondycjonowanej pozostałości

jeśli zastosowano

, odpowiednio. do warunku wstępnego błędu

jeśli zastosowano

P^{- 1} r

$P^{-1}r$

P^{- 1} A

$P^{-1}A$

P^{- 1} δ x

$P^{-1}\delta x$

A P^{- 1}

$AP^{-1}$

Arnold Neumaier,

Dobrze, zredagowałem swoją odpowiedź. Zauważ, że prawidłowa skrzynka kondycjonowana daje ci kontrolę nad

, odwijanie kondycjonera wstępnego (zastosowanie

) zwykle wzmacnia błędy w trybach niskoenergetycznych.

P δ x

$P\delta x$

P^{- 1}

$P^{-1}$

Jed Brown

Innym sposobem spojrzenia na ten problem jest rozważenie narzędzi z dyskretnych problemów odwrotnych, to znaczy problemów obejmujących rozwiązanie lub gdzie jest bardzo źle uwarunkowane (tzn. Stosunek pierwszej i ostatniej liczby pojedynczej jest duży). $Ax=b$ $\min ||Ax-b||_2$ $A$ $\sigma_1/\sigma_n$

Tutaj mamy kilka metod wyboru kryterium zatrzymania, a dla metody iteracyjnej zaleciłbym kryterium krzywej L, ponieważ dotyczy ono tylko ilości, które są już dostępne (OŚWIADCZENIE: Mój doradca wprowadził tę metodę, więc jestem zdecydowanie stronniczy to). Z powodzeniem wykorzystałem to w metodzie iteracyjnej.

Chodzi o monitorowanie normy resztkowej i norma rozwiązania , gdzie jest . Podczas iteracji zaczyna to rysować kształt litery L na wykresie dziennika (rho, eta), a punkt na rogu tej litery L jest optymalnym wyborem. $\rho_k=||Ax_k-b||_2$ $\eta_k=||x_k||_2$ $x_k$ $k$

$(\rho_k,\eta_k)$

$abs(\frac{\log(\eta_k)-\log(\eta_{k-1})}{\log(\rho_k)-\log(\rho_{k-1})})$

Istnieją również bardziej szczegółowe metody znajdowania narożnika, które działają lepiej, ale wymagają przechowywania znacznej liczby iteracji. Baw się z tym trochę. Jeśli korzystasz z Matlaba, możesz skorzystać z przybornika Narzędzia do regularyzacji, które implementują niektóre z tych funkcji (w szczególności obowiązuje funkcja „narożnika”).

Należy pamiętać, że takie podejście jest szczególnie odpowiednie w przypadku problemów na dużą skalę, ponieważ dodatkowy czas obliczeniowy jest niewielki.

OscarB
źródło

Wielkie dzięki! Czyli na wykresie loglog (rho, eta) zaczynamy od prawej strony krzywej L i kończymy na górze L, prawda? Po prostu nie znam zasady tego kryterium. Czy możesz wyjaśnić, dlaczego zawsze zachowuje się jak krzywa L i dlaczego wybieramy róg?

Hui Zhang

| | A x - b | |_{2} = | | e | |_{2}

$||Ax-b||_2=||e||_2$

e

$e$

b_{e x a c t} = b + e

$b_{exact}=b+e$ . Aby uzyskać więcej analiz, zobacz Hansen, PC i O'Leary, DP (1993). Zastosowanie krzywej L w regularyzacji dyskretnych źle postawionych problemów. SIAM Journal on Scientific Computing, 14. Zwróć uwagę, że właśnie zaktualizowałem post.

OscarB

@HuiZhang: nie zawsze jest to L. Jeśli regularyzacja jest niejednoznaczna, może to być podwójna litera L, co prowadzi do dwóch kandydatów do rozwiązania, jednego z rażącą cechą lepiej rozwiązać, a drugiego z pewnymi szczegółami lepiej. (I oczywiście mogą pojawić się inne złożone kształty.)

Arnold Neumaier

Czy krzywa L ma zastosowanie do problemów źle uwarunkowanych, w których powinno istnieć unikalne rozwiązanie? To znaczy, interesują mnie problemy Ax = b, gdzie b jest znane „dokładnie”, a A jest prawie pojedyncza, ale wciąż technicznie odwracalna. Wydaje mi się, że jeśli użyjesz czegoś takiego jak GMRES, norma twojego obecnego przypuszczenia x nie zmienia się zbytnio w czasie, szczególnie po pierwszych, jakkolwiek wielu iteracjach. Wydaje mi się, że pionowa część krzywej L występuje, ponieważ nie ma unikalnego / ważnego rozwiązania źle postawionego problemu; czy ta pionowa cecha byłaby obecna we wszystkich źle uwarunkowanych problemach?

nukeguy

W pewnym momencie osiągniesz taką pionową linię, zwykle dlatego, że błędy numeryczne w twojej metodzie rozwiązania powodują, że || Ax-b || nie maleje. Jednak masz rację, że w takich bezszumowych problemach krzywa nie zawsze wygląda jak L, co oznacza, że zwykle masz kilka narożników do wyboru, a wybranie jednego z drugiego może być trudne. Uważam, że w artykule, do którego nawiązałem w moim komentarzu powyżej, krótko omówiono scenariusze pozbawione hałasu.