On multilevel methods based on non-nested meshes [Elektronische Ressource] / vorgelegt von Thomas Dickopf

Thomas Dickopf

Sujets

• Mathematics

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2010
• Nombre de lectures: 41
• Langue: Deutsch
• Poids de l'ouvrage: 7 Mo

Extrait

On Multilevel Methods Based
on Non-Nested Meshes
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakult at
der
Rheinischen Friedrich-Wilhelms-Universit at Bonn
vorgelegt von
Thomas Dickopf
aus
Dernbach
Bonn, August 2010Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen Fakult at
der Rheinischen Friedrich-Wilhelms-Universit at Bonn
1. Referent: Prof. Dr. Rolf Krause
2. Referent: Prof. Dr. Martin Rumpf
Tag der Promotion: 18. November 2010
Erscheinungsjahr: 2010
Diese Dissertation ist mit Unterstutzung durch ein Hausdor -Stipendium der von der
Deutschen Forschungsgemeinschaft getragenen Bonn International Graduate School in
Mathematics (BIGS) entstanden. Weitere Mittel der Deutschen Forschungsgemeinschaft
wurden durch den Sonderforschungsbereich Singul are Ph anomene und Skalierung in mathe-
matischen Modellen (SFB 611) zur Verfugung gestellt.Zusammenfassung
Diese Arbeit besch aftigt sich mit Multilevel-Verfahren zur e zienten L osung von Partiellen
Di erentialgleichungen im Bereich des Wissenschaftlichen Rechnens. Dabei liegt ein wei-
terer Schwerpunkt auf der eingehenden Untersuchung des Informationsaustauschs zwischen
Finite-Elemente-R aumen zu nicht-geschachtelten Gittern.
Zur Diskretisierung von komplizierten Geometrien mit einer Finite-Elemente-Methode
sind unstrukturierte Gitter oft von Vorteil, weil sie der Form des Rechengebiets einfacher
angepasst werden k onnen. Solche Gitter, und somit die zugeh origen diskreten Funktio-
nenr aume, besitzen im Allgemeinen keine leicht zug angliche Multilevel-Struktur, die sich
zur Konstruktion schneller L oser ausnutzen lie e. In der vorliegenden Arbeit stellen wir
eine Klasse \semi-geometrischer" Multilevel-Iterationen vor, die auf Hierarchien voneinan-
der unabh angiger, nicht-geschachtelter Gitter beruhen. Dabei bestimmen in einem varia-
tionellen Ansatz rekursiv die Bilder geeigneter Prolongationsoperatoren im jeweils folgenden
(feineren) Raum die Grobgitterr aume. Das semi-geometrische Konzept ist sehr allgemeiner
Natur verglichen mit anderen Verfahren, die auf geometrischen Uberlegungen beruhen. Dies
zeigt sich in der verh altnism a ig losen Beziehung der verwendeten Gitter zueinander. Der
konkrete Nutzen des Ansatzes mit nicht-geschachtelten Gittern ist die Flexibiliatt der Wahl
der Grobgitter. Diese k onnen beispielsweise unabh angig mit Standardverfahren generiert
werden. Die Au osung des Randes des tats achlichen Rechengebiets in den konstruierten
Grobgitterr aumen ist eine Eigenschaft der entwickelten Verfahrensklasse.
Die exible Einsetzbarkeit und die E zienz der vorgestellten L osungsverfahren zeigt sich
in einer Reihe von numerischen Experimenten. Dazu geben wir Hinweise zur praktischen
Umsetzung der semi-geometrischen Ideen und konkreter Transfer-Konzepte zwischen nicht-
geschachtelten Gittern. Darub er hinaus wird eine Erweiterung zu einem semi-geometrischen
monotonen Mehrgitterverfahren zur L osung von Variationsungleichungen untersucht.
Wir fuhren die Analysis der Konvergenz- bzw. Vorkonditionierungseigenschaften im
Rahmen der Theorie der Teilraumkorrekturmethoden durch. Unsere technische Ausar-
beitung liefert ein quasi-optimales Resultat, das wir mithilfe lokaler Argumente fur allge-
meine, shape-regul are Gitterfamilien beweisen. Als relevante Eigenschaften der Operatoren
zur Prolongation zwischen nicht-geschachtelten Finite-Elemente-R aumen erweisen sich die
1 2H -Stabilit at und eine L -Approximationseigenschaft sowie die Lokalit at des Transfers.
Diese Arbeit ist ein Beitrag zur Entwicklung schneller L oser fur Gleichungen auf kom-
plizierten Gebieten mit Schwerpunkt auf geometrischen Techniken (im Unterschied zu al-
gebraischen). Verbindungen zu anderen Ans atzen werden sorgf altig aufgezeigt. Daneben
untersuchen wir den Informationsaustausch zwischen nicht-geschachtelten Finite-Elemente-
R aumen als solchen. In einer neuartigen Studie verbinden wir theoretische, praktische und
experimentelle Uberlegungen. Eine sorgf altige Prufung der qualitativen Eigenschaften sowie
eine quantitative Analyse der Unterschiede verschiedener Transfer-Konzepte zueinander
fuhren zu neuen Ergebnissen bezuglic h des Informationsaustauschs selbst. Schlie lich errei-
chen wir durch die Einfuhrung eines verallgemeinerten Projektionsoperators, der Pseudo-
2 2L -Projektion, eine deutlich bessere Approximation der eigentlichen L -orthogonalen Pro-
jektion als andere Ans atze aus der Literatur.Danksagung
Mein erster Dank gilt Herrn Professor Rolf Krause, der mich in das Gebiet des Wis-
senschaftlichen Rechnens und insbesondere in die Theorie der Teilraumkorrekturmethoden
eingefuhrt hat. Fur die vielf altige F orderung und die zahlreichen Hilfestellungen sowie
die M oglichkeit der aktiven Teilnahme an internationalen Konferenzen bin ich ihm sehr
dankbar. Sein wertvoller Rat hat gro e Teile dieser Arbeit ma geblich beein usst. Ich
danke Herrn Professor Martin Rumpf fur die freundliche Fortfuhrung der Betreuung in Bonn
verbunden mit der angenehmen Einfuhrung in seine Arbeitsgruppe und der Ubernahme des
Zweitgutachtens. Herrn Professor Helmut Harbrecht danke ich fur sein wohltuendes Inter-
esse an meiner Arbeit.
Der Bonn International Graduate School in Mathematics sei gedankt fur die Gew ahrung
eines Hausdor -Stipendiums sowie gro zugiger Reisemittel. Fur die Bereitstellung einer
hervorragenden Infrastruktur und weiterer nanzieller Mittel danke ich dem Institut fur
Numerische Simulation der Rheinischen Friedrich-Wilhelms-Universit at in Bonn, dem Son-
derforschungsbereich Singul are Ph anomene und Skalierung in mathematischen Modellen
(SFB 611) und dem Institute of Computational Science der Universit a della Svizzera italiana
in Lugano.
Ein herzlicher Dank gilt allen Kollegen am Institut fur Numerische Simulation der
Rheinischen Friedrich-Wilhelms-Universit at in Bonn und am Institute of Computational
Science der Universit a della Svizzera italiana in Lugano. Ihre au erordentliche Freund-
lichkeit wei ich sehr zu sch atzen. Vor allem danke ich Frau Mirjam Walloth, die mir
bei einer Vielzahl von Details bereitwillig zugeh ort hat und mir oft weiterhelfen konnte.
Darub er hinaus hat sie einen gro en Teil dieser Arbeit sehr intensiv korrekturgelesen. Herrn
Christian Gro bin ich besonders dankbar fur die abwechslungsreiche Zeit in unseren beiden
gemeinsamen Buros und auf verschiedenen Konferenzreisen. Die mathematischen, informa-
tischen und weltanschaulichen Diskussionen habe ich sehr genossen. Ich danke Herrn Arne
Dirks, mit dem ich in einem Zwischenstadium dieser Arbeit einige Implementierungsfragen
diskutieren durfte. Bei Herrn Dorian Krause bedanke ich mich fur die stets zuverl assige
Administration des Rechenclusters in Lugano und unkomplizierte Hilfe bei dessen Verwen-
dung. Frau Christina Mohr und Herrn Johannes Steiner danke ich fur ihr angenehmes
Interesse an meiner Arbeit und das sorgf altige Korrekturlesen gro er Teile derselben.
I would like to thank Professor David Keyes and his group at the Department of Applied
Physics and Applied Mathematics, Columbia University in the City of New York for their
kind hospitality during an inspiring research stay in fall 2008, especially Mr. Aron Ahmadia
and Mr. Braxton Osting for their continuous help and friendship.
Schlie lich habe ich vielen Freunden zu danken, die mich in den letzten Jahren begleitet
und unterstutzt haben. Ganz besonders danke ich meiner Familie fur ihre uneingeschr ankte
Unterstutzung, die mir stets gro artigen Ruc khalt gibt.
Bonn, August 2010 Thomas DickopfContents
Zusammenfassung iii
Introduction 1
1 Derivation of the model problems 7
1.1 Elliptic partial di erential equations . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Di usion equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.2 Linear elasticity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Variational inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.1 Scalar obstacle problems . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.2 Elastic contact . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.3 Existence of weak solutions and regularity . . . . . . . . . . . . . . . 15
1.3 Finite element approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 The need for preconditioning . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Multilevel methods for elliptic equations 23
2.1 Standard linear iterative methods . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2 Geometric multigrid methods . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Information transfer between nested nite element spaces . . . . . . 26
2.2.2 Coarse level correction . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2.3 The standard algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.4 Full multigrid or nested iteration . . . . . . . . . . . . . . . . . . . . 31
2.2.5 BPX-like preconditioners . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3 Convergence analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3.1 Subspace splitting and subspace correction . . . . . . . . . . . . . . 34
2.3.2 A relevant norm equivalence . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.3 The theory of Schwarz methods . . . . . . . . . .