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!
Odpowiedzi:
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:
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.
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.
Briggs, Multigrid Tutorial , SIAM, 2000 (Możesz pobrać slajdy tutaj i tutaj ) Jest to swobodne źródło, zapewniające delikatne wprowadzenie do zasad wielosieciowych, głównie w przypadku problemów eliptycznych.
Brandt, Multigrid Techniques , poprawione wydanie, SIAM 2011 (lub pobierz pdf ). Jest to wielki rozwój filozofii wielosiatkowej i modelowania wieloskalowego i ma dużą szansę na głęboką zmianę sposobu myślenia o rozwiązaniach niejawnych. Strona internetowa Achi Brandta zawiera wiele innych referencji, w tym jego recenzję Multiscale Scientific Computation z 2000 roku .
Trottenberg, Oosterlee i Schueller, Multigrid , Academic Press, 2001 To więcej sprawdzonych przykładów niż Brandt, w tym wiele eksperymentów i szczegółów na temat konkretnych metod, szczególnie w kontekście dynamiki płynów.
Hackbusch, Multigrid Methods and Applications , Springer, 1985 Zapewnia to rygorystyczną teorię konwergencji, w tym „multigrid drugiego rodzaju” dla operatorów integralnych Fredholm.