Multigrid-metod

Multigridmetoden ( MS , engelska multigrid ) är en metod för att lösa ett system av linjära algebraiska ekvationer baserat på användningen av en sekvens av minskande rutnät och övergångsoperatorer från ett rutnät till ett annat. Grids byggs på grundval av stora värden i systemmatrisen, vilket gör det möjligt att använda denna metod för att lösa elliptiska ekvationer även på oregelbundna rutnät.

Grunderna i metoden

Antag att vi behöver lösa ett formsystem

$Au=f,$

var är en matris med element . För enkelhetens skull, låt oss jämföra indexen med rutnätsnoder, sålunda är värdet vid noden . Uppsättningen av rutnätsnoder kommer att betecknas som . Huvudtanken med multigrid-metoder är att ett fel som inte kan elimineras med relaxationsmetoder måste tas bort med hjälp av en korrigering från den grova rutnätslösningen. $A$ $n\ gånger n$ $a_{ij}$ ${\displaystyle u_{i))$ $u$ $i$ ${\displaystyle \Omega =\left\{1,\,2,\,\dots ,\,n\right\))$ $e$

Med den upphöjda texten som nivånummer introducerar vi följande beteckningar:

Sekvensen av rutnät och . ${\displaystyle \Omega =\Omega ^{1}\supset \Omega ^{2}\supset \dots \supset \Omega ^{M))$ $\Omega ^{k}=C^{k}\cup F^{k},\quad C^{k}\cap F^{k}=\emptyset ,\quad \Omega ^{k+1 }\equiv C^{k}$
Nätoperatörer . ${\displaystyle A=A^{1},\,A^{2},\,\dots ,\,A^{M))$
Interpolationsoperatorer . $P^{k},k=1,\,2,\,\dots ,\,M-1$
Utjämna operatörer . $S^{k},k=1,\,2,\,\dots ,\,M-1$

Alla dessa komponenter i multigridmetoden byggs i det första steget, känt som byggsteget .

Byggfasen

Jämför . $k=1$
Dela upp i osammanhängande set och . ${\displaystyle \Omega ^{k))$ ${\displaystyle C^{k))$ ${\displaystyle F^{k))$
1. Jämför . ${\displaystyle \Omega ^{k+1}=C^{k))$
2. Bygg en interpolationsoperator . $P^{k}$
Bygg . ${\displaystyle A^{k+1}=\left(P^{k}\right)^{T}A^{k}P^{k))$
Bygg om det behövs . $S^{k}$
Om gallret är tillräckligt litet, utjämna och stoppa. Annars går du till steg 2. ${\displaystyle \Omega ^{k))$ $M=k+1$ $k=k+1$

När byggfasen är klar kan en rekursiv lösningsbyggslinga definieras:

Algoritm:

MGV\left(A^{k},\,P^{k},\,S^{k},\,u^{k},\,f^{k}\right)

Om , lös med den direkta metoden.

k=M

{\displaystyle A^{M}u^{M}=f^{M))

Annat: Använd avslappningsmetoden en gång för att .

S^{k}

{\displaystyle \mu _{1))

{\displaystyle A^{k}u^{k}=f^{k))

Gör en korrigering på ett grovt rutnät: Beräkna .

{\displaystyle r^{k}=f^{k}-A^{k}u^{k))

Beräkna .

{\displaystyle r^{k+1}=\left(P^{k}\right)^{T}r^{k))

Ansök .

MGV\left(A^{k+1},\,P^{k+1},\,S^{k+1},\,e^{k+1},\,r^{ k+1}\höger)

Uppdatera lösning .

{\displaystyle u^{k}=u^{k}+P^{k}e^{k+1))

Använd avslappningsmetoden en gång för att .

S^{k}

{\displaystyle \mu _{2))

{\displaystyle A^{k}u^{k}=f^{k))

Algoritmen ovan beskriver en loop. $V\left(\mu _{1},\,\mu _{2}\right)$

Valet av rutnätssekvens och interpolationsoperatören är de viktigaste delarna i byggskedet och avgör till stor del kvaliteten på multigridmetoden. Kvalitetskriteriet är två mätbara storheter:

konvergensfaktor - visar hur snabbt metoden konvergerar, det vill säga hur många iterationer som krävs för att uppnå en given noggrannhet;
operatörens komplexitet - som bestämmer antalet operationer och mängden minne som krävs för varje iteration av metoden.

Operatörskomplexitet beräknas som förhållandet mellan antalet icke-nollelement i alla matriser och antalet icke-nollelement i matrisen på första nivån . $C_{op}$ $A_{k},\,k=1,\,2,\,\dots ,\,n$ $A^{1}=A$

Litteratur

Volkov KN, Deryugin Yu. N., Emelyanov VN et al Kapitel 2. Geometriska multigrid metoder., Kapitel 3. Algebraiska multigrid metoder. // Metoder för att accelerera gasdynamiska beräkningar på ostrukturerade nät. M. FIZMATLIT, 2014. - S. 75-255. — 535 sid. - ISBN 978-5-9221-1542-1 .
Press, WH avsnitt 20.6. Multigrid-metoder för problem med gränsvärden // Numeriska recept: The Art of Scientific Computing / WH Press, SA Teukolsky, WT Vetterling … [ och andra ] . — 3:a. - New York: Cambridge University Press, 2007. - ISBN 978-0-521-88068-8 .

Metoder för att lösa differentialekvationer

Rutnätsmetoder

Finita elementmetoder	Finita elementmetod Galerkin metod Diskontinuerlig Galerkin-metod Flerskalig finita elementmetod Multigrid-metod
Andra metoder	Ändlig skillnadsmetod Metod med ändlig volym Godunovs metod Gränselementmetod

Icke-grid-metoder