Które iteracyjne solwery liniowe są zbieżne w przypadku dodatnich macierzy półprzewodników?

Chcę wiedzieć, które z rozwiązują klasyczny liniowych (np Gauss-Seidel Jacobiego, SOR) gwarantowane są zbieżne do problemu , gdzie jest pozytywne pół definitywna i oczywiście $Ax=b$ $A$ $b \in im(A)$

(Uwaga jest półokreślona i nieokreślona) $A$

— olamundo
źródło

Masz na myśli pozytywne półokreślone macierze?

— meawoppl

Po co rozwiązywać układ liniowy z taką matrycą? Jeśli się nie mylę, jeśli twoja dodatnia półfinałowa macierz nie jest pojedyncza, to jest po prostu pozytywnie określona.

— faleichik

Tak jestem pewna. Muszę odświeżyć pamięć jak na faktyczny dowód, ale zgodnie z tym, co mówiłeś - jeśli mianownik w obliczeniu wynosi zero, oznacza to, że wynosi zero, co oznacza, że wszystkie „kierunki wyszukiwania”, w których A nie jest pojedyncza, zostały wyczerpane, a resztki, które pozostały, nie znajdują się w przedziale A (a zatem jest to „optymalne” rozwiązanie). W przypadku, gdy w rzeczywistości , tak się nie stanie, ponieważ reszta osiągnie zero tuż przed pierwszym

α

$\alpha$

A P_{k}

$A P_k$

b \in s p a n (A)

$b \in span(A)$

A P_{k} = 0

$AP_k=0$

— olamundo

Ustaw . Następnie . CG zbiegnie się z powodu dla wszystkich . Innymi słowy, nigdy nie pozostawiasz dla którego jest pozytywnie określone.

x_{0} = b

$x_0=b$

A^{n} b \in I m (A)

$A^nb\in Im(A)$

x_{n}^{*} A x_{n} > 0

$x_n^\ast Ax_n> 0$

0 \neq x_{n} \in I m (A)

$0\ne x_n\in Im(A)$

I m (A)

$Im(A)$

A

$A$

— Deathbreath

@faleichik: Macierze o zmniejszonej gęstości w mechanice kwantowej są dodatnie półokreślone w bardzo wielu przypadkach.

— Deathbreath

Odpowiedzi:

Algorytm sprzężonego gradientu działa w przypadku problemów półfinałowych i daje rozwiązanie normy minimalnej.

— Arnold Neumaier
źródło

dzięki. Wszelkie pomysły na temat „archaicznych” solverów, np. SOR Gauss-Seidel itp.

— olamundo

Nie są już prawie nigdy używane i nie wiem, jak się zachowują.

— Arnold Neumaier

Aby wyjaśnić: CG z pewnością nie działa w formie wanilii dla półokreślonych matryc; teoretycznie może działać, jeśli B jest na obrazie A; ale raczej nie zakończy się to dobrze w praktyce numerycznej. Bardzo podobny MINRES na bazie krylova jest tutaj znacznie lepszym wyborem. Ponadto, te „archaiczne” solwery są szeroko stosowane w solverach z wieloma sieciami, żeby wymienić tylko jeden przykład.

— Eelco Hoogendoorn,

$b$ $A$

To samo nie jest prawdą w przypadku Jacobiego; co jest wstydem, ponieważ kto chce zawracać sobie głowę Gauss-Seidelem na temat nowoczesnego sprzętu komputerowego? Jeśli twój problem można podzielić na bloki po przekątnej, masz szczęście; możesz zastosować aktualizacje Jacobi do tych bloków w sposób stopniowy Gaussa-Seidela i uzyskać to, co najlepsze w przypadku tego rodzaju półokreślonych problemów.

— Eelco Hoogendoorn
źródło