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$

linear-algebra iterative-method convergence linear-solver 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