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
linear-algebra
iterative-method
convergence
krylov-method
Allan P. Engsig-Karup
źródło
źródło
Odpowiedzi:
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 rx
Left Wstępne przygotowanie(P−1(Ax−b))
R =p - 1 ( x -b)
No / Right Preconditioning(AP−1Px=b)
R = x -b
Kryteria konwergencji
Kryteria dywergencji
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.
Resztkowy NaN - jeśli w dowolnym momencie resztkowy ocenia się na NaN, solver powraca jako rozbieżny.
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 ‖dtol
Podział solwera Sama metoda Kryłowa może zasygnalizować rozbieżność, jeśli wykryje pojedynczą macierz lub warunek wstępny.
źródło