Metody iteracyjne dla układów nieokreślonych bez struktury blokowej

9

Nieokreślone układy macierzy pojawiają się na przykład w dyskretyzacji problemów punktu siodłowego przez mieszane elementy skończone. Macierz systemową można następnie wprowadzić w formie

(\begin{matrix} ZA & b^{t} \\ b & do \end{matrix})

$\begin{pmatrix} A & B^t \\ B & C\end{pmatrix}$

gdzie jest ujemne (pół) -definiowane, jest dodatnie (pół-) określone, a jest arbitralne. Oczywiście, w zależności od konwencji możesz użyć warunków definitywności, ale taka jest w zasadzie struktura tych macierzy. $A$ $C$ $B$

W przypadku tych metod można zastosować metodę Uzawy, która w rzeczywistości jest po prostu „sztuczką” do przekształcenia układu w równoważny układ półokreślony, który można rozwiązać za pomocą gradientu sprzężonego, spadku gradientu i tym podobnych.

Mam do czynienia z nieokreślonym systemem, który nie ma takiej struktury bloków. W takim przypadku metody typu uzawa nie mają zastosowania. Zdaję sobie sprawę z metody Minimal Residual (MINRES), która została wprowadzona przez Paige & Saunders, która jest tylko trzyterminową rekurencją i wydaje się łatwa do wdrożenia.

Pytanie: Czy MINRES jest ogólnie dobrym wyborem, powiedzmy, do prototypowania? Czy ma to jakieś praktyczne znaczenie? Wstępne przygotowanie nie jest obecnie głównym problemem.

linear-algebra iterative-method shuhalo
źródło

Czy możesz powiedzieć coś więcej o tym, co wyróżnia twoje matryce? Np. Z jakiego rodzaju problemu pochodzi? Czy jest w tym jakaś inna struktura? Itd. Itd.

Bill Barth,

Pozostawiłem to celowo puste, aby uzyskać najbardziej ogólną odpowiedź (szczerze mówiąc, domyślnie zakłada się, że istnieje satysfakcjonująca odpowiedź ogólna). Ale przykład z poniższym równaniem Helmholtza jest dość tym, co miałem na myśli.

shuhalo

7

Jeśli nie przejmujesz się kondycjonowaniem wstępnym, MINRES jest standardowym wyborem. Należy jednak pamiętać, że MINRES wymaga symetrycznego pozytywnego określonego warunku wstępnego.

Jeśli zajmujesz się przygotowaniem wstępnym, ważne jest, aby wziąć pod uwagę różnice strukturalne między większością problemów związanych z siodłem a ogólnymi problemami nieokreślonymi. Większość problemów z punktami siodłowymi powstaje podczas rozwiązywania problemów eliptycznych z ograniczeniami narzuconymi przez mnożniki Lagrange'a. Brak ściśliwości i ograniczenia kontaktowe są częstymi przykładami. W przypadku takich problemów operator stosuje przymus w podprzestrzeni, w której ograniczenie jest spełnione, a funkcje Greena szybko zanikają. Takie problemy można skutecznie rozwiązać za pomocą wstępnych bloków wstępnych (wstępnie kondycjonowany Uzawa jest członkiem tej rodziny), wielosieciowych z kompatybilnymi wygładzaczami (np. Vanka lub opartych na dekompozycji blokowej), lub dekompozycji domen wielopoziomowych z odpowiednimi lokalnymi i grubymi problemami.

Prototypowym przykładem problemu na czas nieokreślony, który nie jest problemem punktu siodłowego, jest równanie Helmholtza

- \nabla \cdot (za \nabla u) - k^{2)} u = fa

$-\nabla\cdot \big( a \nabla u \big) - k^2 u = f$

gdzie jest równomiernie ograniczone powyżej i poniżej przez dodatnie stałe. W przypadku dużych, funkcje Greena są wysoce oscylacyjne, co utrudnia wstępne kondycjonowanie (i dyskretyzację). Dwoma rozsądnymi podejściami są zamiatanie warunków wstępnych opartych na idealnie dopasowanych warstwach i „wielosieciowaniu falowym”, jak opisano w odpowiedziach na to pytanie . Niestety metody te są raczej niestandardowe dla konkretnego równania i techniczne do zaimplementowania. $a(x)$ $k$

Jed Brown
źródło

1

Szczerze mówiąc, podczas gdy zamiatające warunki wstępne są z pewnością technicznie skuteczne w realizacji równolegle, pomysł ten nie jest specyficzny dla Helmholtza; głównym wymaganiem jest absorbujący warunek brzegowy (np. idealnie dopasowane warstwy).

Jack Poulson

3

Powiązane pytanie, które może być interesujące, to jakich wskazówek należy przestrzegać przy wyborze rzadkiego liniowego rozwiązania solvera? , chociaż w tym przypadku interesują Cię tylko metody iteracyjne. Rozumiem metody iteracyjne, że konwergencja dla dowolnej metody jest silnie zależna od spektrum macierzy. Chociaż nie możesz użyć metody Uzawy, wciąż możesz wypróbować GMRES, Biconjugate ustabilizowany gradient, MINRES, quasi-minimalną metodę resztkową i inne metody iteracyjne, które mają zastosowanie do macierzy nieokreślonych.

Jeśli problem stanowi kodowanie różnych metod, możesz wywołać solwery w algorytmie za pomocą biblioteki takiej jak PETSc , która implementuje różne iteracyjne solwery liniowe.

Geoff Oxberry
źródło

1

MINRES jest najlepszym wyborem dla tego rodzaju problemów.

Kees Vuik
źródło

1

Nie łącz w ten sposób swojej witryny osobistej. Nie krępuj się łączyć określonych zasobów, które są istotne dla Twojej odpowiedzi, ale nie łącz w ten sposób swojej witryny osobistej. Usunąłem go z tej odpowiedzi. Takie linki należą do Twojego profilu użytkownika.

Jed Brown

Czy możesz wyjaśnić, dlaczego MINRES jest najlepszym wyborem dla tego rodzaju problemów? Dodanie większej liczby szczegółów sprawi, że twoja odpowiedź będzie bardziej użyteczna dla społeczności i zwiększy liczbę głosów.

Geoff Oxberry

Metody iteracyjne dla układów nieokreślonych bez struktury blokowej

Odpowiedzi: