metoda wielosiatkowa do rozwiązania PDE

15

Potrzebuję prostego wyjaśnienia metody wielosiatkowej lub literatury na ten temat.

Znam metody iteracyjne, w tym BiCGStab, CG, GS, Jacobi i kondycjonowanie wstępne, ale jestem początkującym w metodzie wielosiatkowej.

Czy ktoś może wyjaśnić to szczegółowo lub przynajmniej podać wyraźnie pseudokod lub kod źródłowy, nawet z dobrą literaturą dla początkujących? Dzięki!

Nurlan
źródło

Odpowiedzi:

15

Główną ideą multigrid jest projekcja. Staram się myśleć o tym w następujący sposób:

Załóżmy, że chcę rozwiązać PDE z dużą dokładnością, więc dyskretyzuję domenę (powiedzmy, stosując metodę różnic skończonych) na bardzo drobnej siatce z dużą ilością punktów. Na koniec ustawiam swój system równań i jestem gotów go rozwiązać. Próbuję użyć mojego ulubionego solvera iteracyjnego (jacobi, gauss seidel, gradient sprzężony itp.). Poczekam dłużej niż dzień i zdaję sobie sprawę, że mój komputer wciąż próbuje obliczyć odpowiedź !!!

Powodem, dla którego te metody iteracyjne nie działają szybko, jest to, że (zazwyczaj), gdy konfigurujesz duży układ równań takich jak ten, sama macierz ma wartości własne bardzo zbliżone do 1. Dlaczego to ma znaczenie? Ponieważ szybkość zbieżności wielu metod iteracyjnych jest odwrotnie proporcjonalna do największej wartości własnej (patrz link Christiana Clasona do Multigrid Tutorial Slides Brigga, część 1, strona 27). Zatem im bliższa największej wartości własnej jest 1, tym wolniejsza jest metoda iteracyjna. (Uwaga: nieco to upraszcza, ale pomaga zmotywować potrzebę korzystania z wielu sieci).

Oczywiście, zawsze szybciej jest rozwiązać problem, jeśli jest mniej niewiadomych (tj. Na grubej siatce z mniejszą liczbą punktów siatki). Co ważniejsze, rozwiązanie (lub rozwiązanie przybliżone) na grubszej siatce jest dobrym punktem wyjścia do rozwiązania problemu na drobniejszej siatce. Jest to kluczowa idea większości (jeśli nie wszystkich) metod wielosieciowych. Dlaczego tak jest? Intuicyjnie ma to sens, ale istnieje matematycznie rygorystyczny sposób uzasadnienia tego.

Spójrzmy na cztery tryby błędu w metodzie iteracyjnej (dla argumentów, powiedzmy Jacobi lub Gauss Seidel) zastosowane do pierwotnego problemu drobnej siatki. Widzimy, że w ciągu pierwszych kilku iteracji większość błędów wysokiej częstotliwości (wysoce oscylacyjnych) jest usuwana! Jest to świetne, ale nadal występuje błąd niskiej częstotliwości (mniej oscylacyjny), który wciąż pozostaje i nie ustępuje szybko. W rzeczywistości jest to błąd niskiej częstotliwości, który uniemożliwia szybką konwergencję standardowej metody iteracyjnej.

kiedy rozwiązujemy problem na grubszej siatce (powiedzmy, metodą iteracyjną, taką jak Jacobi lub Gauss-Seidel), zasadniczo jesteśmy w stanie znacznie szybciej usunąć błędy niższej częstotliwości (tj. w mniejszej liczbie iteracji) niż na drobnej siatce . Tak więc, jeśli rozwiążemy problem grubej siatki, mamy rozwiązanie, którego błędy dolnej częstotliwości zostały znacznie zmniejszone. Byłby zatem użyteczny jako punkt wyjścia do iteracyjnej metody na drobniejszej siatce.

Chociaż istnieją różne metody wielosieciowe, większość z nich działa w kilku wariantach:

  1. Zacznij od problemu z drobną siatką
  2. Projektuj na grubej siatce (znanej również jako ograniczenie )
  3. Przybliżenie rozwiązania na grubej siatce (za pomocą innego solwera)
  4. Rzuć gruboziarniste rozwiązanie na drobniejszą siatkę (znaną również jako przedłużenie )
  5. Wykorzystując projekcję z 4. jako wstępne przypuszczenie, rozwiąż problem drobnej siatki metodą iteracyjną.

Dla mnie najtrudniejszą częścią metody wielosiatkowej są rzuty między siatkami. Samouczki Briggs sugerowane przez @ChristianClason radzą sobie z tym tematem znacznie lepiej niż ja.

Paweł
źródło
Dziękuję za szczegółową odpowiedź! Teraz mam podstawową wiedzę na temat metody multigrdi. Teraz mam konkretne pytanie dotyczące procesów ograniczania i przedłużania. Czytałem, że niektóre Macierze Ograniczeń R i Macierzy Interpolacji M i formułach takich jak A2 = RAI używane były do ​​projekcji między siatkami. Ale nie zrozumiałem, jak skonstruować macierze R i I. Czy są jakieś pomysły na ten temat?
Nurlan
Spójrz na slajdy 45–57 wieloukładowego samouczka Briggsa (część 1) opublikowanego przez ChristianClason. Tam Briggs opisuje proces Geometrycznej Metody Wielosieciowej. To najprostsze wytłumaczenie, jakie mogę znaleźć. Jeśli masz dodatkowe pytania, napisz nowe pytanie! :)
Paweł
15

Ta strona prawdopodobnie nie jest dobrym miejscem, aby poprosić o szczegółowe wyjaśnienie za pomocą pseudokodu (jak podano w FAQ : „Jeśli możesz sobie wyobrazić całą książkę, która odpowiada na twoje pytanie, pytasz za dużo”), więc możesz chcieć zacząć od jednej z klasycznych książek na ten temat (wymienionych poniżej) i powrócić z konkretnymi pytaniami na temat konkretnych szczegółów, z którymi masz problem.

Christian Clason
źródło
2
Briggs jest naprawdę dobry!
vanCompute,
5

Kolejny klasyk:

  • Wesseling, Wprowadzenie do metod wielosiatkowych, John Wiley & Sons, 1992.

Przykładowe kody można znaleźć w MGNet

Chris
źródło