Według mojej wiedzy istnieją 4 sposoby rozwiązania układu równań liniowych (popraw mnie, jeśli jest więcej):
- Jeśli macierz systemowa jest kwadratową matrycą pełnego rzędu, można użyć reguły Cramera;
- Oblicz odwrotność lub pseudoinwersję macierzy systemowej;
- Użyj metod rozkładu macierzowego (eliminacja Gaussa lub Gaussa-Jordana jest uważana za rozkład LU);
- 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 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.
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.
źródło
Odpowiedzi:
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 x~
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 tutajA
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:
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.
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).
źródło
The decision tree in Section 4 of the relevant chapter in the NAG Library Manual answers (in part) some of your questions.
źródło
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
źródło