Aditivní Schwarzova metoda - Additive Schwarz method - Wikipedia

v matematika, aditivní Schwarzova metoda, pojmenoval podle Hermann Schwarz, řeší a problém mezní hodnoty pro parciální diferenciální rovnice přibližně jeho rozdělením na problémy s hraničními hodnotami na menších doménách a přidáním výsledků.

Přehled

Parciální diferenciální rovnice (PDE) se používají ve všech vědy na Modelka jevy. Pro účely výkladu uvádíme příklad fyzického problému a doprovodného problému okrajové hodnoty (BVP). I když čtenář notaci nezná, účelem je pouze ukázat, jak vypadá BVP, když je zapsán.

(Problém s modelem) Distribuce tepla ve čtvercové kovové desce tak, že levá hrana je udržována na 1 stupni a ostatní hrany jsou udržovány na 0 stupních, poté, co ji necháme dlouho sedět, splňuje následující problém mezní hodnoty:

F_xx(X,y) + F_yy(X,y) = 0

F(0,y) = 1; F(X,0) = F(X,1) = F(1,y) = 0

kde F je neznámý funkce, F_xx a F_yy označit druhý částečné derivace s ohledem na X a y, resp.

Tady je doména je čtverec [0,1] × [0,1].

Tento konkrétní problém lze vyřešit přesně na papíře, takže není třeba počítač. Jedná se však o výjimečný případ a většinu BVP nelze vyřešit přesně. Jedinou možností je použít počítač k nalezení přibližného řešení.

Řešení na počítači

Typickým způsobem, jak toho dosáhnout, je vzorek F pravidelně intervaly v náměstí [0,1] × [0,1]. Například bychom mohli odebrat 8 vzorků v X směr v X = 0,1, 0,2, ..., 0,8 a 0,9 a 8 vzorků v y směr na podobné souřadnice. Pak bychom měli 64 vzorků čtverce na místech jako (0,2,0,8) a (0,6,0,6). Cílem počítačový program by bylo vypočítat hodnotu F v těchto 64 bodech, což se zdá být snazší než najít abstraktní funkci čtverce.

Existují určité obtíže, například není možné vypočítat F_xx(0,5,0,5) s vědomím F na pouhých 64 bodech ve čtverci. Abychom to překonali, použijeme nějakou numerickou aproximaci derivací, viz například Metoda konečných prvků nebo konečné rozdíly. Tyto potíže ignorujeme a soustředíme se na další aspekt problému.

Řešení lineárních problémů

Bez ohledu na to, jakou metodu k řešení tohoto problému zvolíme, budeme muset vyřešit velkou lineární soustava rovnic. Čtenář si může vybavit lineární systémy rovnic ze střední školy, vypadají takto:

2A + 5b = 12 (*)

6A − 3b = −3

Toto je systém 2 rovnic ve 2 neznámých (A a b). Pokud výše uvedené BVP vyřešíme navrženým způsobem, budeme muset vyřešit systém 64 rovnic v 64 neznámých. Pro moderní počítače to není těžký problém, ale pokud použijeme větší počet vzorků, ani moderní počítače nemohou vyřešit BVP velmi efektivně.

Dekompozice domény

Což nás přivádí k metodám rozkladu domén. Rozdělíme-li doménu [0,1] × [0,1] na dvě subdomény [0,0,5] × [0,1] a [0,5,1] × [0,1], každý má pouze polovinu vzorkovacích bodů. Můžeme se tedy pokusit vyřešit verzi našeho modelového problému na každé subdoméně, ale tentokrát má každá subdoména pouze 32 vzorových bodů. Nakonec, vzhledem k řešení na každé subdoméně, se můžeme pokusit je sladit a získat řešení původního problému na [0,1] × [0,1].

Velikost problémů

Pokud jde o lineární systémy, snažíme se rozdělit systém 64 rovnic v 64 neznámých na dva systémy 32 rovnic ve 32 neznámých. To by byl jasný zisk z následujícího důvodu. Při pohledu zpět na systém (*) vidíme, že existuje 6 důležitých informací. Jsou to koeficienty A a b (2,5 na prvním řádku a 6, -3 na druhém řádku) a pravá strana (kterou píšeme jako 12, -3). Na druhou stranu, pokud vezmeme dva „systémy“ 1 rovnice v 1 neznámé, může to vypadat takto:

Systém 1: 2A = 12

Systém 2: -3b = −3

Vidíme, že tento systém má pouze 4 důležité informace. To znamená, že počítačový program bude mít snazší čas vyřešit dva systémy 1 × 1 než řešení jednoho systému 2 × 2, protože dvojice systémů 1 × 1 je jednodušší než jediný systém 2 × 2. Zatímco systémy 64 × 64 a 32 × 32 jsou příliš velké na to, abychom je zde ilustrovali, analogicky bychom mohli říci, že systém 64 × 64 má 4160 informací, zatímco systémy 32 × 32 mají každý 1056, což je zhruba čtvrtina Systém 64 × 64.

Algoritmus dekompozice domény

Bohužel z technických důvodů obvykle není možné rozdělit naši mřížku 64 bodů (systém lineárních rovnic 64 × 64) na dvě mřížky 32 bodů (dva systémy lineárních rovnic 32 × 32) a získat odpověď na 64 × 64 systém. Místo toho se ve skutečnosti stane následující algoritmus:

1) Začněte s přibližným řešením systému 64 × 64.

2) Ze systému 64 × 64 vytvořte dva systémy 32 × 32, abyste vylepšili přibližné řešení.

3) Vyřešte dva systémy 32 × 32.

4) Spojte dvě řešení 32 × 32 „dohromady“, abyste vylepšili přibližné řešení systému 64 × 64.

5) Pokud řešení ještě není příliš dobré, opakujte postup od 2.

Existují dva způsoby, jak to může být lepší než řešení základního systému 64 × 64. Za prvé, pokud je počet opakování algoritmu malý, řešení dvou systémů 32 × 32 může být efektivnější než řešení systému 64 × 64. Za druhé, dva systémy 32 × 32 nemusí být řešeny na stejném počítači, takže tento algoritmus lze spustit paralelní využívat sílu více počítačů.

Ve skutečnosti je nepravděpodobné, že by řešení dvou systémů 32 × 32 namísto systému 64 × 64 na jednom počítači (bez použití paralelismu) bylo efektivní. Pokud však použijeme více než dvě subdomény, obraz se může změnit. Mohli bychom například použít čtyři problémy 16 × 16 a existuje šance, že jejich řešení bude lepší než řešení jediného problému 64 × 64, i když je třeba algoritmus dekompozice domény několikrát iterovat.

Technický příklad

Zde předpokládáme, že čtenář je obeznámen s parciálními diferenciálními rovnicemi.

Budeme řešit parciální diferenciální rovnici

u_xx + u_yy = F (**)

Vnucujeme omezenost v nekonečnu.

Doménu rozložíme R² do dvou překrývajících se subdomén H₁ = (− ∞,1] × R a H₂ = [0,+ ∞) × R. V každé subdoméně budeme řešit BVP ve formě:

u^{( j )}_xx + u^{( j )}_yy = F v H_j

u^{( j )}(X_j,y) = G(y)

kde X₁ = 1 a X₂ = 0 a vezmeme omezenost v nekonečnu jako další okrajovou podmínku. Označíme řešení u^{( j )} výše uvedeného problému S (F,G). Všimněte si, že S je bilineární.

Schwarzův algoritmus probíhá následovně:

Začněte s přibližnými řešeními u^{( 1 )}₀ a u^{( 2 )}₀ PDE v subdoménách H₁ a H₂ resp. Inicializovat k až 1.
Vypočítat u^{( j )}_{k + 1} = S (F,u^{(3 − j)}_k(X_j)) s j = 1,2.
Zvýšit k o jednu a opakujte 2, dokud nedosáhnete dostatečné přesnosti.

Viz také

Reference

Barry Smith, Petter Bjørstad, William Gropp, rozklad domény, paralelní víceúrovňové metody pro eliptické parciální diferenciální rovnice, Cambridge University Press 1996
Andrea Toselli a Olof Widlund, metody dekompozice domény - algoritmy a teorie, Springerova řada v počítačové matematice, sv. 34, 2004

externí odkazy

Oficiální stránka Metody rozkladu domény