Funktionalorientierte Gitteroptimierung bei der Finite ...richter/pdf-files/diplom.pdf · der Finite-Elemente L¨osung werden Ansatzr ¨aume verwendet, deren Funktio-nen auf den Zellen

Funktionalorientierte

Gitteroptimierung bei der

Finite-Elemente Approximation

elliptischer Differentialgleichungen

Diplomarbeit

von

Thomas Richter

Betreuer:

Prof. Dr. R. Rannacher

Fakultat fur Mathematik

Universitat Heidelberg

1. Januar 2001

Inhaltsverzeichnis

1 Einleitung 4

2 Die adaptive Finite-Elemente Methode 8

2.1 Finite-Elemente Methode, Grundlegende Notationen . . . . . . 8

2.2 Der a-posteriori Fehlerschatzer . . . . . . . . . . . . . . . . . . 11

2.3 Fehlerindikatoren und Adaptivitat . . . . . . . . . . . . . . . . 17

3 Optimierung der Funktionalauswertung 31

4 Optimale Gittererzeugung 37

4.1 Mehrfache Verfeinerung einer Zelle . . . . . . . . . . . . . . . 38

4.2 Erhohte Genauigkeit im dualen Problem . . . . . . . . . . . . 41

4.2.1 Der Algorithmus mit zwei Gittern . . . . . . . . . . . . 42

4.2.2 Auswertung des Fehlerschatzers . . . . . . . . . . . . . 43

4.2.3 Auswertung der Fehlerindikatoren . . . . . . . . . . . . 43

4.2.4 Die innere Iteration . . . . . . . . . . . . . . . . . . . . 44

4.2.5 Verfeinern des Gitters . . . . . . . . . . . . . . . . . . 45

4.3 Numerische Beispiele . . . . . . . . . . . . . . . . . . . . . . . 46

4.4 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . 54

5 Remeshing 57

5.1 Der adaptive FE-Algorithmus mir”Remeshing“ . . . . . . . . 59


2

6 Anisotrope Finite-Elemente 63

6.1 Erkennen von Anisotropie . . . . . . . . . . . . . . . . . . . . 64

6.1.1 Anisotropie im Interpolationsfehler . . . . . . . . . . . 65

6.1.2 Anisotrope Interpolationsabschatzungen . . . . . . . . 67

6.1.3 Anisotropie in den Fehlerindikatoren . . . . . . . . . . 68

6.2 Erzeugen von optimalen Tensorgittern . . . . . . . . . . . . . 71

6.2.1 Lokale Gittergenerierung . . . . . . . . . . . . . . . . . 71

6.2.2 Gittergenerierung . . . . . . . . . . . . . . . . . . . . . 72

6.2.3 Globale Gittergenerierung . . . . . . . . . . . . . . . . 72


6.4 Gitteroptimierung mit lokalen Interpolationsfehlern . . . . . . 82

6.5 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . 87

7 Ausblick 88

Literaturverzeichnis 90

3

Kapitel 1

Einleitung

Gegenstand dieser Arbeit ist die adaptive Finite-Elemente Approximation

partieller Differentialgleichungen. Bei der Finite-Elemente Methode wird zur

Losung der Differentialgleichung die beste Approximation in einem Funk-

tionenraum, dem Ansatzraum, gesucht. Grundlegend ist die Diskretisierung

der analytischen Gleichung. Hierzu wird das Gebiet, in dem die Differential-

gleichung zu losen ist, trianguliert, in Dreiecke oder Vierecke unterteilt. Im

dreidimensionalen Fall werden entsprechend Tetraeder oder Hexaeder ver-

wendet. Die Elemente der Triangulation heißen Zellen.

Die Gute der Diskretisierung wird durch die Triangulation bestimmt. Bei

der Finite-Elemente Losung werden Ansatzraume verwendet, deren Funktio-

nen auf den Zellen der Triangulation stuckweise polynomial sind. Die Ba-

sisfunktionen haben einen kleinen Trager, der sich nur uber wenige Zellen

erstreckt.

Bei der adaptiven Finite-Elemente Methode wird die Losung schrittweise

berechnet: zunachst wird eine Approximation der Losung auf einem gro-

ben Gitter, also einem Gitter mit wenigen Zellen, bestimmt. Mit einem a-

posteriori Fehlerschatzer wird die Gute dieser Approximation geschatzt. Ist

der Fehler zu groß, so muß eine genauere Approximation berechnet werden.

Hierzu werden Zellen des Gebiets verfeinert. Bei der adaptiven Methode wer-

den stets nur moglichst wenig Zellen zur Verfeinerung ausgewahlt, da der

Aufwand des Verfahrens mit der Zahl der Zellen steigt. Ziel ist es, die opti-

4

male Balance zwischen Aufwand und Genauigkeit zu finden, das bedeutet die

Zellen zu erkennen, die verfeinert werden mussen, um ein”optimales Gitter“

zu erzeugen.

Hierzu beschreiben lokale Fehlerindikatoren die Wirkung der einzelnen

Zellen auf den Gesamtfehler. Diese Fehlerindikatoren dienen zur Verfeine-

rung der Triangulation. Zellen, deren Fehlerindikatoren groß sind, werden

verfeinert. Auf der neuen Triangulation wird jetzt eine bessere Naherung der

Losung bestimmt. Dieser Prozeß wird solange wiederholt, bis der Fehler eine

gewunschte Toleranz unterschreitet und die Approximation in ausreichender

Genauigkeit vorliegt.

In dieser Arbeit werden folgende Fragen untersucht:

• Gibt es einen”optimalen Fehlerschatzer“? Optimal bedeutet hier, daß

der Wert des Fehlerschatzers sehr nahe am wirklichen Fehler liegt.

• Existiert eine”optimale Triangulierung“ zur Losung der Differential-

gleichung? Die vorgegebene Toleranz soll bei minimaler Anzahl an Zel-

len und mit moglichst wenigen Adaptionsschritten erreicht werden.

• Welche Diskretisierungsparameter neben den Zellgroßen bestimmen die

Approximation? Kann das adaptive Verfahren erweitert werden, so daß

auch die optimale Geometrie, also die Form der Zellen erkannt und

berucksichtigt wird?

Ein grundlegendes Werkzeug in dieser Arbeit ist die von Braack vorgestellte

Formel zur Berechnung der optimalen Zellgroße (siehe z.B. [1]). Eine Funk-

tion gibt fur jeden Punkt im Gebiet die optimale Zellweite an:

hopt(x) =

(W

Ncells

)12

Ψ(x)−14 .

Dabei ist Ncells die Zahl der Zellen der Triangulation, W und Ψ(x) werden

durch das Problem und Gebiet bestimmt.

In Kapitel 2 wird die adaptive Finite-Elemente Methode zunachst vor-

gestellt und im Detail diskutiert. Ein sehr allgemeiner Fehlerschatzer – von

Becker und Rannacher entwickelt [2] – wird vorgestellt. Dieser Fehlerschatzer

5

ermoglicht es, den Fehler in Funktionalen zu bestimmen. Ist man zum Bei-

spiel nur an der Losung in einem Punkt interessiert, so kann der Fehler auch

genau in diesem Punkt geschatzt werden. Weiter werden ubliche Adapti-

onsstrategien zur Gittersteuerung und auch die schon genannte Gitterformel

vorgestellt. Diese Adaptionsstrategien optimieren das Gitter in Bezug auf

das spezielle Fehlerfunktional und werden in diesem Kapitel analysiert und

erweitert.

Der Fehlerschatzer aus Kapitel 2 wird in Kapitel 3 verwendet werden,

um ohne zusatzlichen Rechenaufwand die Genauigkeit der Funktionalaus-

wertung zu erhohen. Soll die Losung im Funktional ausgewertet werden (z.B.

Ableitung in einem Punkt, Mittelwert in einem Teilgebiet, ..), kann der Feh-

lerschatzer einfließen, um den Wert des Fehlerfunktionals zu bestimmen.

Kapitel 4 beschaftigt sich mit dem Problem der”optimalen Gittersteue-

rung“. Hier wird ein Algorithmus vorgestellt, der die Zahl der Zwischenrech-

nungen, die bis zum entgultigen Ergebnis notig sind, reduziert. Die Gitterfor-

mel zeigt die optimalen Zellgroßen auf dem ganzen Gebiet. Es wird versucht,

eine Triangulation zu erzeugen, welche die von der Gitterformel vorgegebenen

Zellgroßen optimal widerspiegelt. Hierzu mussen die Zellen der Triangulati-

on in einem Schritt gleich mehrmals verfeinert werden, da das Gitter die

Zielgroßen moglichst schnell erreichen soll.

In Kapitel 5 wird die bisher betrachtete Methode der lokalen Gitterverfei-

nerung mit der Gittergenerierung verglichen. Bei lokaler Gitterverfeinerung

werden einzelne Zellen des Gitters in neue Zellen aufgeteilt, um eine feinere

Triangulation und somit eine bessere Approximation der Losung zu erreichen.

Die Struktur des Grobgitters bleibt dabei immer gleich, es werden keine Git-

terpunkte verschoben. Bei der Gittergenerierung wird in jedem Schritt ein

neues Gitter erzeugt. Gittergeneratoren versuchen ein Gitter zu erzeugen,

das vorgegebene Zellweiten optimal widerspiegelt. Ziel dieses Kapitels ist es

nicht, optimale Gittergeneratoren zu entwickeln; ein Gittergenerator wird nur

herangezogen, um zu prufen, ob vorgegebene Zellgroßen mit lokaler Gitter-

verfeinerung uberhaupt realisiert werden konnen, oder ob die Verwendung

von Gittergeneratoren hierfur unerlaßlich ist.

In Kapitel 6 wird auf anisotrope Probleme eingegangen. Ein stark ani-

6

sotropes Verhalten tritt bei vielen partiellen Differentialgleichungen auf. Be-

trachtet man z.B. Kanalstromungen bei hoheren Reynoldzahlen, so stellt man

fest, daß die Losung ihr Verhalten senkrecht zum Kanalrand stark andert,

sie tangential zum Rand aber nahezu konstant bleibt. Mogliche Anisotropie

soll a-posteriori erkannt werden und in die Diskretisierung einfließen. Mußten

bisher nur optimale Zellgroßen bestimmt werden, so ist es jetzt notwendig,

auch die optimale”Verzerrung“ der Zellen zu erkennen. Diese Information

uber die Anisotropie der Losung soll automatisch erkannt und berucksichtigt

werden. Die Gitteroptimierungsformel liefert hierfur keine Ansatze. Ziel ist

es, eine entsprechende Formel fur den anisotropen Fall zu entwickeln.

An dieser Stelle mochte ich Herrn Prof. Dr. R. Rannacher fur die Vergabe

des interessanten Themas sowie seine begleitende Betreuung beim Anfertigen

der Arbeit danken. Mein besonderer Dank gilt auch Herrn Dr. M. Braack fur

anregende Diskussionen und Herrn W. Bangerth fur programmiertechnische

Unterstutzung. Weiter mochte ich der ganzen AG Numerik fur ihr gutes

Arbeitsklima und stets offene Turen danken.

7

Kapitel 2

Die adaptive Finite-Elemente

Methode

2.1 Finite-Elemente Methode, Grundlegende

Notationen

Die adaptive Finite-Elemente Methode kann am besten an einem Beispiel

vorgestellt werden. Die Poissongleichung mit homogenen Dirichlet Randwer-

ten soll auf einem Quadrat gelost werden:

−∆u = f in Ω ⊂ R2

u = 0 auf ∂Ω

Ω = (−1, 1)2.

(2.1)

Dieses sehr einfache Problem ist leicht zu untersuchen und in vieler Hinsicht

typisch fur elliptische partielle Differentialgleichungen. Es wird im folgenden

oft als Modellproblem herangezogen. Eine Funktion u heißt klassische Losung

der Differentialgleichung, wenn u ∈ C2(Ω)∩C0(Ω) und u die Gleichung (2.1)

erfullt. In [3] wird gezeigt, daß dieses Problem eine Losung u ∈ C2,α(Ω) fur

alle f ∈ Cα(Ω) besitzt. Dabei ist

Cm,α(Ω) = v ∈ Cm(Ω) : ∂sv holder-stetig zum Exponenten α ∀ |s| = m.

Das Gebiet Ω muß hinreichend regular sein, zur”Klasse C2,α“ gehoren.[5]

8

Bei der Finite-Elemente Methode wird die Differentialgleichung als Va-

riationsgleichung gelost. Hierzu wird die Gleichung zunachst mit einer Test-

funktion ϕ multipliziert, welche die gleichen Randwerte wie u erfullt (ϕ = 0

auf ∂Ω). Anschließend wird uber das Gebiet Ω integriert:

−∫

Ω

∆uϕ dx =

∫

Ω

fϕ dx . (2.2)

Trivialerweise ist jede Losung u des Modellproblems (2.1) auch Losung der

variationellen Formulierung (2.2) fur alle Funktionen ϕ ∈ C∞0 . Mit partieller

Integration ergibt sich:∫

Ω

∇u∇ϕ dx −∫

∂Ω

∂nu ϕ︸︷︷︸=0

dx =

∫

Ω

fϕ dx . (2.3)

Dabei ist ∂nu :=< n,∇u >, wenn n der nach außen gerichtete Normalvektor

am Rand des Gebietes ist. Im Gegensatz zu (2.1) reichen bei dieser For-

mulierung schwachere Regularitatsbedingungen u ∈ H1(Ω). Dabei ist der

Sobolew-Raum Hp(Ω) die Vervollstandigung von (z.B. [4])

X := f ∈ C∞(Ω); ‖f‖p <∞, mit ‖f‖p :=∑

|α|≤p

‖∂αf‖L2(Ω) .

Die Losung der Variationsgleichung (2.3) wird nun in H10 (Ω) der entsprechen-

den Vervollstandigung des Funktionenraums

X := f ∈ C∞0 (Ω); ‖f‖p <∞

gesucht. Variiert wird uber alle Testfunktionen ϕ aus H10 (Ω). Das Problem

lautet dann:

suche u ∈ H10 (Ω) : (∇u,∇ϕ) = (f, ϕ) ∀ϕ ∈ V = H1

0 (Ω). (2.4)

Dabei werden folgende Bezeichnungen eingefuhrt:

(u, v) =

∫

Ω

uv dx ,

(u, v)K =

∫

Ω

uv dx , fur K ⊂ Ω,

‖u‖ =√

(u, u),

‖u‖K =√

(u, u)K.

9

Abbildung 2.1: Lineares Dreiecks- und bilineares Viereckselement.

Aus dem Riesz’schen Darstellungssatz folgt, daß das Variationsproblem (2.4)

fur alle f ∈ L2(Ω) eine Losung in u ∈ H10 (Ω) besitzt. Liegt dieses u in C2(Ω),

so stimmt diese Losung mit der klassischen Losung uberein.

Zur numerischen Losung des Variationsproblems wird dieses diskretisiert.

Der Ansatzraum, in dem die Losung u gesucht wird, sowie der Testraum der

Funktionen ϕ werden durch endlich dimensionale Unterraume ersetzt. Bei

der Finite-Elemente Methode sind dies Raume von stuckweise polynomialen

Funktionen. Die Basisfunktionen besitzen Trager, die sich nur uber wenige

Zellen erstrecken. Abbildung 2.1 zeigt eine Basisfunktion fur eine Dreieckstri-

angulation und fur eine Viereckstriangulation. Die diskreten Raume werden

stets mit Vh bezeichnet. Die diskretisierte Variationsgleichung nimmt folgen-

de Form an:

suche uh ∈ Vh : (∇uh,∇ϕh) = (f, ϕh) ∀ϕh ∈ Vh. (2.5)

In [3] und [5] wird genau auf die Fehleranalyse der Finite-Elemente Metho-

de eingegangen. Hier werden nur einige, fur diese Arbeit wichtige Punkte

betrachtet.

Wesentlicher Bestandteil von numerischen Methoden sind Fehlerschatzer.

Grundlegend fur die Fehlerbetrachtung ist die Galerkinorthogonalitat. Da

sowohl die kontinuierliche Losung u, als auch die diskrete Losung uh die

Variationsgleichung (2.5) erfullen, ergibt sich fur den Fehler e = u − uh die

Galerkinorthogonalitat:

(∇(u− uh),∇ϕh) = (∇e,∇ϕh) = 0, ∀ϕh ∈ Vh. (2.6)

10

Der Fehler steht orthogonal auf dem diskreten Testraum Vh. Damit laßt sich

der Fehler der Approximation uh in der naturlichen Norm des Problems, der

Energienorm ‖∇e‖ =√

(∇e,∇e) abschatzen.

‖∇e‖2 = (∇e,∇e) = (∇e,∇(u− uh))

= (∇e,∇(u− vh)) ∀vh ∈ Vh

≤ ‖∇e‖ ‖∇(u− vh)‖ .

Fur den Fehler ergibt sich

‖∇e‖ ≤ ‖∇(u− vh)‖ ∀vh ∈ Vh.

Die Finite-Elemente Approximation ist bezuglich der Energienorm die beste

Approximation im Ansatzraum und kann z.B. durch den Interpolationsfehler

abgeschatzt werden. Daraus ergibt sich die Fehlerabschatzung:

‖∇e‖ ≤ cih∥∥∇2u

∥∥ .

Dabei ist h die maximale Zellweite (der maximale Durchmesser) aller Ele-

mente der Triangulation und ci eine Interpolationskonstante. Dieser Feh-

lerschatzer ist ein sogenannter a-priori Fehlerschatzer. Der Fehlerschatzer

kann unabhangig von einer berechneten Approximation der Losung, also vor

dem Losen des Problems berechnet werden.

Grundlegender Nachteil dieses a-priori Fehlerschatzers ist, daß er in dieser

Form numerisch nicht auswertbar ist. Die Ableitungen der Losung sind nicht

bekannt. Der wirkliche Fehler wird zudem stark uberschatzt. Im folgenden

werden sogenannte a-posteriori Fehlerschatzer verwendet. Diese schatzen den

Fehler erst nach dem Losen der Gleichung. Der in dieser Arbeit verwendete

a-posteriori Fehlerschatzer wird genauer sein als der a-priori Schatzer und

zusatzlich im Verlauf der Rechnung an Genauigkeit gewinnen.

2.2 Der a-posteriori Fehlerschatzer

Beim adaptiven Finite-Elemente Verfahren wird zunachst eine Naherungs-

losung der Differentialgleichung bestimmt. Mit den Informationen aus dieser

11

Losung – a-posteriori – wird der Fehler geschatzt. Ist der Fehler noch zu

groß, so muß eine genauere Losung bestimmt werden. Hierfur werden aus

der bisherigen Losung Informationen uber die Diskretisierung gewonnen, die

einfließen, um eine bessere Triangulation zu erzeugen. Dieser Prozeß wird

solange wiederholt, bis der Fehler klein genug ist (oder die Kapazitat des

Computers erschopft ist). Ein a-posteriori Fehlerschatzer kann zwei Aufgaben

erfullen:

1. Der Fehler der Losung muß berechnet werden. Dieses wird als der ei-

gentliche Fehlerschatzer bezeichnet und dient als Abbruchskriterium

fur die Rechnung.

2. Aus dem Fehlerschatzer mussen Strategien zur Gitteradaption herge-

leitet werden. Eine Moglichkeit ist, den Ursprung des Fehlers zu lokali-

sieren: fur jede Zelle der Triangulation wird ein Wert – der Fehlerin-

dikator – vorliegen, der den Einfluß dieser Zelle auf den Gesamtfehler

beschreibt. Die Fehlerindikatoren werden zur Verfeinerung der Trian-

gulation verwendet.

Der Fehler e = u− uh soll allgemein in (linearen) Funktionalen

j : H1(Ω) → R

gemessen werden konnen. Dabei konnen die Funktionale z.B. Punkt- oder

Mittelwerte uber den Fehler oder Ableitungswerte des Fehlers beschreiben.

Herkommliche Fehlerschatzer messen den Fehler in (teils gewichteten) glo-

balen Normen. Der Ansatz uber Funktionale ist viel allgemeiner. Mogliche

Funktionale sind:

Punktfehler j(u) = u(x0), x0 ∈ Ω,

Ableitungsfehler j(u) = ∂xu(x0), x0 ∈ Ω,

Mittelwerte j(u) = 1/ |W|∫Wu dx , W ⊂ Ω,

Randintegrale j(u) =∫

∂Ω∂nu dx .

12

In der gerechneten Losung uh, in den Daten f und in dem Gebiet allein

sind nicht genug Informationen enthalten, um den Fehler in dieser Allge-

meinheit zu bestimmen. Das im folgenden vorgestellte Verfahren wurde von

Becker und Rannacher (siehe z.B. [2]) entwickelt und erlaubt es, den Fehler

in beliebigen linearen Funktionalen zu bestimmen.

Um den Fehler in einem linearen Funktional j : H1(Ω) → R zu bestim-

men, wird das duale Problem definiert:

suche z ∈ V (∇ϕ,∇z) = j(ϕ) ∀ϕ ∈ V. (2.7)

Im folgenden wird davon ausgegangen, daß sowohl u, als auch z mit linearen,

bzw. bilinearen Elementen berechnet werden. Dann gilt mit e = u − uh fur

alle zh ∈ Vh wegen der Galerkinorthogonalitat (2.6) folgende Fehleridentitat:

j(e) = (∇e,∇z)= (∇(u− uh),∇(z − zh))

= (f, z − zh) − (∇uh,∇(z − zh))

=∑

K∈Th

(f + ∆uh, z − zh)K − 〈∂nuh, z − zh〉∂K

=∑

K∈Th

(f + ∆uh, z − zh)K − 12〈[∂nuh] , z − zh〉∂K .

(2.8)

Dabei sind [∂nuh] fur ∂K ⊂ Ω, also fur Kanten, die nicht am Rand des

Gebietes liegen, die Sprunge uber die Normalableitung am Zellrand:

[∂nuh] (x) = limt→0+

∂uh

∂n(x− tn) − ∂uh

∂n(x+ tn)

.

n ist der nach außen gerichtete Normalvektor an ∂K. Liegt ∂K ⊂ ∂Ω auf

dem Rand des Gebiets, so ist

[∂nuh] (x) = 2∂nuh(x).

Da aber sowohl z als auch zh auf dem Rand identisch Null sind, fallt das Ska-

larprodukt an allen Zellen des Rands weg. Wird eine Moglichkeit gefunden,

die duale Losung z numerisch auszuwerten, so kann ein Schatzwert fur den

Fehler in jedem linearen Funktional ermittelt werden.

13

Da die rechte Seite f und die diskrete Losung uh bekannt sind, konnen

die Residuen numerisch ausgewertet werden. Die Gewichte konnen in dieser

Form nicht ausgewertet werden, da die duale Losung z nicht vorliegt. Fur

eine Naherung gibt es folgende Ansatze:

1. Die duale Losung wird in einem Ansatzraum von hoherer Ordnung

z(2) ∈ V(2)h , zum Beispiel mit biquadratischen Elementen berechnet;

(z − zh) wird durch (z(2)h − ihz

(2)h ) ersetzt, wobei ih die Interpolation

ih : H1(Ω) → Vh ist. Als auswertbarer Fehlerschatzer ergibt sich:

η1 =∑

K∈Th

(f, z(2) − ihz

(2)h ) −

(∇uh,∇(z

(2)h − ihz

(2)h ))

. (2.9)

Dieser Ansatz scheidet wegen seiner hohen Kosten allerdings aus, da

schon das Losen mit biquadratischen Elementen, im Gegensatz zu bi-

linearen Elementen, einen enormen Mehraufwand bedeutet.

2. Liegt die duale Losung in H2(Ω), so kann die in Vh frei wahlbare Funk-

tion zh als ihz, die Knoteninterpolierende von z gewahlt werden. Mit

der Interpolationskonstante ci gelten die Interpolationsabschatzungen

‖z − ihz‖K ≤ cih2K

∥∥∇2z∥∥

K,

‖z − ihz‖∂K ≤ cih3

2

K

∥∥∇2z∥∥

K.

(2.10)

Die zweiten Ableitungen von z konnen dann uber einen Differenzen-

quotienten ∇2hzh(xK) ausgewertet werden:

η2 =∑

K∈Th

cIh3K(‖f‖K + h

12K ‖[∂nuh]‖)

∣∣∣∇2hzh(xK)

∣∣∣K

(2.11)

3. Die duale Losung wird im gleichen Ansatzraum Vh berechnet und (z−zh) wird durch (z∗h − zh) ersetzt. Dabei ist z∗h die patchweise Interpo-

lierte von zh in einen Raum hoherer Ordnung: die Losung zh wird auf

einer Gruppe von 2 × 2 aneinandergrenzenden Zellen mit der gleichen

Verfeinerungsstufe (auf einem”Patch“) quadratisch interpoliert. Diese

biquadratisch Interpolierte z∗h ist eine genauere Approximation von z

als die gerechnete zh:

η3 =∑

K

(f, (z∗h − zh))K − 1

2〈[∂nuh] , (z

∗h − zh)〉∂K

. (2.12)

14

Die Qualitat eines Fehlerschatzers kann an seiner Nahe zum wirklichen

Fehler gemessen werden. Um die Gute eines Fehlerschatzers η quantitativ

messen zu konnen, wird der Effektivitatsindex

Ieff =η

j(e)

eingefuhrt. Je naher dieser Wert bei 1 liegt, umso genauer ist der Feh-

lerschatzer. Asymptotisch sollte der Effektivitatsindex gegen 1 oder zuminde-

stens gegen eine Konstante konvergieren. Ist die Konstante nicht unabhangig

vom Problem, so ist der Fehlerschatzer als Abbruchskriterium wertlos. In

Beispiel (2.1) werden die Effektivitatsindizes der Fehlerschatzer (2.9, 2.11,

2.12) getestet.

Beispiel 2.1 (Effektivitatsindex) Gelost wird das Modellproblem (2.1).

Zwei verschiedene Fehlerfunktionale werden betrachtet:

j1(ϕ) = ϕ(

14, 1

4

),

j2(ϕ) =1

|W|

∫

W

ϕ, W =[−1

2, 0]×[0, 1

2

].

Die rechte Seite wird anhand der vorgegebenen Losung bestimmt:

u(x, y) = (1 − x2)(1 − y2) sin(4x) sin(4y).

Verglichen werden die Effektivitatsindizes der Fehlerschatzer η1 (2.9), η2

(2.11) und η3 (2.12).

In Tabelle 2.1 werden fur eine Sequenz von lokal verfeinerten Gittern die

Effektivitatsindizes angegeben. Zusatzlich wird die Zeit angegeben, die ins-

gesamt (bei der gesamten Sequenz) fur die Berechnung des Fehlerschatzers

aufgewendet wurde. Der numerische Aufwand besteht insbesondere in der

Quadratur. Bei Fehlerschatzer η1 spielt die Berechnung der dualen Losung

mit biquadratischen Elementen die großte Rolle. Das hier verwendete Ver-

fahren zur Gitteradaption, also zur lokalen Gitterverfeinerung wird spater

beschrieben.

Die Fehlerschatzer η1 und η3 liegen sehr schnell nahe am Fehler. Bei

beiden Fehlerfunktionalen konvergieren sie gegen 1. Der Fehlerschatzer η2

15

Mittelwert

N j(e) η1/e η2/e η3/e

81 0.076 1.0151 393.5 1.0588

151 0.027 1.0072 337.9 1.0710

653 0.0036 0.9995 229.9 0.9963

1435 0.0014 1.0017 177.2 1.0074

2937 0.00065 1.0002 120.8 0.9852

6249 0.00032 1.0004 84 1.0087

12995 0.00012 1.0001 84.1 0.9964

26603 7.25 · 10−5 1.00009 55.6 1.0038

56073 2.70 · 10−5 1.00004 61.6 0.9963

Zeit fur Auswertung 1400 sec 182 sec 130 sec

Punktfehler

N j(e) η1/e η2/e η3/e

81 0.4288 0.179 69.6 0.187

151 0.1463 0.269 83.1 0.205

297 0.0382 0.267 115.8 0.245

635 0.0102 0.305 123.6 0.285

1443 0.00295 0.398 129.1 0.407

2875 0.000945 0.528 130.9 0.515

6229 0.000289 0.614 147.7 0.605

12521 0.000108 0.742 148.1 0.727

26903 3.948 · 10−5 0.824 155.3 0.806

55287 1.624 · 10−5 0.893 155.8 0.882

Zeit fur Auswertung 1540 sec 188 sec 138 sec

Tabelle 2.1: Die Effektivitatsindizes fur alle drei Fehlerschatzer und die Zeit,

die insgesamt zur Auswertung der Fehlerschatzer (inkl. duales Problem) auf-

gewendet wurde. (Beispiel 2.1)

16

liefert aber keine brauchbaren Ergebnisse. Der Effektivitatsindex pendelt sich

zwar ein, jedoch ist dieser Wert nicht problemunabhangig, und die Konstante

ist sehr groß. Bei diesem Fehlerschatzer fließt neben Interpolationskonstanten

zusatzlich die Ungenauigkeit, die durch die Anwendung der Cauchy-Schwarz

Ungleichung hervorgerufen wird, ein.

Der zeitliche Aufwand fur die Berechnung der patchweisen Interpolie-

renden z∗h ist sehr gering, somit scheint dieser Fehlerschatzer der optimale

hinsichtlich Genauigkeit und Aufwand zu sein. Der geringfugig bessere Ef-

fektivitatsindex bei η1 ist nicht den hohen Aufwand wert, der mit der Losung

des dualen Problems mit biquadratischen Finiten Elementen verbunden ist.

Wenn im Folgenden vom Fehlerschatzer die Rede ist, ist stets η3 gemeint,

und er wird einfach mit η bezeichnet.

2.3 Fehlerindikatoren und Adaptivitat

Adaptive Finite-Elemente Verfahren passen das Gitter wahrend der Rech-

nung dem Problem an. Um den Fehler der Rechnung zu reduzieren, werden

stets die Zellen verfeinert, die zu einem”optimal erreichbaren“ Gitter fuhren:

der Fehler auf dem neuen Gitter soll bei moglichst wenig Zellen klein sein.

Hierzu werden Zellen verfeinert, deren Fehlerindikatoren”groß“ sind. Bei

globaler Verfeinerung wird das Gitter auch da verfeinert, wo der erwunschte

Fehler schon weit unterschritten ist. An Stellen mit großem Fehlerindika-

tor wird unter Umstanden zuwenig verfeinert. Adaptive, lokale Verfeinerung

kann zu”optimalen Gittern“ fuhren, auf denen die Losung mit weniger Zel-

len, also mit weniger Freiheitsgraden und somit weniger Rechenaufwand ge-

wonnen werden kann. Der ubliche Algorithmus zum adaptiven Losen einer

Differentialgleichung ist:

1. Vorgegeben ist ein Startgitter Th, und eine Toleranz TOL,

die im Fehlerfunktional erreicht werden soll.

2. Berechne uh zur Triangulation Th.

3. Berechne den Fehlerschatzer η.

17

4. η < TOL: Abbruch.

5. Berechne die Fehlerindikatoren ηK.

6. η > TOL: Verfeinere das Gitter mit den Fehlerindikatoren

ηK und wiederhole ab 2.

Die Berechnung des Fehlerschatzers in Schritt 3 des Algorithmus wurde

in Abschnitt 2.2 behandelt. Jetzt soll kurz auf die Fehlerindikatoren einge-

gangen werden:

Die Fehlerindikatoren stellen eine Lokalisierung des Fehlers da. Um mit

ihnen ein Gitter zu erzeugen, mussen sie stets positiv sein. Ausgehend von den

drei Fehlerschatzern η1, η2 und η3 (2.9, 2.11, 2.12) des letzten Kapitels liegt es

nahe, die lokale Struktur des Fehlerschatzers zu nutzen und die Indikatoren

als

j(e) ≤∑

K∈Th

ηK ,

η1K =

∣∣∣(f, z(2)h − ihz

(2)h )K −

(∇uh,∇(z

(2)h − ihz

(2)h ))

K

∣∣∣ ,

η2K = h3

K

(‖f‖K + 1

2h−

12

K ‖[∂nuh]‖∂K

) ∣∣∣∇2hzh(xK)

∣∣∣ ,

η3K =

∣∣(f, z∗h − zh)K − 12〈[∂nuh] , z

∗h − zh〉∂K

∣∣

zu definieren. Die Anteile der Fehlerindikatoren werden ublicherweise in Re-

siduen ρK und Gewichte ωK aufgeteilt. Die Fehlerindikatoren η2K schreiben

sich dann als:

ηK = (ρ(1)K + ρ

(2)K )ωK

ρ(1)K = ‖f‖K

ρ(2)K = 1

2h−

12


ωK = h3K

∣∣∣∇2hzh(xK)

∣∣∣ .

(2.13)

Die Residuen beschreiben die Approximation der Losung, die Gewichte geben

den Einfluß des Fehlerfunktionals an. Es zeigt sich, daß ρ(2)K ωK der maßgeb-

liche Term im Fehlerschatzer ist. Wird die frei wahlbare Funktion zh ∈ Vh

18

als eine Interpolierende von z auf einem Patch P von 2 × 2 Zellen gewahlt,

so bleibt ein Freiheitsgrad in der Mitte des Patchs ubrig, um folgende Eigen-

schaft dieser speziellen Interpolierenden iP z zu erreichen:∫

P

(z − iP z) = 0. (2.14)

Dann steht z− iP z also orthogonal auf allen patchweise konstanten Funktio-

nen und der Fehlerschatzer laßt sich schreiben als:

j(e) =∑

P∈Th

(f − fP , z − iP z)P − 12〈[∂nuh] , (z − iP z)〉∂P .

Der Term ‖f − fP‖P ‖z − iP z‖P ist um eine h-Potenz kleiner als der Sprung-

term und kann fur h→ 0 vernachlassigt werden.

Zunachst wird auf Schritt 6 des Algorithmus, dem Erzeugen eines neu-

en Gitters, eingegangen. Prinzipiell gibt es bei adaptiven Finite-Elemente

Methoden zwei Moglichkeiten, ein neues Gitter zu erzeugen:

Mesh Refinement Zellen des Gitters werden verfeinert, oder mehrere Zel-

len werden zu einer groberen Zelle zusammengefaßt. Bei einem zweidi-

mensionalen Rechteckgitter kann eine Zelle entweder in vier neue Zellen

unterteilt werden, oder es wird ein Patch aus 2 × 2 Zellen mit gleicher

Verfeinerungsstufe zu einer Zelle zusammengefaßt.

Remeshing Ausgehend von den Fehlerindikatoren wird ein vollstandig neu-

es Gitter erzeugt. Aus den Fehlerindikatoren werden optimale Zellwei-

ten berechnet und es wird versucht, ein Gitter zu erzeugen, welches

diese Zellweiten am besten wiederspiegelt. In einem spateren Abschnitt

wird diese Methode der Gittererzeugung mit der lokalen Gitterverfeine-

rung verglichen. Genauere Untersuchungen hierzu sind nicht Ziel dieser

Arbeit.

Zunachst wird die erste Methode, das Mesh Refinement (die”lokale Gitter-

verfeinerung“) untersucht. Bei lokaler Gitterverfeinerung entsteht folgende

Situation: wird eine Zelle verfeinert, so entstehen auch neue Freiheitsgrade.

Diese treffen nicht zwangslaufig auf Freiheitsgrade von anderen Zellen, son-

dern konnen auch mitten auf der Kante einer Nachbarzelle liegen. Wurde

19

Abbildung 2.2: Gitter mit zwei”hangenden Knoten“

man diese sogenannten”hangenden Knoten“ (siehe Abbildung (2.2)) nicht

gesondert berucksichtigen, so ware die Finite-Elemente Methode nicht kon-

form, d.h. Vh 6⊂ H1(Ω). Diese Bedingung ist aber absolut erforderlich. Die

zusatzlichen Freiheitsgrade durfen nicht wie die ubrigen behandelt werden;

an diesen Stellen muß Stetigkeit erzwungen werden. Hierzu werden die Werte

der diskreten Funktionen an diesen Freiheitsgraden auf den Mittelwert der

beiden angrenzenden Freiheitsgrade gesetzt. Auf jeder Kante einer Zelle ist

nur ein hangender Knoten erlaubt. Hangende Knoten und die damit auf-

tauchenden Probleme werden z.B. in [7] diskutiert. Mit diesem Vorgehen ist

lokale Gitterverfeinerung moglich. In jedem Schritt der Verfeinerung sollen

stets die Zellen verfeinert werden, deren Fehlerindikatoren”groß“ sind. Die

Fehlerindikatoren der Zellen gleichen sich mit jedem Schritt der Verfeinerung

an. In einem”optimalen Gitter“ sind die Fehlerindikatoren aquilibriert. Mit

entsprechender Abstraktion kann dieses bewiesen werden. Dazu seien Ki fur

i = 1, . . . , N die N Zellen einer Triangulation mit Fehlerindikatoren ηi. Nach

Verfeinerung einer Zelle entstehen vier neue Zellen, jeweils mit Fehlerindika-

toren

η[1]i =

1

16ηi.

Hier wurde quadratische Konvergenz angenommen. Die Rechnung kann ent-

sprechend mit jeder anderen Konvergenzordnung durchgefuhrt werden. Die

Vereinfachung besteht in der Annahme, daß die Konvergenzordnung auf dem

ganzen Gebiet gleich ist. Davon kann i.A. nicht ausgegangen werden. Da die

Fehlerindikatoren positiv sind, meist einfach Absolutwerte der lokalen Dar-

stellung des Fehlerschatzers sind, mußte auch der Zusammenhang zwischen

20

der”Konvergenz“ der Fehlerindikatoren und des Fehlerschatzers betrachtet

werden. Hier wird aber davon ausgegangen, daß sich die Fehlerindikatoren

wie der Fehler verhalten.

Satz 2.1 (Aquilibrierung) Auf einem Gitter mit N Zellen seien die Feh-

lerindikatoren η1, . . . , ηN mit ηi > 0 gegeben. Weiter entstehen nach ri-facher

Verfeinerung einer Zelle Ki 4ri neue Zellen, jeweils mit Fehlerindikator

η[ri]i = 16−riηi. (2.15)

Zu vorgegebener Fehlertoleranz TOL entsteht bei ri-facher lokaler Verfeine-

rung der Zellen Ki genau dann ein Gitter mit minimaler Zahl von Zellen,

wenn die Fehlerindikatoren η[ri]i aquilibriert sind.

Beweis:

Es sei r = (r1, . . . , rN) ∈ NN . Die Zelle Ki wird ri mal verfeinert. Dann hat

das entstehende Gitter

N(r) =N∑

i=1

4ri

Zellen. Die Summe der Fehlerindikatoren ist wegen der Voraussetzung

E(r) =N∑

i=1

4riηi16−ri =N∑

i=1

ηi4−ri.

Im folgenden wird nur ein kontinuierliches Problem fur r ∈ RN gelost. Nur

fur diesen Fall ist ein Lagrange-Ansatz moglich. Ist ein Toleranzwert TOL

vorgegeben, so ist das Minimierungsproblem

! minN(r), E(r) ≤ TOL

zu losen. Mit dem Lagrange-Ansatz

L(r, λ) = N(r) + λ(TOL− E(r))

∂L

∂ri(r, λ) = ln 4 · 4ri + ληi ln 4 · 4−ri

∂

∂λL(r, λ) = TOL− E(r)

21

erhalt man gleich fur ∂riL = 0:

ηi = −1

λ16ri. (2.16)

Setzt man (2.16) in (2.15) ein, so ergibt sich fur η[ri]i nach ri-facher Verfeine-

rung ein vom ursprunglichen Fehlerindikator unabhangiger Wert:

η[ri]i = −ηi

1

ληi

= −1

λ,

Eigentlich ware hier ein ganzzahliges Optimierungsproblem zu losen. Das

Ziel, eine Aquilibrierung der Fehlerindikatoren zu erreichen bleibt aber be-

stehen. Das Ergebnis zeigt vielmehr die Einschrankung der”zulassigen Git-

ter“, die durch lokale Gitterverfeinerung erzeugt werden konnen. Eine echte

Aquilibrierung ist nicht moglich.

Ist eine Aquilibrierung der Fehlerindikatoren erreicht, so wird nach wei-

terer globaler Verfeinerung ein”optimales Gitter“ mit aquilibrierten Fehler-

indikatoren erhalten.

Satz 2.2 (Globale Verfeinerung) Auf einem Gitter mit N Zellen seien

die Fehlerindikatoren aquilibriert: ηi = η, ∀i ∈ 1, . . . , N. Nach ri-facher

Verfeinerung einer Zelle Ki enstehen 4ri neue Zellen, mit Fehlerindikator

η[ri]i = 16−riη.

Nach globaler Verfeinerung entsteht ein Gitter mit minimaler Zahl von Zellen

in der Klasse der”zulassigen“ Gitter, auf dem die Losung mit der Fehlerto-

leranz TOL approximiert wird.

Beweis:

Nach r-facher globaler Verfeinerung gilt fur die Fehlerindikatoren aller Zellen

η[r]i = 16−rη.

Die Fehlerindikatoren sind also auch im neuen Gitter aquilibriert, und das

Gitter ist mit den Ergebnissen von Satz 2.1 optimal.

22

Die Auswahl der Zellen zur Verfeinerung kann nach unterschiedlichen

Verfeinerungsstrategien (Adaptionsstrategien) geschehen. Einige, haufig ver-

wendete werden im folgenden genannt und diskutiert. Insbesondere wird un-

tersucht, ob sich bei den Adaptionsstrategien aquilibirierte Fehlerindikatoren

einstellen und ob diese dann unter weiterer Verfeinerung erhalten bleiben.

1) Fixed error fraction:

Es werden die Zellen mit den großten Fehlerindikatoren verfeinert, die sum-

miert einen Anteil γ des Fehlers ausmachen. Hierzu werden die Fehlerindika-

toren zunachst absteigend sortiert

ηKi≥ ηKi+1

.

Alle Zellen Ki fur i = 1, . . . , I mit

I = arg

max

1≤I≤N

I∑

i=1

ηKi≤ γη

werden verfeinert. Dieses Vorgehen hat den Nachteil, daß nicht gesteuert

werden kann, wieviele Zellen verfeinert werden. Sind die Fehlerindikatoren

aquilibriert, so werden nur γN Zellen verfeinert.

2) Fixed number:

In jedem Schritt wird ein bestimmter Anteil γ von Zellen mit großem Fehler-

indikator verfeinert. Die Fehlerindikatoren werden wieder absteigend sortiert

und alle Zellen Ki mit i = 1, · · · , γN werden verfeinert. Dieses Verfahren

berucksichtigt nicht die Verteilung der Fehlerindikatoren. Sind die Indika-

toren ungleich verteilt, so werden zu Beginn zuviele Zellen verfeinert. Eine

Aquilibrierung wird nicht dauerhaft erreicht und wenn sie vorliegen sollte,

sofort wieder gestort, da nicht global verfeinert wird.

3) Error balancing:

Zu einer vorgegebenen Toleranz TOL wird ein zellweiser Toleranzwert

tol =TOL

N

berechnet. Verfeinert werden alle ZellenK, deren Fehlerindikator uber diesem

Wert liegen

ηK > tol.

23

Eine sinnvolle Strategie ist, die Toleranz TOL auf die Halfte der Summe der

Fehlerindikatoren zu setzen. Dann ist sichergestellt, daß die Fehlerindikatoren

zunachst aquilibriert werden. Ist dieses der Fall, so wird das Gitter global

verfeinert.

4) Optimierungsformel

Ist das Ziel vorgegeben, die Fehlerindikatoren auf einem niedrigen Wert zu

aquilibrieren, so kann dieses als Optimierungsproblem formuliert werden. Als

Losung erhalt man die optimale Gitterweite hopt(x) als Funktion. (Siehe hier-

zu z.B. [1], [6]). Zunachst wird angenommen, daß fur die Residuen (2.13)

ρK = ρ(1)K + ρ

(2)K

mit h→ 0 ein gitterunabhangiger Grenzwert

h−1K ρK ≈ Ψu(xK) (2.17)

gilt. Dabei bedeutet a ≈ b, daß es eine von h unabhangige Konstante C gibt,

so daß gilt:1

Cb ≤ a ≤ Cb.

Auch fur die duale Losung gilt entsprechend fur z ∈ H2(Ω)

h−3K ωK ≤ cihK

∥∥∇2z∥∥

K≈ ci

∣∣∇2z(xK)∣∣ =: Ψz(xK). (2.18)

Mit (2.17) und (2.18) sei dann

Ψ(x) := Ψu(xK)Ψz(xK), mit x, xK ∈ K.

Der Fehler η =∑

K∈ThρKωK laßt sich damit schreiben als

η ≈ E(h) =∑

K∈Th

h4KΨ(xK) =

∫

Ω

h(x)2Ψ(x) dx . (2.19)

Grundlegend fur das weitere Vorgehen ist die Existenz dieser Fehlerdarstel-

lung. Insbesondere das Integral∫

Ψ(x) dx muß existieren. Hierfur ist Voraus-

setzung, daß die zweiten Ableitungen von u und z im Produkt integrierbar

sind. Mit diesen Definitionen lassen sich zwei Optimierungsprobleme formu-

lieren:

24

(I) Minimiere E(h) unter der Nebenbedingung N ≤ Nmax.

(II) Minimiere N unter der Nebenbedingung E(h) ≤ TOL.

Satz 2.3 (Gitteroptimierungsformel) Unter der Voraussetzung, daß der

Fehlerschatzer asymptotisch fur h→ 0 die Form (2.19) annimmt und folgen-

des Integral existiert

W :=

∫

Ω

Ψ(x)1

2 dx <∞,

haben die Optimierungsprobleme (I) und (II) die Losungen

(I) hopt(x) ≈(

W

Nmax

)12

Ψ(x)−1

4

(II) hopt(x) ≈(TOL

W

)12

Ψ(x)−1

4

Beweis:

Der Beweis wird nur fur das erste Optimierungsproblem gefuhrt (der zweite

lauft entsprechend), da dieses der in der Praxis relevante Fall sein durfte

(optimales Ergebnis bei beschrankten Ressourcen). Fur die Schrittweite in

Abhangigkeit der”Gitterweitenfunktion“ h(x) gilt

N(h) =∑

K∈Th

hK(xK)2hK(xK)−2 ≈∫

Ω

h(x)−2.

Das Lagrangefunktional zum Optimierungsproblem (I) ist

L(h, λ) = E(h) + λ(N(h) −Nmax),

mit der Ableitung

L′[ϕ, λ] =

( ∫Ωϕ(x) (2h(x)Ψ(x) − 2λh(x)−3) dx

µ(∫

Ωh(x)−2 −Nmax dx

))T

.

Im stationaren Punkt (L′ = 0) ergibt sich fur alle Variationen von ϕ und µ:

h(x)Ψ(x) − λh(x)−3 = 0,

∫

Ω

h(x)−2 dx −Nmax = 0.

25

Folglich gilt:

h(x) =

(λ

Ψ(x)

) 1

4

, Nmax =

(1

λ

) 12∫

Ω

Ψ(x)12 dx .

Mit

λ =W 2

N2max

folgt schließlich die optimale Gitterfunktion:

hopt(x) = λ1

4 Ψ(x)−1

4 .

Eine Verfeinerungsstrategie mit dieser Formel ware etwa:

• Verfeinere Zelle K, wenn hopt(xK) < 12hK

• Vergrobere Zelle K, wenn hopt(xK) > 2hK

Diese Strategie entspricht der Error Balancing Strategie, mit einer speziell

gewahlten Toleranz. Die Optimierungsformel birgt einige Probleme:

• Es ist nicht sichergestellt, daß zu der Gitterweitenfunktion hopt(x) auch

ein entsprechendes Gitter gehort. Fur eine Strategie, wie gerade ge-

nannt, ist die Formel jedoch anwendbar.

• Die gitterunabhangigen Grenzwerte (2.17) und (2.18) mussen existie-

ren, damit sich der Fehlerschatzer in der Form (2.19) schreiben laßt.

Diese Bedingung liegt z.B. schon dann nicht vor, wenn der Fehler in

einem Punkt ausgewertet wird. Die duale Losung ist dann die loga-

rithmische Green’sche Funktion, deren zweiten Ableitungen sich wie

1/r2 verhalten, wenn r der Abstand zum Auswertungspunkt ist. Das

Integral in (2.19) existiert dann nur, wenn die zweiten Ableitungen der

primale Losung ∂αu, |α| = 2 im Auswertungspunkt verschwinden.

• Die Gitterformel liefert als Gitterweitenverteilung eine zellweise kon-

stante Funktion. Diese Funktion beschreibt nur die optimale Gitter-

weite unter den bekannten Informationen und in der Klasse der Gitter,

deren Zellen auf dem Gebiet der ursprunglichen Zellen gleich groß sind.

26

5) Optimales Gitter:

Es wird versucht, das Produkt aus Fehler und Anzahl der Zellen zu mi-

nimieren. Dieses Produkt kann als eine Art Qualitatsindex fur das Gitter

herangezogen werden und wird als der Gitterindex definiert:

Definition 1 (Gitterindex) Ein Gitter bestehe aus N Zellen und die Lo-

sung auf diesem Gitter habe den Fehler j(e). Hat das Verfahren die Konver-

genzordnung O(N−α), so heißt

IG = Nαj(e)

der Gitterindex und mißt die Qualitat des Gitters fur das entsprechende Pro-

blem.

Bei der Verwendung von bilinearen Finiten Elementen ist α als 1 zu wahlen,

wenn u und z hinreichend regular sind. Die Fehlerindikatoren werden zunachst

wieder absteigend sortiert

η1 ≥ η2 ≥ · · · ≥ ηN ,

und es sollen die ersten m Zellen, also die mit den großten Fehlerindikatoren

verfeinert werden. Der Fehler, der bei Verfeinerung von m Zellen im neuen

Gitter zu erwarten ist, wird mit E(m), die Anzahl der Zellen im neuen Gitter

mit N(m) bezeichnet.

min [N(m)E(m)] , 1 ≤ m ≤ N.

N(m) = n + 3m.

Dann wird folgendes Optimierungsproblem gelost:

E(m) =

N∑

i=1

ηi − (1 − 14)

m∑

i=1

ηi.

Auch wenn dieses Problem analytisch nur schwer losbar ist, konnen alle

Moglichkeiten getestet werden. So entsteht ein O(n · log n) Algorithmus, der

stets das optimale Gitter (im Sinne von Definition 1) erzeugt.

27

In der Anwendung sind keine großen Unterschiede zwischen den Verfahren

1) bis 5) festzustellen. Der große Nachteil der Fixed Fraction und Fixed Num-

ber Methode ist die Wahl der Parameter. Es kann nicht gesteuert werden,

wieviele Zellen verfeinert werden mussen. Alle anderen Verfahren bestimmen

diese Zahl selbst, und verhindern vor allem, daß zu viel verfeinert wird.

Die Optimierungsformel liefert auch neue Erkenntnisse. Sind die – git-

terunabhangigen – Werte der Funktion Ψ(x) ausgeglichen, so liegt bei Ver-

wendung bilinearer FE-Raume immer eine Konvergenz der Ordnung TOL ∼N−1

max vor. Um den Fehler zu reduzieren, muß dann stets global verfeinert

werden. Dieses wird nun an zwei Beispielen illustriert.

Beispiel 2.2 (Globale Verfeinerung bei aquilibrierten Gittern)

Gerechnet wird wieder das Modellproblem (2.1). Es wird solange mit der Op-

timierungsformel verfeinert, bis die Fehlerindikatoren aquilibriert sind. Eine

Aquilibrierung ist erreicht, wenn ein bestimmter Anteil α der Fehlerindika-

toren nahe am Mittelwert uber alle Fehlerindikatoren liegt:

aquilibriert, wenn∑

K∈Th

αK ≥ αN.

aK =

1 1

2η ≤ ηK ≤ 2η

0 sonst,

η =1

N

∑

K∈Th

ηK .

Danach wird stets global verfeinert. Die rechte Seite wird zu zwei vorgege-

benen Losungen bestimmt:

u1(x, y) = (1 − x2)(1 − y2) sin(4x) sin(6y),

u2(x, y) = (1 − x2)(1 − y2)

√√x2 + y2 + y.

u2 hat im Nullpunkt eine Singularitat in der Ableitung. Im ersten Fall,

(Losung ohne Singularitat) wird das erhoffte Ergebnis erreicht: bei globa-

ler Verfeinerung bleibt eine Konvergenz der Ordnung N−1. Bei u2 liegt bei

globaler Verfeinerung lediglich eine Konvergenz der Ordnung O(N−1/2) vor.

Hier laßt sich der Fehler jedoch auch nicht in der Form (2.19) schreiben. Das

28

1e-05

0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000 1e+06

j(e)

DOFs

lokale VerfeinerungGlobale Verfeinerung

0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)

DOFs

lokale VerfeinerungGlobale Verfeinerung

Abbildung 2.3: Globale Verfeinerung, sobald die Fehlerindikatoren aquili-

briert sind; oben: glatte Losung; unten: Losung mit Singularitat.

29

Freiheitsgrade IG bei η2K IG bei η3

K

81 34.73 34.73

140 21.24 19.98

800 9.45 7.74

4000 3.01 3.06

8700 2.01 1.95

20000 1.354 1.452

50000 0.874 1.268

80000 0.787 0.960

Tabelle 2.2: Gitterindex bei beiden Fehlerindikatoren

Integral uber die Ableitungen von u und z ist nicht endlich. Abbildung 2.3

zeigt die Ergebnisse.

Mit den beschriebenen Adaptionsstrategien kann jetzt die Qualitat der

Fehlerindikatoren uberpruft werden. A-priori gibt es kein Maß fur die Qua-

litat eines Fehlerindikators. Eine Bewertung kann nur anhand des erzeugten

Gitters erfolgen. Hierzu wird ein numerisches Beispiel gerechnet.

Beispiel 2.3 (Qualitat von Fehlerindikatoren) Wieder wird das Modell-

problem (2.1) gelost. Das Fehlerfunktional ist j2, der Punktfehler. Die Gitter

werden mit der”Optimales Gitter“-Strategie erzeugt. Die Qualitat der Feh-

lerindikatoren wird am erzeugten Gitter gemessen. Hierzu wird der Gitterin-

dex (Definition 1) herangezogen. Als Fehlerindikatoren dienen die lokalen

Absolutwerte der Fehlerschatzer η2 und η3 (2.11, 2.12) aus Abschnitt 2.2:

η2K = h3

K

(‖f‖K + 1

2h−

12

K ‖[∂nuh]‖∂k

) ∣∣∣∇2hzh

∣∣∣

η3K =

∣∣(f, z∗h − zh)K − 12〈[∂nuh] , z

∗h − zh〉∂K

∣∣ .In Tabelle 2.3 sind die Gitterindizes fur beide Sequenzen von Gittern auf-

getragen. Auch wenn die Unterschiede nicht groß sind, erzeugen die Fehler-

indikatoren η2K deutlich bessere Gitter. Der sehr ungenaue Fehlerschatzer η2

laßt sich gut als Fehlerindikator verwenden und der Gitterindex liegt um 20%

niedriger, die Gitter sind um 20% effizienter.

30

Kapitel 3

Optimierung der

Funktionalauswertung

Ist man an dem Wert des Fehlerfunktionals j(u) interessiert, so kann der Feh-

lerschatzer verwendet werden, um einen genaueren Wert fur das Funktional

zu erhalten. Es gilt

j(u) = j(uh) + (∇e,∇z)

Ware es moglich den Fehlerterm (∇e,∇z) exakt zu bestimmen, so konnte

auch das Funktional exakt ausgewertet werden. (Unabhangig von der Appro-

ximation von uh). Die Genauigkeit der dualen Losung kann also verwendet

werden, um das Funktional mit hoher Genauigkeit zu bestimmen. Im folgen-

den werden verschiedene Verfahren vorgestellt, den Fehler (∇e,∇z) durch

einen Fehlerschatzer η zu ersetzten und mit

j(u) = j(uh) + η

einen besseren Wert fur das Funktional zu erhalten, als er mit j(uh) vorliegt.

Auch ohne die primale Losung zu rechnen, konnte der Wert des Funktionals

exakt ermittelt werden, wenn die kontinuierliche duale Losung vorliegt. Denn

fur uh = 0 gilt:

j(u) = j(0) + (∇e,∇z) = (f, z).

Alle Informationen uber den Wert des Fehlerfunktionals lassen sich auch aus

der rechten Seite f und der dualen Losung z gewinnen. Insbesondere kann

31

die Genauigkeit des bereits vorgestellten Fehlerschatzers verwendet werden,

um einen besseren Schatzwert fur das Fehlerfunktional zu erhalten. Der Term

(∇e,∇z) wird also durch den auswertbaren Fehlerschatzer η ersetzt (2.12),

der mit der hochsten Genauigkeit vorliegt. Als erste Moglichkeit fur einen im

Vergleich zu j(uh) verbesserten Funktionalwert j1(uh) ergibt sich:

j1(uh) := j(uh) + (f, z∗h) − (∇uh,∇z∗h) , (3.1)

und fur den Fehler j(u) − j1(uh)

j(u) − j1(uh) = (∇(u− uh),∇z) − (∇(u− uh),∇z∗h)= (∇(u− uh),∇(z − z∗h)) .

(3.2)

Die Verbesserung zum ursprunglichen Fehler (Vergleiche 2.8) besteht in der

Verwendung der patchweisen Interpolierten z∗h. Eine Verbesserung der Kon-

vergenz ist schwer vorhersagbar, da es fur den Term (z−z∗h) keine verlaßliche

Interpolationsabschatzung gibt. Es existiert kein Fehlerschatzer fur j(u) −j(uh) auf der Basis von uh, zh und z∗h. Wendet man auf (3.2) die Cauchy-

Schwarz Ungleichung an, so erhalt man

∣∣j(u) − j(uh)∣∣ ≤ ‖∇(u− uh)‖ ‖∇(z − z∗h)‖ , (3.3)

den Fehler in u und einen modifizierten Fehler in z in der Energienorm.

Nun konnte man versuchen, fur beide Energiefehler ein”optimales Gitter“ zu

erzeugen. Da von der dualen Losung z nur ein zh ∈ Vh, also nur eine Funktion

aus dem primalen Testraum abgezogen werden darf, ist es nicht ohne weiteres

moglich, fur das duale Problem ein”optimales Gitter“ zu verwenden.

Der Fehlerschatzer muß in einer Form geschrieben werden, die es erlaubt,

von z Funktionen aus getrennten Ansatzraumen abzuziehen. Hierzu wird ein

modifiziertes Funktional j(uh) eingefuhrt, mit

j(u) − j(uh) = (∇(u− uh),∇(z − zD))

⇔ j(uh) := j(uh) + (f, zD) − (∇uh,∇zD)(3.4)

wobei zD ∈ VD aus einem eigenen Ansatzraum stammt, also auf einem un-

abhangigen Gitter berechnet werden kann; es gilt nicht notwendig VD ⊃ Vh.

32

Eine (3.1) entsprechende Darstellung fur eine weitere Moglichkeit der Funk-

tionalauswertung j2(u) erhalt man sofort durch

j(u) = j(uh) + j(e) = j(uh) + [j(u) − j(uh)] + j(uh) − j(uh)

= (∇(u− uh),∇(z − zD)) + j(uh) + (f, zD) − (∇uh,∇zD)

≈ (∇(u− uh),∇(z∗ − zD)) + j(uh) + (f, zD) − (∇uh,∇zD)

⇒ j2(uh) := j(uh) + (f, z∗D) − (∇uh,∇z∗D) .

Dabei ist z∗D wieder die patchweise Interpolierte von zD auf einem Patch. Fur

den Fehler j(u) − j2(u) gilt dann:

j(u) − j2(uh) = (f, z) − j(uh) − (f, z∗D) + (∇uh,∇z∗D)

= (f, z − z∗D) − (∇uh,∇(z − z∗D))

= (∇(u− uh),∇(z − z∗D))

≤ ‖∇ (u− uh)‖ ‖∇ (z − z∗D)‖ .

(3.5)

Wieder erhalt man zwei Energiefehler. Diesmal ist es moglich, die Gitter von

u und z getrennt zu optimieren. Zur weiteren Verbesserung des Funktional-

werts kann auch noch die diskrete primale Losung uh durch die biquadrati-

sche Interpolierte u∗h ersetzt werden. Es ist zu erwarten, daß diese eine bessere

Naherung fur u darstellt:

j3(u) = j(u∗h) + (f, z∗D) − (∇u∗h,∇z∗D) .

Fur samtliche hier vorgestellte Methoden existiert nun kein Fehlerschatzer

mehr. Es ist aber stets∣∣j(u) − j(uh)

∣∣ ≤ |j(u) − j(uh)| zu erwarten, da die

patchweise Interpolierte eine bessere Approximation ist und z auf einem ge-

trennten Gitter berechnet wurde. In Beispiel (3.1) wird der Effekt der ver-

schiedenen Methoden zur Auswertung des Funktionals verglichen. Da eine ex-

akte Losung vorgegeben sein wird, kann der Fehler auch ohne Fehlerschatzer

genau bestimmt werden. Dieses gibt zumindestens Anhaltspunkte fur die

Anwendung der Methode auf andere Probleme:

Beispiel 3.1 (Auswertung des Funktionals) Gelost wird das Modellpro-

blem (2.1). Das Fehlerfunktional und die rechte Seite werden so gewahlt, daß

33

primale und duale Losung große zweite Ableitungen in unterschiedlichen Ge-

bieten haben: (Abbildung 3.1)

u(x, y) =(1 − x2)(1 − y2) exp

(− 1

x4

)

j(ϕ) =

∫ 1

−1

ϕ(x, 0) dx .

Die Gitter des primalen und dualen Problems werden getrennt gefuhrt und

verfeinert. Zur Verfeinerung der Gitter wird stets ein Energiefehlerschatzer

verwendet. Ziel ist es, den Fehler in Bezug auf NP +ND, die Summe der Frei-

heitsgrade des primalen und dualen Gitters, zu minimieren. Dieser Wert steht

fur den Aufwand der numerischen Losung. Verfeinert wird stets das Gitter,

welches weniger Freiheitsgrade hat. Zur Auswertung des Fehlerfunktionals

werden vier Methoden verwendet:

O j(uh),

I j1(uh) = j(uh) + (f, zD) − (∇uh,∇zD) ,

II j2(uh) = j(uh) + (f, z∗D) − (∇uh,∇z∗D) ,

III j3(uh) = j(u∗h) + (f, z∗D) − (∇u∗h,∇z∗D) .

In Abbildung 3.2 ist der Fehler gegen die Summe der Freiheitsgrade beider

Gitter aufgetragen. Methode I bringt bei der Auswertung keine wesentlichen

Vorteile gegenuber dem Standartvorgehen O. Bei den anderen beiden Me-

thoden II und III liegt jedoch eine Konvergenz der Ordnung N−2 in Bezug

auf die Summe der Zahl der Freiheitsgrade aus beiden Gittern vor.

Der a-posteriori Fehlerschatzer konnte bisher fur die Erzeugung von ef-

fizienten Gittern verwendet werden, da die Residuen und die Gewichte ge-

meinsam und lokal den Fehler bestimmen. Hier wird die Cauchy-Schwarz

Ungleichung verwendet und die Gitter werden getrennt verfeinert. An den

Stellen, an denen z glatt ist, mußte das primale Gitter nicht verfeinert wer-

den. Gleiches gilt entsprechend fur das duale Gitter. Diese Auswertung des

Funktionals beruht auf getrennten Gittern fur u und z. Beispiele haben ge-

zeigt, daß die Ergebnisse nicht so gut sind, wenn zur Verfeinerung des pri-

malen Gitters die ublichen Fehlerindikatoren verwendet werden.

34

Nprim Ndual Nprim + Ndual j(e) j1(e) j2(e) j3(e)

81 81 162 0.441 0.438 0.134 0.117

289 81 370 0.105 0.105 0.035 0.00124

289 189 478 0.105 0.015 0.015 0.00338

289 401 690 0.105 0.032 0.0032 0.00093

665 401 1066 0.026 0.026 0.00098 0.00054

665 921 1568 0.026 0.0103 0.00024 0.00025

2333 921 3254 0.0065 0.0065 7.97 · 10−5 2.05 · 10−6

2333 1953 4286 0.0065 0.0036 1.01 · 10−4 3.11 · 10−5

2333 5329 7662 0.0065 0.0019 3.04 · 10−5 3.55 · 10−5

6945 5329 12274 0.0016 0.0011 2.47 · 10−5 2.08 · 10−6

6945 8661 15606 0.0016 0.0010 9.80 · 10−6 2.18 · 10−6

23805 8661 32466 0.00038 0.00030 4.07 · 10−6 8.44 · 10−7

23805 23701 47506 0.00038 0.00025 2.17 · 10−6 2.69 · 10−7

Tabelle 3.1: Freiheitsgrade des primalen und dualen Gitters und Wert des

Fehlerfunktionals bei allen Methoden der Auswertung von Beispiel 3.1.

Eine weitere Anwendung dieser Methode ist die Moglichkeit, den Fehler

zu reduzieren, ohne uber eine genaue Approximation der primalen Losung

zu verfugen. Angenommen, zu verschiedenen rechten Seiten muß stets der

Wert der Losung in einem Punkt bestimmt werden. Dann reicht es eine gute

duale Losung zu berechnen und, zu jeder rechten Seite, die primale Losung

uh nur auf einem Grobgitter zu bestimmen. Das Fehlerfunktional kann dann

wie gerade beschrieben als

j(uh) = j(uh) + (f, z∗D) − (∇uh,∇z∗D)

ausgewertet werden. Ist z∗D einmal berechnet, so kann zu jedem f der Wert

j(uh) uber eine Residuumsberechnung bestimmt werden.

35

Primale Loesung

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

-0.0050

0.0050.01

0.0150.02

0.0250.03

0.0350.04

0.045

z

Duale Loesung

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

z

Abbildung 3.1: Losung des primalen und dualen Problems zu Beispiel 3.1.

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

100 1000 10000 100000

j~(e

)

N_primal+N_dual

OIIIIII

Abbildung 3.2: Die Fehler bei den verschiedenen Auswertungsmoglichkeiten

des Funktionals bei Beispiel 3.1. O: j(uh), I: j(uh) + (f, zD) − (∇uh,∇zD),

II: j(uh) + (f, z∗D) − (∇uh,∇z∗D), III: j(u∗h) + (f, z∗D) − (∇u∗h,∇z∗D)

36

Kapitel 4

Optimale Gittererzeugung

Die bisher vorgestellten Verfahren haben den Nachteil, daß in jedem Ver-

feinerungsschritt jede Zelle hochstens einmal in vier neue Zellen aufgeteilt

werden kann. Der Reduktion des Fehlers pro Verfeinerungsschritt sind Gren-

zen gesetzt. Nach dem Verfeinern mussen das primale und das duale Problem

erneut gerechnet werden.

Die Gitteroptimierungsformel liefert zusatzliche Informationen, die ver-

wendet werden konnten, um sofort ein sehr viel feineres Gitter zu erzeugen.

Neben der Entscheidung, ob eine Zelle zu verfeinern ist, kann eine optimale

Gitterweite fur diese Zelle angegeben werden. Es ware moglich, sofort ein

Gitter zu erzeugen, das dem Problem optimal angepaßt ist. Hierzu mußte in

jedem Schritt sofort mehrfach verfeinert werden.

Dieses Verfahren ist auf alle oben genannten Adaptionsstrategien anwend-

bar. Ich orientiere mich am Error Balancing : Eine Zelle K wird verfeinert,

wenn ηK > tol der zellweisen Fehlertoleranz ist. Diese Zelle wird in vier neue

Zellen K1, . . . , K4 geteilt. Ware bekannt, wie sich der Fehler entwickelt und

wie groß er auf den neuen Zellen K1 bis K4 ware, so konnten diese Zellen

noch einmal verfeinert werden. Es mussen Fehlerindikatoren ηKibestimmt

werden, die den Fehler auf diesen neuen Zellen angeben.

37

4.1 Mehrfache Verfeinerung einer Zelle

Die Entwicklung des Fehlerindikators ηK auf die Kinder K ′ der Zelle K nahe-

rungsweise berechnet werden. Fur die Darstellung des Fehlerindikators auf

K gilt dann mit (2.11) zunachst:

ηK ≤(‖f‖K + 1

2h−

12


)h3

K

∣∣∇2hz(xK)

∣∣

≈ h4K

(∣∣∣f(xK)∣∣∣+∣∣∣∇2

hu(xK)∣∣∣) ∣∣∣∇2

hz(xK)∣∣∣ .

Dabei sind hK |f(xK)|, hK |∇2hz(xK)|, hK |∇2

hu(xK)| geeignete Approximatio-

nen der Normen auf der Zelle K und es wird angenommen, daß sich die

Sprunge uber die Normalableitungen wie die zweiten Ableitungen von u ver-

halten.

Auf diese Weise liegt ein Fehlerindikator vor, in dem nur die Gitterweite

hK als gitterabhangige Große eingeht. Der Fehler auf einer Zelle K kann

auch auf verfeinerte Zellen K ′ ⊂ K ubertragen werden. Angenommen: K ′

sei direktes Kind der Zelle K, also durch einfache Verfeinerung entstanden.

Dann ist hK ′ = 12hK . Damit gilt fur den Fehler auf K ′:

ηK ′ = h4K ′

(∣∣∣f(xK ′)∣∣∣+∣∣∣∇2u(xK ′)

∣∣∣) ∣∣∣∇2

hz(xK ′)∣∣∣

≈ h4K

16

(∣∣∣f(xK)∣∣∣+∣∣∣∇2u(xK)

∣∣∣) ∣∣∣∇2

hz(xK)∣∣∣

=ηK

16

Diese Rechnung gilt entsprechend fur weitere Kinder der neuen Zelle K ′.

Nach n-facher Verfeinerung gilt also fur eine Kn – ein n-tes Kind von K –

mit Zellweite hKn= 2−nhK naherungsweise fur den Fehler ηKn

:

ηKn≈ ηK

16n

Wird eine Zelle n mal verfeinert, so entstehen 4n neue Zellen. Die Sum-

me der Fehlerindikatoren auf diesen Zellen muß die vorgegebene, zellweise

Toleranz tol erreichen:

tol = 4n · ηK

16n=ηK

4n

⇔ nK = log4

ηK

tol

(4.1)

38

Verfeinert man die Zellen K jeweils nK mal, so ergeben sich folgende Proble-

me:

1) Die zweiten Ableitungen von u und z mussen existieren. Dieses wurde aber

generell eine Konvergenz der Ordnung h2 bedeuten. Enthalt das Funktional

jedoch Ableitungen von u, so liegt diese Konvergenzordnung schon nicht mehr

vor. Es stellt sich dann das Problem, daß keine globale Konvergenzaussage

mehr getroffen werden kann.

2) Es ist zu erwarten, daß diese Verfeinerungsstrategie zu sehr schlechten

Gittern fuhrt. Angenommen, die Ableitung in einem Punkt soll minimiert

werden. Der Fehlerindikator wird in allen Zellen, die diesen Punkt beruhren,

sehr groß sein und mehrmalige Verfeinerung vorschlagen. Nach dem ersten

Verfeinern kann nicht zwischen Fehlerindikatoren auf den neuen Zellen un-

terschieden werden, alle Zellen mussen wieder verfeinert werden. Die Verfei-

nerung wird auf Patchen durchgefuhrt und zu viele Zellen werden beruck-

sichtigt. Es werden entweder alle Kinder verfeinert oder keines. Das Gitter

ist dem Problem nicht entsprechend angepaßt und es werden weit mehr Zel-

len benotigt um einen bestimmten Fehler zu erreichen, als wenn das Gitter

langsam verfeinert wurde. Hierzu ein

Beispiel 4.1 (Gitter bei mehrfacher Verfeinerung) Es wird erneut das

Problem von Beispiel 2.1 gelost. Als Fehlerfunktional wird diesmal nur der

Mittelwert uber einen Teil des Gebiets betrachtet:

j(ϕ) =1

|W|

∫

W

ϕ, W =[−1

2, 0]×[0, 1

2

].

Die Gitter werden auf zwei Arten adaptiert:

Strategie 1 Nach der Berechnung des dualen und des primalen Problems

wird das Gitter nach der”Error Balancing“ Strategie verfeinert. Es

werden alle Zellen des Gitters verfeinert, deren Fehlerindikatoren uber

einem Schwellenwert liegen. Dann werden primales und duales Problem

erneut berechnet.

Strategie 2 Nach der Berechnung des primalen und dualen Problems wer-

den wie in (4.1) alle Zellen so oft verfeinert, bis (bei geschatzter Kon-

39

0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000 1e+06

j(e)

DOFs

Strategie IIStrategie I

Abbildung 4.1: Anzahl der Freiheitsgrade und Fehler zum Erreichen der Ge-

nauigkeit von j(e) ≤ 2 · 10−6 bei Strategie I und Strategie II (mehrfache

Verfeinerung der Zellen)

vergenz zweiter Ordnung) die Fehlerindikatoren aquilibriert sind und

ein Schwellenwert erreicht ist. Der Schwellenwert wird in jedem Schritt

der Rechnung neu bestimmt.

Abbildung 4.1 zeigt den Fehler j(e) in Abhangigkeit von der Anzahl der Frei-

heitsgrade (DOFs). Die Anzahl der Gitterpunkte zum Erreichen des gleichen

Fehlers steigt bei mehrfacher Verfeinerung (Strategie II) sehr stark. Das Git-

ter ist nicht optimal an das Problem und das Fehlerfunktional angepaßt, und

es wird offensichtlich nicht optimal verfeinert.

Dieses Beispiel zeigt deutlich, daß nicht genugend Informationen vorlie-

gen, um ein”optimales Gitter“ zu erzeugen. Die Anzahl der Zellen steigt

exponentiell mit der Zahl der Verfeinerungen pro Schritt. Mehrfache Verfei-

nerung ohne das Problem erneut zu rechnen kann nur erfolgreich sein, wenn

genauere Fehlerindikatoren fur die Kinder einer Zelle vorliegen. Ohne Ent-

scheidungskriterien zur Verfeinerung von Kindern – von Zellen auf denen der

Fehlerschatzer nicht berechnet werden kann – wird die Strategie nicht zu

guten Gittern fuhren. Der Rechenaufwand wird zu groß und es kann trotz

schneller Verfeinerung keine Zeitersparnis erzielt werden. Hier zeigt sich auch

das Problem bei der Verwendung der Optimierungsformel (Satz 2.3). Es wird

40

zwar eine Gitterweitenfunktion bestimmt, diese aber ist auf dem Gebiet einer

Zelle des groben Gitters stets konstant. Die Optimierung beschrankt sich auf

die Klasse der Gitter, die auf Patchen konstante Zellgroße hat. Das Ergebnis

kann also nicht ein optimales Gitter sein. Liegt z.B. ein Auswertungspunkt

in einer Zelle, so wird die Gitterweitenfunktion sehr kleine neue Zellen auf

dem Gebiet dieser Zelle vorschlagen. Diese kleine Gitterweite wird jedoch

nur in unmittelbarer Nahe des Auswertungspunkts benotigt. Die Daten lie-

gen fur die Optimierungsformel nicht in hinreichender Genauigkeit vor, um

ein wirklich optimales Gitter zu erzeugen.

Eine Moglichkeit, um dieses Problem zu beheben, ist, das duale Problem

genauer zu rechnen. Die Gewichte (2.13) im Fehlerschatzer konnen dann mit

hoherer Genauigkeit ermittelt werden und die Verfeinerung kann gezielter

erfolgen. So wurde der Aufwand fur die Berechnung des primalen Problems

gespart. Alternativ konnte auch das duale Problem festgehalten, und das

primale weiter gerechnet werden. Im nachsten Kapitel wird ein Verfahren

vorgeschlagen, um genaue Informationen uber den Fehlerschatzer zu erhalten,

die verwendet werden konnen, sehr schnell gute Gitter zu erzeugen.

4.2 Erhohte Genauigkeit im dualen Problem

Wenn die Residuen und Gewichte im Fehlerschatzer als kontinuierliche Funk-

tion vorliegen wurden, so konnte mit der Gitteroptimierungsformel (Satz 2.3)

in einem Schritt ein”optimales Gitter“ erzeugt werden. Die bisherigen Ver-

suche, eine Zelle sofort mehrfach zu verfeinern, schlagen wegen der nicht vor-

handenen Information uber die Fehlerverteilung innerhalb einer Zelle fehl.

Die Genauigkeit des Fehlerschatzers soll nun durch eine bessere Approxima-

tion der dualen Losung erhoht werden. Das duale Problem erhalt hierzu ein

separates Gitter Dh und dieses wird solange verfeinert (D(1)h ,D(2)

h , . . . ,D(m)h ),

bis der Wert des Fehlerschatzers konvergiert. Der Fehlerschatzer wird jetzt

stets in Abhangigkeit von zwei Eingabewerten fur die primale und duale

41

Losung geschrieben:

η(uh, zD) =∑

K∈Th

ηK(uh, zD),

ηK(uh, zD) = ‖f‖K ‖z − zD‖K + 12‖[∂nuh]‖∂K ‖z − zD‖∂K .

(4.2)

Dabei liegt uh in Vh(Th), dem Finite-Elemente Raum auf einem primalen

Gitter Th, und zD ∈ Vh(Dh) auf einem dualen Gitter.

Erst wenn dieser Fehlerschatzer nahe genug am optimalen Wert η(uh, zD) →η(uh, z), dem Fehlerschatzer mit der kontinuierlichen dualen Losung liegt,

wird mit diesem genauen Fehlerschatzer ein neues primales Gitter erzeugt.

Jetzt sollten genug Informationen vorliegen, um in einem Schritt ein sehr

feines Gitter erzeugen zu konnen. Das duale Problem muß zwar – wie bei der

ublichen, schrittweisen Gitterverfeinerung – mehrfach gerechnet werden, der

Aufwand fur das primale Problem ist jedoch reduziert.

4.2.1 Der Algorithmus mit zwei Gittern

Man geht von einer vorgegebenen Toleranz TOL aus, die im Fehlerfunktional

j(e) erreicht werden soll. Fur die Berechnung des dualen Problems wird eine

weitere Fehlertoleranz γD benotigt. Sie gibt die Genauigkeit an, die fur den

Fehlerschatzer erwartet wird: |η(uh, z) − η(uh, zD)| ≤ γD. Starttriangulatio-

nen Th und D1h sind gegeben.

1. Berechne uh auf Th.

2. Setze j = 1

(a) Berechne zj auf Djh

(b) Berechne den Fehlerschatzer ηj aus u und zj

(c) Wenn der Fehlerschatzer nicht genau genug ist

(|η(uh, z) − η(uh, zD)| > γD), erzeuge das Gitter

Dj+1h aus Dj

h und gehe zu (2a) mit j := j + 1

42

3. Wenn η > TOL, berechne die Fehlerindikatoren und erzeuge

neues Gitter T (∗)h fur das primale Problem. Weiter bei 1

mit diesem Gitter -- ansonsten Abbruch.

Das primale Problem muß bei diesem Vorgehen nur selten gerechnet wer-

den. Durch die hohe Genauigkeit des Fehlerschatzers ist zu erwarten, daß die

Gitter effektiv sind, die Verfeinerung auf das Problem und das Fehlerfunktio-

nal optimal abgestimmt ist. Im folgenden werden die einzelnen Schritte im

Algorithmus erklart.

4.2.2 Auswertung des Fehlerschatzers

Ziel ist es jetzt, eine Form des Fehlerschatzers zu finden, in der primales und

duales Problem unterschiedliche Triangulationen haben. Um die optimale

Genauigkeit fur den Fehlerschatzer zu erhalten, wird die duale Losung z

durch die patchweise Interpolierte z∗j der diskreten dualen Losung zj auf dem

dualen Gitter ersetzt. Die Fehleridentitat kann dann ausgewertet werden als:

ηj =∑

K∈Th

(f, z∗j − ihz∗j )K −

(∇uh,∇(z∗j − ihz

∗j ))

K. (4.3)

Dabei ist ih die Interpolation in den primalen Testraum Vh. Die Interpolierte

ihz∗j kann in der Auswertung des Fehlerschatzers wegen der Galerkinortho-

gonalitat naturlich weggelassen werden.

Die Auswertung des Fehlerschatzers ist mit hohem Aufwand verbunden,

da Funktionen aus unterschiedlichen Raumen in einem Skalarprodukt inte-

griert werden mussen. Bei der Implementation ist es notwendig, die primale

Losung uh und die patchweise Interpolierte z∗j der dualen Losung zunachst in

einen gemeinsamen Funktionenraum zu interpolieren, der beide Ansatzraume

enthalt.

4.2.3 Auswertung der Fehlerindikatoren

Um die genaueren Informationen uber die duale Losung nutzen zu konnen,

mussen die Fehlerindikatoren, die bisher nur auf den Zellen des primalen Git-

ters vorliegen, auf beliebigen Verfeinerungen von primalen Zellen auswertbar

43

sein. Zusatzlich muß berucksichtigt werden, daß die Gewichte auf einem ge-

trennten Gitter vorliegen. Es sollen Fehlerindikatoren, wie (2.11) hergeleitet

werden, da diese die besten Ergebnisse lieferten. Der typische Fall wird sein,

daß die Residuen auf Zellen P ∈ Th des primalen Gitters vorliegen. Die

Gewichte liegen auf den Zellen D ∈ Dh des dualen Gitters vor und die Feh-

lerindikatoren mussen auf Zellen K ⊂ P ∈ Th ausgewertet werden, die Ver-

feinerungen von primalen Zellen sind. Hierzu ist es notwendig, die Residuen

und Gewichte der Fehlerindikatoren unabhangig von h-Potenzen anzugeben.

Die Residuen und Gewichte mussen gegen einen gitterunabhangigen Wert

konvergieren.

Bei den Gewichten sind die Potenzen der Gitterweite bereits separiert

(2.11). Fur die Residuen gilt:

ρ(1)K + ρ

(2)K = ‖f‖K + 1

2h−

12


= hK

(h−1

K ‖f‖K + 12h− 3

2


).

Der Ausdruck in den Klammern nimmt eine gitterunabhangige Form an,

wenn an die Regularitat von uh eine Bedingung wie bei der Gitteroptimie-

rungsformel (2.19) gestellt wird:

h−1K ‖f‖K + 1

2h− 3

2

K ‖[∂nuh]‖∂K ≈∣∣∣f(xK)

∣∣∣+ 12

∣∣∣∇2hu(xK)

∣∣∣ .

Der Fehlerschatzer laßt sich nun allgemein auf Zellen K schreiben, wenn die

Daten der Residuen und Gewichte auf primalen Zellen P und dualen Zellen

D vorliegen:

ηK = h4K

(h−1

P ‖f‖P + 12h− 3

2

P ‖[∂nuh]‖∂P

) ∣∣∣∇2hz(xK)

∣∣∣ , (4.4)

wobei K ⊂ P und hK |∇2hz(xK)| eine Approximation von ‖∇2z‖K ist.

4.2.4 Die innere Iteration

In der inneren Iteration des Algorithmus wird das duale Gitter solange ver-

feinert, bis der Fehlerschatzer ηj auskonvergiert ist. In jedem Schritt muß

44

das duale Gitter dem”Fehler im Fehlerschatzer“ angepaßt werden. Hierzu

mußte eigentlich ein weiteres duales Problem zu einem speziellen Funktional

gerechnet werden. Zur Vereinfachung wird aber das duale Gitter mit einem

Energiefehlerschatzer verfeinert.

Als Abbruchskriterium wird die Abweichung zweier aufeinander folgen-

der Schatzwerte |ηi+1 − ηi| benutzt. Wenn diese unter einem Toleranzwert γD

liegt, so ist die duale Losung genau genug. Bei diesem Vorgehen muß sicher-

gestellt werden, daß das duale Gitter in jedem Schritt hinreichend verfeinert

wird. Hat Di+1h die gleiche Anzahl von Zellen wie Di

h, so andert sich auch

der Wert des Fehlerschatzers nicht. Wird aber zur Gitteradaption die”Fixed

Fraction“ oder”Fixed Number“ Methode verwendet, so kann hinreichende

Verfeinerung sichergestellt werden.

4.2.5 Verfeinern des Gitters

Das Verfeinern der primalen Gitters zielt auf aquilibrierte Fehlerindikatoren.

Es wird zunachst ein Toleranzwert vorgegeben. Das Verfeinern geschieht dann

nach folgendem Algorithmus:

Vorgegeben ist maxV , die maximale Anzahl von Verfeinerungsschritten.

Weiter sei err die Summe der Fehlerindikatoren. Diese Summe soll nach

maxV Verfeinerungsschritten einen Toleranzwert erreichen.

Setze T 1h = Th die aktuelle Triangulation und wiederhole fur i =

1, . . . , maxV :

1. Setze TOL < err (Zielwert) und tol = TOL/Ncells (Der Schwel-

lenwert auf jeder Zelle)

2. Fur alle P ∈ T ih:

(a) berechne ηP (wie in 4.4).

(b) Wenn ηP > TOL: Wahle P zum Verfeinern aus.

3. Fuhre Verfeinerungen aus und erzeuge neue Triangulation fur

das primale Problem T ih → T i+1

h .

45

Erfullen z und u die Regularitatsvoraussetzungen der Gitterformel (Satz

2.3), so sollten nach hinreichend vielen Verfeinerungsschritten des primalen

Gitters die Fehlerindikatoren aquilibriert sein und der Algorithmus schlagt

globale Verfeinerung vor.

4.3 Numerische Beispiele

Das Modellproblem (2.1) wird mit unterschiedlichen rechten Seiten und un-

terschiedlichen Fehlerfunktionalen auf dem Quadrat [−1, 1]2 betrachtet. Als

abschließendes Beispiel wird die Poissongleichung auf einem Gebiet mit Schlitz

betrachtet. Hier treten zusatzlich Eckensingularitaten auf. Die rechten Seiten

bestimmen sich stets aus vorgegebenen Losungen:

u1(x, y) = (1 − x2)(1 − y2) sin(4x) sin(6y),

u2(x, y) = (1 − x2)(1 − y2)(1 − x),

u3(x, y) = (1 − x2)(1 − y2)

√√x2 + y2 + y,

u4(x, y) = (1 − x2)(1 − y2) exp

(− 1

x4

).

Die Losung u3 hat Nullrandwerte auf dem Rand und auf dem Schlitz 0 ×[−1, 0] und wird auf einem speziellen Gebiet Ω′ berechnet:

Ω′ = (−1, 1)2\(0 × [1, 0]).

Diese Losung hat in der Ableitung eine Singularitat im Ursprung. Die Vor-

aussetzungen der Gitterformel (Satz 2.3) gelten hier nicht. Das Integral uber

die zweiten Ableitungen von u und z ist nicht endlich. Die betrachteten Feh-

lerfunktionale sind:

j1(ϕ) = ϕ(x0) x0 = (14, 1

4),

j2(ϕ) =

∫

Γ1

∂nϕ dx Γ1 = [−1 × (−1, 1)] ∪ [(−1, 1) × 1],

j3(ϕ) =1

|W|

∫

W

ϕ dx W = (−12, 0) × (0, 1

2),

j4(ϕ) =

∫ 1

−1

ϕ(x, 0) dx .

46

Die beiden Funktionale j1 und j2 liegen nicht in H−1(Ω) und mussen daher

regularisiert werden. (Siehe z.B. [2]). Am Beispiel von j1 bedeutet dies, das

der Punktwert als Mittelwert uber eine Umgebung Bε(x0) des Punktes x0

ausgewertet wird:

j1(ϕ) =1

|Bε(x0)|

∫

Bε(x0)

ϕ(x) dx , Bε(x0) = z ∈ Ω : |z − x0| ≤ ε.

Der Parameter ε muß hinreichend klein gewahlt werden und orientiert sich

an der Fehlertoleranz TOL, so daß der durch die Regularisierung entstehende

Fehler nicht ins Gewicht fallt.

Zu den rechten Seiten und Fehlerfunktionalen werden folgende funf Bei-

spiele gerechnet:

Losung Funktional

Beispiel 4.2 u1 j1

Beispiel 4.3 u2 j2

Beispiel 4.4 u2 j3

Beispiel 4.5 u3 j3

Beispiel 4.6 u4 j4

Die Beispiele wurden so gewahlt, daß moglichst viele Falle abgedeckt werden:

zu rechten Seiten mit unterschiedlichen Regularitatseigenschaften werden

verschiedene Fehlerfuntionale ausgewertet. Bis auf u3 in Beispiel 4.5 liegen

alle Losungen in H2(Ω). Als stark singulares Funktional wird bei Beispiel 4.3

die Normalableitung ausgewertet. Bei diesen beiden Beispielen (4.3, 4.5) sind

die Regularitatsvoraussetzungen der Gitteroptimierungsformel nicht erfullt.

Alle Probleme werden mit zwei unterschiedlichen Strategien gelost:

Strategie 1: Primales und duales Problem werden auf demselben Gitter

berechnet.

Strategie 2: Das duale Problem wird auf einem eigenen Gitter berechnet.

Die Rechnung lauft nach Algorithmus 4.2.1.

47

Die Zellen werden bei beiden Strategien mit der Methode des”Optimalen

Gitters“ zur Verfeinerung ausgewahlt. Die Zellen des dualen Gitters werden

bei Strategie 2 mit der”Fixed-Fraction“ Methode ausgewahlt. Im Algorith-

mus zum Verfeinern des primalen Gitters (4.2.5) wird der Parameter maxV

als drei gewahlt. Auch das duale Problem wird maximal dreimal verfeinert,

bis die Abweichung im Fehlerschatzer (durch eine genauere duale Losung)

unter einem Prozent liegt. (Abschnitt (4.2.4) im Algorithmus). Zu den Bei-

spielen sind die kontinuierlichen Losungen bekannt. Der Fehler kann – bis auf

numerische Integration – stets exakt bestimmt werden. Alle Gleichungssy-

steme werden mit einem SSOR-vorkonditionierten konjugierten Gradienten-

Verfahren (CG-Verfahren) gelost.

In Abbildungen 4.2 bis 4.6 ist der Fehler der Approximation in Abhangig-

keit der benotigten Freiheitsgrade und in Abhangigkeit der CPU-Zeit angege-

ben, die benotigt wurde, einen Toleranzwert zu erreichen. Dabei werden alle

Zwischenrechnungen, die auf groben Gittern durchgefuhrt werden mussen,

mit einbezogen. Weiter wird zu den Beispielen die Anzahl der Zwischengitter

fur das primale Problem angegeben, also die Zahl der durchgefuhrten Rech-

nungen. Zu jedem Beispiel wird ein Gitter angegeben, daß mit Strategie 2

erzeugt wurde.

48

Beispiel 4.2 (Losung u1, Fehlerfunktional j1)

1e-05

0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)/

j(u)

Freiheitsgrade

Strategie 1Strategie 2

1e-05

0.0001

0.001

0.01

0.1

1

0.01 0.1 1 10 100 1000

j(e)/

j(u)

Zeit


Abbildung 4.2: Punktfehler bei glatter Losung.

Strategie 1 Strategie 2

Freiheitsgrade 93000 87000

Zeit 1. 0.45

Rechnungen des primalen Problems 10 4

Rechnungen des dualen Problems 10 9

49


0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)/

j(u)

Freiheitsgrade


0.0001

0.001

0.01

0.1

1

0.01 0.1 1 10 100 1000

j(e)/

j(u)

Zeit


Abbildung 4.3: Integral uber Normalableitung bei glatter rechter Seite.



Zeit 1. 0.56



50


1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

10 100 1000 10000 100000 1e+06

j(e)/

j(u)

Freiheitsgrade


1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

0.01 0.1 1 10 100 1000 10000

j(e)/

j(u)

Zeit


Abbildung 4.4: Mittelwert uber Teil der Losung bei glatter rechter Seite.



Zeit 1. 0.70



51


0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)/

j(u)

Freiheitsgrade


0.0001

0.001

0.01

0.1

1

0.01 0.1 1 10 100 1000

j(e)/

j(u)

Zeit


Abbildung 4.5: Die Losung hat eine Eckensingularitat, der Fehler wird in

einem Punkt ausgewertet.



Zeit 1. 0.49



52


0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)/

j(u)

Freiheitsgrade


0.0001

0.001

0.01

0.1

1

0.01 0.1 1 10 100 1000

j(e)/

j(u)

Zeit


Abbildung 4.6: Das Fehlerfunktional ist ein Linienintegral, die Funktion hat

zwei Stellen mit großen Ableitungen.



Zeit 1. 0.47



53

Die Abbildungen und Tabellen 4.2 bis 4.6 zu den Beispielen 4.2 bis 4.6

zeigen, daß Strategie 2 deutlich uberlegen ist. Es werden meist Zeitersparnisse

von 50% erreicht. Auch die Gitter sind – im Gegensatz zu Beispiel 4.1 – sehr

effizient. Es werden bei Strategie 2 nicht mehr Freiheitsgrade benotigt, um

einen Fehler zu erreichen, als bei der ublichen, schrittweisen Verfeinerung von

Strategie 1. Liegt der duale Fehlerschatzer hinreichend genau vor, so kann

das duale Gitter optimal verfeinert werden.

Unabhangig von der Problemstellung liefert der Algorithmus zur mehrfa-

chen Verfeinerung sehr gute Ergebnisse. Die angegebenen Gitter zeigen, daß

dieses Verfahren auf verschiedenste Probleme angewendet werden kann.

Insgesamt zeigt sich, daß dieses Verfahren erst effektiv ist, wenn primale

und duale Losung große zweite Ableitungen haben. Es hat sich aber auch

schon beim Vergleich der Adaptionsstrategien in Kapitel 2 gezeigt, daß bei

sehr glatten Losungen keine Unterschiede zwischen den Strategien festzu-

stellen sind. In Beispiel 4.4 ist der Zeitgewinn nur sehr gering. Bei diesem

Beispiel sind die Fehlerindikatoren schon nach der ersten Verfeinerung aqui-

libriert; danach wird nur noch global verfeinert.

4.4 Zusammenfassung

Die Strategie zur mehrfachen Verfeinerung ist mit einem hohen technischen

Aufwand verbunden. Es mussen zwei Gitter verwaltet werden, die Losungen

liegen auf beiden Gittern (bei unterschiedlicher Zahl von Freiheitsgraden) vor

und mussen haufig zwischen den Gittern interpoliert werden. Trotz des hoher-

en Aufwands lohnt sich die Gitterstrategie, da insgesamt bei weitem weniger

Losungen berechnet werden mussen. In allen Beispielen war das Verfahren

nach drei oder vier Verfeinerungen am Ziel. Mit der klassischen Strategie

wurde dieses erst nach mindestens doppelt so vielen Schritten erreicht. Da

das Verfahren stets versucht, die Fehlerindikatoren wirklich zu aquilibrieren,

sind die Gitter oft effektiver als bei einfacher Verfeinerung.

Ein Problem der Strategie 2 ist die große Schrittweite bei der Verfeinerung

des Gitters: in Beispiel 4.4 hat das primale Gitter Th ausgehen von 64 Zellen

54

nach nur drei Verfeinerungsschritten mehr als 300.000 Zellen. Das Verfahren

ist schwer zu steuern. Der Parameter maxV kann wahrend der Berechnung

adaptiv gewahlt werden; wenn der derzeitige Wert des Fehlerschatzers schon

nahe an der gewunschten Fehlertoleranz liegt, so muß maxV klein gewahlt

werden. Um die gewunschten Effekte zu erreichen, mußten sehr geringe Feh-

lertoleranzen vorgegeben werden (oft 10−5). Bei nur wenigen Verfeinerungs-

schritten ist Strategie II noch nicht uberlegen.

Auf der Seite der Implementation des Verfahrens ergeben sich insbe-

sondere im Zusammenhang mit der verwendeten Finite-Elemente Software-

Bibliothek deal.II [13, 14] einige Probleme:

• Zwei vollkommen getrennte Gitter mussen verwaltet werden. Der Spei-

cherbedarf ist deutlich hoher. Alle Daten liegen nun verteilt auf zwei

Gittern vor. Da die Gitter lokal verfeinert sein sollen, besteht keine

direkte Verbindung zwischen den Gittern.

• Die Zellen des primalen Gitters mussen oft mit denen im dualen in

Verbindung gebracht werden. Im Fehlerschatzer mussen zu den Zellen

des derzeitigen Gitters entsprechende Zellen aus dem primalen und dem

dualen Gitter gesucht werden, um die Residuen und Gewichte zu ermit-

teln. Der Aufwand fur die Suche nach einer Zelle ist O(M · logN), wenn

M die Zahl der Zellen im Grobgitter ist. Um diesen Faktor verlangert

sich nun die Laufzeit verschiedener Algorithmen (Auswertung des Feh-

lerschatzers und der Fehlerindikatoren).

• Werden fur das duale und primale Problem die gleichen Gitter ver-

wendet, so kann bei diesen einfachen Beispielen fur beide Probleme

die gleiche Besetzungsstruktur der Matrix verwendet werden. Bei zwei

getrennten Gittern sind aber unterschiedlichen Besetzungsstrukturen

notwendig.

Die dargestellte Strategie kann nicht ohne weiteres auf nichtlineare Pro-

bleme ubertragen werden. Sollen diese Probleme mit dem Newton-Verfahren

gelost werden, so muß bei bestimmten nichtlinearen Problemen fur jeden

55

Schritt eine hinreichend gute Startlosung bekannt sein. Unterscheiden sich

die Gitter nicht sehr stark, so ist die Interpolation der alten Losung in das

neue Gitter meist ein guter Startwert. Werden aber die Gitter so stark ver-

feinert wie bei der hier vorgestellten Strategie, so kann gegebenenfalls nicht

mehr mit dem Newton-Verfahren gelost werden. Es mußten Verfahren, mit

geringerer Konvergenzordnung verwendet werden. Diese wurden den mit der

Verfeinerungsstrategie erreichten Vorteil wieder aufheben.

56

Kapitel 5

Remeshing

Die in Kapitel 2 vorgestellte Methode der lokalen Gitterverfeinerung soll nun

mit dem Remeshing verglichen werden. Ausgehend von den Fehlerindikato-

ren muß nun nicht mehr entschieden werden, ob eine Zelle verfeinert wird,

sondern ein komplett neues Gitter muß erzeugt werden. Dabei bleibt die

Struktur des Gitters nicht mehr erhalten.

Bei diesem Verfahren werden in jedem Schritt des Remeshings fur alle

Zellen des derzeitigen Gitters neue Zellweiten berechnet, so daß die Fehler-

indikatoren im neuen Gitter aquilibriert sind. Es ist nicht sichergestellt (und

im Allgemeinen auch nicht zu erwarten), daß zu den gewunschten Zellwei-

ten auch ein Gitter gehort. Gerade bei der Verwendung von Vierecksgittern

sind die Gestaltungsmoglichkeiten begrenzt, da die Triangulation gewissen

Regularitatsbedingungen genugen muß.

Es wurde den Rahmen dieser Arbeit sprengen, naher auf dieses Problem

und allgemein auf die Erzeugung von Gittern einzugehen. Vielmehr wird

in diesem Kapitel versucht, die Ergebnisse des dualen Fehlerschatzer (2.12)

auf die Gittergenerierung zu ubertragen. Weiter wird untersucht, ob es mit

Remeshing besser moglich ist, eine gewunschte Gitterweitenverteilung auf

einem Gitter zu realisieren, als mit hierarchischer Gitterverfeinerung. Die

quantitativen Ergebnisse der Berechnungen spielen hier zunachst keine Rolle.

Grundlegend ist die Vorgabe einer Gitterweitenfunktion. Die Gitteropti-

mierungsformel (Satz 2.3) liefert sofort eine Verteilung der Gitterweiten h(x)

57

und wird als Eingabe fur einen Gittergenerator verwendet.

Alternativ kann – ausgehend von Fehlerindikatoren – ηK und einer an-

genommenen Konvergenzordnung α die optimale Zellweite hopt berechnet

werden: hat die Zelle K die Zellweite hK und soll auf den neuen Zellen der

Fehler tol erreicht werden, so ist hopt fur α = 1 bestimmt als:

hopt =

(tol

ηK

) 1

4

hK .

Bei beiden Moglichkeiten spielen die Konstanten des Fehlerschatzers eine

große Rolle. Das erzeugte Gitter hat zwar aquilibrierte Fehlerindikatoren, je-

doch sind diese mit der – nicht bekannten – Konstante skaliert. Die Anzahl

der Zellen im neuen Gitter wird durch die Konstante beeinflußt und kann

nicht vorhergesagt werden. Eine Moglichkeit, diesem Problem aus dem Weg

zu gehen, ist die gewunschte Anzahl der Zellen im neuen Gitter vorher fest-

zulegen. Ist hopt(x) die optimale Gitterfunktion im Gebiet Ω, so ist die Zahl

der zu erwartenden Zellen im neuen Gitter:

N =

∫

Ω

h−2opt(x) dx .

Wenn die gewunschte Zahl der Zellen als N vorgegeben ist, so muß die Git-

terfunktion skaliert werden durch:

hopt(x) =

√N

N· hopt(x).

Diese Gitterfunktion kann nun an einen Gittergenerator ubergeben werden.

In den folgenden Beispielen wird der Gittergenerator BAMG 1 [9] verwen-

det. BAMG verwendet einen”Quadtree“-Algorithmus (siehe z.B. [8]) und

erzeugt eine Dreiecks-Triangulation. Da die verwendete FE-Bibliothek de-

al.II [13, 14] nur mit Rechtecksgitter rechnen kann, werden die Dreiecksgitter

in Rechtecksgitter transformiert. Bei der Transformation werden Vierecks-

gitter erzeugt, die moglichst starken Regularitatsbedingungen an ihre Form

genugen. Die Transformation erfolgt in zwei Schritten:

1

”Bidemensional Anisotropic Mesh Generator“ von Frederic Hecht.

http://www-rocq.inria.fr/Frederic.Hecht

58

Abbildung 5.1: Die beiden Transformationsschritte von einem Dreiecksgitter

zu einem Vierecksgitter.

1. Zusammenfassen von zwei Dreiecken zu einem Viereck:

Je zwei Dreiecke mit gemeinsamer Seite werden zu einem Viereck zu-

sammengefaßt, wenn fur das Verhaltnis von langster Seite l zu kurzester

Seite k im erzeugten Viereck

1 ≤ l

k≤ 2

und fur alle Innenwinkel αi des erzeugte Vierecks

1

3π ≤ αi ≤

2

3π

gilt. Die neuen Vierecke werden alle einmal global verfeinert.

2. Aufteilen der ubrigen Dreiecke in jeweils drei Vierecke:

Die ubrigen Dreiecke werden in jeweils drei Vierecke aufgeteilt. Hierzu

werden neue Ecken in der Mitte der Seitenlinien des Dreiecks und im

Mittelpunkt des Dreiecks erzeugt.

Auf diese Art entsteht ein Vierecksgitter ohne hangende Knoten. Abbildung

5.1 zeigt den Transformationsprozeß an einem einfachen Beispiel.

5.1 Der adaptive FE-Algorithmus mir”Re-

meshing“

Das adaptive Finite-Elemente Verfahren muß nur bezuglich der Gittersteue-

rung verandert werden. Anstelle der Gitterverfeinerung tritt nun der Gitter-

generator.

59

1. Vorgegeben ist ein Startgitter Th, und eine Toleranz TOL,

die im Fehlerfunktional erreicht werden soll.

2. Berechne uh zur Triangulation Th.

3. Berechne den Fehlerschatzer η und ηK.

4. η < TOL: Abbruch.

5. Berechne aus den Fehlerindikatoren die optimale Gitterfunk-

tion. Passe die Gitterfunktion der gewunschten Anzahl von

Zellen an.

6. Erzeuge mit einem Gittergenerator ein neues Gitter und star-

te mit diesem Gitter ab 2.

In Punkt (5) des Algorithmus muß in jedem Schritt die Anzahl der Zellen

gewahlt werden. Im Prinzip konnte stets die gleiche Zahl von Zellen gewahlt

werden. In jedem Schritt wird das Gitter bei gleicher Zellenzahl effizienter

und der Fehler geringer. Jeder Schritt der Berechnung wurde dann aber hohe

Kosten verursachen. Ein mogliches effizienteres Verfahren ware, in jedem

Schritt die Zahl der Zellen langsam zu erhohen.


Zunachst soll uberpruft werden, in wie weit der benutzte Gittergenerator

eine vorgegebene Dichtefunktion in einem Gitter darstellen kann. Verglichen

werden die vorgegebenen Zellweiten mit den Zellweiten, die das erzeugte

Gitter darstellt. Zusatzlich wird das Ergebnis des Gittergenerators mit den

erreichten Zellweiten bei lokaler Gitterverfeinerung verglichen.

Beispiel 5.1 Gerechnet wird das Modellproblem (2.1) zu vorgegebener Losung

u(x, y) = (1 − x2)(1 − y2) sin(4x) sin(6y)

mit dem Fehlerfunktional

j(ϕ) = ∂xu(x0), x0 = (14, 1

4).

60

Das Fehlerfunktional liegt nicht in H−1(Ω) und muß regularisiert werden.

(Siehe z.B. Abschnitt 4.3). Die duale Losung hat eine starke Singularitat im

Punkt x0 (jetzt wird die Ableitung im Punkt ausgewertet). Beim Remeshing

erhalt der Gittergenerator als Dichtefunktion die Ergebnisse der Optimie-

rungsformel (Satz 2.3). Ausgewertet werden jeweils die Gitterweiten aller

Zellen entlang einer Testlinie, die durch das Gebiet lauft. Einmal wird ent-

lang der Linie (t, 0.25) und einmal entlang der Linie (t, 0.8) ausgewertet.

In den Grafiken 5.2 sind jeweils die Zellweiten gegen die x-Koordinate auf-

getragen. In jeder Grafik ist das Ergebnis der Gitterformel (Satz 2.3), sowie

die realisierten Zellweiten bei Gittergenerierung und Gitterverfeinerung auf-

getragen. Da die Zellweiten stark schwanken konnen, werden die Ergebnisse

in Abbildung 5.3 zusatzlich als Bezier-Kurven gezeigt.

In den Grafiken 5.2 und 5.3 zeigt sich, daß beide Verfeinerungsstrategien

in der Lage sind, die Ergebnisse der Gitterformel darzustellen. Der in der

Grafik 5.3 klare Vorteil des Gittergenerators liegt nur an der Unscharfe der

lokalen Gitterverfeinerung: benachbarte Zellweiten konnen nur um den Fak-

tor 2 variieren. Im kritischen Punkt x = 0.25 fallt die Wahl aber auf die

kleinere Zellweite, die nahe an der Vorgabe der Gitterformel liegt. Samtliche

Ergebnisse des Gittergenerators zeigen Fehler am Rand. Hier mussen Zellen

kunstlich verkleinert werden, um an den Rand des Gebiets zu passen.

61

1e-05

0.0001

0.001

0.01

0.1

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

GittergeneratorGitterverfeinerung

Zielwert

0.01

0.1

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

GittergeneratorGitterverfeinerung

Zielwert

Abbildung 5.2: Die Zellweiten entlang der Linien (t, 0.25) (oben) und (t, 0.8).

1e-05

0.0001

0.001

0.01

0.1

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

h

(x,0.25)

ZielwertGittergenerator

Gitterverfeinerung

0.01

0.1

-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

h

(x,0.8)

ZielwertGittergenerator

Gitterverfeinerung

Abbildung 5.3: Die interpolierten Zellweiten entlang beider Linien.

62

Kapitel 6

Anisotrope Finite-Elemente

In vielen Fallen hat die Losung einer Differentialgleichung ein stark aniso-

tropes Verhalten: z.B. konnen Grenzschichten am Rand auftreten, Anisotro-

pien konnen durch anisotrope Daten, durch Sprunge in der rechten Seite

oder durch Singularitaten des Gebiets, schließlich auch durch Singularitaten

im Operator hervorgerufen werden. Auf der anderen Seite kann durch das

Fehlerfunktional ein anisotropes Verhalten erzeugt werden. Werden Integrale

entlang einer Linie – zum Beispiel am Rand – ausgewertet, so zeigt die dua-

le Losung anisotropes Verhalten an dieser Linie. Insgesamt lassen sich die

Ursachen fur anisotropes Verhalten in vier Bereichen zusammenfassen:

1. Daten: die rechte Seite oder die Randwerte besitzen Sprunge oder stark

anisotropes Verhalten.

2. Gebiet: bei einspringenden Ecken verandert die Losung ihr Verhalten

sehr stark in Richtung der Ecke. Bei einspringenden Kanten (in 3D)

kann sich so ein stark anisotropes Verhalten entwickeln.

3. Operator: der Operator ist anisotrop, z.B. (∇·a∇) mit anisotropem a.

4. Fehlerschatzer: das verwendete Fehlerfunktional erzeugt eine anisotrope

duale Losung.

Bei der Realisierung einer anisotropen Finite-Elemente Methode muß die

Anisotropie in das Gitter einfließen. Es werden Zellen benotigt, die stark in

63

eine Richtung gestreckt sind. Bei der Umsetzung sind einige Probleme zu

losen:

• Der Fehlerschatzer (2.8) muß modifiziert werden. Ein Problem ergibt

sich erst dann, wenn Interpolationsabschatzungen verwendet werden

sollen. Wird, wie bei (2.12), die patchweise Interpolierte verwendet, so

ist der Fehlerschatzer auch im anisotropen Fall anwendbar.

• Es muß die Moglichkeit zur anisotropen Verfeinerung geschaffen wer-

den. Die Finite-Elemente Bibliothek deal.II [13, 14] leistet dieses nicht.

Es konnen nur Rechteckelemte oder Hexaeder verwendet werden, und

diese nur in je vier (in 2D) und acht (3D) neue Elemente verfeinert

werden. Die numerischen Untersuchungen werden sich deshalb auf Ten-

sorgitter, das sind insbesondere Gitter ohne lokale Verfeinerung, be-

schranken. Zur weiteren Untersuchung – und zur vollen Auflosung von

Anisotropie – ist die Verwendung von Dreiecksgittern unerlaßlich.

• Uber den Wert des Fehlerschatzers und die Fehlerindikatoren hinaus

muß der Fehlerschatzer die”Richtung“ und

”Starke“ der Anisotropie

ermitteln konnen. Hierauf wird gesondert und detailiert eingegangen.

• Die Verwendung von anisotropen Gittern beeinflußt die Kondition der

Systemmatrix negativ. Dieses wirkt sich auf die Losung der Gleichungs-

systeme negativ aus. Durch spezielle Vorkonditionierer und spezielle

Sortierung der Freiheitsgrade kann dieses Problem behandelt werden.

(siehe z.B. [11]).

6.1 Erkennen von Anisotropie

Ein grundsatzliches Problem besteht im Ablesen der Informationen uber die

Anisotropie aus der gerechneten Losung und gegebenenfalls aus weiteren

Hilfsdaten. Beim Losen der partiellen Differentialgleichungen soll die Aniso-

tropie adaptiv erkannt und berucksichtigt werden. Wie der Fehler der Finite-

Elemente Losung, laßt sich auch die Anisotropie auf den Interpolationsfehler

zuruckfuhren.

64

v

Abbildung 6.1:

6.1.1 Anisotropie im Interpolationsfehler

Als Zugang zu diesem Thema wird ein sehr einfaches Beispiel betrachtet. Eine

Funktion u soll auf einer Linie eindimensional interpoliert werden. Dabei

sei Ih : C2 → P1 die eindimensionale Knoteninterpolation in den Raum

der linearen Funktionen. Gesucht ist die Ausrichtung v der Linie, so daß

der Interpolationsfehler minimal bzw. maximal wird. Die Lange der Linie

sei |v| = 1 und die zweiten Ableitungen der Funktion u seien konstant. In

Abbildung (6.1) ist diese Situation dargestellt. Es ist dann folgendes Problem

zu losen: Zu einer Funktion u ∈ C2(B) mit konstanten zweiten Ableitungen

in B bestimme v ∈ R2 mit

‖u− Ihu‖Γv→ min

Γv =λv ∈ R

2; 0 ≤ λ ≤ 1, |v| = 1

(6.1)

Dann gilt fur die Interpolationsabschatzung

‖u− Ihu‖Γv≤ c ‖∂ttu‖Γv

≈∣∣∣∂ttu (ζ)

∣∣∣= |〈v,Huv〉|

Hu =

(∂xxu ∂xyu

∂xyu ∂yyu

).

Dabei ist Hu die Hessematrix. Die Ableitungswerte ∂ sind geeignete Mit-

telwerte. Als symmetrische Matrix hat Hu zwei reelle Eigenwerte λ1 ≤ λ2;

65

es existiert somit eine orthogonale Transformationsmatrix T , bestehend aus

den Eigenvektoren v1, v2, so daß die Matrix Hu diagonalisierbar ist:

Hu = T TDT, D = diag(λ1, λ2), T T = (v1, v2) .

Das Minimierungsproblem (6.1) hat dann die einfache Form

min‖x‖=1

|〈x,Dx〉|

und nimmt sein Minimum fur den Einheitsvektor e1. Den geringsten Inter-

polationsfehler erhalt man in Richtung v1, dem zum betragsmaßig kleinsten

Eigenwert gehorenden Eigenvektor. Schreibt man das Problem als Maximie-

rungsproblem, so erhalt man entsprechend v2 als Richtung mit dem großten

Interpolationsfehler.

Dieses einfache Beispiel zeigt, daß die gesuchten Informationen in den

zweiten Ableitungen der Losung zu suchen sind. Die Anisotropie der Funk-

tion u kann an der Hessematrix abgelesen werden. Dabei kennzeichnet das

Verhaltnis der Eigenwerte λ1 : λ2 das Anisotropieverhaltnis und die Eigen-

vektoren die – stets orthogonalen – Richtungen der maximalen und mini-

malen Anisotropie. Grundsatzlich sind zwei Aspekte zu untersuchen: 1. die

”Lage“ der Anisotropie, das ist die optimale Ausrichtung eines Gitters und

2. die”Starke“ der Anisotropie, also die Streckung der Zellen. Da das erste

Problem durch Tensorgitter nicht dargestellt werden kann, wird diese Frage

hier nicht weiter behandelt.

Eine erste Erweiterung des zweiten Aspektes ist das Ermitteln der opti-

malen Hohe und Breite eines Rechtecks zur Minimierung des Interpolations-

fehlers auf einer Zelle. Der Flacheninhalt sei dabei stets konstant A = hx ·hy.

Das zugehorige Minimierungsproblem ist: Zu u ∈ C2(K) suche hx, hy > 0:

‖u− Ihu‖K(hx,hy) → min, hx · hy = A.

Die zweiten Ableitungen seien wieder konstant. Es ergibt sich dann

‖u− Ihu‖K(hx,hy) ≤ (hxhy)12 (h2

x |∂xxu| + h2y |∂yyu|)

=√A(h2

x |∂xxu| + A2h−2x |∂yyu|).

66

Als notwendige Bedingung fur einen Extrempunkt erhalt man

0 = 2hx |∂xxu| − 2A2h−3x |∂yyu|

h4x = A2 |∂yyu|

|∂xxu|.

Das optimale Verhaltnis von Hohe und Breite des Elements ist

hx

hy=

( |∂yyu||∂xxu|

) 12

. (6.2)

FallsK(hx, hy) 6⊂ K, und somit die Regularitatsvoraussetzungen nicht sicher-

gestellt sind, so kann A entsprechend kleiner gewahlt werden. Das optimale

Verhaltnis ist unabhangig von der Zellgroße A.

6.1.2 Anisotrope Interpolationsabschatzungen

Im folgenden sind anisotrope Interpolationsabschatzungen notwendig. Ver-

sucht man, eine Interpolationsabschatzung uber das Bramble-Hilbert Lemma

herzuleiten, so erhalt man bei der H1-Interpolationsabschatzung durch die

Transformation auf ein Referenzelement den Faktor hmax/hmin, den Quoti-

enten aus maximaler und minimaler Zellweite. Der anisotrope Fehlerschatzer

und die Finite-Elemente Methode sollen aber auch stabil sein, wenn dieser

Quotient gegen unendlich strebt. Eine Interpolationsabschatzung ohne die-

sen Faktor laßt sich jedoch zeigen, wenn die Ableitungen ∂x(u − Ihu) und

∂y(u− Ihu) getrennt abgeschatzt werden:

Satz 6.1 (H1-Interpolationsabschatzung) Es seien hx, hy die Zellwei-

ten der Zelle K eines Tensorgitters. Der Knoteninterpolationsoperator Ih

erfullt fur alle u ∈ H2(K) ∩ C(K) die Abschatzung:

‖∇(u− Ihu)‖K ≤ c(h2

x ‖∂x∇u‖2K + h2

y ‖∂y∇u‖2K

)12

Der Beweis wird z.B. in [7] gefuhrt.

67

6.1.3 Anisotropie in den Fehlerindikatoren

Fur die anisotrope Finite-Elemente Methode mussen Informationen uber die

Anisotropie der primalen und der dualen Losung gemeinsam erfaßt werden.

Eine Moglichkeit ware, wie in (6.2) den Interpolationsfehler fur u und z

gleichzeitig zu minimieren. Als Verfeinerungsindikator wird das Produkt der

lokalen Interpolationsfehler verwendet:

ηK := ‖∇(u− Ihu)‖K ‖∇(z − Ihz)‖K . (6.3)

Die Abschatzung ‖u− uh‖ ≤ ‖u− Ihu‖ ist jedoch nur global auf ganz Ω

gultig. Dieser heuristische Ansatz entspricht auch nicht dem Vorgehen beim

dualen Fehlerschatzer. Hier werden nur lokale Interpolationsfehler betrachtet.

Die Fehlerverbreitung, also insbesondere der Einfluß von Fehleranteilen auf

andere Teile des Gebiets werden nicht berucksichtigt.

Es zeigt sich aber in numerischen Beispielen, daß (6.3) als Verfeinerungs-

indikator sinnvoll einsetzbar ist. Mit der Interpolationsabschatzung (Satz 6.1)

ergibt sich – wieder fur A = hx · hy aus (6.3):

ηK ≤ c(h2x ‖∂x∇u‖2

K + h2y ‖∂y∇u‖2

K)12 (h2

x ‖∂x∇z‖2K + h2

y ‖∂y∇z‖2K)

12

∼ (h4x ‖∂x∇u‖2

K ‖∂x∇z‖2K + A4h−4

x ‖∂y∇u‖2K ‖∂y∇z‖2

K + A2C)12

C := ‖∂x∇u‖2K ‖∂y∇z‖2

K + ‖∂y∇u‖2K ‖∂x∇z‖2

K .

Minimiert man diesen Ausdruck, wieder unter der Bedingung hx ·hy = A, so

erhalt man:

h4x = A2 ‖∂y∇u‖K ‖∂y∇z‖K

‖∂x∇u‖K ‖∂x∇z‖K

.

Fur das optimale Verhaltnis ergibt sich so

hx

hy=

(‖∂y∇u‖K ‖∂y∇z‖K


)12

. (6.4)

Auf diese Art konnen die Anisotropie der Losung und die Anisotropie des

Funktionals zusammen ermittelt werden. Auch Anisotropien, die durch das

Gebiet entstehen (”einspringende Kanten“ in 3D) werden berucksichtigt, da

sich die Anisotropie sowohl auf u als auch auf z auswirkt.

68

Bei diesem Zugang werden nur die Interpolationsfehler minimiert. Bes-

ser ware eine Minimierung der Fehlerindikatoren, die aus dem dualen Feh-

lerschatzer (2.8) hergeleitet werden konnen. Versucht man jedoch die Infor-

mationen direkt aus dem Fehlerschatzer abzulesen, so ergibt sich folgendes

Problem:

ηK = (f, z − zh)K − 12〈[∂nuh] , z − zh〉∂K

≈hxhy

(∣∣∣f(xK)∣∣∣(h2

x

∣∣∣∂xxz(xK)∣∣∣+ h2

y

∣∣∣∂yyz(xK)∣∣∣)

+h2x

∣∣∣∂yyu(xK)∣∣∣∣∣∣∂xxz(xK)

∣∣∣+ h2y

∣∣∣∂xxu(xK)∣∣∣∣∣∣∂yyz(xK)

∣∣∣).

(6.5)

Der erste Teil, der vom Gebietsskalarprodukt kommt, ist unabhangig von

den Ableitungen von u. In der rechten Seite f stecken zwar die zweiten Ab-

leitungen von u, diese sind aber nicht in die beiden Koordinatenrichtungen

getrennt.

Im zweiten Teil treten die Ableitungen von u und von z entgegengesetzt

auf. Ableitungen ∂xx von u werden mit Ableitungen ∂yy von z multipliziert.

Versucht man das optimale Verhaltnis zu bestimmen, so ergibt sich

ηK → min, hx · hy = A

⇒ hx

hy=

( |∂xxu| |∂yyz||∂yyu| |∂xxz|

)12

.(6.6)

Dieses Ergebnis ist entgegengesetzt zu den bisherigen Formeln (6.2) und

(6.4) und kann nicht die optimale Anisotropie beschreiben: angenommen,

die Funktion u sei in x-Richtung ein Polynom vom Grad 1, also ∂xxu = 0.

Die Formel (6.6) wurde vorschlagen, das Gitter in x-Richtung beliebig oft zu

verfeinern - also genau in der falschen Richtung. Es kann im anisotropen Fall

nicht reichen, nur das Skalarprodukt uber den Rand der Zellen

〈[∂nuh] , z − zh〉∂K

zu betrachten. Auch im Gebietsskalarprodukt mussen Informationen liegen.

Wie in Abschnitt 2.2 bei (2.14) kann versucht werden, das Ergebnis zu

verbessern, indem anstelle der zellweise Interpolierenden ihz die spezielle In-

terpolierende iP z auf einem Patch abgezogen wird. Dann ergibt sich:

ηP = (f − fP , z − iP z) − 12

∑

K∈P

〈[∂nuh] , z − iP z〉∂K .

69

So ist es moglich, die Ableitungen von f in die Koordinatenrichtungen zu

trennen. Aus dem ersten Teil dieser Darstellung des Fehlerschatzers kann

dann ein optimales Verhaltnis entsprechend (6.4) hergeleitet werden, es muß

nur u durch f ersetzt werden und es entstehen erste Ableitungen von f .

Dieses Ergebnis bringt allerdings Probleme mit sich:

• Die Ableitungen von f entsprechen dritten Ableitungen von u. Da f oft

aber nicht einmal als stetige Funktion gegeben ist, sind die Ableitungen

von f nicht auswertbar. Auch die dritten Ableitungen von u konnen

– gerade bei bilinearen Elementen – nicht ausgewertet werden, zumal

deren Existenz uberhaupt nicht sicher ist.

• Durch das Einschieben einer Interpolation bei f wird das Gebietsska-

larprodukt kleiner. Der Fehler wird umso starker durch den zweiten

Term mit den Sprungen uber die Kanten bestimmt. In diesem Term

treten die Ableitungen von u und z weiterhin entgegengesetzt auf.

Obwohl von der Fehleridentitat ausgegangen wurde, laßt sich aus dem Aus-

druck (6.5) nicht das optimale Anisotropieverhaltnis bestimmen. Es hat sich

jedoch schon in Kapitel 2 gezeigt, daß die Fehleridentitat nicht notwendig

gute Fehlerindikatoren liefert. Ist man nur an einer Richtungsentscheidung

interessiert, ob Verfeinerung in x- oder in y-Richtung erfolgen muß, so kann

diese Information aus der Fehleridentitat abgelesen werden. Wird jedoch ein

quantitatives Ergebnis benotigt, so muß die Anisotropie anhand der Interpo-

lationsfehler identifiziert werden. In den weiteren Untersuchungen wird von

einem optimalen Verhaltnis von hx zu hy nach (6.4) ausgegangen und auf

jeder Zelle sei dieses Verhaltnis gegeben durch

αK :=

(‖∂y∇u‖K ‖∂y∇z‖K


) 12

. (6.7)

Spater wird ein globaler Prozeß vorgestellt, um die Anisotropie zu ermitteln.

Dann wird wieder der Fehlerschatzer verwendet werden.

70

6.2 Erzeugen von optimalen Tensorgittern

Die Moglichkeiten bei der Gestaltung von Tensorgittern sind sehr gering. Es

ist lediglich eine Verteilung von Gitterpunkten auf der x- und auf der y-

Achse zu wahlen. Diese sollen in jedem Schritt alle neu bestimmt werden. Es

reicht nicht, nur neue Linien einzufugen. In jedem Schritt des”remeshings“

– es kann nicht mehr von Verfeinerung gesprochen werden, da ganz neue

Gitter entstehen – werden die Gitterlinien neu verteilt. Es muß jetzt eine

Entscheidung uber die Lage der Gitterlinien und auch uber die Anzahl der

Gitterlinien getroffen werden.

Zum Erzeugen des neuen Gitters stehen als Informationen die Fehlerindi-

katoren ηK und auf jeder Zelle ein optimales Anisotropieverhaltnis αK (6.7)

zur Verfugung.

6.2.1 Lokale Gittergenerierung

Zunachst wird versucht, fur jede Zelle eine optimale Große zu bestimmen, die

sowohl den Wert des Fehlerindikators, als auch die Anisotropie berucksichtigt.

Die so gewonnenen Zellgroßen werden auf Spalten und Zeilen des Gitters

gemittelt und aus diesen Werten wird ein neues Gitter erzeugt.

Es wird wieder versucht, den Fehler auf jeder Zelle zu aquilibrieren, also

auf jeder Zelle den Fehler tol zu erreichen und dabei das optimale Verhaltnis

hx/hy = aK auszunutzen. Gegeben ist eine Zelle K mit Kantenlangen hx und

hy; bekannt sind Approximationen√hxhy

∣∣∣∂xxu∣∣∣ ≈ ‖∂xxu‖K der Normen der

zweiten Ableitungen von u und z. Bestimmt werden sollen neue Kantenlangen

nx, ny, so daß auf den neuen Zellen der Fehler tol bei geringstem Aufwand

erreicht wird. Als Fehlerindikator wird (6.5) verwendet. Mit der Bedingung

nx = αKny und der lokalen Anisotropie (6.7) ergibt sich:

tol = cn2yαK

(∣∣∣∂xxu∣∣∣ +∣∣∣∂xxu

∣∣∣) (

n2yα

2K

∣∣∣∂xxz∣∣∣+ n2

y

∣∣∣∂yyz∣∣∣)

⇔ ny =

(tol

cαK

)14 [(∣∣∣∂xxu

∣∣∣+∣∣∣∂xxu

∣∣∣) (

α2K

∣∣∣∂xxz∣∣∣+∣∣∣∂yyz

∣∣∣)]−1

4,

nx = αKny.

71

Diese optimalen Zellgroßen mussen jetzt auf die Spalten und Zeilen des

Gitters ubertragen werden. Es mussen Funktionen hx(x) und hy(y) erzeugt

werden, welche die Gitterweite angeben. Da es nicht moglich sein wird, die

lokalen Zellgroßen in einem Tensorgitter zu realisieren, mussen Mittelwerte

gebildet werden.

6.2.2 Gittergenerierung

Im nachsten Schritt muß aus den Gitterfunktionen hx(x) und hy(y) ein neues

Gitter generiert werden. Dafur muß die Anzahl der Gitterlinien in beide Ko-

ordinatenrichtungen und die Verteilung der Gitterpunkte bestimmt werden.

Fur die Zahl der Gitterlinien auf einer Koordinatenachse wird das Verhalt-

nis N = 1/h genutzt und man erhalt, ubertragen auf den kontinuierlichen

Fall

Nx =

∫ b

a

hx(x)−1dx

Ny =

∫ b

a

hy(y)−1dy,

wenn Ω = (a, b)2.

(6.8)

Da die Anzahl der Gitterlinien ganzzahlig sein muß, werden die Funktionen

hx(x) und hy(y) mit ⌈Nx⌉/Nx (entsprechend bei Ny) skaliert. Dabei ist

⌈x⌉ := minn∈N,x≤n

n.

Die neuen Gitterpunkte x0, . . . , xNxwerden jetzt gleichmaßig im Sinne

von hx(x)−1 verteilt:

i = 0, . . . , Nx xi :

∫ xi

a

hx(x)−1dx = i,

i = 0, . . . , Ny yi :

∫ yi

a

hy(y)−1dy = i.

(6.9)

6.2.3 Globale Gittergenerierung

Der bisherige Zugang zu optimalen Zellgroßen hx(K) und hy(K) hat den

Nachteil, daß zu diesen neuen Großen kein Tensorgitter paßt. Durch das Bil-

den von Mittelwerten sind die erzeugten Gitter nicht mehr optimal. In diesem

72

Abschnitt wird ein Verfahren entwickelt, um eine optimale Verteilung von

Gitterlinien zu erhalten, die auf Tensorgittern zu realisieren ist. Dabei wer-

den nur Informationen verwendet, die spater auch in einem Gitter dargestellt

werden konnen. In diesem Prozeß werden keine lokalen Zellgroßen bestimmt.

Dieser Zugang halt sich wieder streng an den dualen Fehlerschatzer, also an

die Fehleridentitat. Es muß nicht auf die heuristische Minimierung der lokalen

Interpolationsfehler zuruckgegriffen werden. Das Tensorgitter sei nun durch

die beiden – kontinuierlichen – Funktionen hx(x) und hy(y), welche die Zell-

große entlang der beiden Koordinatenachsen angeben dargestellt. Das Gebiet

Ω sei im folgenden das Rechteck [a, b] × [c, d]. Dann ist:

N = NxNy =

(∫ b

a

hx(x)−1dx

)(∫ d

c

hy(y)−1dy

)(6.10)

die Anzahl der Zellen des Gitters. Als Verfeinerungsindikatoren wird von der

Fehleridentitat (2.8) ausgegangen. Mit Interpolationskonstanten c1, c2 gilt:

η =∑

K∈Th

(f, z − zh)K−12〈[∂nuh] , z − zh〉∂K

≤∑

K∈Th

hx(K)hy(K)(hx(K)2

∣∣∣∂xxz∣∣∣(c1

∣∣∣∂xxu∣∣∣+ (c1 + c2)

∣∣∣∂yyu∣∣∣))

+

(hy(K)2

∣∣∣∂xxz∣∣∣((c1 + c2)

∣∣∣∂xxu∣∣∣+ c1

∣∣∣∂yyu∣∣∣))

.

(6.11)

Die Konstante c1 kommt von der Gebietsinterpolation ‖z − Ihz‖K , c2 ist die

Interpolationskonstanten von den Sprungtermen. hx(K) und hy(K) sind die

Zellgroßen der Zelle K. Dieser Ausdruck wird nun als Integral uber das ganze

Gebiet Ω geschrieben. Die Zellgroßen hx, hy werden jetzt als kontinuierliche

Funktionen geschrieben:

η =

∫ b

a

hx(x)2Φx(x) dx +

∫ d

c

hy(y)2Φy(y) dy ,

Φx(x) =

∫ d

c

∣∣∣∂xxz∣∣∣(c1

∣∣∣∂xxu∣∣∣+ (c1 + c2)

∣∣∣∂yyu∣∣∣)

dy

Φy(y) =

∫ b

a

∣∣∣∂yyz∣∣∣((c1 + c2)

∣∣∣∂xxu∣∣∣+ c1

∣∣∣∂yyu∣∣∣)

dx .

73

Φx und Φy sind vom Gitter unabhangige, numerisch auswertbare Funktionen,

die die Ableitungen der primalen und dualen Losung beschreiben. Diese Dar-

stellung des Fehlerschatzers wird nun mit der Nebenbedingung N ≤ Nmax

minimiert. Das Lagrange-Funktional ist dann:

L(hx, hy, λ) = η(hx, hy) + λ(N(hx, hy) −Nmax).

Minimiert wird wie ublich uber alle”zulassigen“ Variationen. Dabei muß

darauf geachtet werden, daß z.B. die Funktion hx(x) auch nur mit positiven

Funktionen, die in y-Richtung konstant sind, variiert wird. Es gilt∫ b

a

∫ d

c

ϕ(x)f(x, y) dx dy = 0 ∀ϕ ∈ C1, ϕ > 0 ⇔∫ d

c

f(x, y) dy = 0.

Es bleibt ein Linienintegral ubrig. Aus der Bedingung

∂

∂tL(hx(x) + tψx(x), hy(y) + tψy(y), λ+ tµ)

∣∣∣∣t=0

= 0.

ergibt sich dann

2hx(x)Φx(x) − λhx(x)−2Ny = 0,

2hy(y)Φy(y) − λhy(y)−2Nx = 0,

Nmax = NxNy.

Aus den ersten beiden Gleichungen erhalt man

hx(x)3 =

λNy

2Φx(x),

hy(y)3 =

λNx

2Φy(y).

(6.12)

Um hieraus einen Nutzen ziehen zu konnen, muß das optimale Verhaltnis von

Nx zu Ny bekannt sein. Hierzu werden die bisherigen Ergebnisse in die Fehler-

darstellung eingesetzt. Folgender Ausdruck wird unter der Nebenbedingung

NxNy = Nmax und ohne Berucksichtigung des Faktors λ/2 minimiert:

η =N2

3y

∫ b

a

Φx(x)1

3 dx

︸︷︷︸Ψx

+N2

3x

∫ d

c

Φy(y)1

3 dy

︸︷︷︸Ψy

=ΨxN2

3maxN

− 2

3x + ΨyN

2

3x .

74

Es ergibt sich

0 = −2

3ΨxN

2

3maxN

− 5

3x +

2

3ΨyN

− 1

3x ,

N4x =

(Ψx

Ψy

)3

N2max.

Auf diese Weise erhalt man Nx und mit Ny = Nmax/Nx auch diesen Wert.

Danach kann mit (6.12) auch hx(x) und hy(y) ausgerechnet werden. Der

Lagrange-Multiplikator λ geht spater als Faktor in die optimalen Zellweiten

ein. Interessant ist zunachst aber nur das Verhaltnis hx : hy. Es kann λ = 1

gesetzt werden. Die Anzahl der Zellen muß stets vorgegeben werden. Hier

bietet es sich an, Nmax – die gewunschte Zahl von Zellen – im nachsten

Gitter langsam zu erhohen.

75


In mehreren Beispielen wird nun das im vorherigen Abschnitt entwickelte

Verfahren zur Gittererzeugung bei anisotropen Tensorgittern getestet. Wie

in den letzten Kapiteln wird wieder stets die Poissongleichung mit homogenen

Dirichletrandwerten gelost. Es werden nur Probleme gewahlt, deren Anisotro-

pien auf einem Tensorgitter darstellbar sind. Die Anisotropie verlauft immer

parallel zu den Koordinatenachsen. Um weitergehende Probleme zu losen,

ware die Verwendung von Dreieicksgittern unerlaßlich. Die rechten Seiten

werden zu zwei vorgegebenen Losungen betrachtet:

u1(x, y) = (1 − x2)(1 − y2) exp

(− 1

x4

),

u2(x, y) = (1 − x2)(1 − y2)(1 − x).

u2 ist im ganzen Gebiet sehr glatt und isotrop. u1 hat in zwei Streifen, parallel

zur y-Achse, große Ableitungen ∂xxu1. Abbildung 6.3 zeigt diese Funktion.

Der Fehler wird in drei Funktionalen ausgewertet:

j1(u) =

∫ 1

−1

u(x, 0) dx ,

j2(u) =

∫ 1

−1

∂yu(x, 0.5) dx ,

j3(u) =

∫

∂Ω

∂nu dx .

Die zugehorigen dualen Losungen sind alle anisotrop. Die Funktionale j1 und

j2 erzeugen duale Losungen z mit großen Ableitungen ∂yyz in Teilen des Ge-

biets, die duale Losung zum Funktional j3 hat große Ableitungen normal zum

Rand des Gebiets. Die Funktionale j2(u), j3(u) liegen nicht in H−1(Ω) und

mussen regularisiert werden. Das Funktional j3 wurde auch in [6] behandelt.

Es wird durch das regularisierte Funktional jε3 ersetzt, mit:

jε3(ϕ) =

1

ε

∫

Ωε

∂nϕ(x) dx ,

Ωε = x ∈ Ω : dist(x, ∂Ω) ≤ ε.

76

Es wird der Mittelwert der Normalableitung uber einen Streifen am Rand

gebildet. Dann gilt

limε→0

jε3(ϕ) = j3(ϕ).

Bei der Losung des dualen Problems wird ε so gewahlt, daß jε(ϕ) − j(ϕ) ≪‖ϕ‖ TOL, wenn TOL die Fehlertoleranz ist. Als duale Losung z fur das nicht-

regularisierte Funktional wurde sich

z =

1 x ∈ Ω

0 x ∈ ∂Ω

ergeben. Da die duale Losung im Innern des Gebiets konstant Eins ist, liefern

die Zellen im Innern auch keinen Anteil zum Fehler. Die Verfeinerung muß

also nur am Rand des Gebiets erfolgen.

Drei Beispiele werden zu folgenden Kombinationen von rechten Seiten

und Fehlerfunktionalen gerechnet:

Losung Funktional

Beispiel 6.1 u1 j1

Beispiel 6.2 u1 j2

Beispiel 6.3 u2 j3

Das Beispiel 6.1 entspricht dabei Beispiel 4.6 mit isotroper, lokaler Git-

terverfeinerung. Zu allen Rechnungen wird in den Tabellen 6.1 bis 6.3 der

Fehler, der Effektivitatsindex und die im Gitter dargestellte Anisotropie an-

gegebenen. Dabei ist A die mittlere Anisotropie uber alle Zellen des Gitters

und Amax die maximale Anisotropie einer Zelle des Gitters:

aK = max

hx(xK)

hy(xK),hy(xK)

hx(xK)

∀K ∈ Th,

A = N

√∏

K∈Th

aK , Amax = maxK∈Th

aK .

77

0.0001

0.001

0.01

0.1

1

10 100 1000 10000 100000

j(e)

Freiheitsgrade

isotrope Verfeinerunganisotrope Verfeinerung

Abbildung 6.2: Konvergenzverhalten bei anisotroper und isotroper Verfeine-

rung zu Beispiel 6.1.

Beispiel 6.1 Die Losungen des primalen und dualen Problems haben beide

ein stark anisotropes Verhalten. Die Ausrichtung der Anisotropie ist jedoch

entgegengesetzt. Bei u ist |∂xxu| groß, bei z ist |∂yyz| groß. (Siehe auch Ab-

bildung 3.1 zu Beispiel 3.1). In jedem Schritt der Gittersteuerung wird die

Zahl der Zellen um den Faktor 5 erhoht (siehe Abschnitt 6.2.3).

Bei der Rechnung mit anisotroper Verfeinerung auf Tensorgittern wurde

der gleiche Fehler wie bei Rechnung mit isotroper lokaler Gitterverfeinerung

Freiheitsgrade j(e) η/j(e) A Amax

81 0.441 0.69 1 1

315 0.0812 0.92 1.86 4.83

1107 0.00711 0.97 2.60 18.51

3927 0.00089 0.99 3.50 115.97

13755 0.00021 1.00 3.30 221.09

Tabelle 6.1: Freiheitsgrade, Fehler, Effektivitatsindex und Anisotropie bei

der anisotropen Rechnung.

78


81 0.45 1.82 1 1

299 0.0743 2.34 3.28 22.70

1035 0.00259 2.11 3.98 25.15

3735 0.00125 1.73 7.60 163.97

13137 0.000232 2.18 8.17 782.43

46269 1.22 · 10−5 13.72 17.41 20433.6


Beispiel 6.2

mit nur 25% der Freiheitsgraden fur TOL = 10−4 erreicht. In Abbildung 6.2

ist das Konvergenzverhalten der Losung dargestellt. Der direkte Vergleich zu

Beispiel 4.6 zeigt, daß die anisotrope Finite-Elemente Methode hier uberlegen

ist. Tabelle 6.1 legt nahe, daß die im Gitter dargestelle Anisotropie gegen

einen festen Wert konvergiert.

Beispiel 6.2 In Abbildung 6.3 sind primale und duale Losung zu diesem

Beispiel dargestellt. Im Gegensatz zu Beispiel 6.1 wird im Fehlerfunktio-

nal die Ableitung ausgewertet. Die duale Losung hat demnach eine starke

Singularitat entlang der Auswertungslinie. In Tabelle 6.2 sind die Zahl der

Freiheitsgrade und der Fehler sowie der Effektivitatsindex (η/j(e)) und die

Anisotropie angegeben. In diesem Beispiel konvergiert die Anisotropie nicht.

Da diese von den zweiten Ableitungen der dualen Losung bestimmt wird, die

hier nicht existieren, kann eine Konvergenz auch nicht erwartet werden.

Auch der Effektivitatsindex konvergiert nicht gegen 1. Die duale Losung

hat entlang einer Linie einen Sprung (Abbildung 6.3). Durch die Regula-

risierung des Funktionals wird dieser Sprung geglattet. Mit der richtigen

Wahl des Regularisierungsparameters ε sollten Probleme vermieden wer-

den. Der schlechte Effektivitatsindex ist auf die Verwendung der biquadra-

tischen, patchweisen Interpolierenden zuruckzufuhren. Die Approximations-

eigenschaften dieser Interpolierenden sind sehr schlecht, wenn der Sprung in

der dualen Losung mitten durch einen Patch verlauft.

79

primales Problem

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

-0.0050

0.0050.01

0.0150.02

0.0250.03

0.0350.04

0.045

z

duales Problem

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

-1.5

-1

-0.5

0

0.5

1

z

Abbildung 6.3: Primale und duale Losung zu Beispiel 6.2.

80


81 0.12631 1.06 1 1

289 0.02824 1.03 2 4

289 0.00099 0.98 53 292

289 7.77 · 10−5 0.99 380 4287

289 2.02 · 10−5 0.99 1444 16178

289 5.19 · 10−6 1.01 6196 67037

275 3.33 · 10−6 1.00 13077 339212

289 2.29 · 10−6 1.00 14644 165504

289 5.46 · 10−7 1.00 120839 1.57 · 106


Beispiel 6.3

Beispiel 6.3 Im dritten Beispiel wird der Fehler in der Normalableitung

uber den ganzen Rand gemessen. Bei den Uberlegungen zur Regularisierung

hat sich herausgestellt, daß Verfeinerung nur am Rand des Gebiets erfolgen

muß. Um dieses numerisch zu uberprufen, wird im Algorithmus zum Er-

zeugen des Gitters (6.2.3) stets versucht, ein Gitter mit etwa 300 Zellen zu

erzeugen. In Tabelle 6.3 werden der Fehler und die Anisotropie angegeben.

Die Zahl der Freiheitsgrade bleibt nahezu konstant. Trotzdem liegt eine hohe

Konvergenzrate (jetzt in Bezug auf die Anisotropie) vor. Diese Ergebnisse

bestatigen die Theorie: bei stark steigender Anisotropie jedoch konstanter

Zahl von Zellen, konvergiert der Fehler gegen Null. Abbildung 6.4 zeigt den

Fehler in Abhangigkeit der mittleren Anisotropie. Es zeigt sich hier die zu er-

wartende Konvergenzordnung 1/hmin, wenn hmin die jeweils kleinere Seite der

Zellen am Rand ist (es gilt etwa A ≈ h−1min). Dieses Beispiel zeigt auch die Sta-

bilitat des Fehlerschatzers gegenuber (extremer) Anisotropie. Der kritische

Punkt ist die Verwendung der biquadratischen Interpolierten. Bei diesem Bei-

spiel ist aber sichergestellt, daß der Sprung in der dualen Losung immer am

Rand eines Patchs liegt. Tabelle 6.3 zeigt, daß der Effektivitatsindex sofort

gegen 1 konvergiert.

81

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

1 10 100 1000 10000 100000

j(e)

Anisotropie

Abbildung 6.4: Fehler in Abhangigkeit der mittleren Anisotropie in Beispiel

6.3. Bei gleichbleibende Zellenzahl konvergiert der Fehler wie 1/A.

6.4 Gitteroptimierung mit lokalen Interpola-

tionsfehlern

Orientiert man sich beim Erkennen der Anisotropie wie bisher streng an

der Fehleridentitat (Abschnitt 6.2.3), so kann die Anisotropie der primalen

Losung nicht exakt erfaßt werden. Angenommen die rechte Seite ist konstant

Null. Dann ist in (6.11) die Interpolationskonstante c1 = 0 zu wahlen und

hx(x), hy(y) sind gegeben durch:

hx(x)3 =

Ny

2Φx

, hy(y)3 =

Nx

2Φy

Φx =

∫ d

c

∣∣∣∂xxz∣∣∣∣∣∣∂yyu

∣∣∣ , Φy =

∫ b

a

∣∣∣∂yyz∣∣∣∣∣∣∂xxu

∣∣∣ .

Große zweiten Ableitungen ∂xxu erzeugen also kleines hy.

In Abschnitt 6.1.3 wurde bei (6.7) eine Moglichkeit vorgestellt, die Ani-

sotropie aus dem Produkt der lokalen Interpolationsfehler, ausgehend von

η =∑

K∈Th

‖∇(u− Ihu)‖K ‖∇(z − Ihz)‖K

82

zu bestimmen. Die Abschatzung ‖∇(u− uh)‖ ≤ ‖∇(u− Ihu)‖ gilt jedoch

nur auf dem ganzen Gebiet Ω, nicht aber zellweise. Im folgenden wird ver-

sucht werden, den Vorteil dieser Darstellung, also das einfache Erkennen der

Anisotropie mit dem Vorgehen des letzten Abschnitts zu verbinden. Als lo-

kale Fehlerindikatoren werden jetzt

η′K = ‖∇(u− Ihu)‖K ‖∇(z − Ihz)‖K

≤ cihxhy

(hx

∣∣∣∂x∇u∣∣∣+ hy

∣∣∣∂y∇u∣∣∣) (

hx

∣∣∣∂x∇z∣∣∣ + hy

∣∣∣∂y∇z∣∣∣) (6.13)

verwendet. Wie in Abschnitt 6.2.3 wird der Fehlerschatzer als Integral uber

das gesamte Gebiet geschrieben. Gesucht wird ein optimales hx(x) und hy(y).

Als Ergebnis erhalt man entsprechend zu (6.12):

hx(x)3 =

Ny

2Φx(x),

hy(y)3 =

Nx

2Φy(y),

Φx(x) =

∫ d

c

∣∣∣∂x∇u∣∣∣∣∣∣∂x∇z

∣∣∣ dy ,

Φy(y) =

∫ b

a

∣∣∣∂y∇u∣∣∣∣∣∣∂y∇z

∣∣∣ dx .

(6.14)

Bei allen gelosten Differentialgleichungen dieses Kapitels verhalt sich diese

Methode der Gittersteuerung wie die bisher verwendete. Unterschiede werden

deutlich, wenn starke Anisotropie in der primalen Losung vorliegt:

Beispiel 6.4 Gelost wird die Modellgleichung (2.1). Die rechte Seite wird

zu einer vorgegebenen Losung bestimmt:

u(x, y) = (1 − x2)(1 − y2)1

kx2 + 0.1.

Der Parameter k steuert die Starke der Anisotropie. In Abbildung 6.5 sind

Losungen zu zwei Werten von k dargestellt. Das Problem wird fur k =

1, 4, 16, 64 mit zwei Strategien gelost:

Strategie I Die Gittersteuerung basiert auf der Fehleridentitat (6.12), wie

im letzten Abschnitt.

83

Strategie II Gittersteuerung erfolgt mit lokalen Interpolationsfehlern. (6.14)

Als Fehlerfunktional wird der Mittelwert uber das gesamte Gebiet gewahlt:

j(ϕ) =1

|Ω|

∫

Ω

ϕ dx .

Anisotropie entsteht bei diesem Problem nur durch die primale Losung, das

duale Problem entspricht −∆z = 1, z = 0 auf dem Rand, ist also isotrop.

k jI(e) jII(e) jI(e)/jII(e) AI AII

1 1.20 · 10−5 1.32 · 10−5 0.91 1.35 1.71

4 6.44 · 10−5 1.36 · 10−5 4.72 1.82 2.72

16 1.76 · 10−4 1.56 · 10−5 11.30 2.75 4.67

64 4.40 · 10−4 1.47 · 10−5 29.83 4.44 8.35

Tabelle 6.4: Vergleich der Strategien bei Beispiel 6.4.

Mit starker werdender Anisotropie in der primalen Losung wird Strategie

II uberlegen. Abbildung 6.6 zeigt, daß sich der Fehler bei beiden Strategien

asymptotisch gleich verhalt, Strategie II aber eine bessere Fehlerkonstante

erzeugt. In Tabelle 6.4 sind die Fehler jI , jII und die mittlere Anisotropie

AI , AII im Gitter jeweils fur beide Strategien aufgetragen. Zusatzlich ist der

Quotient jI/jII angegeben. Alle Gitter haben etwa 40000 Freiheitsgrade.

Dieser heuristische Zugang verwendet lediglich lokale Interpolationsab-

schatzungen als Fehlerindikatoren. Im Abschnitt 2.3 hat sich bei den Berech-

nungen zu Beispiel 2.3 herausgestellt, daß mit den sehr einfachen Fehlerin-

dikatoren ηK = h3/2K ‖[∂nuh]‖∂K

|∇2hz(xK)| die besten Gitter erzeugt werden

konnten. Selbst ein exakter Fehlerschatzer muß nicht zwangslaufig gute Feh-

lerindikatoren liefern.

84

Loesung fuer k=4

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

0

2

4

6

8

10

12

z

Loesung fuer k=64

-1-0.5

00.5

1x -1

-0.5

0

0.5

1

y

0

2

4

6

8

10

12

z

Abbildung 6.5: Losungen zu Beispiel 6.4 fur k = 4 und k = 64.

1e-05

0.0001

0.001

1000 10000 100000

j(e)

Freiheitsgrade

Strategie IStrategie II

1e-05

0.0001

0.001

0.01

1000 10000 100000

j(e)

Freiheitsgrade


1e-05

0.0001

0.001

0.01

1000 10000 100000

j(e)

Freiheitsgrade


1e-05

0.0001

0.001

0.01

0.1

1

1000 10000 100000

j(e)

Freiheitsgrade


Abbildung 6.6: Freiheitsgrade und Fehler bei Rechnungen zu verschieden

starker Anisotropie (k = 1, 4, 16, 64).

85

Die Fehleridentitat konnte nicht verwendet werden, um das optimale Ani-

sotropieverhaltnis zu bestimmen. Ausgehend von

j(e) =∑

K∈Th

(f, z − Ihz)K − 12〈[∂nuh] , z − Ihz〉∂K

konnte nur die Anisotropie in der dualen Losung identifiziert werden. Im

Fehlerschatzer kann auch eine Galerkinorthogonalitat bezuglich z ausgenutzt

werden. Wenn j die rechte Seite zum dualen Problem −∆z = j ist, gilt

j(e) =∑

K∈Th

(j, u− Ihu)K − 12〈[∂nzh] , u− Ihu〉∂K .

Dabei ist j als diejenige Funktion aufzufassen, so daß fur alle ϕ ∈ H1(Ω)

gilt: j(ϕ) = (j, ϕ). Die Existenz dieser Funktion ist durch den Riesz’schen

Darstellungssatz [4] gesichert. Auf diese Weise kann fur u das optimale Aniso-

tropieverhaltnis bestimmt werden. Versucht man aber, etwa den Mittelwert

beider Fehlerdarstellungen zu minimieren, so bleiben die Sprunge uber die

Normalableitung erhalten. Zur Bestimmung der Anisotropie bleibt nur der

heuristische Zugang uber die Minimierung lokaler Interpolationsfehler.

86

6.5 Zusammenfassung

In diesem Kapitel wurde nur ein kleiner Teil der Moglichkeiten, die anisotro-

pe Gitter bieten, betrachtet. Auch so zeigt sich aber, daß in vielen Fallen die

Berucksichtigung der Anisotropie in der Finite-Elemente Methode unerlaßlich

scheint. Wird die Anisotropie ausgenutzt, so kann zunachst – bis das Gitter

die Anisotropie richtig darstellt – eine hohere Konvergenzordnung erzielt wer-

den. In Fallen mit extremer, unbeschrankter Anisotropie (z.B. Beispiel 6.3)

kann wahrend der gesamten Losung des Problems eine bessere Konvergenz

erreicht werden. Zu untersuchen bleibt das Erkennen der Lage und der Aus-

richtung der Anisotropie. Wie angesprochen, waren zu einer allgemeineren

Umsetzung von anisotropen Gittern Dreieckselemente notwendig. Anisotro-

pes Verhalten, das diagonal im Gitter oder sogar entlang allgemeiner Kurven

auftritt, laßt sich mit Rechtecksgittern nur unzureichend darstellen. Damit

ist die hier behandelte Problemklasse sehr begrenzt. Die Ergebnisse lassen

sich aber leicht auf den allgemeinen Fall ubertragen.

87

Kapitel 7

Ausblick

Zielstellung dieser Arbeit war eine optimale Gittersteuerung fur die Finite-

Elemente Approximation partieller Differentialgleichungen. Eine Losung auf

einem”optimalen Gitter“ sollte bei moglichst wenigen Zellen einen geringen

Fehler erreichen.

In Kapitel 4 wurde gezeigt, daß die Fehlerindikatoren mit sehr hoher

Genauigkeit vorliegen mussen, um mit ihnen ein”optimales Gitter“ zu er-

zeugen. Dann aber kann sehr schnell ein feines, optimal auf das Problem

abgestimmtes Gitter erzeugt werden. Der in diesem Kapitel vorgestellte Al-

gorithmus kann das Gitter sofort um mehrere Stufen verfeinern, und er be-

rechnet die Fehlerindikatoren adaptiv mit der notwendigen Genauigkeit. Es

ist unter Umstanden erforderlich, das duale Problem genauer zu rechnen als

das primale. Trotz des hoheren Aufwands fur die Berechnung des dualen

Problems und des Fehlerschatzers laßt sich eine Zeitersparnis von bis zu 50%

erzielen.

Die entwickelte Methode kann nicht ohne weiteres auf nichtlineare Pro-

bleme erweitert werden. Gerade bei dieser Problemklasse ist – aufgrund des

weit hoheren Aufwands – eine Optimierung der Gitteradaption notwendig.

Da nichtlineare Probleme in dieser Arbeit nicht behandelt wurden, wurde

auch diese Frage nicht weiter untersucht.

Die Verwendung von anisotropen Gittern in Kapitel 6 zeigt, daß die

Berucksichtigung von Anisotropie in adaptiven Verfahren keinen hohen Auf-

88

wand, aber eine starke Effizienzsteigerung darstellt. Mit starker werdender

Anisotropie, die durch das Fehlerfunktional erzeugt wird, wachst die Erspar-

nis im Aufwand, wenn die Anisotropie richtig in das Gitter einfließt. Die vor-

gestellte Methode der anisotropen Gitteradaption erzeugt in sehr wenigen

Schritten extrem feine Gitter, die schon bei schwacher Anisotrope effizienter

sind als Gitter mit lokaler Verfeinerung.

Die Untersuchungen der Anisotropie haben sich in dieser Arbeit auf Ten-

sorgitter beschrankt. Die theoretischen Ergebnisse lassen sich sofort auf be-

liebige Gitter ubertragen und mussen noch numerisch uberpruft werden. Das

adaptive Erkennen der”Richtung der Anisotropie“ wurde in dieser Arbeit

kaum betrachtet. Es ware nicht moglich gewesen, samtliche Informationen

uber Anisotropie in den verwendeten Tensorgittern darzustellen. Die Erwei-

terung der Gitteradaption um diesen Aspekt scheint jedoch sinnvoll, da so die

Problemklasse, bei der Anisotropie effizienzsteigernd genutzt werden kann,

weiter vergroßert werden wurde. Hier ware die Verwendung von Dreiecksgit-

tern zwingend notwendig.

Die vorgestellte Fehleridentitat, die im isotropen Fall zu einer Formel

fuhrt, die eine optimale Gitterweitenfunktion angibt, konnte in dieser Ar-

beit nicht vollstandig auf den anisotropen Fall erweitert werden. Zur Feh-

lerschatzung ist der duale Fehlerschatzer auch bei anisotropen Gittern sehr

gut geeignet, die Starke und Richtung der Anisotropie konnte aber nicht

exakt identifiziert werden. Alternativ wurde ein heuristisches Verfahren vor-

gestellt, welches die lokalen Interpolationsfehler der primalen und dualen

Losung minimiert und zu sehr effizienten Gittern fuhrt.

89

Literaturverzeichnis

[1] M. Braack. An Adaptive Finite Element Method for Reactive Flow

Problems, Dissertation, Heidelberg 1998.

[2] R. Becker, R. Rannacher. A feed-back approach to error control in finite

element methods: Basic analysis and examples, East-West J. Numer.

Math. 4, No.4, 237-264, 1996.

[3] Ch. Grossman, H.-G. Roos. Numerik partieller Differentialgleichungen,

B.G.Teubner Stuttgart 1994.

[4] H.W. Alt. Lineare Funktionalanalysis, Springer-Verlag 1992.

[5] D. Braess. Finite Elemente. Theorie, schnelle Loser und Anwendungen

in der Elastizitatstheorie. 2. Auflage, Springer-Verlag 1997.

[6] R. Rannacher. Adaptive Galerkin Finite Element Methods for Partial

Differential Equations, Preprint SFB 359, 20/1999, Heidelberg, 1999.

[7] R. Becker. Adaptive Finite Element Method for the Incompressi-

ble Navier-Stokes Equations on Time-dependent Domains, Dissertation,

Heidelberg, 1995.

[8] S. A. Mitchel, S. A. Vavasis. Quality Mesh Generation in Higher Di-

mensions, SIAM Journal of Computing, Vol. 29, No. 4, pages 1334-1370,

2000.

[9] F. Hecht. Dokumentation zum Gittergenerator BAMG, http://www-

rocq.inria.fr/gamma/cdrom/www/bamg/eng.htm

90

[10] T. Apel. Interpolation of non-smooth functions on anisotropic finite

element meshes, Math. Modeling Numer. Anal. 33(1999), 1149-1185

[11] R. Bridson, W. Tang. Ordering, anisotropy, and factored sparse appro-

ximate inverses, SIAM J. Sci. Comput., Vol. 21, No. 3, pages 867-882,

1999.

[12] L. R. Scott, S. Zhang. Finite element interpolation of non-smooth func-

tions satisfying boundary conditions, Math. Comp., 54:483-493, 1990.

[13] W. Bangerth, u.a. Adaptive Finite-Elemente Software-Bibliothek,

http://gaia.iwr.uni-heidelberg.de/˜ deal

[14] W. Bangerth, G. Kanschat. Concepts for Object-Oriented Finite Ele-

ment Software - the deal.II Library, Preprint SFB 359, 17/99, Heidel-

berg, 1999.

91

Documents

Funktionalorientierte Gitteroptimierung bei der Finite ...richter/pdf-files/diplom.pdf · der Finite-Elemente L¨osung werden Ansatzr ¨aume verwendet, deren Funktio-nen auf den Zellen