Multigrid metoda

Metoda multigrid ( MS , anglicky multigrid ) je metoda pro řešení soustavy lineárních algebraických rovnic založená na použití posloupnosti klesajících mřížek a přechodových operátorů z jedné mřížky do druhé. Mřížky jsou postaveny na základě velkých hodnot v systémové matici, což umožňuje pomocí této metody řešit eliptické rovnice i na nepravidelných sítích.

Základy metody

Předpokládejme, že potřebujeme vyřešit systém formuláře

$Au=f,$

kde je matice s prvky . Pro usnadnění porovnejme indexy s uzly mřížky, tedy hodnota v uzlu . Sada uzlů mřížky bude označena jako . Hlavní myšlenkou multigridních metod je, že chybu , kterou nelze odstranit relaxačními metodami, je nutné odstranit pomocí korekce z řešení hrubé mřížky. $A$ $n\krát n$ ${\displaystyle a_{ij))$ ${\displaystyle u_{i))$ $u$ $i$ ${\displaystyle \Omega =\left\{1,\,2,\,\tečky ,\,n\right\))$ $E$

Pomocí horního indexu jako čísla úrovně zavádíme následující označení:

Posloupnost mřížek a . ${\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 }\ekviv C^{k}$
Operátoři sítě . ${\displaystyle A=A^{1},\,A^{2},\,\dots ,\,A^{M))$
Interpolační operátory . $P^{k},k=1,\,2,\,\tečky ,\,M-1$
Vyhlazovací operátory . $S^{k},k=1,\,2,\,\tečky ,\,M-1$

Všechny tyto součásti metody multigrid jsou sestaveny v prvním kroku, známém jako krok sestavení .

Stavební fáze

rovnat se . $k=1$
Rozdělte na disjunktní množiny a . ${\displaystyle \Omega ^{k))$ ${\displaystyle C^{k))$ ${\displaystyle F^{k))$
1. rovnat se . ${\displaystyle \Omega ^{k+1}=C^{k))$
2. Vytvořte interpolační operátor . $P^{k}$
Sestavit . ${\displaystyle A^{k+1}=\left(P^{k}\right)^{T}A^{k}P^{k))$
V případě potřeby sestavit . $S^{k}$
Pokud je mřížka dostatečně malá, vyrovnejte ji a zastavte. V opačném případě přejděte ke kroku 2. ${\displaystyle \Omega ^{k))$ $M=k+1$ $k=k+1$

Jakmile je fáze sestavení dokončena, lze definovat smyčku sestavení rekurzivního řešení:

Algoritmus:

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

Pokud , vyřešte pomocí přímé metody.

k=M

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

V opačném případě: Aplikujte relaxační metodu jednou na .

S^{k}

{\displaystyle \mu _{1))

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

Proveďte opravu na hrubé mřížce: Vypočítejte .

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

Vypočítejte .

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

Použít .

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

Aktualizovat řešení .

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

Aplikujte relaxační metodu jednou na .

S^{k}

\mu _{2}

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

Výše uvedený algoritmus popisuje smyčku. $V\left(\mu _{1},\,\mu _{2}\right)$

Volba posloupnosti mřížky a operátor interpolace jsou nejdůležitějšími prvky fáze výstavby a do značné míry určují kvalitu metody více mřížek. Kritériem kvality jsou dvě měřitelné veličiny:

faktor konvergence – ukazuje, jak rychle metoda konverguje, to znamená, kolik iterací je potřeba k dosažení dané přesnosti;
složitost operátoru – která určuje počet operací a množství paměti potřebné pro každou iteraci metody.

Složitost operátoru se vypočítá jako poměr počtu nenulových prvků ve všech maticích k počtu nenulových prvků v matici první úrovně . $C_{op}$ $A_{k},\,k=1,\,2,\,\tečky ,\,n$ $A^{1}=A$

Literatura

Volkov KN, Deryugin Yu. N., Emelyanov VN a kol., Kapitola 2. Geometrické metody s více mřížkami, Kapitola 3. Algebraické metody s více mřížkami. // Metody pro urychlení plynodynamických výpočtů na nestrukturovaných sítích. M. FIZMATLIT, 2014. - S. 75-255. — 535 str. - ISBN 978-5-9221-1542-1 .
Tisk, WH Oddíl 20.6. Vícesíťové metody pro problémy s hraničními hodnotami // Numerické recepty: Umění vědeckého počítání / WH Press, SA Teukolsky, WT Vetterling … [ a další ] . — 3. - New York: Cambridge University Press, 2007. - ISBN 978-0-521-88068-8 .

Metody řešení diferenciálních rovnic

Metody mřížky

Metody konečných prvků	Metoda konečných prvků Galerkinova metoda Diskontinuální Galerkinova metoda Víceškálová metoda konečných prvků Multigrid metoda
Jiné metody	Metoda konečných rozdílů Metoda konečných objemů Godunovova metoda Metoda hraničních prvků

Negridové metody