Multigrid módszer

A multigrid módszer ( MS , angolul multigrid ) lineáris algebrai egyenletrendszer megoldására szolgáló módszer, amely csökkenő rácsok és egyik rácsból a másikba való átmenet operátorok sorozatának felhasználásán alapul . A rácsok a rendszermátrixban található nagy értékek alapján épülnek fel, ami lehetővé teszi ennek a módszernek az elliptikus egyenletek megoldását még szabálytalan rácsokon is.

A módszer alapjai

Tegyük fel, hogy meg kell oldanunk egy formarendszert

$Au=f,$

ahol egy mátrix elemekkel . A kényelem kedvéért hasonlítsuk össze az indexeket a rácscsomópontokkal, így a csomópont értéke . A rácscsomópontok halmaza a következővel lesz jelölve . A többrácsos módszerek lényege, hogy a relaxációs módszerekkel nem kiküszöbölhető hibát a durva rácsos megoldás korrekciójával kell eltávolítani. $A$ $n\szer n$ $a_{ij}$ ${\displaystyle u_{i))$ $u$ $én$ ${\displaystyle \Omega =\left\{1,\,2,\,\dots ,\,n\jobbra\))$ $e$

A felső indexet szintszámként használva a következő megnevezéseket vezetjük be:

A rácsok sorozata és . ${\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}$
Hálózati üzemeltetők . ${\displaystyle A=A^{1},\,A^{2},\,\dots ,\,A^{M))$
Interpolációs operátorok . $P^{k},k=1,\,2,\,\pontok ,\,M-1$
Simító operátorok . $S^{k},k=1,\,2,\,\dots ,\,M-1$

A multigrid módszer összes összetevője az első lépésben, az úgynevezett build lépésben épül fel .

Építési fázis

Egyenlíteni . $k=1$
Osszuk diszjunkt halmazokra és . ${\displaystyle \Omega ^{k))$ ${\displaystyle C^{k))$ ${\displaystyle F^{k))$
1. Egyenlíteni . ${\displaystyle \Omega ^{k+1}=C^{k))$
2. Hozzon létre egy interpolációs operátort . $P^{k}$
Építsd meg . ${\displaystyle A^{k+1}=\left(P^{k}\right)^{T}A^{k}P^{k))$
Építsd meg, ha szükséges . $S^{k}$
Ha a rács elég kicsi, egyenlítse ki és állítsa le. Ellenkező esetben folytassa a 2. lépéssel. ${\displaystyle \Omega ^{k))$ $M=k+1$ $k=k+1$

A felépítési fázis befejezése után egy rekurzív megoldás-összeállítási hurok definiálható:

Algoritmus:

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

Ha , oldja meg a közvetlen módszerrel.

k=M

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

Másképp: Alkalmazza egyszer a relaxációs módszert .

S^{k}

{\displaystyle \mu _{1))

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

Végezzen korrekciót egy durva rácson: Számolja ki .

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

Számolja ki .

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

Alkalmazni .

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

Frissítse a megoldást .

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

Alkalmazza egyszer a relaxációs módszert .

S^{k}

\mu _{2}

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

A fenti algoritmus egy hurkot ír le. $V\left(\mu _{1},\,\mu _{2}\right)$

A rácssorozat és az interpolációs operátor kiválasztása az építési szakasz legfontosabb elemei, és nagymértékben meghatározzák a multigrid módszer minőségét. A minőségi kritérium két mérhető mennyiség:

konvergenciafaktor - megmutatja, hogy a módszer milyen gyorsan konvergál, vagyis hány iteráció szükséges egy adott pontosság eléréséhez;
az operátor összetettsége - amely meghatározza a műveletek számát és a szükséges memória mennyiségét a metódus egyes iterációihoz.

Az operátor komplexitását az összes mátrixban lévő nullától eltérő elemek számának az első szintű mátrixban lévő nem nullától eltérő elemeinek számához viszonyított arányaként számítjuk ki . $C_{op}$ $A_{k},\,k=1,\,2,\,\pontok ,\,n$ $A^{1}=A$

Irodalom

Volkov KN, Deryugin Yu. N., Emelyanov VN et al. 2. fejezet Geometriai többrácsos módszerek, 3. fejezet Algebrai többrácsos módszerek. // Módszerek gázdinamikai számítások gyorsítására strukturálatlan rácsokon. M. FIZMATLIT, 2014. - S. 75-255. — 535 p. - ISBN 978-5-9221-1542-1 .
Nyomja meg, WH 20.6. szakasz. Multigrid módszerek határérték-problémákra // Numerikus receptek: A tudományos számítástechnika művészete / WH Press, SA Teukolsky, WT Vetterling … [ és mások ] . — 3. - New York: Cambridge University Press, 2007. - ISBN 978-0-521-88068-8 .

Differenciálegyenletek megoldási módszerei

Rács módszerek

Végeselem módszerek	Végeselem módszer Galerkin módszer Nem folyamatos Galerkin módszer Többléptékű végeselemes módszer Multigrid módszer
Egyéb módszerek	Véges különbség módszer Véges térfogatú módszer Godunov módszere Határelem módszer

Nem rácsos módszerek