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

31

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 Ax=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.ATAx=ATb

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.

chaohuang
źródło
1
Cześć @chaohuang i witamy w SciComp! Być może zechcesz zobaczyć tę dyskusję: scicomp.stackexchange.com/questions/81/...
Paul
Cześć, Paul, dzięki za komentarze, czy ten wątek dotyczy tylko rzadkich matryc czy jakiejkolwiek matrycy?
chaohuang,
6
Twoje pytanie ma szeroki zakres i może być nieco zbyt szerokie dla formatu pytań i odpowiedzi, który mamy tutaj na stosie wymiany ... czy istnieje konkretna klasa systemu macierzy, którą jesteś zainteresowany?
Paweł
3
@chaohuang Istnieje wiele książek na ten temat. To pytanie przypomina trochę pytanie lekarza, jak wybierają leczenie „ogólnie”. Jeśli chcesz zadać pytanie, które nie jest specyficzne dla określonej klasy problemów, powinieneś zaangażować się w pracę, aby zapoznać się z polem i zadać coś precyzyjnego. W przeciwnym razie wyjaśnij konkretny problem, który Cię dotyczy.
Jed Brown
2
Z FAQ: Jeśli potrafisz wyobrazić sobie całą książkę, która odpowiada na twoje pytanie, zadajesz zbyt wiele. Z tym pytaniem związane są całe czasopisma i setki książek.
David Ketcheson

Odpowiedzi:

45

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 :Ax~

  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?x~x~x~x<103x
  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 tutajA

  • 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:

  • 1000O(n2)O(n3)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

  • AA

  • 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).

Christian Clason
źródło
2
Podoba mi się twoja analogia do śrubokręta!
Paweł
@chaohuang Jeśli odpowiedziałeś na twoje pytanie, powinieneś je zaakceptować. (Jeśli tak się nie stanie, możesz wskazać, czego brakuje).
Christian Clason
@ChristianClason zaakceptował to. Czekałem i miałem nadzieję, że ktoś rzuci nieco światła na kwestię prostokątnych matryc. Ponieważ
minęło sporo
@chaohuang Thank you. If you're still interested in rectangular matrices, you should pose a (linked) question on "How to choose a method for solving overdetermined systems".
Christian Clason
Here a reference on use of iterative methods for solving large sparse systems of linear equations.
chaohuang