E
Numerick´a anal´yza transportn´ıch proces˚ u - NTP2
Pˇredn´aˇska ˇc. 8 ´ Uvod do pˇresnosti MKP, generace s´ıt´ı a metod ˇreˇsen´ı soustav line´arn´ıch rovnic
´ Uvod do pˇresnosti metody koneˇcn´ych prvk˚ u
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u S´ıt’ koneˇ cn´ ych prvk˚ u
•
Metoda koneˇcn´ych prvk˚ u je zaloˇzena na diskretizaci p˚ uvodn´ı spojit´e konstrukce soustavou prvk˚ u (nebo obecnˇeji na diskretizaci slab´e formulace ˇr´ıdic´ıch rovnic) ⇒ v´ysledkem je pˇribliˇzn´e ˇreˇsen´ı
Pˇresnost pˇribliˇzn´eho ˇreˇsen´ı z´avis´ı na - volbˇe typu koneˇcn´ych prvk˚ u - velikosti jednotliv´ych prvk˚ u - na pr˚ ubˇehu slab´eho ˇreˇsen´ı - u ˇcasovˇe z´avisl´ych probl´em˚ u na typu ˇcasov´e diskretizace a algoritmu ˇreˇsen´ı • MKP je silnˇ e ovlivnˇena konstrukc´ı s´ıtˇe koneˇcn´ych prvk˚ u (obecnˇe b´azov´ych funkc´ı) •
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u •
•
Kovergence metody koneˇ cn´ ych prvk˚ u Teorie je velmi propracovan´a pro u´lohy mechaniky (line´arn´ı statika) poznatky jsou vyuˇz´ıv´any pro ˇreˇsen´ı transportn´ıch proces˚ u (stacion´arn´ı → nestacion´arn´ı) ˇ eme, ˇze posloupnost re´aln´ych Pojem kovergence (Cauchyho koncepce): Reknˇ ˇc´ısel an konverguje k limitˇe a, pokud pro libovoln´e > 0 m˚ uˇzeme naj´ıt takov´e n0, ˇze pro kaˇzd´e n ≥ n0 plat´ı |a − an| ≤ . Pak p´ıˇseme: lim an = a
n→∞ •
Pˇredchoz´ı definice jin´ymi slovy tvrd´ı, ˇze dok´aˇzeme posloupnost´ı an aproximovat limitu a s libovolnou pˇresnost´ı > 0
•
V MKP jde o to, zda lze slab´e ˇreˇsen´ı dan´e u´lohy uex aproximovat s libovolnou pˇresnost´ı koneˇcnˇeprvkov´ym ˇreˇsen´ım umkp n : ex umkp n (x) → u
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Kovergence metody koneˇ cn´ ych prvk˚ u • •
V MKP n´as zaj´ım´a konvergence funkc´ı Pˇr´ıklad: taˇzen´y tlaˇcen´y prut
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Kovergence metody koneˇ cn´ ych prvk˚ u •
Zav´ad´ıme tzv. energetickou normu funkce u Z du 2 2 ku(x)k = E(x)A(x) dx, dx L kter´a m´a fyzik´aln´ı v´yznam energie konstrukce, udˇel´ıme-li ji dan´y posun u
•
Zkoum´ame, zda plat´ı: ex kumkp n (x)k → ku (x)k
•
V MKP jednotliv´a ˇreˇsen´ı paramterizujeme rozmˇerem prvku h m´ısto poˇctem prvk˚ un
•
V ide´aln´ım pˇr´ıpadˇe by mˇelo platit: ex lim kumkp h (x)k → ku (x)k
h→0
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Kovergence metody koneˇ cn´ ych prvk˚ u
•
Tedy pro zvolenou pˇresnost > 0 jsme schopni naj´ıt takovou velikost prvku h, ˇze plat´ı: ex kumkp h (x) − u (x)k < jsme tedy schopni aproximovat slab´e ˇreˇsen´ı s libovolnou pˇresnost´ı v energetick´e normˇe
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Kovergence metody koneˇ cn´ ych prvk˚ u
B´azov´e funkce mus´ı splˇnovat podm´ınky: •
dostateˇcn´e hladkosti: funkce maj´ı derivace ˇr´adu o jeden vyˇsˇs´ı neˇz se objevuje ve slab´em ˇreˇsen´ı
•
spojitosti: funkce mus´ı b´yt spojit´e jak uvnitˇr prvku, tak na hranici
•
u´plnosti: napˇr. pro teorii pruˇznosti: - mus´ı popstat konstantn´ı stav deformace - a mus´ı reprezentovat pˇrem´ıstˇen´ı prvku jako tuh´eho tˇelesa bez vzniku deformac´ı
• Prvek jehoˇ z b´azov´e funkce splˇnuj´ı jak podm´ınky spojitosti, tak u´plnosti se naz´yv´a
konformn´ı → monot´onn´ı konvergence • Pokud je splnˇ ena podm´ınka u´plnosti, ale nen´ı podm´ınka spojitosti, prvek se naz´yv´a
nekonformn´ı • U nekonformn´ıch prvk˚ u je anal´yza splnˇen´ı podm´ınky u´plnosti velmi komplikovan´a,
proto je pro kontrolu spr´avnosti ˇreˇsen´ı vyuˇz´ıv´an tzv. PATCH TEST
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Kovergence metody koneˇ cn´ ych prvk˚ u
PATCH TEST
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Adaptivn´ı techniky v MKP
•
Adaptivn´ı techniky v MKP se zab´yvaj´ı zjemˇnov´an´ım s´ıt´ı a zvyˇsov´an´ım stupnˇe polynomu aproximaˇcn´ıch funkc´ı, rychlost´ı konvergence
•
Rychlost konvergence lze ovlivnit - zjemˇnov´an´ım s´ıtˇe h → 0 - tzv. h konvergence - zvyˇsov´an´ım stupnˇe polynomick´e aproximace - tzv. p konvergence - kombinac´ı obou pˇr´ıstup˚ u - tzv. hp konvergence
•
Z v´ypoˇcetn´ıho hlediska je v´yhodn´e prov´adˇet zjemˇnov´an´ı s´ıtˇe resp. zvyˇsov´an´ım stupnˇe polynomu tam, kde pˇribliˇzn´e ˇreˇsen´ı dobˇre nevystihuje pˇresn´e ˇreˇsen´ı → adaptivn´ı varianta MKP. - napˇr. v m´ıstech koncentrace napˇet´ı, v m´ıstech extr´emn´ıch gradinet˚ u teplot a vhlkost´ı, ...
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Adaptivn´ı techniky v MKP
•
Pro libovolnou adaptivn´ı techniku je nutn´e zn´at chybu pˇribliˇzn´eho ˇreˇsen´ı e(x) = umkp (x) − uex (x)
(1)
ke(x)k = kumkp (x) − uex (x)k
(2)
respektive •
N´azornˇejˇs´ı veliˇcinou je relativn´ı chyba ˇreˇsen´ı η=
kek kuk
(3)
´ Uvod do pˇresnosti metody koneˇ cn´ ych prvk˚ u Adaptivn´ı techniky v MKP
•
Pˇresn´e ˇreˇsen´ı uex nen´ı obecnˇe zn´am´e, je nutn´e se spokojit “pouze” s odhadem chyby 0kek nebo relativn´ı chyby 0η
•
Metody odhadu chyby - metoda ZZ (navrˇzen´a Zienkiewiczem a Zhuem) - vhodn´a pro h adaptivn´ı metodu O. C. Zienkiewicz and J. Z. Zhu, A simple error estimator and adaptive procedure for practical engeneering analysis, International Journal for Numerical Methods in Engineering 24 (1987), 337-357.
´ Uvod do automatick´eho generov´an´ı s´ıt´ı viz str´anky pˇredmˇetu NTP2 nebo http://ksm.fsv.cvut.cz/∼dr/t3d.html - internetov´e str´anky T3D
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ych soustav line´arn´ıch rovnic
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic
•
Hled´ame ˇreˇsen´ı Ax = b kde poˇcet rovnic je velk´y (106) a matice A je ˇr´ıdk´a
(4)
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ukl´ ad´ an´ı ˇr´ıdk´ ych matic •
P´asov´a matice
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ukl´ ad´ an´ı ˇr´ıdk´ ych matic •
Skyline
•
Souˇradnicov´e ukl´ad´an´ı - vhodn´e pro iteraˇcn´ı ˇreˇsiˇce
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ˇreˇsen´ı
Pˇr´ım´e metody •
Idea: faktorizace (rozklad) matice na souˇcin matic, kter´e jsou snadnˇeji invertovateln´e (troj´uheln´ıkov´e) s moˇznou permutac´ı pro dosaˇzen´ı stability
•
Pˇr´ıklad: LU dekompozice A = LU , kde L a U jsou doln´ı, resp. horn´ı troj´uheln´ıkov´e matice. Pokud je rozklad k dispozici, ˇreˇsen´ı je pak: Ax = (LU )x = L(U x) = b, Ly = b, U x = y
•
V´yhoda rozkladu spoˇc´ıv´a ve snadn´em ˇreˇsen´ı obou podprobl´em˚ u (dopˇredn´a a zpˇetn´a substituce)
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ˇreˇsen´ı
Pˇr´ım´e metody •
V´yhody: - garantovan´y poˇcet operac´ı - schopnost ˇreˇsit velk´e 2D a 3D u´lohy - rychlost robustnost
•
Nev´yhody: - nutnost sestavit matici soustavy - m˚ uˇze znamenat znaˇcn´e komplikace
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ˇreˇsen´ı
Iteraˇcn´ı metody •
Dva hlavn´ı typy iteraˇcn´ıch algoritm˚ u: relaxaˇcn´ı (Jacobi, Gauss-Seidel) a projekˇcn´ı (Krylovovy metody: CG, GMRES)
•
Idea: generovat posloupnost aproximac´ı ˇreˇsen´ı x0, x1, . . . xn tak, aby lim xn → x∗, kde x∗ je pˇresn´e ˇreˇsen´ı Narozd´ıl od pˇr´ım´ych ˇreˇsiˇc˚ u m˚ uˇzeme ˇreˇsen´ı pˇredˇcasnˇe ukonˇcit pomoc´ı vhodn´eho krit´eria V´yhody: - nemus´ı vyˇzadovat explicitn´ı sestaven´ı matice soustavy - velmi n´ızk´e pamˇet’ov´e n´aroky - efektivn´ı pro velmi ˇr´ıdk´e syst´emy, zejm´ena ve 3D Nev´yhody: - ˇcasto vyˇzaduj´ı velk´y poˇcet iterac´ı - ˇcasto nutn´e efektivn´ı pˇredpodm´ınˇen´ı
• •
•
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Metody ˇreˇsen´ı
Hybrin´ı metody •
multigridn´ı metody
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic •
•
•
Paraleln´ı ˇreˇsen´ı soustav rovnic Velikost ˇreˇsen´eho probl´emu je na jednom poˇc´ıtaˇci vˇzdy omezena (rychlost CPU, velikost pamˇeti) → paraleln´ı, distribuovan´e v´ypoˇcty na modern´ıch paraleln´ıch poˇc´ıtaˇc´ıch nebo poˇc´ıtaˇcov´ych svazc´ıch (PC clusters) Architektury: - sd´ılen´a pamˇet’ - distrubuovan´a pamˇet’ - hybridn´ı syst´emy
Programovac´ı modely: - vl´akna (threads) - sd´ılen´a pamˇet’ (POSIX, OpenMP) - Message passing interface - distribuovan´e i sd´ılen´e syst´emy (MPI) - Paraleln´ı datov´y model - sd´ılen´a pamˇet’ (F90, HPF)
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Paraleln´ı ˇreˇsen´ı soustav rovnic Princip: rozdˇelen´ı probl´emu na podprobl´emy, kter´e mohou b´yt ˇreˇseny na individu´aln´ıch uzlech, vz´ajemn´a z´avislost vynucuje vz´ajemnou komunikaci • V MKP se pouˇ z´ıv´a tzv. dom´enov´a dekompozice = rozdˇelen´ı oblasti na podoblasti - pro efektivn´ı zpracov´an´ı je nutn´y paraleln´ı distribuovan´y ˇreˇsiˇc • Poˇ zadavky na dekompozici: rovnomˇern´a distribuce pr´ace (poˇcet prvk˚ u), minim´aln´ı rozhran´ı mezi subdom´enami (komunikace) •
•
Metody ˇreˇsen´ı: 1. prim´arn´ı dom´enov´a dekompozice - Metoda Schurov´ych doplˇnk˚ u 2. du´aln´ı dom´enov´a dekompozice - metodat FETI (Finite Element Tearing and Interconnecting method)
•
Load Ballancing - distribuce pr´ace mezi uzly (statick´a, dynamick´a) je d˚ uleˇzit´a pro efektivn´ı v´ypoˇcet
´ Uvod do metod ˇreˇsen´ı ˇr´ıdk´ ych soustav line´ arn´ıch rovnic Pˇr´ıklad dekompozice
´ Uvod do pˇresnosti MKP, generace s´ıt´ı a metod ˇreˇsen´ı soustav line´ arn´ıch rovnic
T´emata pˇredn´aˇsky jsou pˇrevztata z pˇredmˇetu NAK1 Doc. Dr. Ing. Boˇrka Patz´aka a z pˇredn´aˇsek Doc. Dr. Ing. Daniela Rypla.
