Jak ustalić, że iteracyjna metoda dla dużych układów liniowych jest w praktyce zbieżna?

W informatyce często spotykamy duże układy liniowe, które musimy rozwiązać za pomocą niektórych (skutecznych) środków, np. Metod bezpośrednich lub iteracyjnych. Jeśli skupimy się na tym drugim, jak możemy ustalić, że iteracyjna metoda rozwiązywania dużych układów liniowych jest w praktyce zbieżna?

Oczywiste jest, że możemy przeprowadzić analizę prób i błędów (por. Dlaczego mój iteracyjny liniowy solver nie jest zbieżny? ) I polegać na iteracyjnych metodach, które gwarantują zbieżność przez dowody lub mają solidne podstawy doświadczenia (np. Metody podprzestrzeni Kryłowa, takie jak CG i GMRES odpowiednio dla systemów symetrycznych i niesymetrycznych).

Ale co można zrobić, aby wprowadzić w praktyce konwergencję? a co się dzieje

W przypadku wielu równań różniczkowych cząstkowych powstających w przyrodzie, szczególnie przy silnych nieliniowościach lub anizotropiach, wybór odpowiedniego warunku wstępnego może mieć duży wpływ na to, czy metoda iteracyjna zbiega się szybko, powoli, czy wcale. Przykłady problemów, o których wiadomo, że mają szybkie i skuteczne warunki wstępne, obejmują silnie eliptyczne równania różniczkowe cząstkowe, w których metoda wielosiatkowa często osiąga szybką zbieżność. Istnieje szereg testów, których można użyć do oceny konwergencji; tutaj wykorzystam jako przykład funkcjonalność z PETSc, ponieważ jest to prawdopodobnie najstarsza i najbardziej dojrzała biblioteka do iteracyjnego rozwiązywania rzadkich układów równań liniowych (i nieliniowych).

PETSc używa obiektu o nazwie KSPMonitor do monitorowania postępu solvera iteracyjnego i decydowania o tym, czy solver jest zbieżny czy rozbieżny. Monitor używa czterech różnych kryteriów, aby zdecydować, czy zatrzymać. Więcej szczegółów na temat dyskusji tutaj można znaleźć na stronie podręcznika dla KSPGetConvergedReason () .

Zakładamy, że użytkownik rozwiązuje następujący układ równań dla : Nazywamy bieżące zgadywanie i definiujemy pozostały oparciu o styl wstępnego kondycjonowania:x = b x $x$

1. Left Wstępne przygotowanie$\left(P^{-1}(Ax − b) \right)$ R =p - 1 ( x -b)

   $$\hat{r}=P^{-1}(A\hat{x}-b)$$

2. No / Right Preconditioning$\left(AP^{-1}Px = b \right)$ R = x -b

   $$\hat{r}=A\hat{x}-b$$

Kryteria konwergencji

1. Absolutna tolerancja - Kryterium absolutnej tolerancji jest spełnione, gdy normalna wartość rezydualna jest mniejsza niż wstępnie zdefiniowana stała : $a_{tol}$ $$\|\hat{r}\| \le a_{tol}$$
2. Względna tolerancja - Kryterium względnej tolerancji jest spełnione, gdy normalna wartość rezydualna jest mniejsza niż norma po prawej stronie przez współczynnik z góry określonej stałej : ‖ R ‖ ≤ r t O l ⋅ ‖ b $r_{tol}$ $$\|\hat{r}\| \le r_{tol}\cdot \|b\|$$
3. Inne kryteria - Rozwiązanie iteracyjne może również zbiegać się z powodu wykrycia małej długości kroku lub krzywizny ujemnej.

Kryteria dywergencji

1. Maksymalna liczba iteracji - liczba iteracji, które solver może wykonać, jest ograniczona maksymalną liczbą iteracji. Jeśli żadne z pozostałych kryteriów nie zostanie spełnione po osiągnięciu maksymalnej liczby iteracji, monitor powróci jako rozbieżny.

2. Resztkowy NaN - jeśli w dowolnym momencie resztkowy ocenia się na NaN, solver powraca jako rozbieżny.

3. Rozbieżność normy resztkowej Monitor powraca jako rozbieżny, jeśli w którymkolwiek momencie norma wartości resztkowej jest większa niż norma po prawej stronie o współczynnik predefiniowanej stałej : ‖ R ‖ ≥ d t O l ⋅ ‖ b $d_{tol}$

   $$\|\hat{r}\| \ge d_{tol}\cdot \|b\|$$

4. Podział solwera Sama metoda Kryłowa może zasygnalizować rozbieżność, jeśli wykryje pojedynczą macierz lub warunek wstępny.