Elliptikus egyenletek iterációs megoldásának rácsfüggetlen szuperlineáris konvergenciája Antal István A doktori értekezés tézisei Témavezető: Karátson János egyetemi docens, PhD
Matematikai Doktori Iskola a doktori iskola vezetője: Dr. Laczkovich Miklós a Magyar Tudományos Akadémia Rendes tagja
Doktori program: Alkalmazott Matematika a doktori program vezetője: Dr. Michaletzky György a Magyar Tudományos Akadémia doktora
Alkalmazott Analízis és Számításmatematikai Tanszék Matematikai Intézet Eötvös Loránd Tudományegyetem, Természettudományi Kar 2012
Bevezetés Elliptikus parciális differencálegyenletek numerikus megoldásakor, mivel nemkorlátos problémát közelítünk, rosszul viselkedő véges dimenziós egyenletekkel kell foglalkozni. Lineáris esetben, ill. nemlineáris egyenletek linearizálásakor a diszkretizációval kapott lineáris egyenletrendszer mátrixa rosszul kondicionált. Végeselem diszkretizáció esetén a végeselem altér finomításával egyrészt az egyenletrendszer mérete másrészt az egyenletrendszerhez kapcsolódó mátrix kondíciószáma is minden határon túl nő. Ezen probléma enyhítésére egy hatásos módszer az egyenlet prekondícionálása, amellyel lényegében egy jobban kezelhető segédfeladatra transzformáljuk az eredetit. Ezen dolgozatban a prekondícionáló mátrix az egyenlet főrészének diszkretizáltja, a diszkrét egyenletet balról szorozva már egy korlátos egyenletet kapunk (a végeselem altértől függetlenül egyenletesen), hasonlóan a folytonos esethez ahol a Szoboljev-térbeli megoldásnál a főrésszel prekondicionálunk, ugyanis például a legegyszerűbb Dirichlet feladatnál, a fellépő Szoboljev-tér megegyezik a Laplace operátor által meghatározott energiatérrel. A dolgozatban szereplő lineáris elliptikus feladatok megoldására használt konjugált gradiens módszerről mutatjuk meg, hogy megfelelő prekondicionálással a konvergencia sebessége szuperlineáris, függetlenül a választott végeselem altértől. Nemszimmetrikus feladatok esetén a normálegyenletre alkalmazott konjugált gradiens módszerről látjuk be ugyanezen tulajdonságot. Nemlineáris feladatok esetén megmutatjuk, hogy a javasolt kvázi-Newton módszer konvergenciája továbbá a lineáris részfeladataira alkalmazott konjugált gradiens módszer is szuperlineáris.
Előzmények és eredmények rövid összefoglalása A konjugált gradiens módszer szuperlineáris konvergenciája először [10]-ben szerepel, azóta több hasonló eredmény született, jelen dolgozatban a [5, 19] konvergenciaeredményeket használjuk. Ehhez kapcsolódóan az elliptikus parciális differenciálegyenletek operátorszintű prekondicinálásának vizsgálata az 1980-as években kezdődött. Ellipikus peremértékfeladatok bizonyos osztályaira jellemzték azon prekondicionáló operátorok osztályát, amelyekkel a konjugált gradiens módszer (CG) szuperlineárisan konvergál [9, 8]. A feltételek gyengítésével egyenletek egyre bővebb osztályaira, illetve a CG bizonyos általánosításaira láttak be hasonló eredményeket. Később a fenti típusú egyenletek végeselem diszkretizációval kapott végesdimenziós egyenletek megoldásakor szuperlineáris konvergenciát láttak be [6, 7]. A bizonyítások a végeselem megoldás és az eredeti differenciálegyenlet szoros kapcsolatán alapul. Ezáltal a funcionálanalízis
1
illetve a Szoboljev terek elméletének hatásos technikái alkalmazhatóak. Először lineáris és nemlineáris szimmetrikus egyenletrendszereket vizsgálunk. Mindkét esetben a használt iterációs módszerek szuperlineáris konvergenciáját látjuk be, pontos konvergencia rendet is megadva. Ezekben az esetekben a rácsfüggetlen konvergenciabecslést érdemben a Laplace operátor inverzének Hilbert-Schmidt normájának segítségével igazoljuk. Ezután nemszimmetrikus nemlineáris és interface-típusú egyenletekre látunk be szuperlineáris konvergenciát. Ezekben az esetekben az előfordulo operátorok sajátértékeit vizsgálva kapunk konvergenciabecslést. Majd végezetül egy rövid áttekintést nyújtunk a dolgozatban szereplő bizonyított konvergenciarendekről.
Az alkalmazott eszközök rövid összefoglalása A dolgozatban vizsgált egyenletek a következő alakban írhatóak fel: Su + Q(u) = f, ahol az S és Q operátorok egy alakja alkalmas H Hilbert-téren van értelmezve, S elliptikus operátor és Q az egyenlet kisebbrendű tagjait vagy a peremfeltételeket tartalmazza. Ennek gyenge alakja a következő alakban írható fel: hu + S −1 Q(u), viS = hf, vi, ahol S −1 Q a HS energiatéren van definiálva. Lineáris esetben illetve nemlineáris egyenlet linearizációjakor a Q operátor lineáris, és az általunk kirótt feltételek miatt pozitív. Az egyenlet diszkretizációját a következőképp definiáljuk. Legyen Vk = span{ϕ1 , . . . , ϕk } ⊂ P HS egy véges dimenziós altér, ekkor a végeselem megoldást uh = ki=1 ci ϕi alakban keressük ami kielégíti a következő gyenge alakban felírt egyenletet hSuh + Q(uh ), ϕi i = hf, ϕi i,
i = 1, . . . , k,
Ami az Sk = {hϕi , ϕj iS }ki,j=1 mátrixszal való prekondicionálás után az együtthatókra vonatkozó algebrai egyenlet alakját veszi fel: c + N (c) = f . Lineáris esetben a Qh = {hQϕi , ϕj i}ki,j=1 és fh = {hf, ϕi i}ki=1 2
(1)
jelölésekkel a következő egyenletre jutunk: (Ih + Sh−1 Qh )c = Sh−1 fh .
(2)
Ez utóbbi egyenletet oldjuk meg a konjugált gradiens módszerrel az Sh skalárszorzatot használva. Ez az egyenlet az identitás egy perturbációja és ilyen típusú egyenletekre a pertulbáló operátor tulajdonságait vizsgálva kapunk konvergenciabecsléseket. A következő konvergenciaeredményeket használjuk. Tétel 1 ([5]). Jelölje en az n. approximáció hibáját, ekkor ken kSh +Qh ≤ ke0 kSh +Qh
3
S −1 Qh 2 h 2n
n/2 ,
ahol |k·k| a mátrix Frobenius normáját jelöli. Tétel 2 ([19]). Jelölje rn az n. reziduálist, ekkor krn k ≤ kr0 k
!n n 2 X λi (Sh−1 Qh ) . n i=1
A dolgozatban megmutatjuk, hogy mindkét esetben a jobboldalon a zárojelben levő rész a végeselem altér választásától függetlenül nullához tart. Nemlineáris esetben a (1) egyenletet egy kvázi-Newton módszerrel oldjuk meg a következő eredményt felhasználva: Tétel 3 ([11]). Legyen X Banach tér és F : X → X be differenciálható operátor, amely eleget tesz a következő feltételeknek (i) kF 0 (u)hk ≥ λkhk (u, b ∈ X) valamileyn λ > 0 konstanssal függetlenül u, h választásától, (ii) kF 0 (u)−F 0 (v)k ≤ Lku−vk (u, v ∈ X) valamileyn L > 0 konstanssal függetlenül u, v választásától. (ii’) kF 0 (u) − F 0 (v)k ≤ L(r)ku − vk (u, v ∈ X, kuk < r, kvk < r) valamilyen L : R+ → R+ monoton növekedő függvényre. Ekkor az F (u) = b egyenlet megoldását előállító algoritmus a következő: legyen u0 ∈ X, r0 = b − F (u0 ) while krn k > ε do rn = b − f (un ),
3
olyan pn keresendő, amelyre kF 0 (un )pn − rn k ≤ δn krn k ahol 0 < δn ≤ δ0 < 1 n o 1−δn λ2 , legyen τn = min 1, (1+δ 2 n ) Lkrn k legyen un+1 = un + τn pn end while A fent definiált eljárás a következő konvergencia tulajdonsággal bír: · Az (un ) sorozat konvergál az u∗ megoldáshoz kun − u∗ k ≤ kF (un ) − bk → 0 monoton módon. · Ha δn ≡ δ0 akkor a konvergencia lineáris, · ha δn ≤ konst · kF (un ) − bkγ (0 < γ ≤ 1) akkor a konvergencia rendje lokálisan 1 + γ, azaz n0 lépésig a konvrgencia lineáris, amíg kF (un ) − bk ≤ ε, ahol ε 1 legfeljebb (1 − δn ) 2L , ezután kun − u∗ k ≤ Cq (1+γ)
n−n0
teljesül
· (ii’) teljesülése esetén ha a kiindulási vektorhoz elég nagy R-et választva a fenti konvergenciabecslés teljesuk L = L(R)-et választva. Megmutatjuk hogy az általunk vizsgált feladatokra a fenti tétel feltételei teljesülnek, és a konvergencia független a végeselem altér választásától.
Eredmények összegzése Szimmetrikus szemilineáris egyenletrendszerek Az első fejezetben szimmetrikus elliptikus rendszereket vizsgálunk. Tekintsük a (
−∆u(x) + f (x, u(x)) = g(x) u = 0, ∂Ω
peremérték-problmémát, ahol u = (u1 , u2 , . . . , us ), g = (g1 , g2 , . . . , gs ), és amire a következő feltételek teljesülnek: [P1 ] ∂Ω ⊂ Rd (d = 2 or 3) korlátos tartomány, a pereme darabonként C 2 -beli és lokálisan konvex a sarkokban, [P2 ] gi ∈ L2 (Ω) (i = 1, 2, . . . , s), 4
[P3 ] f : Ω × Rs → Rs , m.m. x ∈ Ω esetén f (x, ξ) rendelkezik egy ψ : Ω × Rs → R potenciállal, azaz f = ∂ξ ψ, továbbá differenciálható az ξ változójában, és a derivált ezekben a pontokban szimmetrikus pozitív szemidefinit, [P4 ] m.m. x ∈ Ω esetén a ∂ξ f (x, ξ) deriváltak egyenletesen becsülhetők egy alkalmas M (x) mátrixszal, amely µj (x) sajátértékeire 0 ≤ µj (x) ≤ c1 teljesül valamilyen alkalmas c1 > 0 konstanssal, (f )
[P4’ ] a derivált λj (x, ξ) (j = 1, . . . , s) sajátértékei korlátosak a következő értelemben: 0≤
(f ) λj (x, ξ)
≤ c2 + c3
s X
|ξ|p−2 ,
j=1
alkalmas c2 , c3 > 0 és p ≥ 2 konstansokkal, [P5 ] m.m. x ∈ Ω esetén f deriváltja Lipschitz folytonos, azaz valamilyen C konstansra k∂ξ f (x, ξ1 ) − ∂ξ f (x, ξ2 )k ≤ Ckξ1 − ξ2 k [P5’ ] m.m. x ∈ Ω esetén f deriváltja lokálisan Lipschitz folytonos, azaz valamilyen C : (0, ∞) → (0, ∞) monoton növekedő függvényre k∂ξ f (x, ξ1 ) − ∂ξ f (x, ξ2 )k ≤ C(r)kξ1 − ξ2 k ha kξ1 k, kξ2 k ≤ r. Ezen feltételek mellett a korábban említett (1) végeselem egyenletre alkalmazott kváziNewton algoritmus konvergál. Megmutatjuk, hogy a Tétel 3 feltételében szereplő Lipschitz tulajdonságot leíró L illetve L(r) megválasztható végeselem altértől független módon. A kvázi-Newton módszer lineáris segédfeladatában szereplő lineáris operátor a következő gyenge alakban áll elő 0
Z
hw + N (u)w, viS =
∇w(x) · ∇v(x) + ∂ξ f (x, u(x))w(x)v(x) dx. Ω
Azaz a prekondicionált alak az identitás perturbáltjaként is felfogható, így hasznáható a CG konvergenciabecslése ls ezzel az f deriváltjára kirótt feltételek miatt a következő teljesül: Tétel 4. Jelölje rk a k. reziduálist, ekkor: krk kSk ≤ kr0 kSk
K |kCk|2 k
!k/2 ,
ahol K alkalmas pozitív konstans és C = (−∆−1 , . . . , −∆−1 ), illetve |kCk| a C operátor Hilbert-Schmidt normáját jelöli. Ez utóbbi a d = 1, 2, 3 dimenziókban ez véges, így a CG módszer szuperlineárisan konvergál a végeselem altér választásától függetlenül. 5
Nemlineáris nemszimmetrikus és interface típusú egyenletek A dolgozat második fejezetében a fenti Hilbert-Schmidt normát használó becslés helyett a Tétel 2-ben szereplő konvergencia-becslést használjuk, mert ezzel gyengébb feltételek mellett is igazolható szuperlineáris konvergencia. A következő nemlineáris transzport egyenletek osztályát vizsgáltuk −div (Ki ∇ui ) + bi · ∇ui + fi (x, u1 , . . . , ul ) = gi
ui |∂Ω = 0
(i = 1, . . . , l)
egy Ω ⊂ Rd (d = 2 or 3) tartományon, ami eleget tesz a következő feltételeknek: (i) Ki ∈ L∞ (Ω),
bi ∈ C1 (Ω)d és gi ∈ L2 (Ω) (i = 1, . . . , l), továbbá az f =
(f1 , . . . , fl ) : Ω × Rl → Rl korlátos és mérhető az x változójában és C 1 ξ-ben. (ii) létezik m > 0 amelyre Ki ≥ m teljesül minden i = 1, . . . , l indexre, továbbá a fξ0 (x, ξ) :=
∂f (x,ξ) ∂ξ
deriváltra fξ0 (x, ξ) η · η −
1 max div bi (x) |η|2 ≥ 0 i 2
minden (x, ξ) ∈ Ω × Rl esetén, ahol η ∈ Rl . (iii) legyen 3 ≤ p
(ha d = 2) vagy 3 ≤ p < 6 (ha d = 3), legyenek c1 , c2 ≥ 0
konstansok amelyekkel tetszőleges (x, ξ1 ) és (x, ξ2 ) ∈ Ω × Rl vektorokra
0
fξ (x, ξ1 ) − fξ0 (x, ξ2 ) ≤ c1 + c2 (max |ξ1 |, |ξ2 |)p−3 |ξ1 − ξ2 |
teljesül.
(iv) legyen p mint (iii)-ban, legyenek c3 , c4 > 0 konstansok amelyekkel tetszőleges (x, ξ1 ) és (x, ξ2 ) ∈ Ω × Rl vektorokra |fξ0 (x, ξ)| ≤ c3 + c4 |ξ|p−2
teljesül.
Ebben az esetben is az előzőhöz hasonló konvergencia-tulajdonságokkal bír a fent említett kvázi-Newton eljárás. A lineáris részfeladat nemszimmetrikussága miatt a CG módszer direkten nem alkalmazható, a normálegyenletre már igen, ekkor a nemlineáris rész deriváltjának sajátértékeit vizsgálva a következő konvergenciabecslést igazoltuk felhasználva a Szoboljev terek beágyazásához kapcsolódó Gelfand számokra vonatkozó ismereteket [18]:
6
Tétel 5. Jelölje rk a k. reziduálist, ekkor:
krk kSk kr0 kSk
1/k = O(k −1/p ) (ha d = 2),
O(k (6−p)/(6p) ) (ha d = 3).
Végül interface-típusú feladatokat vizsgáltunk. Gyakran interface-típusú feladatok írják le különböző fizikai tulajdonsággal bíró anyagok találkozási felületén végbemenő folyamatokatm. Egy ilyen alkalmazás lokalizált reakció-diffúzió egyenletek vizsgálatánál merül fel [12, 13]. A szakirodalomban több megoldási módszert javasoltak [12, 16, 14, 15]. Mi a gyenge alak segítségével a korábban használt technikákat használva javasoltunk egy megoldási módszert. −div (A(x)∇u) + q(x, u) = f (x) in Ω \ Γ, [u]Γ = 0 on Γ, A(x) ∂u + s(x, u) = γ(x) on Γ, ∂ν Γ u = g(x) on ∂Ω, ahol [u]Γ és A(x) ∂u jelöli az ugrását (azaz a közös Γ felület két oldalán vett határértékek ∂ν Γ különbségét) rendre az u és A(x) ∂u kifejezéseknek. A következő feltevéseket használtuk: ∂ν (A1) Ω ⊂ Rd (d = 2 or 3) korlátos tartomány , az interface Γ ⊂ Ω és a tartomány peremedarabonként elegendően sima Lipschitz felületek, (A2) A ∈ L∞ (Ω, Rd×d ), m.m. x ∈ Ω esetén A(x) szimmetrikus és teljesíti a szokásos ellipticitási feltételeket 0 < µ0 |ξ|2 ≤ hA(x)ξ, ξi ≤ µ1 |ξ|2 alkalmas µ0 , µ1 konstansokkal. (A3) q : Ω × R → R és s : Γ × R → R korlátos mérhető függvények az első változójuk szerint és C 1 -beliek a második változójuk szerint. Továbbá f ∈ L2 (Ω), γ ∈ L2 (Γ) és g ∈ H 1 (Ω). (A4) Legyen 2 ≤ p1 ha d = 2 or 2 ≤ p1 < 6 ha d = 3, továbbá legyen 2 ≤ p2 ha d = 2 vagy 2 ≤ p2 < 4 ha d = 3. Léteznek α1 , α2 , β1 , β2 ≥ 0 konstansok, hogy tetszőleges x ∈ Ω (x ∈ Γ) és ξ ∈ R esetén 0 ≤ ∂ξ q(x, ξ) ≤ α1 + β1 |ξ|p1 −2 ,
0 ≤ ∂ξ s(x, ξ) ≤ α2 + β2 |ξ|p2 −2 .
Megmutattuk, hogy a korábban bemutatott kvázi-Newton eljárás az előzőekhez hasonló konvergencia-tulajdonságokkal bír. Továbbá a Szoboljev terek beágyazásához 7
tartozó Gelfand számok [17] segítségével megmutattuk hogy a lineáris segédfeladatra a CG algoritmusra a következő konvergencia-becslés teljesül: Tétel 6. Jelölje rk a k. reziduálist, ekkor:
krk kSk kr0 kSk
1/k = O(k −1/d+(p−2)/2p + k −1/(d−1) ).
A disszertácó alapjául szolgáló publikációk [1] Antal, I. Mesh independent superlinear convergence of the conjugate gradient method for discretized elliptic systems, Hung. Electr. Jou. Sci. HU ISSN 14187108: HEJ Manuscript no.: ANM-080107-A [2] Antal, I. Mesh independent superliear convergence of an inner-outer iterative method for semilinear elliptic systems , NMA 2006, LNCS 4310/2007, pp. 508515, Eds.: T. Boyanov, S. Dimova, K. Georgiev, G. Nikolov, Springer-Verlag 2007, [3] Antal I., Karátson J., A mesh independent superlinear algorithm for some nonlinear nonsymmetric elliptic systems, Comput. Math. Appl. 55 (2008), 21852196. [4] Antal I., Karátson J., Mesh independent superlinear convergence of an innerouter iterative method for semilinear elliptic interface problems, J. Comp. Appl. Math. 226 (2009), 190-196.
Hivatkozások [5] Axelsson, O., Kaporin, I., On the sublinear and superlinear rate of convergence of conjugate gradient methods. Mathematical journey through analysis, matrix theory and scientific computation (Kent, OH, 1999), Numer. Algorithms 25 (2000), no. 1-4, 1–22. [6] Axelsson, O., Karátson J., Mesh independent superlinear PCG rates via compact-equivalent operators, SIAM J. Numer. Anal., 45 (2007), No. 4, pp. 14951516 (electronic). [7] Axelsson, O., Karátson J., Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators, Numer. Math. 99 (2004), No. 2, 197-223. 8
[8] Faber, V., Manteuffel, T., Parter, S.V., Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal. 21 (1984), no. 2, 352–362. [9] Faber, V., Manteuffel, T., Parter, S.V., On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations, Adv. in Appl. Math., 11 (1990), 109-163. [10] Hayes, R. M., Iterative methods of solving linear problems on Hilbert space, Contributions to the solution of systems of linear equations and the determination of eigenvalues, National Bureau of Standards Applied Mathematics Series No. 39, U. S. Government Printing Office, Washington, D. C., 1954, pp. 71-103. MR [11] Faragó I., Karátson J., Numerical solution of nonlinear elliptic problems via preconditioning operators: theory and application. Advances in Computation, Volume 11, NOVA Science Publishers, New York, 2002. [12] Kandilarov, J. D., A monotone iterative method for numerical solution of diffusion equations with nonlinear localized chemical reactions, Numerical Methods and Appllications, Lecture Notes in Computer Sciences, vol. 4310,2007, pp615-622. [13] Kandilarov, J. D., Vulkov, L. G.., Analysis of immersed interface difference schemes for reaction-diffusion problems with singular own sources, Comput. Methods Appl. Math. 3 (2003), no. 2, 253–273. [14] Li, Zh., A fast iterative algorithm for elliptic interface problems, SIAM J. Numer. Anal. 35 (1998), no. 1, 230–254. [15] Li, Zh., Ito, K., Maximum principle preserving schemes for interface problems with discontinuous coefficients, SIAM J. Sci. Comput. 23 (2001), no. 1, 339–361 (electronic). [16] LeVeque, R. J., Li, Zh., The immersed interface method for elliptic equations with discontinuous coefficients and singular sources, SIAM J. Numer. Anal. 31 (1994), no. 4, 1019–1044. [17] Schneider, C., Trace operators on fractalst, entropy and approximation numbers, Georgian Math. J. 18 (2011), 549-575. [18] Vybíral, J., Widths of embeddings in function spaces, Journal of Complexity, 24 (2008), 545-570.
9
[19] Winter, R., Some superlinear convergence results for the conjugate gradient method, SIAM J. Numer. Anal., 17 (1980), 14-17.
10
