Jak wybrać metodę rozwiązywania równań liniowych

Według mojej wiedzy istnieją 4 sposoby rozwiązania układu równań liniowych (popraw mnie, jeśli jest więcej):

1. Jeśli macierz systemowa jest kwadratową matrycą pełnego rzędu, można użyć reguły Cramera;
2. Oblicz odwrotność lub pseudoinwersję macierzy systemowej;
3. Użyj metod rozkładu macierzowego (eliminacja Gaussa lub Gaussa-Jordana jest uważana za rozkład LU);
4. Użyj iteracyjnych metod, takich jak metoda gradientu sprzężonego.

W rzeczywistości prawie nigdy nie chcesz rozwiązywać równań za pomocą reguły Cramera lub obliczania odwrotności lub pseudoinwersji, szczególnie w przypadku matryc wielowymiarowych, więc pierwsze pytanie brzmi, kiedy należy zastosować odpowiednio metody rozkładu i metody iteracyjne. Myślę, że to zależy od wielkości i właściwości macierzy systemowej.

Drugie pytanie dotyczy twojej wiedzy, jakie metody dekompozycji lub metody iteracyjne są najbardziej odpowiednie dla określonej matrycy systemowej pod względem stabilności numerycznej i wydajności.

Na przykład metodę gradientu sprzężonego stosuje się do rozwiązywania równań, w których macierz jest symetryczna, a dodatnia jest określona, ​​chociaż można ją również zastosować do dowolnych równań liniowych, przekształcając $\mathbf{A}x=b$ do . Również w przypadku dodatniej określonej macierzy można użyć metody rozkładu Cholesky'ego, aby znaleźć rozwiązanie. Ale nie wiem, kiedy wybrać metodę CG, a kiedy wybrać rozkład Choleskiego. Mam wrażenie, że lepiej byłoby zastosować metodę CG dla dużych matryc.$\mathbf{A}^{\rm T}\mathbf{A}x=\mathbf{A}^{\rm T}b$

W przypadku matryc prostokątnych możemy użyć rozkładu QR lub SVD, ale znowu nie wiem, jak wybrać jedną z nich.

W przypadku innych macierzy nie wiem, jak wybrać odpowiedni solver, takie jak matryce hermitowskie / symetryczne, macierze rzadkie, macierze pasmowe itp.

Twoje pytanie przypomina trochę pytanie o to, który śrubokręt wybrać w zależności od napędu (gniazdo, Phillips, Torx, ...): Poza tym, że jest ich zbyt wiele , wybór zależy również od tego, czy chcesz po prostu dokręcić jedną śrubę, czy zamontować cały zestaw półek bibliotecznych. Niemniej jednak, w częściowej odpowiedzi na twoje pytanie, oto kilka kwestii, o których powinieneś pamiętać przy wyborze metody rozwiązania układu liniowego . Ograniczę się także do odwracalnych matryc; przypadki nadmiernie lub zbyt słabo określonych systemów to inna sprawa i naprawdę powinny to być osobne pytania.$Ax=b$

Jak słusznie zauważyłeś, opcje 1 i 2 są od razu: Obliczenie i zastosowanie macierzy odwrotnej jest niezwykle złym pomysłem, ponieważ jest znacznie droższe i często mniej stabilne numerycznie niż zastosowanie jednego z innych algorytmów. To pozostawia wybór pomiędzy metodami bezpośrednimi a iteracyjnymi. Pierwszą rzeczą do rozważenia nie jest macierz , ale to, czego oczekujesz od rozwiązania numerycznego ˜ x :$A$$\tilde x$

1. Jak dokładna musi być? Czy musi rozwiązać system aż do precyzji maszyny, czy jesteś zadowolony z ˜ x spełniającego (powiedzmy) ‖ ˜ x - x ∗ ‖ < 10 - 3 , gdzie x ∗ jest dokładnym rozwiązaniem?$\tilde x$$\tilde x$$\|\tilde x - x^*\| < 10^{-3}$$x^*$
2. Jak szybko tego potrzebujesz? Jedyną istotną miarą tutaj jest czas na twoim komputerze - metoda, która doskonale skaluje się w ogromnym klastrze, może nie być najlepszym wyborem, jeśli nie masz jednej z nich, ale masz jedną z tych błyszczących nowych kart Tesli.

Ponieważ nie ma czegoś takiego jak darmowy lunch, zwykle musisz zdecydować się na kompromis między nimi. Następnie zaczniesz patrzeć na macierz (i swój sprzęt), aby zdecydować się na dobrą metodę (a raczej metodę, dla której możesz znaleźć dobrą implementację). (Zwróć uwagę, jak unikałem pisania „najlepszego” tutaj ...) Najważniejsze właściwości tutaj$A$

• Struktura : Czy symetryczne? Czy to jest gęste czy rzadkie? Pasiasty?$A$
• Te wartości własne : Czy wszystkie są dodatnie (tzn jest dodatnio określona)? Czy są skupione? Czy niektóre z nich mają bardzo małą lub bardzo dużą wielkość?$A$

Mając to na uwadze, musisz przeszukiwać (ogromną) literaturę i oceniać różne metody, które znajdziesz dla konkretnego problemu. Oto kilka ogólnych uwag:

• $1000$$\mathcal{O}(n^2)$$\mathcal{O}(n^3)$$A$

  Dotyczy to również (dużych) rzadkich macierzy, jeśli nie napotkasz problemów z pamięcią: Ogólnie rzecz biorąc, rzadkie macierze nie mają rzadkiego rozkładu LU, a jeśli czynniki nie pasują do (szybkiej) pamięci, metody te stają się bezużyteczne.

  $A$

• $A$$A$

• Jeśli wielokrotnie musisz rozwiązywać układy liniowe z tą samą matrycą i różnymi prawymi bokami, metody bezpośrednie mogą nadal być szybsze niż metody iteracyjne, ponieważ wystarczy tylko raz obliczyć rozkład. (To zakłada sekwencyjne rozwiązanie; jeśli masz wszystkie prawe strony w tym samym czasie, możesz użyć blokowych metod Kryłowa.)

Oczywiście są to tylko bardzo przybliżone wytyczne: Dla każdego z powyższych stwierdzeń istnieje prawdopodobnie macierz, dla której odwrotność jest prawdziwa ...

Ponieważ poprosiłeś o referencje w komentarzach, oto kilka podręczników i artykułów przeglądowych na początek. (Żadne z nich - ani zestaw - nie jest wyczerpujące; to pytanie jest zbyt szerokie i zbytnio zależy od konkretnego problemu).

• Golub, van Loan: Matrix Computations (wciąż klasyczne odniesienie do algorytmów macierzowych; znacznie rozszerzone czwarte wydanie omawia teraz również rzadkie macierze i ma kod Matlab zamiast Fortran, a także obszerną bibliografię)
• Davis: Direct Methods for Sparse Linear Systems (dobre wprowadzenie do metod dekompozycji dla rzadkich matryc)
• Duff: Metody bezpośrednie (artykuł przeglądowy; więcej szczegółów na temat nowoczesnych bezpośrednich metod „wielopłaszczyznowych” dla rzadkich matryc)
• Saad: Iteracyjne metody dla rzadkich układów liniowych (teoria i - w mniejszym stopniu - praktyka metod Kryłowa; obejmuje również wstępne przygotowanie)

The decision tree in Section 4 of the relevant chapter in the NAG Library Manual answers (in part) some of your questions.

The Eigen Library Documentation also has a nice overview page with a lot of information about different matrix decompositions:

http://eigen.tuxfamily.org/dox/group__TopicLinearAlgebraDecompositions.html