Sparse grid methods for higher dimensional approximation [Elektronische Ressource] / vorgelegt von Christian Feuersänger

Christian Feuersänger

Sujets

• Informatik
• Naturwissenschaften
• Mathematics

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2010
• Nombre de lectures: 55
• Langue: Deutsch
• Poids de l'ouvrage: 7 Mo

Extrait

Sparse Grid Methods
for
Higher Dimensional
Approximation
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch–Naturwissenschaftlichen Fakultät
der
Rheinischen Friedrich–Wilhelms–Universität Bonn
vorgelegt von
Christian Feuersänger
aus
Düsseldorf
Bonn 2010Angefertigt mit Genehmigung der Mathematisch–Naturwissenschaftlichen Fakultät der
Rheinischen Friedrich–Wilhelms–Universität Bonn
1. Gutachter: Prof. Dr. Michael Griebel
2. Gutachter: Prof. Dr. Marc Alexander Schweitzer
Tag der Promotion: 7. September 2010
Erscheinungsjahr: 2010
iZusammenfassung
Diese Arbeit befasst sich mit Dünngitterverfahren zur Lösung von höherdimensionalen
Problemen. Sie zeigt drei neue Aspekte von Dünnen Gittern auf: Erweiterungen der
elementaren Werkzeuge zur Arbeit mit Dünnen Gittern, eine Analyse von sowohl inhä-
renten Einschränkungen als auch Vorteilen von Dünnen Gittern speziell für die Anwen-
dungzurDichteapproximation(Fokker–Planck–Gleichung)sowieeinenneuenAnsatzzur
dimensions- und ortsadaptiven Darstellungvon Funktionen effektiv niedriger Dimension.
Der erste Beitrag beinhaltet die erste (dem Autor bekannte) Fehlerschranke für in-
homogene Randbedingungen bei Dünngitterapproximation und eine erweiterte Opera-
tionsbibliothek zur Durchführung von Addition, Multiplikation und Hintereinanderaus-
führung von Dünngitterdarstellungen sowie einen adaptiven Kollokationsansatz für ap-
proximative Integraltransformationen mit beliebigen Kernen. Die Analyse verwendet
Konditionszahlen für den Datenfehler und verallgemeinert damit die speziellen Elemen-
tarabschätzungenaus[Gri98]und[MgF07].FernerwirderstmalsauchderKonsistenzfeh-
ler bei derartigen Operationen berücksichtigt sowie eine adaptive Methode zur Kontrolle
desselben vorgeschlagen, die insbesondere zuvor vorhandene Schwachstellen behebt und
die Methode verlässlich macht.
Der zweite Beitrag ist eine Untersuchung von dimensionsabhängigen Kosten/Nutzen-
Koeffizienten, wie sie bei der Lösung von Fokker–Planck–Gleichungen und der damit ver-
bundenen Approximation von Wahrscheinlichkeitsdichten auftreten. Es werden sowohl
theoretische Schranken als auch A-posteriori-Fehlermessungen anhand einer repräsenta-
dtivenFallstudiefürlineareFokker–Planck–GleichungenundderNormalverteilungaufR
vorgestellt und die auftretenden dimensionsabhängigen Koeffizienten bei Interpolation
und Bestapproximation (sowohlL als auch beim Lösen der Gleichung mittels Galerkin-2
Verfahren) untersucht. Dabei stehen reguläre Dünne Gitter, adaptive Dünne Gitter und
die speziell für die Energienorm optimierten Dünnen Gitter im Vordergrund (letzteres
ähnlich wie die Energieabschätzungen in [Gri06]). Insbesondere werden Schlussfolgerun-
gen auf inhärente Einschränkungen aber auch auf Vorteile gegenüber klassischen Voll-
gitterverfahren diskutiert.
Der dritte Beitrag dieser Arbeit ist der erste Ansatz für dimensionsadaptive Verfeine-
rung, der insbesondere für Approximationsprobleme konzipiert wurde. Der Ansatz be-
hebt bekannte Schwierigkeiten mit frühzeitiger Terminierung, wie sie bei bisherigen An-
sätzen zur Verallgemeinerung der erfolgreichen Dimensionsadaptivität aus dem Bereich
Dünngitterquadratur zu beobachten waren (vgl. [Gar04]). Das Verfahren erlaubt eine
systematische Reduktion der Freiheitsgrade für Funktionen, die effektiv nur von weni-
gen (Teilmengen von) Koordinaten abhängen. Der Ansatz kombiniert die erfolgreiche
ortsadaptive Dünngittertechnik aus dem Bereich der Approximation mit der ebenfalls
erfolgreichen dimensionsadaptiven Verfeinerung aus dem Bereich der Dünngitterqua-
dratur [GG03, Hol08]. Die Abhängigkeit von unterschiedlichen (Teilmengen von) Ko-
ordinaten wird mittels gewichteter Räume unter Zuhilfenahme der ANOVA-Zerlegung
durchgeführt [NW08]. Die Arbeit stellt neue a priori optimierte Dünngitterräume vor,
die optimale Approximation für Funktionenräume mit gewichteten gemischten zweiten
Ableitungen und bekannten Gewichten erlauben. Die Konstruktion liefert die bekannten
iiregulären Dünnen Gitter mit gewichtsabhängigen Leveln für jede Teilmenge von Koor-
dinaten (ANOVA Komponenten) im Unterschied zu bekannten Dünngitterkonstruktio-
nen aus [Kna00] (der Ansatz verläuft ähnlich wie die gewichteten Quadraturräume in
[Hol08]). Für unbekannte Gewichte wird eine neue a-posteriori dimensionsadaptive Me-
thode vorgestellt, die im Unterschied zu bekannten Verfahren aus [GG03, Gar04] explizit
ANOVA Komponenten ermittelt und berücksichtigt und so höhere Verlässlichkeit beim
Einsatz für Approximationsanwendungen erzielt. Neben reinerer Ap-
proximation erlaubt das Verfahren auch erstmals gekoppelte orts- und dimensionsadap-
tive Verfeinerung. Die Arbeit stellt die Methodik dar und verifiziert die Verlässlichkeit
anhand dimensionsadaptiver Interpolation und dimensionsadaptiver Lösung partieller
Differentialgleichungen.
Danksagung
An dieser Stelle gilt mein Dank Gott als meinem Schöpfer für die Fähigkeit, Stärke und
auch Gelegenheit zum Studium interessanter Themen mit faszinierenden Werkzeugen
– und das in exzellenter Arbeitsatmosphäre. Besonders bedanke ich mich hiermit bei
Prof. Dr. Michael Griebel für die Überlassung des interessanten Themas, die hochwer-
tige Betreuung, zahlreiche Ideen und Anregungen, den Arbeitsplatz und die exzellenten
Arbeitsbedingungen, sowohl in Bezug auf Ausstattung als auch in Bezug auf das Mitein-
ander in der Arbeitsgruppe. Des weiteren bedanke ich mich herzlich bei Prof. Dr. Marc
Alexander Schweitzer für die Übernahme des Zweitgutachtens. Mein Dank gilt weiter-
hin meinen Kollegen für viele fruchtbringende Diskussionen, an dieser Stelle besonders
Dr. Markus Holtz und Ralf Wildenhues. Mein Dank geht auch an Jens Oettershagen,
Bastian Bohn und Alexander Hullmann, deren Nutzung der entstandenen Softwarebi-
bliothek zahlreiche Qualitätsverbesserungen hervorbrachte. Bei meinen Kollegen Bastian
Bohn, Jürgen Braun, Alexander Hullmann, Jutta Adelsberger und Daniel Wissel bedan-
ke ich mich für die Hilfe bei der Korrektur des Manuskripts. Schließlich bedanke ich
mich bei meiner Frau Kerstin und meinen Eltern für die Unterstützung und Ermutigung
während der Zeit der Promotion.
Bonn, Sommer 2010 Christian Feuersänger
iiiivContents
1 Introduction 1
2 A Sparse Grid Approximation Algebra 5
2.1 Sparse Grid Appro . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 The Common Multiscale Grid Structure . . . . . . . . . . . . . . . 5
2.1.2 Basic Properties of Sparse Grid Spaces . . . . . . . . . . . . . . . . 13
2.1.3 Interpolation Error Bounds for Full and Sparse Grids . . . . . . . 20
2.1.4 Error Bounds for Non-Homogeneous Boundary Conditions . . . . . 23
2.2 Commonly used Algorithms and Complexities . . . . . . . . . . . . . . . . 31
2.2.1 Adaptive Interpolation and Approximation . . . . . . . . . . . . . 31
2.2.2 Fast Algorithms: the Unidirectional Principle . . . . . . . . . . . . 35
2.2.3 Data Structures for Adaptive Sparse Grids . . . . . . . . . . . . . 38
2.3 Approximative Algebraic Operations . . . . . . . . . . . . . . . . . . . . . 48
2.3.1 Motivation and Overview . . . . . . . . . . . . . . . . . . . . . . . 48
2.3.2 Approximative Pointwise Operations . . . . . . . . . . . . . . . . . 49
2.3.3 Approe Function Concatenation . . . . . . . . . . . . . . . 55
2.3.4 Approximate Integral Transformation . . . . . . . . . . . . . . . . 59
3 Sparse Grids and Moderate Dimensional Approximation – Two Case Studies 63
3.1 Overview and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 Case Study: Density Approximation and the Normal Distribution . . . . . 64
3.2.1 Interpolation Error Estimates . . . . . . . . . . . . . . . . . . . . . 64
3.2.2 Error Estimation Using Numerical Experiments . . . . . . . . . . . 72
3.2.3 Generalizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.4 Related Topics in the Area of Information Based Complexity . . . 88
3.2.5 Application in Moderate Dimensions: a Fokker–Planck–Example . 89
3.3 Case Study: Functions with Axis Parallel Structure . . . . . . . . . . . . . 94
3.3.1 Jump along a Hyperplane . . . . . . . . . . . . . . . . . . . . . . . 95
3.3.2 Sparse Grids, Jumps, and Overshooting . . . . . . . . . . . . . . . 95
3.3.3 Jump along a Hypercube . . . . . . . . . . . . . . . . . . . . . . . 97
3.3.4 Diagonal Structure and Sparse Grids . . . . . . . . . . . . . . . . . 98
3.3.5 Jump along an Arc . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.4 Summary on Moderate Dimensional Problems . . . . . . . . . . . . . . . . 101
4 Low Effective Dimensionality – A Dimension Adaptive Method 103
4.1 From ANOVA Decompositions to Sparse Grids . . . . . . . . . . . . . . . 104
4.1.1 ANOVA–like Decompositions . . . . . . . . . . . . . . . . . . . . . 104
vContents
4.1.2 Axis Parallel Structure and Low Effective Dimension . . . . . . . . 106
4.1.3 Sparse Grids as Discretized ANOVA Decomposition . . . . . . . . 107
4