78
NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit¨ at Ilmenau (in der Fassung vom Sommersemester 2009)

NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

  • Upload
    others

  • View
    12

  • Download
    0

Embed Size (px)

Citation preview

Page 1: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

NUMERIK PARTIELLER

DIFFERENTIALGLEICHUNGEN

Elliptische und parabolische Probleme

Prof. Dr. Hans Babovsky

Technische Universitat Ilmenau

(in der Fassung vom Sommersemester 2009)

Page 2: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 1

Inhaltsverzeichnis

1 Einleitung 3

2 Elliptische Differentialgleichungen 5

2.1 Elliptische Differentialoperatoren zweiter Ordnung . . . . . . . . . . . . . 5

2.2 Elliptische Randwertprobleme . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Differenzenschemata fur elliptische Gleichungen 9

3.1 Differenzenapproximationen . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.2 Diskretisierung eines Modellproblems . . . . . . . . . . . . . . . . . . . . 10

3.3 Diskretisierung von Randern . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3.1 Das Dirichlet-Problem auf dem Einheitsquadrat . . . . . . . . . . 13

3.3.2 Das Neumann-Problem auf dem Einheitsquadrat . . . . . . . . . 14

3.3.3 Das Dirichlet-Problem fur beliebige (glatte) Rander . . . . . . . . 14

3.4 M-Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.5 Anwendung auf elliptische RWP’s . . . . . . . . . . . . . . . . . . . . . . 22

4 Variationsformulierung elliptischer RWP’s 25

4.1 Einfuhrungbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 Der Satz von Lax-Milgram . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3 Variationsprobleme in N Dimensionen . . . . . . . . . . . . . . . . . . . . 37

4.4 Ritz-Galerkin-Approximationen . . . . . . . . . . . . . . . . . . . . . . . 42

5 Methode der Finiten Elemente (FEM) 46

5.1 Ein einfuhrendes Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.2 Finite Elemente fur Ω ⊂ lR2 . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2.1 Lineare Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.2.2 Bilineare Elemente . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.2.3 Quadratische Elemente . . . . . . . . . . . . . . . . . . . . . . . . 52

5.3 Finite Elemente mit Nebenbedingungen . . . . . . . . . . . . . . . . . . . 52

5.4 H1-Fehlerabschatzungen fur lineare Elemente . . . . . . . . . . . . . . . 56

6 Parabolische Anfangs-Randwertprobleme 60

6.1 Ein eindimensionales Problem . . . . . . . . . . . . . . . . . . . . . . . . 60

6.1.1 Differenzenapproximationen . . . . . . . . . . . . . . . . . . . . . 60

Page 3: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 2

6.1.2 Stabilitat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6.2 Semidiskretisierungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7 Losung großer linearer Gleichungssysteme 72

7.1 Das Richardson-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 72

7.2 Das cg-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.3 Prakonditionierer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Page 4: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 3

1 Einleitung

Einige partielle Differentialgleichungen:

1. Eine Transportgleichung fur u = u(t, x):

(∂t + a(t, x, u) · ∂x)u = 0

Dies ist eine PDE erster Ordnung (d.h. enthalt nur erste Ableitungen). Ist u(0, x) gege-

ben und a = const, so ist eine Losung gegeben durch

u(t, x) = u(0, x− ta)

Die folgenden Gleichungen sind PDE’s zweiter Ordnung.

2. Die (eindimensionale) Wellengleichung, u = u(t, x):(∂xx −

1

c2∂tt

)u = 0, c2 > 0

Die Gleichung kann umformuliert werden in(∂x −

1

c∂t

)·(∂x +

1

c∂t

)u =(

∂x +1

c∂t

)·(∂x −

1

c∂t

)u = 0

Damit sind Funktionen der Form

u(t, x) = u0(x− t/c) und u(t, x) = u0(x+ t/c)

sowie Linearkombinationen Losungen. Die Differentialgleichung ist (unter gewissen Re-

gularitatsbedingungen) eindeutig losbar, wenn u(0, x) und ut(0, x) vorgegeben sind. Dies

ist ein Beispiel fur eine hyperbolische Differentialgleichung.

3. Die Poissongleichung fur u = u(x, y): Sei Ω beschranktes Gebiet.

(∂xx + ∂yy)u = −f auf Ω

Problem ist eindeutig losbar z.B. unter der Randbedingung u|∂Ω = 0. Losung ist dar-

stellbar z.B. mit Hilfe Greenscher Funktionen G(x, y|x1, y1) in der Form

u(x, y) =

∫Ω

f(x1, y1)G(x, y|x1, y1)dx1dy1

Page 5: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 4

Es handelt sich um eine elliptische Differentialgleichung.

4. Die Tricomi-Gleichung fur u = u(x, y) zur Berechnung von Uberschallstromungen:

(x∂xx + ∂yy)u = 0

Dies ist eine gemischte Gleichung vom hyperbolisch-elliptischen Typ.

5. Warmeleitungsgleichung fur u = u(t, x, y):

(∂t − ∂xx − ∂yy)u = q

Dies ist eine parabolische Differentialgleichung. Das Problem ist eindeutig losbar z.B.

wenn eine Anfangsbedingung u(0, x, y) = u0(x, y) gegeben ist. Die Losung kann z.B.

durch Fouriertransformation bzgl. x und y konstruiert werden. Dies fuhrt auf eine

gewohnliche Differentialgleichung in t.

Page 6: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 5

2 Elliptische Differentialgleichungen

2.1 Elliptische Differentialoperatoren zweiter Ordnung

Ω ⊆ lRn sei ein Gebiet. Auf Ω seien Funktionen ai,j, ai, a : Ω → lR definiert, sowie der

Differentialoperator L fur u ∈ C2(Ω) in x = (x1, . . . , xn)T

Lu(x) =n∑

i,j=1

aij(x) · ∂2

∂xi∂xju(x) +

n∑i=1

bi(x) · ∂∂xi

u(x) + c(x)u(x)

Wegen des Satzes von Schwartz konnen wir voraussetzen, dass aij = aji. (Andernfalls

ersetzen wir aij durch 0.5(aij +aji). Der Differentialoperator andert sich dadurch nicht.)

Fur festes x ∈ Ω definieren wir die Matrix A = A(x) = (aij(x))ni,j=1 sowie die quadrati-

sche Form

P (ξ) := ξTAξ fur ξ ∈ lRn

Da A symmetrisch ist, hat A nur reellwertige Eigenwerte.

(2.1) Definition: (a) L heißt elliptisch in x, falls alle Eigenwerte von A(x) das gleiche

Vorzeichen haben.

(b) Wir nehmen an (o.B.d.A.), dass fur alle x samtliche Eigenwerte positiv sind. Es sei

c(x) der kleinste Eigenwert von A(x). Die Konstante

m := infc(x)|x ∈ Ω

heißt Elliptizitatskonstante.

(c) Der Differentialoperator L heißt gleichmaßig elliptisch, falls m > 0.

(2.2) Beispiele: (a) Zum Laplace-Operator

Lu = ∆u = (∂x1,x1 + · · ·+ ∂xn,xn)u

gehort die Matrix A = I. Er ist damit elliptisch.

(b) Der n-dimensionale Wellenoperator fur (t,x)

Lu = (∆x − ∂tt)u

ist nicht elliptisch, da die zugehorige Matrix gegeben ist durch

A = diag(−1, 1, 1, . . . , 1)

Page 7: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 6

2.2 Elliptische Randwertprobleme

Der Rand ∂Ω des beschrankten Gebietes Ω ⊂ lRn werde mit Γ bezeichnet. Wir setzen

voraus, dass Γ regular ist (ohne dies formal exakt zu definieren). Regulare Rander sind

zum Beispiel solche, welche sich aus endlich vielen ”glatten” Randern zusammensetzen.

(”glatt” bedeutet, dass in jedem Punkt x der Normalenvektor n(x) existiert, und dass

die Abbildung n(.) stetig ist.) Demnach haben z.B. Kugeln, Rechtecke, Quader, Durch-

schnitte von Quadern etc. regulare Rander.

Ist φ eine Funktion auf Γ, so definieren wir Randbedingungen fur Funktionen u ∈ C2(Ω)

durch

(i) u|Γ = φ (Dirichlet-Randbedingung)

(ii) 〈n,∇xu〉|Γ = φ, wobei n der (außere) Normalenvektor an Γ in x ∈ Γ ist

(Neumann-Randbedingung).

(iii) Linearkombination aus (i) und (ii): 〈n,∇xu〉 + σ · u = φ fur x ∈ Γ (Robin-

Randbedingung)

(2.3) Definition: (a) Wir bezeichnen unter einem elliptischen Randwertproblem ein

Problem der Form

Lu(x) = f(x) fur x ∈ Ω

mit einem elliptischen Operator L sowie einer oben definierten Randbedingung fur u|Γ.

(b) Eine Abbildung u : Ω→ lR heißt klassische Losung des RWP, falls die Differential-

gleichung (punktweise) in jedem x ∈ Ω und die Randbedingung auf jedem (regularen)

Punkt x ∈ ∂Ω erfullt ist.

Fur den erfolgreichen Einsatz numerischer Verfahren ist es wichtig, Aussagen uber die

Existenz, Eindeutigkeit und Regularitat von Losungen zu kennen sowie uber die stetige

Abhangigkeit von Daten. Hierzu verweisen wir auf die parallel verlaufende Theorie-

Vorlesung. Zum Dirichlet-Problem zahlen wir einige Resultate ohne Beweis auf.

(2.4) Satz:1 Es sei c ≥ 0, das Gebiet Ω besitze einen regularen Rand, und die Daten f

und φ seien glatt (mindestens stetig). Dann besitzt das Dirichlet-RWP eine eindeutige

1vgl. [1, Satz 2.1]

Page 8: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 7

klassische Losung.

Einige negative Aussagen uber die Regularitat von Losungen ergeben sich aus den fol-

genden Ubungen.

(2.5) Ubungen: (a) Es sei Ω = (0, 1)× (0, 1). Zeigen Sie, dass die Losung des RWP

−∆u = 0 in Ω, u|Γ = x2

nicht zweimal stetig differenzierbar ist.

(b) Im L-Gebiet Ω = (−0.5, 0, 5) × (0.5, 0.5) \ [0, 0.5) × [0, 0.5) sei in Polarkoordinaten

das RWP

−∆u = 0 in Ω

u = r2/3 sin((2φ− π)/3) auf Γ

gegeben. Zeigen Sie, dass die Losung gegeben ist durch

u(r, φ) = r2/3 sin((2φ− π)/3),

und weisen Sie nach, dass u /∈ C1(Ω)

Sehr nutzlich ist die folgende Monotonieeigenschaft fur elliptische RWP.2

(2.6) Satz: Ω ⊂ lRn sei beschrankt, L gleichmaßig elliptisch. Fur v, w ∈ C(Ω) ∩ C2(Ω)

gelte

Lv(x) ≥ Lw(x) fur alle x ∈ Ω,

v(x) ≤ w(x) fur alle x ∈ Γ.

Dann gilt v(x) ≤ w(x) fur alle x ∈ Ω.

(2.7) Beispiel: Es sei Ω ⊂ [0, 2]× [0, 1]. u sei Losung des RWP

∆u = −1 in Ω

u = 0 auf Γ.

Wir suchen Abschatzungen fur u und definieren hierzu die Vergleichsfunktion

v(x, y) = (2− x)x/4 + y(1− y)/4.

2vgl. [1, Satz 2.3]

Page 9: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 8

Es gilt ∆u = ∆v in Ω und u ≤ v auf Γ. Damit ist v obere Schranke fur u auf Ω. Eine

untere Schranke ist w ≡ 0. (Warum?)

Im Zusammenhang damit steht eine Aussage, welche besagt, dass Extremwerte fur ge-

wisse Probleme immer am Rand angenommen werden (Maximumprinzip).

(2.8) Satz: L sei elliptisch mit konstanten Koeffizienten aij. Weiter gelte c(x) < 0 fur

alle x ∈ Ω. Erfullt eine nicht konstante Funktion u ∈ C2(Ω) die Gleichung Lu = f , so

gilt

– Ist f ≤ 0 in Ω, so hat u kein negatives Minimum in Ω

– Ist f ≥ 0 in Ω, so hat u kein positives Maximum in Ω

(Entsprechende Extremwerte werden also hochstens am Rand angenommen.)

(2.9) Ubung: Beweisen Sie das Maximumprinzip fur das eindimensionale Problem

u′′ = f auf dem Intervall Ω = (a, b).

Wir schließen mit einer Aussage zur stetigen Abhangigkeit von den Daten.

(2.10) Satz: L sei gleichmaßig elliptisch mit stetigen Koeffizienten. Erfullen u1, u2 ∈C2(Ω) ∩ C0(Ω) die Gleichungen Lui = fi in Ω und ui = φi auf Γ, so gilt

‖u1 − u2‖∞ ≤ ‖φ1 − φ2‖∞ +M · ‖f1 − f2‖∞.

Die Konstante M hangt hochstens von K := sup|aij|, |bi|, |c| sowie von der Ellipti-

zitatskonstante m und dem Durchmesser diam(Ω) ab.

Page 10: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 9

3 Differenzenschemata fur elliptische Gleichungen

3.1 Differenzenapproximationen

Wir betrachten die Differentialgleichung Lu = f mit

Lu(x) =n∑

i,j=1

aij(x) · ∂2

∂xi∂xju(x) +

n∑i=1

bi(x) · ∂∂xi

u(x) + c(x)u(x)

Mogliche Differenzenapproximationen fur ∂xi sind

die Vorwartsdifferenz ∂+i u(x) := (u(x+ hei)− ui(x))/h

die Ruckwartsdifferenz ∂−i u(x) := (u(x)− ui(x− hei))/hdie zentrale Differenz ∂0

i u(x) := (u(x+ hei)− ui(x− hei))/2h

Eine Approximation fur ∂2u/∂x2i ist

∂+i ∂−i u(x) =

1

h2(u(x+ hei)− 2u(x) + u(x− hei))

Gemischte zweite Ableitungen ∂2u/∂xi∂xj konnen approximiert werden durch

∂0i ∂

0ju(x) = ∂0

i

(1

2h[u(x+ hej)− u(x− hej)]

)=

1

4h2[u(x+ hej + hei)− u(x+ hej − hei)]− [u(x− hej + hei)− u(x− hej − hei)]

(3.1) Beispiel: Der Differentialoperator in zwei Dimensionen,

L = a11∂2x + 2a12∂x∂y + a22∂

2y + b1∂x + b2∂y + c

kann diskretisiert werden durch

a11∂+x ∂−x + 2a12∂

0x∂

0y + a22∂

+y ∂−y + b1∂

0x + b2∂

0y + c

Bei der Diskretisierung von Lu(x) sind insgesamt neun Punkte beteiligt. Die zugehorigen

Gewichte werden gewohnlich in einem ”neun-Punkte-Stern” wie folgt dargestellt.

1

h2

−a12/2 a22 a12/2

a11 −2(a11 + a22) a11

a12/2 a22 −a12/2

+1

2h

0 b2 0

−b1 0 b1

0 −b2 0

+

0 0 0

0 c 0

0 0 0

Page 11: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 10

Bemerkung: Aus numerischen Grunden kann die im Beispiel vorgestellte Diskretisierung

problematisch werden. Wir werden spater genauer darauf eingehen (vgl. Ubung 3.6).

(3.2) Ubungen: (a) Geben Sie zu allen oben vorgestellten Differenzenverfahren die

Approximationsordnung an.

(b) Finden Sie eine Differenzenapproximtion mindestens dritter Ordnung fur die ersten

partiellen Ableitungen ∂/∂xi .

(c) Leiten Sie eine Differenzenapproximation her fur ∆∆u. (Dieser Operator spielt zur

Behandlung elastischer Korper eine wichtige Rolle; vgl. Beispiel (4.25).)

(3.3) Ubung: (a) Gegeben sei das Dirichlet-RWP auf Ω = (0, 1)

u′′ = f in Ω, u(0) = α, u(1) = β.

Gewahlt seien die aquidistanten Stutzstellen

0 = x0 < x1 < · · · < xN < xn+1 = 1.

Stellen Sie ein lineares Gleichungssystem auf zur Bestimmung von ui := u(xi) fur i =

1, . . . , N .

(b) Nun seien nicht aquidistante Stutzstellen

0 = x0 < x1 < · · · < xN < xn+1 = 1

gegeben. Eine glatte bijektive Transformation ξ : [0, 1]→ [0, a] sei gegeben derart, dass

die Punkte ξi := ξ(xi) eine aquidistante Zerlegung von [0, a] darstellen. Transformieren

Sie das RWP aus (a) unter ξ und stellen Sie ein lineares Gleichungssystem zur numeri-

schen Losung auf.3

3.2 Diskretisierung eines Modellproblems

Wir wollen versuchen, das folgende RWP auf Ω = (0, 1)× (0, 1) zu diskretisieren.

∆u = f , u|Γ = φ.

Hierzu wahlen wir ein hinreichend großes N ∈ lN und definieren als Diskretisationspa-

rameter h := 1/(N + 1). Fur i, j = 0 . . . N + 1 definieren wir das aquidistante Gitter

uij := u(i · h, j · h) .

3Vgl. [3, Beispiel 3.1 (S. 38)].

Page 12: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 11

Die Werte ui,0, ui,N+1, u0,j, uN+1,j sind durch die Randbedingungen vorgegeben und da-

mit bekannt. Berechnet werden mussen also nur die Werte ui,j fur i, j ∈ 1, . . . , N.

Wir erhalten den folgenden 5-Punkte-Stern.

1

h2

0 1 0

1 −4 1

0 1 0

Zur Formulierung eines linearen Gleichungssystems mussen wir nun die Punkte (i, j)

in eine lineare Reihenfolge bringen. Dazu gibt es viele Moglichkeiten. Eine Moglichkeit

(lexikografische Ordnung) ist die zeilenweise Numerierung

(i, j)→ k(i, j) = (i− 1) + (j − 1) ·N + 1 fur 1 ≤ i, j ≤ N.

Die Abbildung

k : 1, . . . , N × 1, . . . , N → 1, . . . , N2

ist bijektiv. Wir identifizieren im Folgenden uij mit uk(i,j) =: uk und leiten ein Glei-

chungssystem fur u = (u1, . . . , uN2)T her. Fur (i, j) = (1, 1) ergibt sich aus

1

h2(u21 + u01︸︷︷︸

=φ01

+u12 + u10︸︷︷︸=φ10

−4u11) = f11

die Gleichung

u2 + uN+1 − 4u1 = h2f1 − (φ01 + φ10).

Fur i = 2, . . . , N − 1 erhalten wir mit k = i

uk+1 + uk−1 + uN+k − 4uk = h2 · fk − φ0i.

Der Punkt i = N wird ahnlich wie i = 1 behandelt.

Die Diskretisierung wird in diesem Sinn fortgefuhrt. Fur nicht-Randpunkte ergibt sich

die Gleichung

1

h2(uk+1 + uk−1 + uk+N + uk−N − 4uk) = fk.

Page 13: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 12

Das Ergebnis ist ein Gleichungssystem

Au = f

mit der Matrix A, welche die folgende Blockstruktur besitzt.

A =1

h2

T I

I T I. . . . . . . . .

I T I

I T

Hier ist I die N ×N -Einheitsmatrix und

T =1

h2

−4 1

1 −4 1. . . . . . . . .

1 −4 1

1 −4

.

(3.4) Eigenschaften: Fur A gilt:

Vorzeichen: Die Diagonalelemente sind negativ, die anderen nicht-negativ.

Diagonaldominanz: Es ist

|aii| ≥N2∑j=1j 6=i

|aij|.

Es gibt Zeilen, fur die strikte Ungleichheit gilt.

(3.5) Bemerkung: Anstelle der lexikografischen Ordnung sind auch andere Ordnungen

zur linearen Anordnung der Gitterpunkte ubleich, z.B.

Page 14: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 13

– das Diagonal-Abzahlverfahren, wie es bei der Abzahlung der rationalen Zahlen

ublich ist;

– das Schachbrettmuster (vgl. [2, S. 47]), bei dem zunachst die Punkte (i, j) in schwar-

ze und weiße Punkte getrennt werden und dann nacheinander schwarze und weiße

Punkte wie oben lexikographisch durchnumeriert werden. Dies fuhrt auf eine Matrix

A der Form

A =1

h2

(−4I B

BT −4I

).

Die Eigenschaften (3.4) bleiben erhalten.

(3.6) Ubung: Das RWP auf Ω = (0, 1)× (0, 1),

ε∆u+ b · ∇u = f auf Ω, u|Γ = φ

mit b = (2,−1)T soll auf dem oben definierten aquidistanten Gitter diskretisiert werden.

Welche Diskretisierung fur ∇u muss gewahlt werden, damit die Eigenschaften (3.4) fur

beliebige ε > 0 erhalten bleiben? Bestimmen Sie den 9-Punkte-Stern und fur N = 4 die

Matrix A fur das Gleichungssystem Au = f .

3.3 Diskretisierung von Randern

3.3.1 Das Dirichlet-Problem auf dem Einheitsquadrat

Zu Ω = (0, 1)2 betrachten wir das RWP

∆u = f, u|Γ = φ.

Wir definieren die Schrittweite wie vorher: h := 1/N . Definieren wir uij := u(i · h, j · h)

fur 0 ≤ i, j ≤ N , so stellen die uij (N + 1)2 Unbekannte dar. Hiervon gehoren (N − 1)2

Werte zu inneren Punkten, welche durch die Differentialgleichung bestimmt werden. Die

restlichen Punkte sind Randpunkte und damit durch die Randbedingung vorgegeben.

Aus der Diskretisierung der Differentialgleichung erhalten wir (N − 1)2 Gleichungen fur

(N − 1)2 Unbekannte.

Page 15: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 14

3.3.2 Das Neumann-Problem auf dem Einheitsquadrat

Zu Ω = (0, 1)2 betrachten wir das RWP

∆u = f,∂u

∂n

∣∣∣∣Γ

= n · ∇u|Γ = φ.

Zur Illustration greifen wir uns einen Punkt heraus: (0, k), 1 ≤ k ≤ N − 1. Die Diskre-

tisierung des Laplace-Operators in (0, k · h) fuhrt mit y := k · h auf

∆u(0, y) ≈ 1

h2[u(−h, y) + u(h, y) + u(0, y − h) + u(y + h)− 4u(0, y)].

Der Punkt (−h, y) liegt außerhalb des Definitionsbereichs. Damit ist u(−h, y) nicht

definiert. Ein Ausweg hierbei ist, den Quotienten

(u(−h, y)− u(h, y))/2h

als Approximation von ∂u/∂n aufzufassen und daher mit φ(0, y) gleichzusetzen. Dies

fuhrt auf den 4-Punkte-Stern in (0, y)

1

h2·

0 1 0

0 −4 2

0 1 0

.

Ahnlich kann u in Eckpunkten diskretisiert werden. Zum Beispiel gilt fur den Punkt

(0, 0) der 3-Punkt-Stern

1

h2·

0 0 0

0 −4 2

0 2 0

.

3.3.3 Das Dirichlet-Problem fur beliebige (glatte) Rander

Wir betrachten wieder das RWP

∆u = f, u|Γ = φ,

wobei diesmal Ω ⊂ lR2 ein beliebiges Gebiet mit hinreichend ”harmlosem” Rand ist. Die

Diskretisierung von Ω mit einer Schrittweite h > 0 fuhrt auf die Menge Ωh ⊂ Z2,

Ωh = (x, y) ∈ Ω|x/h ∈ Z, y/h ∈ Z.

Page 16: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 15

(3.7) Definition: Ein Punkt xR = (xR, yR)T ∈ Ω heißt Randpunkt, falls es einen Punkt

x ∈ Ωh und ein s ∈ (−h, h) derart gibt, dass xR = x + sex oder xR = x + sey. In diesem

Fall heißt x randnah.

A – Shortley-Weller-Diskretisierung

Eine Approximation von ∆u in randnahen Punkten beruht auf der folgenden Formel,

welche sich leicht aus der Taylorentwicklung ableiten lasst.

(3.8) Newtons dividierte Differenzen: Ist u : [xL, xR]→ lR dreimal stetig differen-

zierbar, so gilt fur x ∈ (xL, xR) mit h := (xR − xL)

u′′(x) =2

xR − xL·(u(xR)− u(x)

xR − x− u(x)− u(xL)

x− xL

)+O(h)

=2

xR − xL·(

1

xR − xu(xR) +

1

x− xLu(xL)

)− 2

(xR − x)(x− xL)· u(x) +O(h) .

(3.9) Ubung: Leiten Sie eine Formel fur das Restglied in Newtons dividierten Diffe-

renzen her.

Diese Formel wird angewandt im

(3.10) Differenzenschema von Shortley und Weller: Es sei x = (x, y) ein rand-

naher Punkt. sL, sR, sU , sO ∈ (0, 1] seien so gewahlt, dass (x − sLh, y), (x + sRh, y),

(x, y − sUh) und (x, y + sOh) Gitterpunkte oder Randpunkte sind. Dann wird ∆u(x)

approximiert durch durch

2

h2

(1

sR(sR + sL)u(x+ sRh, y) +

1

sL(sR + sL)u(x− sLh, y)

)+

2

h2

(1

sO(sO + sU)u(x, y + sOh) +

1

sU(sO + sU)u(x, y − sUh)

)− 2

h2·(

1

sLsR+

1

sUsO

)u(x)

Page 17: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 16

B – Interpolation

Eine weitere Moglichkeit besteht darin, den Wert u(x) fur randnahe Punkte x durch

lineare Interpolation zu gewinnen. Ist z.B. (x − sL, y) ein Randpunkt und (x + sR, y)

Gitterpunkt oder Randpunkt, so folgt mit linearer Interpolation

u(x) ≈ 1

sL + sR· (sLu(x+ sRh, y) + sRu(s− sLh, y).

Ebenso gilt

u(x) ≈ 1

sU + sO· (sUu(x, y + sOh) + sOu(x, y − sUh).

Addition beider Approximationen liefert

(3.11) Interpolationsschema:

1

h2

(1

sLu(x− sLh, y) +

1

sRu(x+ sRh, y)

)+

1

h2

(1

sUu(x, y − sUh) +

1

sOu(x, y + sOh)

)− 1

h2

(sL + sRsLsR

+sU + sOsUsO

)u(x) = 0

(3.12) Ubung: Auf Ω = (x, y) : x2 + y2 < 1 ist das RWP

∆u = f, u|Γ = φ

gegeben. Zur Diskretisierung wahlen wir das Gitter Ω25 ∩Ω, wobei Ω25 aquidistante 25-

Punkt-Diskretisierung von [0, 1]× [0, 1] ist. Welches sind die randnahen Punkte? Stellen

Sie ein lineares Gleichungssystem zur numerischen Losung des RWP auf.

3.4 M-Matrizen

Wie wir gesehen haben, fuhrt die Diskretisierung eines Randwertproblems zur Diffe-

rentialgleichung ∆u = f auf ein lineares Gleichungssystem der Form Ahuh = f . Wir

wollen nun die Regularitat von Ah, das Verhalten von A−1h fur h 0 und schließlich die

Konvergenz der diskreten Losungen uh gegen die Losung u des ursprunglichen Problems

Page 18: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 17

diskutieren. Von zentraler Bedeutung sind hierbei die Eigenschaften (3.4).

Im Folgenden sei I eine endliche Indexmenge, z.B. I = 1, . . . , N oder I = (i, j), 1 ≤i, j ≤ N. Vergleichsoperatoren zwischen |I| × |I|-Matrizen A = (aα,β)α,β∈I und B =

(bα,β)α,β∈I werden komponentenweise interpretiert. So bedeutet “A ≤ B”, dass fur alle

α, β ∈ I gilt aα,β ≤ bα,β. Die Aussage “A < B” bedeutet entsprechend, dass aα,β < bα,β

fur alle α, β ∈ I.

(3.13) Definition: Die Matrix A heißt M-Matrix, wenn gilt

(i) fur alle α ∈ I ist aα,α > 0; fur alle α, β ∈ I, α 6= β, ist aα,β ≤ 0;

(ii) A ist regular und hat eine Inverse A−1 ≥ 0.

Wir werden herleiten, dass Diskretisierungen elliptischer Gleichungen auf M -Matrizen

fuhren. Hierzu benotigen wir weitere Grundbegriffe.

(3.14) Definition: A sei Matrix wie oben, α und β seien Indizes aus I.

(a) α heißt direkt mit β verbunden, falls aα,β 6= 0.

(b) α heißt mit β verbunden, falls es eine Folge

α = α0, α1, . . . , αk−1, αk = β

gibt mit aαi,αi+16= 0 fur i = 0, . . . , k − 1.

(c) A heißt irreduzibel, falls jedes α mit jedem β verbunden ist.

(3.15) Beispiele: (a) Tridiagonalmatrizen

A =

α1 γ1

β2 α2 γ2

. . . . . . . . .

βn−1 αn−1 γn−1

βn αn

mit αi, βi, γi 6= 0 sind irreduzibel, denn es ist ai,i+1 6= 0 und ai,i−1 6= 0.

(b) 5-Punkte-Stern fur ∆ in Ω ⊂ lR2: Obere, untere, linke und rechte Nachbarn sind

direkt verbunden; die zugehorige Matrix ist irreduzibel.

Page 19: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 18

Im Folgenden bezeichne Kr(z) fur z ∈ lC und r > 0 den Kreis um z mit Radius r:

Kr(z) = ξ ∈ lC : |z − ξ| < r.

(3.16) Satz (Gerschgorin): A sei beliebige I × I-Matrix.

(a) Es sei rα =∑

β 6=α |aαβ|. Alle Eigenwerte von A liegen in⋃α∈I

Krα(aαα).

(b) Ist A irreduzibel, so liegen alle Eigenwerte in(⋃α∈I

Krα(aαα)

)∪

(⋂α∈I

∂Krα(aαα)

).

Beweis: Zu (a): Es sei Au = λu. O.B.d.A. sei u so gewahlt, dass ‖u‖∞ = max |uα| = 1.

Dann gilt fur ein γ ∈ I: |uγ| = 1. Es ergibt sich die folgende Argumentationskette.

λu = Au

⇒ λuγ =∑β∈I

aγβuβ

⇒ (λ− aγγ)uγ =∑β 6=γ

aγβuβ

⇒ |λ− aγγ| ≤∑β 6=γ

|aγβ| · |uβ| ≤∑β 6=γ

|aγβ| = rγ (∗)

⇒ λ ∈ Krγ (aγγ)

Zu (b): λ, u und γ seien wie oben gewahlt. Ist

λ /∈⋃α∈I

Krα(aαα),

so muss nach (a) gelten

λ ∈ ∂Krγ (aγγ)

Es folgt

|λ− aγγ| = rγ

Page 20: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 19

Damit gelten in der Abschatzung (∗) die Gleichheitszeichen. Insbesondere ist

|λ− aγγ| =∑β 6=α

|aγβ| · |uβ| =∑β 6=α

|aγβ|

Daher ist |uβ| = 1 fur alle β, welche mit γ direkt verbunden sind. Jedes β mit dieser

Eigenschaft erfullt die Voraussetzung, welche in (a) an γ gestellt wurde. Daher gilt

λ ∈ Krβ(aββ)

Ist nun β ein beliebiger Index, so ist β mit γ durch eine Kette α1, . . . , αk = β verbunden.

Durch Induktion folgt |uαi | = 1 sowie λ ∈ Krαi(aαiαi). ©

(3.17) Beispiel: Samtliche Eigenwerte von

A =

3 −1 5

2 2 2

−4 −2 2

liegen in der Vereinigung der Kugeln K6(3), K4(2) und K6(2).

(3.18) Definition: (a) A heißt strikt diagonal dominant, falls

∀α ∈ I :∑β 6=α

|aαβ| < |aαα|.

(b) A heißt irreduzibel diagonal dominant, wenn A irreduzibel ist und wenn außerdem

gilt

∀α ∈ I :∑β 6=α

|aαβ| ≤ |aαα|

∃α ∈ I :∑β 6=α

|aαβ| < |aαα|

(3.19) Beispiel: Vergleiche die Diskretisierung von ∆u auf (0, 1)2. Die zugehorige Ma-

trix ist irreduzibel diagonal dominant.

(3.20) Definition: Der Spektralradius ρ(A) einer Matrix A ist definiert durch

ρ(A) = max|λ|, λ Eigenwert von A

Page 21: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 20

Im Folgenden schreiben wir A in der Form A = D −B mit D = diagaαα, α ∈ I.

(3.21) Satz: A sei eine |I|× |I|-Matrix. Fur alle α ∈ I gelte aαα > 0 und fur alle β 6= α

aαβ ≤ 0.

(a) Falls ρ(D−1B) < 1, so ist A eine M-Matrix und

A−1 =

(∞∑n=0

(D−1B)n

)·D−1.

(b) Ist A strikt diagonal dominant oder irreduzibel diagonal dominant, so ist ρ(D−1B) <

1.

Beweis: zu (a): Wir definieren C := D−1B. Aus ρ(C) < 1 folgt, dass die Neumann-

Reihe

S :=∞∑ν=0

konvergiert.

(Ubung: Beweisen Sie dies fur symmetrische Matrizen C.)

Nach Voraussetzung (Vorzeichen der aαβ) sind D−1, B ≥ 0. Damit sind auch Cν ≥ 0

und S ≥ 0. Aus der absoluten Konvergenz folgt fur S

S · (I − C) =∞∑ν=0

Cν −∞∑ν=1

Cν = I,

also

I = S(I − C) = S(I −D−1B) = SD−1(D −B) = SD−1A ≥ 0 .

Damit ist A invertierbar und

A−1 = SD−1.

zu (b): Wie oben sei C = D−1B. Fur die Koeffizienten gilt

cα,α = 0, und fur β 6= α cαβ = −aαβ/aαα.

Nach dem Satz von Gerschgorin liegen alle Eigenwerte von C in⋃α∈I Krα(0).

Fall 1: A ist diagonaldominant. Dann ist

rα =1

|aαα|·∑β 6=α

|aαβ| < 1

Page 22: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 21

und damit ρ(C) < 1.

Fall 2: A ist irreduzibel diagonaldominant. Dann gilt fur alle β ∈ I : rβ ≤ 1, und es gibt

ein α ∈ I : rα < 1.

Falls gilt β ∈ I : rβ < 1, so ist ρ(C) < 1.

Nehmen wir an, es gebe ein γ ∈ I mit rγ = 1. Dann gilt⋂β∈I

∂Krβ(0) ⊆ ∂Krα(0) ∩ ∂Krγ (0) = ∅.

Nach dem Satz von Gerschgorin liegen daher alle Eigenwerte in der offenen Menge⋂β∈I

Krβ(0) = K1(0).

Damit ist ρ(C) < 1. ©

(3.22) Bemerkung: Es gilt auch die Umkehrung von Satz (3.21)(a): Ist A M -Matrix,

so ist ρ(D−1B) < 1.

Damit konnen wir Losungen des Gleichungssystems Ax = b abschatzen und ein Maxi-

mumprinzip fur die Inverse herleiten. Im Folgenden ist die Vektornorm ‖.‖∞ die Maxi-

mumnorm und die Matrixnorm ‖.‖∞ die Zeilensummennorm.

(3.23) Satz: A sei M -Matrix. Dann gilt

(a) Ist A irreduzibel so ist A−1 > 0.

(b) Definiere den Vektor l1 = (1, 1, . . . , 1)T . Ist w ein Vektor mit Aw ≥ l1, so ist

‖A−1‖∞ ≤ ‖w‖∞ .

(c) Ist A′ M -Matrix mit A′ ≥ A, dann ist 0 ≤ A′−1 ≤ A−1. Insbesondere ist ‖A′−1‖∞ ≤‖A−1‖∞.

Beweis: Zu (a): Wegen A−1 = (∑∞

n=0Cn) ·D−1 ist zu zeigen, dass

∑∞n=0 C

n > 0. Hierzu

reicht es zu zeigen dass fur alle Paare (α, β) ∈ I2 ein k existiert mit (Ck)αβ > 0.

Sei also (α, β) beliebig. Wegen der Irreduzibilitat gibt es eine Folge

α = α0, α1, . . . , αk = β (αi 6= αi+1)

mit aαi,αi+1> 0. Damit ist auch cαi,αi+1

> 0 und

(Ck)αβ =∑

γ1,...,γk−1

cαγ1cγ1γ2 · · · cγk−1β ≥ cαα1cα1α2 · · · cαk−1β > 0 .

Page 23: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 22

Zu (b): Es sei Aw ≥ l1. Zu u = (uα)α∈I , definieren wir |u| := (|uα|)α∈I . Wegen A−1 ≥ 0

folgt

|u| ≤ ‖u‖∞ · l1 ≤ ‖u‖∞ · Aw

⇒ |A−1u| ≤ A−1|u| ≤ ‖u‖∞A−1Aw = ‖u‖∞ ·w

⇒ ‖A−1u‖ ≤ ‖u‖∞ · ‖w‖∞

⇒ ‖A−1‖∞ = supu6=0

‖A−1u‖∞‖u‖∞

≤ ‖w‖∞ .

Zu (c): Aus A−1 ≥ 0, A′−1 ≥ 0 und A′ − A ≥ 0 folgt

A−1 − A′−1 = A−1A′A′−1 − A−1AA′−1 = A(A′ − A)A′−1 ≥ 0 . ©

3.5 Anwendung auf elliptische RWP’s

Die Uberlegungen des vorangehenden Abschnitts lassen sich leicht auf allgemeinere el-

liptische Operatoren ubertragen. Betrachten wir beispielsweise die Differentialgleichung

∆u+ b · ∇u = f

Die Diskretisierung von ∆ mittels Funfpunktstern und die ”korrekte” Differenzenappro-

ximation fur b · ∇ (im Sinne der Ubung (3.6)) fuhrt auf eine irreduzible diagonaldomi-

nante Matrix Lh = (lαβ) mit lαα < 0 und lαβ ≥ 0 fur α 6= β. Nach den Ergebnissen des

Abschnitts 3.4 ist damit −Lh eine M-Matrix, was die eindeutige Losbarkeit des diskre-

tisierten Dirichlet-Problems garantiert.

Betrachten wir nun den allgemeinen elliptischen Operator aus Definition (2.1). Offen-

sichtlich fuhrt die Diskretisierung aus Beispiel (3.1) nicht zu einer M -Matrix.

(3.24) Ubung: Es sei c ≤ 0 und |a12(x, y)| ≤ mina11(x, y), a22(x, y). Finden Sie

einen 7-Punkte-Stern fur den elliptischen Operator aus Beispiel (3.1), welcher zu einer

M -Matrix fuhrt.

Zu klaren sind noch die Fragen der Konvergenz numerischer Losungen fur h → 0,

die Kondition des linearen Gleichungssystems und Eigenschaften der diskretisierten

Losungen. Hierbei beschranken wir uns auf das Dirichlet-Problem auf Ω = (0, 1)2,

∆u = f, u|Γ = 0 (III.1)

Page 24: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 23

Mit Ωh bezeichnen wir das aquidistante Gitter zur Schrittweite h = 1/(N + 1). Die

numerische Losung auf Ωh bezeichnen wir mit uh. Außerdem bezeichne

‖u‖h = max|u(x, y)|(x, y) ∈ Ωh .

(3.25) Satz: Fur die Diskretisierung uh des Problems (III.1) gilt:

(a) Mittelwerteigenschaft:

uij =1

4(ui+1,j + ui−1,j + ui,j+1 + ui,j−1).

(b) Maximum-Minimum-Prinzip: Ist (uij)i,j∈I nicht konstant, so gilt

maxuij|i, j ∈ I < maxφ(x)|x ∈ Γ und minuij|i, j ∈ I > minφ(x)|x ∈ Γ.

(3.26) Ubung: Beweisen Sie Satz (3.25). Lassen sich die Ergebnisse auch auf Gebiete

mit gekrummten Randern verallgemeinern?

Es sei Lh die Matrix, welche aus der Diskretisierung eines elliptischen RWP’s entsteht.

Das numerische Verfahren heißt stabil, wenn fur ein Intervall H = (0, h0] (h0 > 0) gilt

suph∈H‖L−1

h ‖∞ <∞ .

(3.27) Ubung: Zeigen Sie fur die aquidistante Diskretisierung des RWP’s (III.1):

‖L−1h ‖∞ ≤

1

8.

(Hinweis: Benutzen Sie Satz (3.23)(b) und verwenden Sie als ”Vergleichsfunktion”w(x, y) :=

0.5 · x(1− x).)

Neben der Stabilitat des Verfahrens ist auch die Konsistenz wichtig. Ist u eine steti-

ge Funktion auf Ω, so bezeichne Rhu die Restriktion von u auf Ωh. Ist nun Lh die zum

Page 25: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 24

5-Punkte-Stern gehorige Matrix, so folgt fur u ∈ C4(Ω) aus der Taylorreihenentwicklung:

‖LhRhu−Rh∆u‖h ≤ C · h2 · ‖u(4)‖∞.

Wir bezeichnen daher Lh als konsistent mit der Ordnung 2.

(3.28) Satz: u sei die exakte Losung des Problems (III.1), uh sei die numerische Losung

auf dem Gitter Ωh. Das Verfahren ist konvergent von der Ordnung 2, d.h. es gilt

‖Rhu− uh‖h ≤ C · h2.

Beweis: Wir definieren wh := uh −Rhu. Aus

Lhuh = Rhf (diskretes System),

∆u = f und Rh∆u = Rhf (exakte Losung)

‖LhRhu−Rh∆u‖h = O(h2) Konsistenz)

folgt

Lhwh = Lhuh − LhRhu = Rhf − LhRhu

= Rhf −Rh∆u︸ ︷︷ ︸=0

+Rh∆u− LhRhu︸ ︷︷ ︸=O(h2)

= O(h2).

Die Behauptung folgt nun aus der Beschranktheit von ‖L−1h ‖∞. ©

Fur numerische Zwecke ist es wichtig, die Kondition der Matrix Lh zu untersuchen. Das

typische Verhalten ergibt sich schon aus dem eindimensionalen Modellproblem.

(3.29) Ubung: (a) Es sei h = π/(n+1). Zeigen Sie: Die Eigenvektoren der n×n-Matrix

Lh =

2 −1

−1 2 −1. . . . . . . . .

−1 2 −1

−1 2

sind

v(i) = (sin(ijh), j = 1, . . . , n) , i = 1, . . . n .

(b) Berechnen Sie die Kondition von Lh bezuglich der Norm ‖.‖∞. Wie verhalt diese

sich fur h→ 0?

Page 26: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 25

4 Variationsformulierung elliptischer RWP’s

4.1 Einfuhrungbeispiel

Wir betrachten das folgende Zweipunkt-Randwertproblem auf Ω = (0, 1):

−(a(x)u′(x))′ + b(x)u′(x) + c(x)u(x) = f(x), u(0) = g0, a(1)u′(1) = g1. (IV.1)

Sind a ∈ C1[0, 1] und b, c, f ∈ C[0, 1], so konnen wir vom klassischen Losungsbegriff

ausgehen und eine Funktion C2[0, 1] als klassische Losung bezeichnen, wenn sie in jedem

Punkt x ∈ [0, 1] die Differentialgleichung und an den Randern die Randbedingungen

erfullt.

(4.1) Ubung: Zeigen Sie, dass jede lineare Differentialgleichung 2. Ordnung

a(x)u′′(x) + b(x)u′(x) + c(x)u(x) = f(x)

mit a ∈ C1[0, 1] und b, c, f ∈ C[0, 1] sich auch in der Form schreiben lasst

−(a(x)u′(x))′ + b(x)u′(x) + c(x)u(x) = f(x)

mit geeigneten Funktionen a ∈ C1[0, 1] und b ∈ C(0, 1).

Variationsformulierung

Wir verfolgen nun ein alternatives Losungskonzept, welches den klassischen Losungsbe-

griff abschwacht und gleichzeitig erlaubt, auf der selben Grundlage als endlich-dimensionale

Variante mit den Finite-Elemente-Methoden ein numerisches Verfahren zu entwerfen.

Hierzu multiplizieren wir die Gleichung (IV.1) mit einer Testfunktion φ ∈ C1[0, 1] und

integrieren uber das Intervall [0, 1]. Fur das erste Integral erhalten wir mit partieller

Integration und durch Einsetzen der Randbedingungen∫ 1

0

−(au′)′φdx = − a(x)u′(x)φ(x)|10 +

∫ 1

0

au′φ′dx

= −g1φ(1) + a(0)u′(0)φ(0) +

∫ 1

0

au′φ′dx (IV.2)

Lassen wir als Testfunktionen nur Funktionen zu, welche die zusatzliche Bedingung

φ(0) = 0

Page 27: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 26

erfullen, so erhalten wir als Variationsformulierung des RWP’s (IV.1) die Gleichung∫ 1

0

[au′φ′ + bu′φ+ cuφ] dx =

∫ 1

0

fφdx+ g1φ(1) (IV.3)

fur beliebige Testfunktionen aus dem Raum

φ ∈ C1[0, 1] : φ(0) = 0 (IV.4)

Zwei Typen von Randbedingungen erkennen wir bei der Herleitung der Variationsfor-

mulierung. Die Bedingung am rechten Rand, a(1)u′(1) = g1, konnte in die partielle In-

tegration (IV.2) eingefugt werden. Bedingungen dieser Art nennen wir naturliche Rand-

bedingungen. Dagegen konnte die Bedingung u(0) = g0 nicht berucksichtigt werden.

Stattdessen mussten wir fordern, dass Testfunktionen am linken Rand verschwinden.

Randbedingungen dieser Art heißen wesentliche Randbedingungen; ihnen muss durch

die geeignete Wahl von Losungsraumen Rechnung getragen werden.

Schwache Ableitungen und Sobolev-Raume

Wir erkennen, dass in der Variationsformulierung die Ableitung u′ nur innerhalb ei-

nes Integrals und in Verbindung mit Testfunktionen vorkommt. Dies erlaubt die Ver-

allgemeinerung des Ableitungsbegriffs. Wir bezeichnen mit C∞0 (0, 1) die Menge aller

C∞-Funktionen auf (0, 1), deren Trager eine kompakte Teilmenge von (0, 1) ist. Durch

partielle Integration rechnen wir nach, dass fur beliebige u ∈ C1[0, 1] und φ ∈ C∞0 gilt∫ 1

0

u′(x)φ(x)dx = −∫ 1

0

u(x)φ′(x)dx (IV.5)

Wir benutzen diese Gleichung nun als Definitionsgleichung fur schwache Ableitungen.

Hierzu beschranken wir uns auf den Raum L2(0, 1) als Grundmenge von Funktionen.

(4.2) Definition: (a) Sei u ∈ L2(0, 1). Eine Funktion u′ ∈ L2(0, 1) heißt schwache

Ableitung von u, wenn (IV.5) gilt fur beliebige φ ∈ C∞0 (0, 1).

(b) Der Sobolev-Raum H1(0, 1) bezeichnet die Menge aller Funktionen u ∈ L2(0, 1),

welche eine schwache Ableitung u′ ∈ L2(0, 1) besitzen. H1(0, 1) heißt auch Sobolevraum

1. Ordnung.

(4.3) Ubung: (a) Auf Ω = [0, 1] sei die stetige und stuckweise lineare Funktion u(x)

definiert. Bestimmen Sie die verallgemeinerte erste Ableitung von u. Besitzt u eine zweite

Page 28: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 27

Ableitung?

(b) f : [0, 1]→ lR sei definiert durch

f(x) =

0 fur x ∈ lQ

1 fur x ∈ lR \ lQ.

Besitzt f eine verallgemeinerte erste Ableitung?

In der Funktionalanalysis wird gezeigt:

(4.4) Lemma: (a) H1(0, 1) ist ein Hilbertraum mit dem Skalarprodukt

(v, w)H1(0,1) =

∫ 1

0

v(x)w(x)dx+

∫ 1

0

v′(x)w′(x)dx

und der zugehorigen Norm

‖v‖H1(0,1) =√

(v, v)H1(0,1)

(b) C1(0, 1) ist bezuglich der H1-Norm dicht in H1(0, 1).

Der Spuroperator

Da Lp-Raume (und damit zunachst auch H1(0, 1)) nicht punktweise definiert sind, muss

genauer untersucht werden, in welchem Sinn Randbedingungen der Form u(ξ) = α fur

ξ ∈ 0, 1 interpretiert werden mussen. Die Schlusselbeobachtung liefert das folgende

Ergebnis.

(4.5) Lemma: Es gibt eine Konstante Ctr > 0 derart, dass fur alle v ∈ C1[0, 1] gilt

|v(0)| ≤ Ctr‖v‖H1(0,1)

Beweis: Aus der Identitat

v(0) = v(x)−∫ x

0

v′(y)dy

folgt mit Hilfe der Dreiecksungleichung und der Cauchy-Ungleichung

|v(0)| ≤ |v(x)|+∫ x

0

|v′(y)|dy ≤ |v(x)|+∫ 1

0

|v′(y)|dy ≤ |v(x)|+ ‖v′‖L2(0,1)

Page 29: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 28

Durch Integration folgt (mit (|a|+ |b|)2 ≤ 2(|a|+ |b|)2 fur beliebige a, b ∈ lR)

|v(0)| ≤∫ 1

0

|v(x)|dx+ ‖v′‖L2(0,1) ≤ ‖v‖L2(0,1) + ‖v′‖L2(0,1)

≤√

2(‖v‖2

L2(0,1) + ‖v′‖2L2(0,1)

)1/2

©

Aus dem Lemma folgt, dass die Abbildung

γ0 : C1[0, 1]→ lR, γ0(v) = v(0)

auf dem Teilraum C1[0, 1] von H1(0, 1) bezuglich der H1-Norm ein beschrankter Ope-

rator ist. Da C1[0, 1] in H1(0, 1) dicht ist, kann γ0 stetig auf ganz H1(0, 1) fortgesetzt

werden. γ0 : H1(0, 1)→ lR heißt Spuroperator.

Endgultige Formulierung des Variationsproblems

Nach diesen Vorbereitungen konnen wir das Randwertproblem vom Beginn dieses Ab-

schnitts umformulieren in ein Variationsproblem. Es sei

V := H1(0, 1)

der Grundraum mit dem Teilraum

V0 = v ∈ V |v(0) = 0

(Menge der Testfunktionen) und dem affinen Teilraum

Vg = v ∈ V |v(0) = g0

in welchem die Losung des RWP’s gesucht wird. Zu a, b, c ∈ L∞(0, 1), f ∈ L2(0, 1) und

g1, g1 ∈ lR definieren wir die Bilinearform a(., .) : V × V → lR,

a(v, w) =

∫ 1

0

[a(x)v′(x)w′(x) + b(x)v′(x)w(x) + c(x)v(x)w(x)]dx (IV.6)

und das lineare Funktional f : V → lR,

〈f, v〉 =

∫ 1

0

f(x)v(x)dx+ g1v(1) (IV.7)

Page 30: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 29

Entsprechend der obigen Herleitung erhalten wir folgendes

(4.6) Variationsproblem: Gesucht ist u ∈ Vg derart, dass

a(u, v) = 〈f, v〉 ∀v ∈ V0

(4.7) Ubung: Wandeln Sie das Randwertproblem

−u′′(x) = f(x) ∀x ∈ (0, 1), −u′(0) = g0 − α0u(0), u(1) = g1

um in ein Variationsproblem.

(4.8) Ubung: Zeigen Sie, dass u(x) =√

2x− x2 eine klassische Losung des RWP’s

−(a(x)u′(x))′ = 1 x ∈ (0, 1), u(0) = 0, a(1)u′(1) = 0

mit a(x) =√

2x− x2 ist, dass aber u /∈ H1(0, 1) und damit keine Losung des entspre-

chenden Variationsproblems ist.

Nachdem wir in Ubung (4.8) gesehen haben, dass eine klassische Losung nicht notwendig

eine schwache Losung ist, kehren wir die Frage um und betrachten eine schwache Losung

u ∈ Vg des Problems. Unter welchen Bedingungen ist diese eine klassische Losung?

Sei also u ∈ Vg eine schwache Losung. Wir nehmen an, dass a stetig differenzierbar

und b, c, f stetig sind sowie dass u zweimal stetig differenzierbar ist. Durch partielle

Integration erhalt man∫ 1

0

a(x)u′(x)v′(x)dx = a(x)u′(x)v(x)|10 −∫ 1

0

(a(x)u′(x))′v(x)dx

Wegen v(0) = 0 folgt aus der Variationsgleichung

a(1)u′(1)v(1) +

∫ 1

0

[−(a(x)u′(x))′ + b(x)u′(x) + c(x)u(x)] v(x)dx

=

∫ 1

0

f(x)v(x)dx+ g1v(1) (IV.8)

Wir wahlen zunachst Testfunktionen v ∈ C∞0 (0, 1) ⊂ V0. Dann ist insbesondere v(0) =

v(1) = 0. Es folgt∫ 1

0

[−(a(x)u′(x))′ + b(x)u′(x) + c(x)u(x)] v(x)dx =

∫ 1

0

f(x)v(x)dx

Page 31: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 30

Da C∞0 (0, 1) bezuglich der L2-Norm dicht in C[0, 1] liegt, folgt

−(a(x)u′(x))′ + b(x)u′(x) + c(x)u(x) = f(x) ∀x ∈ (0, 1) (IV.9)

Damit ist die Differentialgleichung erfullt und aus (4.8) folgt

a(1)u′(1)v(1) = g1v(1) ∀v ∈ V0

also die Randbedingung

a(1)u′(1) = g1

(4.9) Bemerkung: Bei der folgenden theoretischen Untersuchung des Variationspro-

blems ist es storend, dass i.A. V0 6= Vg. Es ist aber leicht einzusehen, dass es ein g ∈ Vgibt mit Vg = g + V0. Setzen wir u = u0 + g, so lasst sich das Variationsproblem (4.6)

umformulieren in ein aquivalentes

(4.10) Homogenisiertes Variationsproblem: Gesucht ist u0 ∈ V0 derart, dass fur

alle v ∈ V0

a(u0, v) = 〈f, v〉

wobei a(., .) wie in (IV.6) definiert, das lineare Funktional (IV.7) aber ersetzt ist durch

〈f, v〉 =

∫ 1

0

f(x)v(x)dx+ g1v(1)− a(g, v)

4.2 Der Satz von Lax-Milgram

Gegeben seien ein Hilbertraum V , eine Bilinearform a(., .) : V ×V → lR und ein lineares

Funktional 〈f, .〉 : V → lR. Untersucht werden soll das Variationsproblem: Gesucht ist

u ∈ V mit

a(u, v) = 〈f, v〉 ∀v ∈ V (IV.10)

Page 32: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 31

A – Der Rieszsche Darstellungssatz

Wir betrachten zunachst das spezielle Variationsproblem mit a(u, v) = (u, v)V (wobei

(., .)V das Skalarprodukt in V ist). Gesucht ist also u ∈ V mit

(u, v)V = 〈f, v〉 ∀v ∈ V (IV.11)

Dieses Problem lasst sich wie folgt als Minimumproblem formulieren.

(4.11) Lemma: Das Variationsproblem (IV.11) ist aquivalent zu folgendem Minimie-

rungsproblem: Gesucht ist u ∈ V derart, dass

J(u) = minv∈V

J(v) mit J(v) =1

2(v, v)V − 〈f, v〉 (IV.12)

Beweis:

J(u) = minv∈V

J(v)

⇔ J(u) ≤ J(u+ tw) ∀w ∈ V, t ∈ [0, 1]

⇔ J(u) ≤ J(u) + t[(u, v)− 〈f, v〉] +t2

2(w,w)V ∀w ∈ V, t ∈ [0, 1]

⇔ (u, v)V − 〈f, v〉+t

2(w,w)V ≥ 0 ∀w ∈ V, t ∈ [0, 1]

⇔ (u,w)V − 〈f, w〉 ≥ 0 ∀w ∈ V

Setzen wir w = v, so folgt

(u, v)V ≥ 〈f, v〉

wahrend mit w = −v folgt

(u, v)V ≤ 〈f, v〉 ©

Ist 〈f, .〉 : V → lR lineares Funktional, so definieren wir die Norm

‖f‖ := supv∈V \0

〈f, v〉‖v‖V

(IV.13)

Page 33: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 32

Den Raum der beschrankten linearen Funktionale auf V bezeichnen wir mit V ∗.

(4.12) Rieszscher Darstellungssatz: Sei V reeller Hilbertraum und f ∈ V ∗. Dann

gibt es eine eindeutige Losung u des Variationsproblems (IV.11) und es gilt ‖u‖V = ‖f‖.

Beweis: Das Funktional J ist nach unten beschrankt, denn

J(v) ≥ 1

2‖v‖2

V − ‖f‖‖v‖V =1

2(‖v‖V − ‖f‖)−

1

2‖f‖2 ≥ −1

2‖f‖2

Daher gibt es eine Folge (uk)k∈lN in V mit

J(uk)→ infv∈V

J(v) > −∞

(uk)k∈lN erfullt das Cauchy-Kriterium, denn wegen

‖uk − ul‖2V + ‖uk + ul‖2

V = (uk − ul, uk − ul)V + (uk + ul, uk + ul)V

= 2‖uk‖2V + 2‖ul‖2

V

ist

‖uk − ul‖2V = 2‖uk‖2

V + 2‖ul‖2V − ‖uk + ul‖2

V

= 4J(uk) + 4J(ul)− 8J

(uk + ul

2

)≤ 4J(uk) + 4J(ul)− 8 inf

v∈VJ(v)→ 0 fur k, l→∞

Da V vollstandig ist, konvergiert (uk) gegen einen Grenzwert u ∈ V . Aus der Stetigkeit

von J folgt

J(u) = limk→∞

J(uk) = infv∈V

J(v)

Sei u eine weitere Losung des Variationsproblems, also

(u, v)V = 〈f, v〉 ∀v ∈ V

Dann ist (u− u, v)V = 0 fur alle v ∈ V , also u = u. Außerdem ist

‖u‖V = supv∈V \0

(u, v)V‖v‖V

= supv∈V \0

〈f, v〉‖v‖V

= ‖f‖ ©

Page 34: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 33

Die Abbildung R : V ∗ → V , die jedem 〈f, .〉 ∈ V ∗ die Losung u ∈ V des Variations-

problems (IV.11) zuordnet, heißt Riesz-Isomorphismus. (Wir schreiben kurz Rf fur das

Bild von 〈f, .〉 unter R.) Offensichtlich ist R linear und es gilt

(Rf, v)V = 〈f, v〉 fur alle v ∈ V, 〈f, .〉 ∈ V ∗ (IV.14)

Wegen des Rieszschen Darstellungssatzes ist R bijektiv und Rf und 〈f, .〉 haben die

gleiche Norm. R ist daher ein isometrischer Isomorphismus, mit Hilfe dessen V ∗ und V

identifiziert werden konnen.

B – Der allgemeine Fall

Die Bilinearform a(., .) : V × V → lR heißt beschrankt, wenn es ein µ1 > 0 gibt derart,

dass

|a(w, v)| ≤ µ1‖v‖V ‖w‖V ∀v, w ∈ V (IV.15)

In diesem Fall ist fur beliebige w ∈ V die Abbildung v → a(w, v) ein Element von

V ∗. Wir bezeichnen mit A : V → V ∗ die Abbildung, welche jedem w ∈ V das lineare

Funktional a(w, .) zuordnet. Es gilt also

a(w, v) = 〈Aw, v〉 ∀v, w ∈ V (IV.16)

Mit dieser Schreibweise lasst sich das Variationsproblem (IV.10) umformulieren in

〈Au, v〉 = 〈f, v〉 ∀v ∈ V

welches wir als Operatorgleichung in V ∗ kurz schreiben als

Au = f (IV.17)

Ist τ ∈ lR \ 0, so lasst sich diese Gleichung mit Hilfe des Riesz-Isomorphismus leicht

umwandeln in die aquivalente Fixpunktgleichung in V

u = u+ τ · R(f − Au) (IV.18)

Wir definieren Gτ : V → V durch

Gτv := v + τ · R(f − Av)

Page 35: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 34

Die Existenz- und Eindeutigkeitsaussage des Satzes von Lax-Milgram beruht auf der An-

wendung des Banachschen Fixpunktsatzes auf dieses Fixpunktproblem. Hierzu benotigen

wir folgende Voraussetzung.

(4.13) Definition: Eine Bilinearform a(., .) : V × V → lR heißt elliptisch auf V (V -

elliptisch), wenn es eine Konstante µ2 > 0 gibt mit

a(v, v) ≥ µ2‖v‖2V ∀v ∈ V (IV.19)

(4.14) Satz von Lax-Milgram: Seien V reeller Hilbertraum und 〈f, .〉 ∈ V ∗. Die Bili-

nearform a(., .) auf V sei beschrankt und V -elliptisch mit Konstanten µ1, µ2 > 0 gemaß

(IV.15) und (IV.19). Dann existiert eine eindeutige Losung u des Variationsproblems

(IV.10) und es gilt

1

µ1

‖f‖ ≤ ‖u‖V ≤1

µ2

‖f‖ (IV.20)

Beweis: Wir betrachten das zu (IV.10) aquivalente Fixpunktproblem

u = Gτu

auf V mit

Gτ (v) = Mτv + gτ , Mτ = (I − τRA), gτ = τRf

Es ist

‖Gτ (w)−Gτ (v)‖V = ‖Mτ (w − v)‖V ≤ ‖Mτ‖‖w − v‖V

Um den Banachschen Fixpunktsatz anwenden zu konnen, genugt es zu zeigen, dass fur

geeignetes τ 6= 0 gilt ‖Mτ‖ < 1.

Fur v ∈ V ist

‖Mτv‖2V = (Mτv,Mτv)V = (v, v)V − 2τ(RAv, v)V + τ 2(RAv,RAv)V

Aus (IV.14), (IV.16) und den Voraussetzungen folgt

(RAv, v)V = 〈Av, v〉 = a(v, v) ≥ µ2‖v‖2V

Page 36: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 35

und

(RAv,RAv)V = ‖RAv‖2V = ‖Av‖2 = sup

w∈V \0

|〈Av,w〉|2

‖w‖2V

= supw∈V \0

|a(v, w)|2

‖w‖2V

≤ µ21‖v‖2

V

Daher ist mit p(τ) := 1− 2µ2τ + µ21τ

2

‖Mτv‖2V ≤ p(τ)‖v‖2

V ∀v ∈ V

(woraus p(τ) ≥ 0 fur alle τ folgt) und

‖Mτ‖ ≤√p(τ)

p nimmt sein Minimum in τ0 = µ2/µ21 an und es ist 0 ≤ p(τ0) = 1 − µ2

2/µ21 < 1. Aus

dem Banachschen Fixpunktsatz folgt nun die Existenz und Eindeutigkeit der Losung

des Variationsproblems. Die Abschatzungen ergeben sich aus

µ2‖u‖2V ≤ a(u, u) = 〈f, u〉 ≤ ‖f‖‖u‖V

und

‖f‖ = supv∈V \0

〈f, v〉‖v‖V

= supv∈V \0

a(u, v)

‖v‖V≤ sup

v∈V \0

µ1‖u‖V ‖v‖V‖v‖V

= µ2‖u‖V ©

C – Anwendung auf das Randwertproblem

Wir wollen untersuchen, ob der Satz von Lax-Milgram auf das zum RWP (IV.1) gehorige

homogenisierte Variationsproblem (4.10) anwendbar ist. Hierzu mussen die Beschrankt-

heit der Bilinearform a(., .) (vgl. (IV.6)) und des in (4.10) definierten Funktionals 〈f, .〉sowie die V -Elliptizitat von a(., .) uberpruft werden. Die Beschranktheit von a(., .) folgt

aus

|a(v, w)| =

∣∣∣∣∫ 1

0

[a(x)v′(x)w′(x) + b(x)v′(x)w(x) + c(x)v(x)w(x)]dx

∣∣∣∣≤ ‖a‖L∞(0,1)‖v′‖L2(0,1)‖w′‖L2(0,1) + ‖b‖L∞(0,1)‖v′‖L2(0,1)‖w‖L2(0,1)

+ ‖c‖L∞(0,1)‖v‖L2(0,1)‖w‖L2(0,1)

≤ (‖a‖L∞(0,1) + ‖b‖L∞(0,1) + ‖c‖L∞(0,1))︸ ︷︷ ︸=:µ1

‖v‖H1(0,1)‖w‖H1(0,1)

Page 37: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 36

Fur 〈f, .〉 ergibt sich die Beschranktheit aus

|〈f, v〉| =

∣∣∣∣∫ 1

0

f(x)v(x)dx+ g1v(1)− a(g, v)

∣∣∣∣≤ ‖f‖L2(0,1)‖v‖L2(0,1) + Ctr|g1|‖v‖H1(0,1) + µ1‖g‖H1(0,1)‖v‖H1(0,1)

mit der Konsequenz

‖f‖ ≤ ‖f‖L2(0,1) + Ctr|g1|+ µ1‖g‖H1(0,1)

(Man verwechsle nicht die beiden unterschiedlichen aber mit dem gleichen Symbol f

bezeichneten Objekte f ∈ L2(0, 1) als der rechten Seite der Differentialgleichung in

(IV.1) und das lineare Funktional 〈f, .〉 ∈ V ∗ !)

Zu uberprufen bleibt die V0-Elliptizitat von a. Dies werden wir hier nur fur den Spezialfall

a(x) = 1, b(x) = c(x) = 0 tun.

(4.15) Friedrichs-Ungleichung: Es gibt eine Konstante CF > 0 derart, dass

‖v‖L2(0,1) ≤ CF‖v′‖L2(0,1) fur alle v ∈ V0

Beweis: Sei v ∈ C1[0, 1] mit v(0) = 0. Aus

v(x) =

∫ x

0

v′(y)dy

folgt

|v(x)| ≤∫ x

0

|v′(y)|dy ≤∫ 1

0

|v′(y)|dy ≤ ‖v′‖L2(0,1)

Durch Integrieren folgt

‖v‖L2(0,1) ≤ CF‖v‖L2(0,1)

Fur beliebige v ∈ V0 folgt die Abschatzung aus der Tatsache, dass C1[0, 1] bezuglich der

H1-Norm dicht in H1(0, 1) ist. ©

Aus der Friedrichs-Ungleichung folgt

‖v′‖2L2(0,1) ≤ ‖v‖H1(0,1) = ‖v′‖2

L2(0,1) + ‖v‖2L2(0,1) ≤ (C2

F + 1)‖v′‖2L2(0,1)

Page 38: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 37

und damit

a(v, v) = ‖v‖2H1(0,1) ≥

1

C2F + 1

‖v‖H1(0,1)‖2

(4.16) Ubung: Gegeben sei das bilineare Funktional

a(v, w) =

∫ 1

0

[a(x)v′(x)w′(x) + b(x)v′(x)w(x) + c(x)v(x)w(x)]dx

des Einfuhrungsbeispiels. Weisen Sie die Elliptizitat von a(., .) in V0 = v ∈ H1(0, 1) :

v(0) = 0 (Teil (i)) bzw. in H1(0, 1) (Teil (ii)) unter jeder der folgenden Bedingungen

nach.

(i) Es ist a0 > 0, CF‖b‖L∞(0,1) < a0 und c0 > 0, wobei a0 = infx∈(0,1) a(x), c0 =

infx∈(0,1) c(x) und CF die Konstante aus der Friedrichs-Ungleichung ist.

(ii) a0 > 0, ‖b‖L∞(0,1) < 2√a0c0 und c0 > 0.

(4.17) Ubung: Wandeln Sie das RWP aus Ubung (4.7) um in ein homogenisiertes

Variationsproblem und uberprufen Sie, ob der Satz von Lax-Milgram anwendbar ist.

4.3 Variationsprobleme in N Dimensionen

Wir wollen die Untersuchungen fur das eindimensionale Einfuhrungsproblem nun auf

N -dimensionale Probleme ubertragen. Die Grundlage dafur ist die Green’sche Formel

(4.18) Greens Formel: Fur Gebiete Ω ⊂ lRN mit glattem Rand Γ, und fur u ∈ H2(Ω),

v ∈ H1(Ω) gilt ∫Ω

∆u · vdx = −∫

Ω

(∇u,∇v)dx+

∫Γ

∂u

∂n· vds

(wobei auf der rechten Seite (., .) das ubliche Skalarprodukt in lRN beschreibt). Hierbei

sind H1(Ω) und H2(Ω) entsprechend der folgenden Definition gegeben.

(4.19) Definition: (a) Sei α = (α1, . . . , αN) ∈ lNN0 ein Multiindex mit |α| :=

∑Ni=1 αi,

und Dαu = ∂α1x1· · · ∂αNxN u die zugehorige α-Ableitung einer Funktion u. Eine Funktion

w ∈ L2(Ω) heißt α-Ableitung einer Funktion u ∈ L2(Ω), falls fur alle v ∈ C∞0 (Ω) gilt∫Ω

wvdx = (−1)|α| ·∫

Ω

u ·Dαvdx. (IV.21)

Page 39: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 38

Wir schreiben hierfur kurz w = Dαu.

(b) Hk(Ω) ist der Raum aller Funktionen u ∈ L2(Ω), fur welche verallgemeinerte Ablei-

tungen Dαu existieren fur alle α mit |α| ≤ k.

In der Funktionalanalysis zeigt man: Mit dem Skalarprodukt

(u, v)k :=

∫Ω

∑|α|≤k

Dαu ·Dαv

dx

wird Hk(Ω) zum Hilbertraum.

Bei der Ubertragung des eindimensionalen Falles auf N Dimensionen beschranken wir

uns auf das folgende Beispiel (wobei Verallgemeinerungen kurz kommentiert werden).

(4.20) N-dimensionales RWP: Ω ⊂ lRN sei Gebiet mit stuckweise glattem Rand γ.

Es sei Γ = Γ1 ∪ Γ2 mit Γ1 ∩ Γ2 = ∅. Wir betrachten das RWP

−∆u+ cu = f in Ω, u|Γ1 = g,∂u

∂n+ pu = q auf Γ2 . (IV.22)

Ziel ist zunachst die aquivalente schwache Formulierung. Multiplikation der Differential-

gleichung mit einer Testfunktion v und Integration liefert nach Anwendung der Green-

schen Formel∫Ω

(∇u,∇v) + cuvdx+

∫Γ2

(pu− q)vds−∫

Γ1

∂u

∂nvds =

∫Ω

fvdx .

Wahlen wir als Raum der Testfunktionen

V0 := v ∈ H1(Ω) : v|Γ1 = 0 ,

so erhalten wir die Variationsformulierung∫Ω

(∇u,∇v) + cuvdx+

∫Γ2

(pu− q)vds =

∫Ω

fvdx . (IV.23)

Es kann gezeigt werden, dass fur u ∈ C2(Ω) und u|Γ2 = g, gilt

u erfullt (IV.22)⇔ u erfullt (IV.23) fur alle v ∈ V .

Page 40: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 39

Der Beweis der Richtung ” ⇒ ” ist unmittelbar klar. Die Umkehrrichtung benutzt

die Greensche Formel und den Satz von de la Vallee-Poussin, welcher besagt, dass die

Bedingung

∀v ∈ H10 (Ω) :

∫Ω

(∆u+ cu)vdx =

∫Ω

fvdx

fur u ∈ C2(Ω) hinreichend ist fur

∆u+ cu = f in Ω .

(4.21) Bemerkungen: (a) Die Randbedingung u|Γ1 = g in Beispiel (4.20) muss durch

einen entsprechenden Ansatz fur u sichergestellt werden (”Zwangsrandbedingung”).

Dagegen erscheint die Randbedingung auf Γ2 in der Variationsgleichung (”naturliche

Randbedingung”).

(b) Ist A = A(x) eine n× n-Matrix, so fuhrt die partielle Integration von

−∇ · (A∇u) = f

auf die Gleichung

−∫

Ω

(∇v, A∇u)dx−∫

Γ

(n,A∇u) · vds =

∫Ω

fvdx

Im zweiten Integral erscheint die ”konormale” Ableitung anstelle der Normalen-Ableitung

∂u/∂n.

Beim Ubergang von der klassischen Formulierung (4.20) des elliptischen RWP’s zur ho-

mogenisierten Variationsformulierung muss zunachst ein geeigneter Hilbertraum gewahlt

werden. Wie im eindimensionalen Fall (vgl. Bemerkung (4.9)) wahlen wir eine beliebi-

ge Funktion u ∈ H1(Ω), welche die Randbedingung u|Γ1= g erfullt. Mit dem Ansatz

u = u0 + u erhalten wir die

(4.22) Variationsformulierung: Es sei V0 = u ∈ H1(Ω) : u|Γ1= 0. Gesucht ist

u0 ∈ V0 derart, dass

a(u0, v) = 〈f, v〉 ∀v ∈ V0 (IV.24)

mit der bilinearen Abbildung a(., .) : V0 × V0 → lR,

a(u, v) =

∫Ω

[(∇u,∇v) + cuv]dx+

∫Γ2

puvds

Page 41: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 40

und dem linearen Funktional 〈f, .〉 ∈ V ∗0 ,

〈f, v〉 = −∫

Ω

[(∇u,∇v) + cuv]dx−∫

Γ2

(pu− q)vds+

∫Ω

fvdx

Um den Satz von Lax-Milgram auf dieses Problem anwenden zu konnen, mussen die

Beschranktheit von a(., .) und 〈f, .〉 sowie die V0-Elliptizitat von a(., .) zu zeigen. Auf

die entsprechenden Abschatzungen wollen wir hier verzichten.

Ahnlich wie Lemma (4.11) zeigt der folgende Satz die Aquivalenz des Variationsproblems

zu einem Extremalproblem.

(4.23) Satz: a(., .) sei V -elliptisch und symmetrisch (d.h. a(u, v) = a(v, u)). Dann

minimiert u ∈ V das Funktional

J(v) :=1

2· a(v, v)− 〈f, v〉

genau dann, wenn a(u, v) = 〈f, v〉 fur alle v ∈ V .

Beweis: ”⇐ ”: Aus

a(w,w)− a(u, u) = a(w + u,w − u) = 2a(u,w − u) + a(w − u,w − u)

folgt

J(w) =1

2· a(w,w)− 〈f, w〉

=1

2· a(u, u)− 〈f, u〉+ a(u,w − u)− 〈f, w − u〉︸ ︷︷ ︸

=0

+1

2a(w − u,w − u)︸ ︷︷ ︸

≥0

≥ J(u) .

” ⇒ ”: J(u) sei minimal. Wir nehmen an, es gebe ein v ∈ V mit a(u, v) 6= 〈f, v〉.O.B.d.A. nehmen wir an, dass a(u, v) < 〈f, v〉 und definieren fur t ∈ lR w(t) := u + tv.

Dann gilt aber fur hinreichend kleines t > 0

J(w(t)) = J(u) + t · (a(u, v)− 〈f, v〉) +1

2t2 · a(v, v) > J(u) ,

was im Widerspruch zur Voraussetzung steht. ©

(4.24) Ubung: Das RWP

Lu := uxx − (1 + x2)u = 1 in (−1, 1), u(−1) = u(1) = 0

Page 42: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 41

soll auf dem Raum V 2 gelost werden, welcher aufgespannt wird durch

b1(x) = 1− x2 , b2(x) = 1− x4 .

Finden Sie die Koeffizienten der Naherungslosung u, indem Sie

(i) das Gleichungssystem (Lu− 1,bi)L2(0,1) = 0 losen fur i = 1, 2,

(ii) das zugehorige Energiefunktional minimieren.

Wir wollen nun noch kurz zwei Beispiele anfuhren, welche in Anwendungen wichtig sind

und uber den oben gewahlten Ansatz hinausgehen.

(4.25) Beispiel (Biharmonische Gleichung): Auf Ω ⊂ lR2 sei das folgende RWP

gegeben

∆(∆u) = f in Ω, u|Γ =∂u

∂n

∣∣∣∣Γ

= 0 ,

welches die Durchbiegung einer fest eingespannten Platte unter einer Last f beschreibt.

Aus der Greenschen Formel folgt∫Ω

∆(∆u) · vdx = −∫

Ω

(∇∆u,∇v)dx+

∫Γ

∂(∆u)

∂n· vds

sowie ∫Ω

∆u ·∆vdx = −∫

Ω

(∇∆u,∇v)dx+

∫Γ

∆u · ∂v∂nds .

Damit ergibt sich∫Ω

∆(∆u) · vdx =

∫Ω

∆u ·∆vdx−∫

Γ

∆u · ∂v∂nds+

∫Γ

∂(∆u)

∂n· vds .

Als Funktionenraum wahlen wir V = H2(Ω)∩H10 (Ω). Fur v ∈ V gilt v|Γ = ∂v/∂n|Γ = 0

und daher die Variationsformulierung∫Ω

∆(∆u) · vdx =

∫Ω

∆u ·∆vdx =

∫Ω

fvdx .

Die zugehorige Bilinearform auf V ist

a(u, v) =

∫Ω

∆u ·∆vdx .

Page 43: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 42

Man kann zeigen, dass diese V -elliptisch ist. Nach Lax-Milgram existiert daher eine ein-

deutige Losung.

(4.26) Beispiel (Stokes-Problem): Das Stokes-Problem ist ein vereinfachtes Modell

einer inkompressiblen Stromung (Navier-Stokes-Gleichungen, wobei Tragheitskrafte ver-

nachlassigt werden). Im Folgenden sei Ω ein Gebiet in lRn, n ∈ 2, 3. Das RWP fur

die Stromungsgeschwindigkeit u = (u1 . . . un)T : Ω → lRn und den Druck p : Ω → lR+

lautet

−∆ui +∂

∂xip = fi, i = 1...n, in Ω (IV.25)

∇ · u =n∑i=1

∂xiui = 0, (IV.26)

ui|Γ = 0, i = 1...n . (IV.27)

Die Bestimmungsgleichung fur p ist implizit durch die Gleichung (IV.26) gegeben. Um

die Gleichung (IV.26) zu erzwingen, definieren wir als Funktionenraum

V := u ∈ (H10 )n|∇ · u = 0 .

Wir werden gleich sehen, dass dadurch die Beschreibung des Drucks unnotig wird. Die

Variationsformulierung mit v ∈ V fuhrt namlich auf∫Ω

(−∆u +∇p,v)dx =n∑i=1

∫Ω

(∇ui,∇vi)dx−∫

Ω

p · (∇ · v)dx

=n∑i=1

∫Ω

(∇ui,∇vi)dx =n∑i=1

∫Ω

fivi .

Die zugehorige Bilinearform lautet demnach

a(u, v) =n∑i=1

∫Ω

(∇ui,∇vi)dx

4.4 Ritz-Galerkin-Approximationen

Die Idee der Ritz-Galerkin-Approximation besteht darin, die Variationsgleichung bzw.

das Variationsproblem auf endlich-dimensionalen Unterraumen V N zu losen. Die Auf-

gabe

a(uN , vN) = f(vN)

Page 44: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 43

in V N fuhrt auf ein endlich-dimensionales lineares Gleichungssystem fur uN .

Dass endlich-dimensionale Losungen das ursprungliche Problem approximieren, zeigt

das folgende Ergebnis.

(4.27) Satz: a(., .) sei stetig V -elliptisch mit der Konstanten γ. Es gelte

|a(u, v)| ≤M · ‖u‖ · ‖v‖ .

V N sei ein endlich-dimensionaler Teilraum von V . Dann ist das Problem

a(uN , vN) = f(vN) ∀vN ∈ V N (IV.28)

fur alle f ∈ V ∗ eindeutig losbar. Ist u ∈ V die Losung von

a(u, v) = f(v) ∀v ∈ V , (IV.29)

so gilt

‖u− uN‖V ≤M

γ· infvN∈V N

‖u− vN‖ .

Beweis: Aus dem Lax-Milgram-Satz folgt, dass das Problem (IV.28) eine eindeutige

Losung uN hat. Aus

a(uN , vN) = f(vN) = a(u, vN)

folgt

a(u− uN , vN) = 0

und damit

a(u− uN , u− uN) = a(u− uN , u)− a(u− uN , uN) = a(u− uN , u)− a(u− uN , vN)

= a(u− uN , u− vN) .

a(., .) ist stetig und V -elliptisch. Hieraus folgt

γ · ‖u− uN‖2 ≤ |a(u− uN , u− vN)| ≤M · ‖u− uN‖ · ‖u− vN‖ . ©

Page 45: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 44

(4.28) Bemerkungen: (a) Ist (V N)N∈lN eine Folge mit V N ⊆ V N+1, und ist⋃N∈lN V

N

dicht in V , so gilt offensichtlich limN→∞ infvN∈V n ‖u− vN‖ = 0 und daher Konvergenz:

uN −→ u fur N →∞ .

(b) Ein lineares Gleichungssystem fur das diskretisierte elliptische Problem kann wie

folgt hergeleitet werden. Es sei b1, . . . ,bN eine Basis von V N . Mit dem Ansatz

uN =N∑i=1

sibi

fuhrt die Gleichung

a(uN , vN) = f(vN) ∀vN ∈ V N

auf das aquivalente System fur s = (si)Ni=1

ANsN = fN mit AN = (aij), aij = a(bi,bj), fN = (f(bi))Ni=1 . (IV.30)

(4.29) Beispiele: (a) Die schwache Formulierung des RWP’s

−u′′ = f in (0, 1), u(0) = u(1) = 0

in V = H10 (0, 1) lautet

a(u, v) = f(v) mit a(u, v) =

∫ 1

0

u′(x)v′(x)dx .

Als endliche Unterraume wahlen wir

V N = span(sin(jπx), j = 1, . . . , N) .

Mit der Basis bj = sin(jπx) gilt

a(bi,bj) =

0 falls i 6= j

π2 · j2/2 fur i = j.

Aus der Analysis ist bekannt, dass

limN→∞

(infv∈V N

‖u− v‖)

= 0 ∀u ∈ V .

Page 46: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 45

Damit ist das Verfahren konvergent.

(b) Wir modifizieren das RWP aus (a) wie folgt:

−u′′ = f in (0, 1), u(0) = u′(1) = 0.

Die zugehorige Bilinearform folgt aus der partiellen Integration:∫ 1

0

−u′′vdx = −u′v|10 +

∫ 1

0

u′v′dx .

Die Randbedingung u′(1) = 0 ist eine naturliche Randbedingung. Wir wahlen

V := v ∈ H1(0, 1) : v(0) = 0 .

Wahlen wir als Unterraume

V N = span(xj/j, j = 1, . . . , N) ,

so ist

aij = a(bi,bj) =1

i+ j − 1.

Dieses Verfahren ist numerisch nicht geeignet, da AN = (aij)1≤i,j≤N eine sehr schlechte

Kondition hat. Z.B. ist (in der Zeilensummennorm) fur N = 10 die Konditionszahl

cond(A) ≈ 1013. Daher sollten geeignetere Unterraume gesucht werden.

(4.30) Ubung: Gegeben ist das Neumann-RWP auf Ω = (0, 1)× (0, 1),

−∆u(x, y) = π2 cos(πx), ∂u/∂n|Γ = 0 .

Finden Sie die schwache Formulierung und berechnen Sie die Ritz-Galerkin-Naherung u

zur Basis b1(x) = x− 0.5, b2 = (x− 0.5)3.

Page 47: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 46

5 Methode der Finiten Elemente (FEM)

5.1 Ein einfuhrendes Beispiel

Bei der Konstruktion eines Ritz-Galerkin-Verfahrens spielt die Wahl der Ansatz- und

der Testfunktionen eine wichtige Rolle. Die Methode der finiten Elemente (FE) besitzt

folgende typischen Merkmale:

– Das Grundgebiet Ω wird in geometrisch einfache Teilgebiete zerlegt, z.B. (in

2D und falls moglich) in Rechtecke und/oder Dreiecke;

– Ansatzfunktionen mit Trager in einer kleinen Anzahl benachbarter Teilgebiete

werden konstruiert;

– Die Glattheitsbedingungen an die Losung des RWP werden durch die Wahl

der Ansatzfunktionen sichergestellt.

Dies soll an einem einfachen Beispiel erlautert werden.

(5.1) Beispiel: Es sei Ω ⊂ lR2 das durch

Ω = (x, y)T : x > 0, y > 0, x+ y < 1

definierte Dreieck. Gelost werden soll auf Ω das RWP (Poisson-Gleichung)

−∆u = f in ω, u|Γ = 0 ,

wobei f eine auf Ω stetige Funktion sei. Die schwache Formulierung wird in H10 (Ω)

formuliert und lautet∫Ω

∇u∇vdx =

∫Ω

fvdx fur alle v ∈ H10 (Ω) .

Zur Diskretisierung suchen wir eine geeignete Zerlegung Z = Ωjmj=1 von Ω. Dies ist

eine Menge von Teilmengen von Ω mit den Eigenschaften

Ω =m⋃j=1

Ωj ,Ωi ∩

Ωj= ∅ fur i 6= j .

Hierzu definieren wir zunachst fur ein N ∈ lN und h = 1/N ein aquidistantes Gitter

G = (kh, lh) : k, l ∈ Z sowie die Menge der hiervon zuΩ gehorigen Punkte GΩ = G∩

Ω.

Die Menge der achsenparallelen Geraden durch diese Punkte zerlegt Ω in Quadrate und

rechteckige Dreiecke, wie es fur N = 5 auf der Folie dargestellt ist. Es sei I = 1, . . . , p

Page 48: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 47

eine Indexmenge, welche die inneren Gitterpunkte abzahlt. Zu jedem dieser Punkte i ∈ Isoll eine stuckweise bilineare Ansatzfunktion bi ∈ H1

0 (Ω) definiert werden, welche ihren

Trager nur in der Vereinigung der zu i benachbarten Gebiete hat.

(5.2) Ubung: Losen Sie dieses Problem im eindimensionalen Fall: Finden Sie zu Ω =

(a, b) und den Gitterpunkten ih, i = 1, . . . , N − 1 mit h = 1/N stuckweise lineare

Ansatzfunktionen bi ∈ H10 (Ω) mit Trager in [(i− 1)h, (i+ 1)h].

In Beispiel (5.1) besitzen alle inneren Gitterpunkte als benachbarte Teilgebiete entweder

4 Quadrate oder 3 Quadrate und 1 Dreieck.

Fall 1: j wird von 4 Quadraten umgeben. In diesem Fall ist

bj(x, y) =

1h2 (h− |x− xj|)(h− |y − yj|) falls max|x− xj|, |y − yj| ≤ h

0 sonst

Fall 2: 3 Quadrate und 1 Dreieck.

bj(x, y) =

1h2 (h− |x− xj|)(h− |y − yj|) falls max|x− xj|, |y − yj| ≤ h

und minx− xj, y − yj ≤ 01h2 (h− x− xj)(h− y − yj) falls max|x− xj|, |y − yj| ≤ h

und minx− xj, y − yj ≥ 0

0 sonst

Alle diese Funktionen liegen in C0(Ω) und sind stuckweise bilinear, also von der Form

bj(x, y) = αxy + βx+ γy + δ.

Wir bezeichnen den durch diese Funktionen aufgespannten Funktionenraum bezeichnen

wir mit V N im Gegensatz zu V := H10 (Ω). Auf V definieren wir die Bilinearform

a(u, v) =

∫Ω

∇u∇vdx

und f ∈(V N)∗

durch

f(vN) =

∫Ω

fvdx .

Zur numerischen Losung des Ausgangs-RWP muss das Problem

a(uN , vN) = f(vN) fur alle vN ∈ V N

Page 49: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 48

gelost werden. Es genugt die Losung von

a(uN , bi) = f(bi) fur i = 1, . . . , p. (V.1)

Hierzu machen wir den Ansatz

uN =

p∑i=1

sibi

und definieren die Koeffizienten

aij = a(bi, bj),

welche wir zur Matrix A = (aij)1≤i,j≤p zusammenfassen. Schreiben wir noch s = (si)1≤i≤p

und c = (f(ei))1≤i≤p, so ist die Losung von (V.1) aquivalent zur Losung des linearen

Gleichungssystems

As = c .

Streng genommen ist in der obigen Ausfuhrung noch eine Lucke. Wir haben noch nicht

streng nachgewiesen, dass die bi wirklich in H10 (Ω) liegen. Wir wissen nur, dass sie in

C(Ω) liegen und bis auf die Rander ∂Ωi stetig differenzierbar sind. Hierzu fuhren wir

(ohne Beweis4) das folgende – allgemeinere – Ergebnis an.

(5.3) Lemma: Z = Ωi, i = 1, . . . , p sei eine Partition von Ω ∈ lRn, wobei Ωi regulare

Gebiete sind, in denen der Gaußsche Satz gilt.

(a) Fur z : Ω → lR sei die Bedingung z|Ωi ∈ C1(Ωi), i = 1, . . . , p erfullt. Dann gilt die

Implikation

z ∈ C(Ω) =⇒ z ∈ H1(Ω).

(b) Fur z : Ω→ lR gelte z|Ωi ∈ C2(Ωi), i = 1, . . . , p erfullt. Dann gilt die Implikation

z ∈ C1(Ω) =⇒ z ∈ H2(Ω).

4Ein Beweis findet sich in Großmann/Roos, Lemmata 4.1 und 4.2

Page 50: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 49

5.2 Finite Elemente fur Ω ⊂ lR2

5.2.1 Lineare Elemente

Ω ⊂ lR2 sei ein Polygon. Wir zerlegen Ω in Dreiecke T1, . . . , Tt.

(5.4) Definition: τ = T1, . . . , Tt heißt zulassige Triangulation von Ω, falls gilt:

∗ Ti(1 ≤ i ≤ t) sind offene Dreiecke;

∗ es ist Ti ∩ Tj = ∅ fur i 6= j; außerdem ist⋃t

1 T i = Ω;

∗ fur i 6= j ist T i ∩ T j entweder

– leer oder

– eine gemeinsame Seite von Ti und Tj oder

– eine gemeinsame Ecke von Ti und Tj.

Die Dreiecke Ti heißen finite Elemente; die Eckpunkte x der Ti heißen Knoten; hierbei

heißt x innerer Knoten falls x ∈ Ω und Randknoten falls x ∈ ∂Ω. N sei die Anzahl der

inneren Knoten, und

VN := u ∈ C0(Ω) : u|∂Ω = 0, u|Ti ist (affin) linear

Die Einschrankung einer Funktion u ∈ VN auf ein Element Ti lasst sich damit in der

Form schreiben

u(x, y) = ai1 + ai2x+ ai3y .

Nach Lemma (5.3)(a) ist VN Unterraum von H10 (Ω). Offenbar ist ein Element u ∈ VN

eindeutig bestimmt durch seine Werte an der inneren Knoten. Dine Basis fur VN lasst

sich leicht konstruieren.

(5.5) Lemma: xi (1 ≤ i ≤ N) seien die inneren Knoten von τ . Die Funktionen bi ∈ VNseien definiert durch bi(xj) = δij. Ist T ∈ τ ein Dreieck mit den Eckpunkten xi = (xi, yi),

x′ = (x′, y′) und x′′ = (x′′, y′′), so ist

bi(x, y) =(x− x′)(y′′ − y′)− (y − y′)(x′′ − x′)(xi − x′)(y′′ − y′)− (yi − y′)(x′′ − x)

auf T .

Auf allen T ∈ τ , welche xi nicht als Eckpunkt haben, verschwindet bi. B = bi : 1 ≤ i ≤t ist eine Basis von VN .

Page 51: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 50

Beweis: Ubung.

(5.6) Bemerkungen: (a) Der Trager der Basisfunktion bi ist

supp(bi) =⋃T : T ∈ τ hat xi als Ecke .

(b) Bi sei das Innere von supp(bi). Es gilt Bi ∩Bj = ∅ genau dann, wenn die Knoten xi

und xj nicht durch eine Kante verbunden sind.

(5.7) Beispiel: Es sei

a(u, v) =

∫Ω

∇u · ∇vdx

die zur Poission-Gleichung gehorende Bilinearform. Bei der Finite-Element-Diskretisie-

rung mittels einer konformen Triangulierung sind folgende Integrale zu berechnen:

Lij := a(bj, bi) =∑k

∫Tk

∇bj · ∇bidx . (V.2)

Hierbei ist die Integration uber die folgenden Dreiecke Tk zu erstrecken:

i = j: alle Tk mit xi als Ecke;

i 6= j: alle Tk mit xi und xj als Ecken.

Eine besonders regelmaßige Triangulation liegt vor, wenn Ω zunachst in gleich große

Quadrate und diese anschließend durch parallele Geradenstucke in Dreiecke zerteilt wer-

den. Diese Zerlegung heißt Quadratgittertriangulation.

(5.8) Ubung: Diskretisieren Sie das RWP auf Ω = (0, 1)2,

∆u = f , u|Γ = 0

mittels Quadratgittertriangulation. Welche Unterschiede bestehen zur Diskretisierung

mittels Differenzenquotienten?

Die Berechnung der Teilintegrale aus (V.2) erfolgt haufig durch Transformation auf ein

Referenzdreieck. Rechnen Sie hierzu nach:

(5.9) Ubung: Es sei T ∈ τ ; x1, x2 und x3 seien die Ecken von T . T sei das Referenz-

dreieck

T = (x, y) : x > 0, y > 0, x+ y = 1 .

Page 52: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 51

Zeigen Sie:

(a) Die Transformation

Φ : (ξ, η)→ x1 + ξ · (x2 − x1) + η · (x3 − x1)

bildet T auf T ab.

(b) Es gilt die folgende Transformationsregel:∫T

v(x, y)dxdy = [(x2 − x1)(y3 − y1)− (y2 − y1)(x3 − x1)] ·∫T

v(Φ(ξ, η))dξdη .

(5.10) Bemerkungen: (a) Die Methode der Finiten Elemente erlaubt lokale Verfeine-

rungen. Dadurch andert sich allerdings die Bandstruktur der Matrix L.

(b) Betrachten wir anstelle der Dirichlet-RB’s u|Γ = 0 die Neumann-Bedingungen

∂nu|Γ = 0, so mussen neben den inneren Knoten auch die Randknoten mit einbezo-

gen werden. Der Raum VN muss entsprechend erweitert werden.

5.2.2 Bilineare Elemente

Eine andere Art der Diskretisierung beruht auf Parallelogrammen anstatt auf Dreiecken.

Sei zunachst P = (x1, x2)×(y1, y2) ein achsenparalleles Rechteck. Eine bilineare Funktion

auf P ist definiert durch

u(x, y) = (a1 + a2x)(a3 + a4y) .

Ist nun P das Parallelogramm mit den Eckpunkten x1, x2, x3 und x4, so lasst sich das

Einheitsquadrat (0, 1)2 auf P transformieren durch

Φ : (ξ, η)→ x1 + ξ · (x2 − x1) + η · (x4 − x1) .

Eine bilineare Funktion u auf P ist definiert durch

u(x, y) = v(Φ−1(x, y)) mit v(ξ, η) = (α + βξ)(γ + δη) .

Die explizite Berechnung von v(Φ−1(x, y)) ist nicht notig, da sich alle Integrale auf das

Referenzquadrat zuruckfuhren lassen.

Ebenso wie im Fall von Dreiecken definieren wir nun zulassige Zerlegungen in Paralle-

logramme. Hierbei gelten die Formulierungen der Definition (5.4) sinngemaß.

Page 53: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 52

(5.11) Ubung: Ω = (0, 1)2 sei in 25 gleich große Quadrate unterteilt. Finden Sie eine

Basis des zu den Randbedingungen u|Γ = 0 gehorenden Finite-Elemente-Raums und

bestimmen Sie die zur Bilinearform

a(u, v) =

∫Ω

∇u · ∇vdx

gehorige Matrix.

5.2.3 Quadratische Elemente

Es sei τ eine zulassige Triangulierung von Ω. Soll die Dimension des Finite-Elemente-

Raums erhoht werden, so kann man beispielsweise auch stuckweise quadratische Funk-

tionen zulassen:

u(x, y) = ai1 + ai2x+ ai3y + ai4x2 + ai5xy + ai6y

2 auf Ti ∈ τ .

Der zugehorige Finite-Elemente-Raum ist dann

VN = u ∈ C0(Ω) : u|∂Ω = 0, u|Ti quadratisch .

Zu vorgegebenem T ∈ τ seien die Ecken xi, i = 1, 2, 3 und die Seitenmittelpunkte xi,

i = 4, 5, 6 gegeben. Leicht zu beweisen sind die folgenden Ergebnisse.

(5.12) Lemma: (a) Jede auf T quadratische Funktion u ist eindeutig durch die Werte

u(xi), i = 1, . . . , 6 bestimmt.

(b) Die Einschrankung einer quadratischen Funktion auf eine Seite von T ergibt ei-

ne eindimensionale quadratische Funktion; diese ist eindeutig bestimmt durch die drei

Funktionswerte auf dieser Seite.

(c)Ist u stetig in allen Knotenpunkten (d.h. Ecken und Seitenmittelpunkte) und qua-

dratisch in allen Ti, so ist u stetig auf Ω).

5.3 Finite Elemente mit Nebenbedingungen

Gelegentlich ist es notig, den Raum der Ansatzfunktionen durch Nebenbedingungen

einzuschranken.

(5.13) Beispiele: (a) Das Neumann-RWP

−∆u = g in Ω,∂u

∂n|Γ = 0

Page 54: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 53

ist nicht eindeutig losbar. Eindeutigkeit konnen wir erzwingen durch eine weitere Be-

dingung, z.B. ∫Ω

u(x)dx = 0 .

Der passende Funktionenraum ist dann

V =

u ∈ H1(Ω) :

∫Ω

u(x)dx = 0

.

Die Variationsformulierung lautet dann: Gesucht ist u ∈ V derart, dass

〈∇u,∇v〉 = g(v) ∀v ∈ V (V.3)

Wir nehmen an, dass eine Diskretisierung WN von W vorliegt, beispielsweise lineare

Finite Elemente zu einer Triangulierung τ mit einer Basis bi, i = 1, . . . , N. Der fur

unser Problem angemessene Raum ist aber

V N = w =N∑i=1

tibi :N∑i=1

ti〈bi, 1〉 = 0 (V.4)

Fur t = (ti)Ni=1 setzen wir

I(t) :=N∑i=1

ti〈bi, 1〉. (V.5)

Identifizieren wir die gesuchte Losung uN =∑N

i=1 sibi und Testfunktionen v =∑N

i=1 tibi

mit ihren Koeffizientenvektoren s = (si) bzw. t = (ti), so lautet das

Variationsproblem in V N : Gesucht ist s mit I(s) = 0 derart, dass

∑i

si

⟨∇bi,

∑j

tj∇bj

⟩=∑j

tjg(bj) ∀(tj) : I(t) = 0. (V.6)

(b) Wir betrachten das sog. Adler-Problem (0 < a ∈ lR)

−∆u+ au = g in Ω, u|Γ = const,

∫Γ

∂u/∂nds =

∫Γ

φds .

Ein angemessener Funktionenraum ist

V =u ∈ H1(Ω) : u konstant auf Γ

.

Page 55: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 54

Ist eine Triangulierung von Ω gegeben mit NR < N Randknoten x(1)R , . . . , x

(NR)R und

einer Basis b1, . . . , bN von V N , z.B. fur lineare Finite Elemente, so lasst sich die Zu-

satzbedingung durch folgende NR − 1 Nebenbedingungen beschreiben:

uN(x(k)R ) = uN(x

(k+1)R ), k = 1, . . . , NR − 1.

In beiden Fallen wird der Losungsraum durch lineare Zusatzbedingungen eingeschrankt.

Ein Ausweg konnte sein, eine neue Basis des diskretisierten Raums zu finden, durch

welche die Zusatzbedingungen automatisch erfullt sind. Dies ist jedoch haufig sehr

umstandlich. Wir behandeln hier dieses Problem auf eine alternative Art.

Allgemeiner Rahmen: Funktionenraum W = H1(Ω); Raum mit Zusatzbedingungen:

V := u ∈ W : u erfullt gewisse lineare homogene Zusatzbedingungen (V.7)

Zu losen sei das Variationsproblem auf V ,

a(u, v) = f(v), v ∈ V (V.8)

τ sei Triangulation von W ; WN sei der zugehorige Raum der linearen Finiten Elemen-

te mit Basis bi : i = 1, . . . , N. Wir nehmen an, dass sich die linearen homogenen

Zusatzbedingungen fur w =∑

j tjbj ∈ WN formulieren lassen in der Form

Ct = 0 (V.9)

mit t = (t1, . . . , tN)T und einer geeigneten MN × N -Matrix C, MN < N . Dann lautet

das

(5.14) Variationsproblem in V N = WN ∩ V : Gesucht ist u ∈ V N :

a(u,w) = f(w) ∀w ∈ WN (V.10)

Berucksichtigt man, dass fur u =∑

i sibi und w =∑

j tjbj gilt

u ∈ V N ⇔ s = (s1, . . . , sN)T ∈ ker(C) (V.11)

w ∈ V N ⇔ t = (t1, . . . , tN)T ∈ ker(C) (V.12)

Page 56: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 55

so lautet eine aquivalente Formulierung: Gesucht ist s = (s1, . . . , sN)T mit Cs = 0 so,

dass ∑i

sia(bi, w) = g(w) ∀w =N∑j=1

tjbj ∈ WN mit Ct = 0 (V.13)

Wir stellen dieser Formulierung eine alternative Formulierung gegenuber.

(5.15) Variationsproblem in WN mit Nebenbedingungen: Gesucht sind u =∑Ni=1 sibi ∈ WN mit Cs = 0 und λ = (λ1, . . . , λMN

)T so, dass fur alle w =∑N

i=1 tibi ∈WN

N∑i=1

sia(bi, w) + 〈λ,Ct〉 = f(w) (V.14)

Setzen wir w = bk (d.h. t = ek) und

A := (aij)Ni,j=1 = (a(bj, bi))

Ni,j=1, f = (fj)

Nj=1 = (f(bj))

Nj=1 (V.15)

so ergibt sich

(As)k + (CTλ)j = fk, (V.16)

zusammen mit der Nebenbedingung Cs = 0 also das zum Variationsproblem (4.15)

aquivalente lineare Gleichungssystem in lRN+MN[A CT

C 0

][s

λ

]=

[f

0

](V.17)

(5.16) Satz: Die Probleme (5.14) und (V.17) sind aquivalent in folgendem Sinn:

(a) Ist (s, λ) eine Losung des Problems (V.17), so ist u =∑

i sibi ∈ V N , und u ist Losung

des Variationsproblems (5.15).

(b) Ist u =∑

i sibi ∈ V N Losung von (5.15), so gibt es ein eindeutiges λ ∈ lRMN derart,

dass (V.17) erfullt ist.

Beweis: (a) Sei (s, λ) Losung von (V.17). Dann ist Cs = 0, also u =∑

i sibi ∈ V N . Fur

w =∑

j tibi mit Ct = 0 folgt außerdem a(u,w) = f(w).

(b) Sei u ∈ V N Losung von (5.15). Dann gilt fur t ∈ ker(C)∑j

tja(u, bj) =∑j

tjf(bj)

Page 57: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 56

also mit a := (a(u, bj))Nj=1

〈t, a− f〉 = 0

woraus mit B := CT folgt

a− f ∈ (ker(C))⊥ = (ker(BT ))⊥ = bild(B)

Damit existiert ein λ ∈ lRMN mit CTλ = Bλ = f − a. Damit ist fur t ∈ lRN

〈CTλ, t〉 = 〈f − a, t〉 = a(u,w)− f(w).

Die Eindeutigkeit von λ folgt aus rang(B) = MN , woraus folgt ker(B) = 0. ©

5.4 H1-Fehlerabschatzungen fur lineare Elemente

Im Folgenden seien Ω ⊂ lR2 ein Polygon, τ eine zulassige Triangulation und V = H1(Ω)

oder V = H10 (Ω). V N ⊂ V sei die Menge der linearen finiten Elemente bzgl. τ .

In Abschnitt 4.4 wurde gezeigt, dass fur V -elliptische Probleme gilt

‖u− uN‖V ≤ c · infv∈V N

‖u− v‖ =: c · dist(u, V N) .

Unter der Einschrankung u ∈ H2(Ω) kann dist(u, V N) abgeschatzt werden.

A – Abschatzung von dist(u, V N):

Das folgende Hilfsergebnis beruht auf Sobolevraum-Abschatzungen und soll hier nicht

bewiesen werden5 (vgl. hierzu Ubung (5.18)).

(5.17) Lemma: T sei ein beliebiges Dreieck mit den Ecken P1, P2 und P3. Fur i, j ∈1, 2, 3 sei |Pi − Pj| ≤ hmax. Alle Winkel seien nach unten durch α0 > 0 beschrankt.

Dann gibt es ein C(α0) derart, dass fur alle u ∈ H2(T ) und fur |β| ≤ 2

‖Dβu‖2L2(T )

≤ C(α0) ·

h2−2|β|max ·

3∑i=1

|u(Pi)|2 + h4−2|β|max ·

∑|α|=2

‖Dαu‖2L2(T )

.

5Fur einen Beweis vgl. Hackbusch, Lemmata 8.4.1, 8.4.2, 8.4.3

Page 58: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 57

(5.18) Ubung: Beweisen Sie Lemma (5.17) fur das Dreieck T = h · T mit dem Re-

ferenzdreieck T aus Ubung (5.9) und fur u ∈ C2(T ). (Uberlegen Sie sich zunachst

die entsprechenden Aussagen des Lemmas im Eindimensionalen, also fur ein Intervall

I = [a0, a1].)

(5.19) Satz: τ sei eine konforme Triangulierung von Ω. Die Seitenlangen aller Dreiecke

T ∈ τ seien nach oben durch h beschrankt, alle Winkel nach unten durch α0 > 0. Dann

existiert ein C(α0) derart, dass fur alle u ∈ H2(Ω) ∩ V und fur k ∈ 0, 1 gilt

infv∈V N

‖u− v‖Hk(Ω) ≤ C(α0)h2−k‖u‖H2(Ω) .

Beweis: Zu gegebenem u ∈ H2(Ω) ∩ V definieren wir v ∈ V N durch

v(x) :=∑

Knoten xi

u(xi)bi(x),

wobei bi die oben definierten linearen Elemente sind. Wegen der Linearitat verschwinden

in jedem Dreieck T ∈ τ alle zweiten Ableitungen; daher gilt fur |α| = 2

‖Dαv‖L2(T ) = 0.

Definieren wir w := u−v, so gilt w(xi) = 0 fur alle Knoten xi. Nach Lemma (5.17) folgt

fur |β| ∈ 0, 1

‖Dβw‖L2(Ω) =∑T∈τ

‖Dβw‖L2(T ) ≤ h4−2|β|C(α0)∑T∈τ

∑|α|=2

‖Dαu‖2L2(T )

= h4−2|β|C(α0)∑|α|=2

‖Dαu‖2L2(Ω) ≤ h4−2|β|C(α0)‖u‖2

H2(Ω) ©

B – Konvergenz uN → u in H1(Ω):

Es sei hν eine monotone Folge mit hν 0 und τν eine Folge von konformen Triangulie-

rungen von Ω mit Seitenlangen beschrankt durch hν . Samtliche Winkel seien nach unten

beschrankt durch α0 > 0. Die beiden folgenden Aussagen sind unmittelbare Folgerungen

aus Satz (5.19).

(5.20) Folgerung: Fur alle u ∈ H2(Ω) ∩ V und alle hν ist

infv∈Vhν

‖u− v‖H1(Ω) ≤ C(α0) · hν · ‖u‖H2(Ω) .

Page 59: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 58

(5.21) Folgerung: Die Bilinearform a(., .) erfulle die beiden Abschatzungen

|a(u, v)| ≤ CS‖u‖V ‖v‖V in V = H1(Ω),

|a(uν , vν)| ≥ CEν‖uν‖Vhν ‖vν‖Vhν in Vhν .

u ∈ H2(Ω) sei die Losung des Variationsproblems a(u, v) = f(v) in V . Sind die Konstan-

ten CEν durch eine Konstante CE > 0 nach unten beschrankt, so gibt es eine Konstante

C (unabhangig von u, hν und ν) mit

‖u− uν‖H1(Ω) ≤ C · hν · ‖u‖H2(Ω) . (V.18)

Die Voraussetzungen der Folgerung (5.21) garantieren die eindeutige Losbarkeit der Va-

riationsprobleme in H1(Ω) (Satz von Lax-Milgram) und nicht in H2(Ω). Damit konnte

die rechte Seite der Ungleichung (V.18) unbeschrankt sein. Es gilt aber der

(5.22) Satz: Sind die Voraussetzungen der Folgerung (5.21) erfullt, so hat das Varia-

tionsproblem eine eindeutige Losung, und es gilt

‖u− uν‖H1(Ω) → 0 .

Beweis: u ∈ H1(Ω) sei die eindeutige Losung des Variationsproblems in V . Wir wissen,

dass gilt

‖u− uν‖V ≤ C · dist(u, Vhν ) .

C ist unabhangig von CS und CE. Da H2(Ω) ∩ V dicht in V liegt, gibt es zu ε > 0 ein

uε ∈ H2(Ω) ∩ V mit

‖u− uε‖V ≤ ε/2 .

Aus Satz (5.19) folgt

infv∈Vhν

‖v − uε‖H1 ≤ C · hν · ‖uε‖H2 .

Page 60: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 59

Wird hν hinreichend klein gewahlt, so gilt

C · hν · ‖uε‖H2 ≤ ε/2

und daher

dist(u, Vhν ) ≤ ‖u− uε‖H1 + infv∈Vhν

‖v − uε‖H1 ≤ ε ©

Page 61: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 60

6 Parabolische Anfangs-Randwertprobleme

Parabolische Operatoren werden angewandt auf Funktionen u = u(t, x) mit dem Zeitpa-

rameter t ∈ [0, T ] und dem Ortsparameter x ∈ Ω ⊆ lRn (Ω sei Gebiet). Das parabolische

ARWP, welches wir hier betrachten, lautet

∂tu− Lu = f, u(0, x) = u0(x), u(t, x)|Γ = φ(t, x)

mit dem elliptischen Operator L. Γ ist der Rand von Ω. u0 und φ sind vorgegebene

Funktionen.

Viele Ideen zur Diskretisierung konnen von den elliptischen Gleichungen ubernommen

werden. Wir demonstrieren dies an einem einfachen eindimensionalen Beispiel.

6.1 Ein eindimensionales Problem

Es sei Ω = (0, 1) und der Zeitbereich wie oben (0, T ). Das Anfangs-Randwertproblem

lautet

ut − uxx = f in (0, T )× (0, 1), u(0, x) = u0(x), u(t, 0) = u0(t), u(t, 1) = u1(t) .

6.1.1 Differenzenapproximationen

Zur Diskretisierung definieren wir einen Ortsschritt h = 1/N und einen Zeitschritt τ

sowie xi := i ·h (i = 1 . . . N) und tj = j · τ . Die numerische Approximation von u(tk, xi)

bezeichnen wir mit uki .

Als Diskretisierung von uxx(xi) verwenden wir wie fruher die Differenzenapproximation

D+D−ui :=1

h2· (ui+1 − 2ui + ui−1) .

Als Approximation von ut(tk) konnen zum Beispiel der links- oder der rechtsseitige

Differenzenquotient dienen:

ut(tk) ≈ 1

τ· (u(tk)− u(tk−1)), ut(t

k) ≈ 1

τ· (u(tk+1)− u(tk)) .

Eine sinnvolle Klasse von Differenzenschemata fur f ≡ 0 konnte mit einem Para-

meter σ ∈ [0, 1] lauten

1

τ· (uk+1

i − uki ) = D+D−(σuk+1i + (1− σ)uki ) (VI.1)

Page 62: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 61

fur i = 1, . . . , N − 1, k = 1, . . . ,M − 1 mit den Anfangs-Randbedingungen

u0i = u0(xi), uk0 = u0(tk), ukN = u1(tk) .

(6.1) Beispiele: (a) Explizites Verfahren (σ = 0): Mit γ = τ/h2 ist

uk+1i = (1− 2γ)uki + γ(uki−1 + uki+1) + τfki .

Dieses Verfahren kann leicht in Zeitrichtung gelost werden.

(b) Rein implizites Verfahren (σ = 1):

(1 + 2γ)uk+1i − γ(uk+1

i+1 + uk+1i−1 ) = uki + τfki .

In diesem Fall muss zur Bestimmung des Zeitschritts k+1 ein Gleichungssystem ahnlich

wie im elliptischen Fall gelost werden.

(c) Crank-Nicolson-Verfahren (σ = 1/2):

2(γ + 1)uk+1i − γ(uk+1

i+1 − uk+1i−1 ) = 2(1− γ)uKi + γ(uki+1 + uki−1) + 2τf(tk + τ/2, xi) .

Da einseitige Differenzenquotienten fur ∂tu von der Ordnung τ und zentrale Quotienten

von der Ordnung von der Ordnung τ 2 sind, folgt durch Einsetzen in die Taylorreihe

leicht

(6.2) Satz: Der lokale Diskretisierungsfehler ist

– von der Ordnung O(h2 + τ) fur σ ∈ 0, 1 und u ∈ C2,4([0, T ]× [0, 1])

– von der Ordnung O(h2 + τ 2) fur σ = 1/2 und u ∈ C3,4([0, T ]× [0, 1]).

6.1.2 Stabilitat

A – Stabilitat bzgl. der Maximumnorm

Wir beschranken uns auf homogene Randbedingungen u0(t) = u1(t) = 0. Der Ansatz

(5.1) fur Differenzenschemata fuhrt auf das Gleichungssystem

−γσuk+1i−1 + (2σγ + 1)uk+1

i − σγuk+1i+1︸ ︷︷ ︸

=:(Auk+1)i

= F ki (VI.2)

Page 63: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 62

mit der rechten Seite

F ki = (1− σ)γuki−1 + (1− 2(1− σ)γ)uki + (1− σ)γuki+1 + τ fki .

Wir nennen ein Verfahren stabil, wenn die Losungskomponenten uki durch u0 und f in

geeigneter Weise abgeschatzt werden konnen. Das Gleichungssystem (5.2) wird beschrie-

ben durch die M-Matrix A. Es ist

(Al1)i =

1 fur i ∈ 2, . . . , n− 1

1 + σγ fur i ∈ 1, n

≥ 1.

Mit Satz (2.24)(b) folgt

‖uk+1‖∞ = ‖A−1F k‖∞ ≤ ‖F k‖∞ .

Setzen wir zusatzlich voraus

1− 2(1− σ)γ ≥ 0 (VI.3)

so folgt die Abschatzung

maxi|uk+1i | ≤ max

i|F ki | ≤ max

i|uki |+ τ max

i|fki |

und hieraus

maxk

maxi|uk+1i | ≤ max |u0(x)|+ τ ·

k∑j=0

maxi|f ji | .

(6.3) Definition: Das Verfahren heißt stabil, wenn (5.3) erfullt ist, wenn also gilt

τ

h2≤ 1

2 · (1− σ). (VI.4)

Die Stabilitatsbedingung koppelt die maximal mogliche Zeitschrittweite an die gewahlte

Ortsschrittweite. Fur die oben genannten Spezialfalle gelten die Beschrankungen

explizit (σ = 0): τ/h2 ≤ 1/2

rein implizit (σ 1): keine Beschrankung

Crank-Nicolson (σ = 1/2): τ/h2 ≤ 1

Page 64: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 63

Mit Hilfe der Konsistenzordnung (Satz (5.2)) und der Stabilitatsbedingung (5.4) kann

die Konvergenz des Verfahrens fur hinreichend glatte Losungen u bewiesen werden. Es

gilt der

(6.4) Satz: Es seien (1−σ)τ/h2 ≤ 1/2 und u ∈ C4,2([0, T ]×[0, 1]) sowie fki = (f(tk, xi).

Dann gilt

maxi,k|u(tk, xi)− uki | ≤ C(h2 + τ).

Fur das Crank-Nicolson-Verfahren gilt zusatzlich fur τ/h2 ≤ 1 und u ∈ C4,3([0, T ] ×[0, 1]) die Abschatzung

maxi,k|u(tk, xi)− uki | ≤ C(h2 + τ 2).

B – Stabilitatsuntersuchung nach von Neumann

Im Falle gewohnlicher Differentialgleichungen wurde die Stabilitat eines numerischen

Verfahrens mit Hilfe eines linearen Testproblems definiert. Wir gehen auch hier so vor

und betrachten als Testproblem das homogene System

∂tu− ∂xxu = 0, u(0, x) = u0(x), u(t, 0) = u(t, 1) = 0.

Exakte Losungen finden wir mit dem Separationsansatz

u(t, x) = v(x) · w(t).

Eingesetzt in das ARWP finden wir

v(x) · w′(t) = vxx · w(t),

also

w′

w=vxxv

=: −λ.

Das Problem

vxx = −λv , v(0) = v(1) = 0

Page 65: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 64

hat fur s = 1, 2, 3, . . . die Losungen

λ(s) = s2π2 , v(s)(x) = sin(sπx) .

Fur w erhalten wir aus w′ = −λ(s)w die exponentiell abklingende Losung w(t) = w(0) ·exp(−s2π2t). Die allgemeine Losung des ARWP lautet damit

u(t, x) =∞∑s=1

cs exp(−s2π2t) sin(sπx) .

Die Losung klingt gegen Null ab.

Die gleiche Technik konnen wir anwenden auf das Schema

uk+1i − ukiτ

= D+D−(σuk+1i + (1− σ)uki ), uk0 = ukN = 0, u0

i = u0(xi) .

fur den Losungsvektor

uk = (uk1, . . . uN)T .

(Es ist xi = i/(N + 1).) Eine Losung erhalten wir durch den Separationsansatz

uki = vi · wk .

Einsetzen liefert

wk+1 − wk

τ· vi = D+D−vi · (σwk+1 + (1− σ)wk)

oder – nach Trennung der Variablen –

wk+1 − wk

τ(σwk+1 + (1− σ)wk)=D+D−vi

vi=: −λ .

Es ist

D+D− =1

h2

−2 1

1 −2 1. . . . . . . . .

1 −2 1

1 −2

(VI.5)

D+D− hat die Eigenvektoren (s = 1, . . . , N)

v(s) =

(sin

isπ

(N + 1)

)Ni=1

Page 66: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 65

mit den Eigenwerten

−λ(s) = − 4

h2sin2 sπ

2(N + 1).

Man beachte, dass fur den großten Eigenwert gilt

λ(s)max = λ(N) ≈ 4

h2. (VI.6)

(6.5) Definition: Das Verfahren heißt stabil fur alle harmonischen Schwingungen,

wenn fur alle λ(s) gilt:

|wk+1| ≤ |wk| .

wk+1 wird bestimmt aus der Gleichung

wk+1 − wk = −λ(s)τ(σwk+1 + (1− σ)wk).

Es folgt die Stabilitatsbedingung∣∣∣∣1− λ(s)τ(1− σ)

1 + λ(s)τσ

∣∣∣∣ ≤ 1 , i = 1, . . . , N.

(6.6) Bemerkung: Explizit, σ = 0: Die Stabilitatsbedingung lautet

|1− λ(s)τ | ≤ 1 .

Mit (5.5) folgt hieraus die Schrittweitenbeschrankung

τ

h2≤ 1

2.

Reim implizit: Keine Beschrankung.

Crank-Nicolson: Keine Beschrankung.

Bezeichnet ‖.‖ die diskrete L2-Norm, d.h.

‖u‖2 = h ·N∑i=1

u2i ,

Page 67: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 66

so folgt aus uk = wk · v die Abschatzung

‖uk+1‖ = |wk+1| · ‖v‖ ≤ |wk| · ‖v‖ = ‖uk‖

und allgemein

‖uk‖ ≤ ‖u0‖ ∀k .

Wahrend der erste Stabilitatsbegriff die L∞-Norm betraf, haben wir hier eine Abschatzung

in der (schwacheren) L2-Norm.

(6.7) Ubung: Untersuchen Sie das Schema (Leapfrog-Schema)

uk+1i − uk−1

i − 2γ(uki−1 + uki+1) + 4γuki = 0

mit γ = τ/h2 zur Diskretisierung der homogenen Warmeleitungsgleichung auf Konsi-

stenz und Stabilitat (im von Neumannschen Sinn).

6.2 Semidiskretisierungen

Eine Moglichkeit der theoretischen Untersuchung numerischer Verfahren besteht in ei-

ner Zwischenstufe – der Semidiskretisierung, bei der die partielle Differentialgleichung

bezuglich der Ortsvariablen diskretisiert wird, wahrend die Zeitvariable kontinuierlich

bleibt.

(6.8) Beispiel: Wir betrachten die ARW-Aufgabe

ut − uxx = f(t, x) in (0, T )× (0, 1)

u(t, 0) = u(t, 1) = 0

u(0, x) = u0(x) .

Fuhren wir wie oben die Ortsdiskretisierung auf dem Gitter xi = i/(N + 1) ein, so

erhalten wir das System gewohnlicher Differentialgleichungen fur u = (u1, . . . , uN)T

∂tu = D+D−u + f ,

wobei D+D− durch (5.5) gegeben ist.

Page 68: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 67

Wir betrachten nun das allgemeinere ARWP

∂tu+ Lu = f in (0, T )× Ω

u = 0 auf (0, T )× ∂Ω

u(0, x) = u0(x) .

Hierbei ist L ein gleichmaßig elliptischer Differentialoperator. Unser Funktionenraum

im Ortsbereich ist V = H10 . Wie im elliptischen Fall wahlen wir wieder eine Variati-

onsformulierung. Es sei a(., .) die zu L gehorige Bilinearform. Als schwache Losung des

ARWP bezeichnen wir eine Funktion u(t, x) mit u(0, x) = u0(x), welche bezuglich t

stetig differenzierbar ist, fur jedes t ∈ [0, T ] in V liegt und fur die gilt

∂t〈u(t), v〉+ a(u(t), v) = 〈f(t), v〉 fur alle v ∈ V . (VI.7)

L soll gemaß der Idee des Ritz-Galerkin-Verfahrens diskretisiert werden. Hierzu nehmen

wir an, dass Vh ein endlich-dimensionaler diskretisierter Funktionenraum ist, und dass

eine Basis von Vh gegeben ist durch φ1, . . . , φM. Die Einschrankung von (5.7) auf Vh

fuhrt auf das Problem

∂t〈uh(t), vh〉+ a(uh(t), vh) = 〈f(t), vh〉 fur alle vh ∈ Vh . (VI.8)

Der Ansatz

uh(t, x) =M∑i=1

ui(t)φi(x)

fuhrt auf das Gleichungssystem

M∑i=1

u′i(t)〈φi, φj〉+M∑i=1

a(φi, φj) = 〈f, φj〉 , j = 1, . . . ,M .

Definieren wir die folgenden Abkurzungen

D = (dij , dij = 〈φi, φj〉,

A(= aij , aij = a(φi, φj),

f = (fi) , fi = 〈f, φi〉, u(t) = (uj),

so lasst sich das System kompakt darstellen als System gewohnlicher Differentialglei-

chungen

D(u(t))′ + Au(t) = f(t) .

Page 69: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 68

(6.9) Beispiel: Fur das ARWP des Beispiels (5.8) fuhrt die Diskretisierung mit linearen

finiten Elementen auf die Matrizen

D =h

6

4 1 · · · 0

1 4 · · · ...... · · ·· · · 4 1

0 · · · 1 4

, A =

1

h

2 −1 · · · 0

−1 2 · · · ...... · · ·· · · 2 −1

0 · · · −1 2

.

Insbesondere ist D keine Diagonalmatrix. Das Gleichungssystem unterscheidet sich da-

her von der semidiskretisierten Version von Beispiel (5.8).

Wir sehen uns zwei Fragestellungen genauer an.

A – Fehlerabschatzung.

Wie vorher sei V = H10 ; es gelte

a(u, u) ≥ α‖u‖2V α > 0 (VI.9)

|a(u, v)| ≤ M‖u‖V · ‖v‖V (VI.10)

∂t〈uh(t), vh〉+ a(uh(t), vh) = 〈f(t), vh〉 ∀vh ∈ Vh (VI.11)

Vh sei der Raum der linearen Finiten Elemente zu einer vorgegebenen zulassigen Trian-

gulation τ .

Zu u ∈ V ist durch fg(vh) := a(u, vh) ein Element des Dualraums V ∗h definiert. Wegen

der V -Elliptizitat von a(., .) ist das Problem

a(uh, vh) = g(vh) ∀vh ∈ Vh (VI.12)

eindeutig losbar. Wir schreiben fur die Losung uh =: Rhu. Der Operator Rh : V ∈ Vhheißt Ritzprojektion. Er ist linear und definiert durch die Bestimmungsgleichung

a(Rhu, vh) = a(u, vh) ∀vh ∈ Vh (VI.13)

Wir wollen nun eine Abschatzung bzgl. der L2-Norm

‖u‖ :=√〈u, u〉 (VI.14)

Page 70: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 69

fur den Fehler u− uh finden. Der Trick besteht in der folgenden Aufspaltung

u− uh = (u−Rhu) + (Rhu− uh) (VI.15)

und in der Abschatzung der beiden Summanden.

Schritt 1: Die Ritzprojektion. Sei u ∈ V fest. Mit g(v) := a(u, v) sind u und Rhu = uh

Losungen von

a(u, v) = g(v) ∀v ∈ V (VI.16)

a(uh, vh) = g(vh) ∀vh ∈ Vh (VI.17)

d.h. die Bestimmungsgleichung fur uh ist die diskretisierte Version der Gleichung fur u.

Aus Satz (3.16) folgt

‖u−Rhu‖ ≤ ‖u−Rhu‖V ≤M

α· distV (u, Vh) (VI.18)

mit distV (u, Vh) = infvh∈Vh‖u − vh‖V . Ist ‖u‖ ∈ H2 ∩ V , so ergibt sich mit Folgerung

(4.21) die Abschatzung

‖u−Rhu‖ ≤ C · h · ‖u‖H2 . (VI.19)

Schritt 2: Zweiter Summand. Mit Rhu− uh =: ρ gilt

〈ρt, vh〉 = 〈∂t(Rhu), vh〉 − 〈∂tuh, vh〉︸ ︷︷ ︸=−a(uh,vh)+〈f,vh〉

(VI.20)

a(ρ, vh) = a(Rhu, vh)− a(uh, vh) = a(u, vh)− a(uh, vh) (VI.21)

und damit

〈ρt, vh〉+ a(ρ, vh) = 〈∂t(Rhu), vh〉−〈f, vh〉+ a(u, vh)︸ ︷︷ ︸=−〈∂tu,vh〉

(VI.22)

= 〈∂t(Rhu− u), vh〉 ∀vh ∈ Vh (VI.23)

Setzen wir in dieser Gleichung vh := ρ, so folgt mit

∂t‖ρ‖2 = 2〈ρt, ρ〉 (VI.24)

Page 71: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 70

der V -Elliptizitat

a(ρ, ρ) ≥ α‖ρ‖2 (VI.25)

und der Schwarzschen Ungleichung

1

2∂‖ρ‖2 + α‖ρ‖2 ≤ ‖∂t(Rhu− u)‖ · ‖ρ‖ (VI.26)

bzw. nach Division durch ‖ρ‖

∂t‖ρ‖+ α‖ρ‖ ≤ ‖∂t(Rhu− u)‖ (VI.27)

Setzen wir

µ(t) := exp(αt) · ‖ρ(t)‖, (VI.28)

so folgt

∂tµ ≤ exp(αt)‖∂t(Rhu− u)‖ (VI.29)

was zur Abschatzung

µ(t) ≤ µ(0) +

∫ t

0

exp(αs)‖∂t(Rhu− u)(s)‖ds (VI.30)

und damit zu

‖ρ(t)‖ ≤ exp(−αt)‖ρ(0)‖+

∫ t

0

exp(−α(t− s))‖∂t(Rhu− u)(s)‖ds (VI.31)

fuhrt. Den ersten Summanden auf der rechten Seite konnen wir mit Hilfe von Schritt 1

abschatzen durch

‖ρ(0)‖ = ‖Rhu(0)− uh(0)‖ ≤ ‖u0 − u0h‖+ ‖Rhu

0 − u0‖︸ ︷︷ ︸≤CdistV (u0,Vh)

≤ ‖u0 − u0h‖+ C · h · ‖u0‖H2

Ebenso ist – falls ∂tu =: ut ∈ H2

‖∂t(Rhu− u)‖ = ‖Rhut − ut)‖ ≤ C · h · ‖ut‖H2 (VI.32)

woraus fur ‖ρ(t)‖ folgt

‖ρ(t)‖ ≤ exp(−αt) · ‖u0 − u0h‖

+C · h ·(

exp(−αt) · ‖u0‖H2 +

∫ t

0

exp(−α(t− s))‖ut(s)‖H2ds

)

Page 72: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 71

Schritt 3: Zusammenfassung. Die Zusammenfassung der ersten beiden Schritte ergibt

‖u(t)− uh(t)‖ ≤ exp(−αt) ·(‖u0 − u0

h‖+ C · h · ‖u0‖H2

)(VI.33)

+C · h ·(‖u(t)‖H2 +

∫ t

0

exp(−α(t− s))‖ut(s)‖H2ds

)(VI.34)

Auffallig ist hierbei, dass der Anfangsfehler exponentiell abklingt. Dies ist eine Folge

der V -Elliptizitat von a(., .) und der damit verbundenen Glattungseigenschaft des ellip-

tischen Operators L.

B – Lumping-Technik.

Bei der praktischen Berechnung des gewohnlichen DGl-Systems

D(u)′ + Au = f (VI.35)

stort, dass D keine Diagonalmatrix ist. Wir modifizieren daher das System.

Sei Pi ein beliebiger innerer Knoten der Triangulation τ , φi die Basisfunktion mit

φi(Pi) = 1 und

τi := T ∈ τ : T ⊆ supp(φi) (VI.36)

Dann ist

dij = 〈φi, φj〉 =∑T∈τi

∫T

φi(x)φj(x)dx (VI.37)

Fur lineare Finite Elemente mit dem Lebesgue-Maß λ∫T

φi(x)φj(x)dx =

λ(T )/12 i = j

λ(T )/6 i 6= j(VI.38)

Eine Naherungsformel erhalten wir, wenn wir fur Integrale der Form∫Tf(x)dx die Qua-

draturformel verwenden

I(f) :=1

3

∑Knoten P

f(P ) · λ(T ) (VI.39)

wobei summiert wird ¨ber die drei Knoten von T . Nach Definition der φi ist

I(φiφj) =

λ(T )/3 i = j

0 i 6= j(VI.40)

Page 73: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 72

Definieren wir die Matrix D = (dij) durch

dij =∑T∈τi

I(φiφj) (VI.41)

so finden wir, dass

dij =

∑j dij i = j

0 i 6= j(VI.42)

Diese Technik wird Lumping-Technik genannt (to lump = in einen Topf werden). Fur

die Losungen dieser Modifikation konnen ahnliche Abschatzungen gefunden werden wie

im ursprunglichen Fall (bei linearen Finiten Elementen).

7 Losung großer linearer Gleichungssysteme

Kennzeichen der bei elliptischen Problemen entstehenden Gleichungssysteme: Sie sind

groß, dunn besetzt, gelegentlich symmetrisch. Da das Gaußsche Eliminationsverfahren

einen Rechenaufwand von O(n3) hat, ist sein Einsatz zumindest in der ursprunglichen

Form nicht moglich. Zudem liegt die Systemmatrix haufig – z.B. bei der Verwendung

unstrukturierter Gitter – gar nicht in geschlossener Form vor, so dass eine LU -Zerlegung

nicht mgloch ist. Als weitaus praktikabler erweisen sich in den Anwendungen diverse

iterative Losungsverfahren. Wir wollen ihre Anwendung zur Losung von

Ax = b (VII.1)

diskutieren.

7.1 Das Richardson-Verfahren

Wir wandeln zunachst die Gleichung in eine aquivalente Fixpunktgleichung um.

x = x+ τ(b− Ax) = Gτ (x) (VII.2)

mit

Gτ (y) = Mτy + gτ , Mτ = I − τA, gτ = τb (VII.3)

Gelost wird dies durch Fixpunktiteration

xk+1 = Gτ (xk) = Mτxg + gτ = xk + τ(b− Axk) (VII.4)

welche in zwei Schritten durchgefuhrt wird:

Page 74: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 73

Gegeben xk,

– berechne das Residuum rk = b− Axk– berechne neue Iterierte xk+1 = xk + τrk

Konvergenzanalyse

Auf lRn gegeben seien ein Skalarprodukt (beliebiges) (., .) und die zugehorige Norm

‖y‖ =√

(y, y). Wir definieren die Bilinearform a(., .) und das Element 〈f, .〉 des Dual-

raums durch

a(z, y) = (Az, y), 〈f, y〉 = (b, y). (VII.5)

Das Gleichungssystem Ax = b ist aquivalent zu

a(x, y) = 〈f, y〉 ∀y ∈ lRn (VII.6)

Eng verbunden mit dem Satz von Lax-Milgram (vgl. Beweis in Zulehner) ist das folgende

Ergebnis.

(7.1) Satz: (a) Es gelte

1. Es gebe µ1 > 0 mit

(Ay, y) ≥ µ1‖y‖2 ∀y ∈ lRn (VII.7)

2. Es gebe µ2 > 0 mit

(Az, y) ≤ µ2‖z‖ · ‖y‖ z, y ∈ lRn (VII.8)

Dann konvergiert das Richardson-Verfahren fur τ ∈ (0, 2µ1/µ22), und fur τ = µ1/µ

22 gilt

‖xk+1 − x‖ ≤ q‖xk − x‖, q =

√1− 1

κ2, κ =

µ2

µ1

(VII.9)

(b) A sei selbstadjungiert und positiv definit bzgl. des Skalarprodukts (., .), und

µ1 · (y, y) ≤ (Ay, y) ≤ µ2 · (y, y) ∀y ∈ lRn. (VII.10)

Page 75: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 74

Dann konvergiert das Richardson-Verfahren fur τ ∈ (0, 2/µ2), und fur τ = 2/(µ1 + µ2)

gilt

‖xk+1 − x‖ ≤ q‖xk − x‖, q =κ− 1

κ+ 1, κ =

µ2

µ1

(VII.11)

(7.2) Beispiel: Ist (y, z) = (y, z)2 =∑n

i=1 yizi das ubliche `2-Skalarprodukt, so konnen

µ1 und µ2 als der kleinste bzw. großte Eigenwert von A gewahlt werden. Die Konver-

genzgeschwindigkeit hangt vom Verhaltnis “kleinster zu großter Eigenwert” ab.

7.2 Das cg-Verfahren

Es sei A symmetrisch und positiv definit. Dann ist obiges Variationsproblem aquivalent

zum Minimierungsproblem

J(x) = miny∈lRnJ(y), J(y) =1

2(Ay, y)− (b, y) (VII.12)

Die Idee besteht darin, J sukzessive entlang zu bestimmender Richtungen zu minimieren.

Sind x, p ∈ lRn, p 6= 0, vorgegeben, so liegt das Minimum von J auf der Gerade Gx,p =

x+ τp, τ ∈ lR im Punkt x′ = x+ αp mit

α =(r, p)

(Ap, p), r = b− Ax (VII.13)

In der Iteration werden zunachst ein Startvektor x0 und eine Richtung p0 = b − Ax0

definiert. Sind pk und xk+1 gegeben, so erweist sich als gunstige Wahl fur pk+1

pk+1 = b− Axk+1 − βpk (VII.14)

mit β so, dass (Apk, pk+1) = 0. Dieses Verfahren fuhrt nach spatestens n Schritten zur

exakten Losung. Wird vorher abgebrochen, so gilt das folgende Ergebnis mit (x, y)A :=

(x,Ay)

(7.3) Satz: Es gilt

‖xk − x‖A ≤2qk

1 + q2k≤ 2qk‖x0 − x‖A, q =

√κ(A)− 1√κ(A) + 1

(VII.15)

mit der Konditionszahl κ(A) bzgl. ‖.‖2.

Dieses Ergebnis zeigt die Notwendigkeit der Vorkonditionierung.

Page 76: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 75

7.3 Prakonditionierer

Die Idee der Prakonditionierung

Mittels einer geeigneten regularen Matrix C soll versucht werden, das Gleichungssystem

Ax = b in ein aquivalentes System C−1Ax = C−1b zu verwandeln, welches gunstigere

Konvergenzeigenschaften hat. Die zugehorige Fixpunktgleichung lautet

x = x+ τ(b− Ax) = Gτ (x) (VII.16)

mit

Gτ (y) = Mτy + gτ , Mτ = I − τC−1A, gτ = τC−1b (VII.17)

Die zugehorige Fixpunktiteration

xk+1 = Gτ (xk) = Mτxg + gτ = xk + τ(b− Axk) (VII.18)

wird nun in drei Schritten durchgefuhrt:

Gegeben xk,

– berechne das Residuum rk = b− Axk– lose Cwk = rk

– berechne neue Iterierte xk+1 = xk + τwk

Wir beschranken uns hier auf den Fall, dass sowohl A als auch C symmetrisch und

positiv und definit sind. In diesem Fall ist C−1A symmetrisch bzgl des Skalarprodukts

(., .)C , definiert durch

(y, z)C = (Cy, z) (VII.19)

denn es gilt

(C−1Ay, z)C = (CC−1Ay, z) = (Ay, z) = (Az, y) = (CC−1Az, y) = (C−1Az, y)C(VII.20)

Nach Satz (6.1) gilt also: Ist

µ1 · (y, y)C ≤ (C−1Ay, y)C ≤ µ2 · (y, y)C , (VII.21)

so gilt

‖xk+1 − x‖C ≤ q‖xk − x‖C , q =κ− 1

κ+ 1, κ =

µ2

µ1

(VII.22)

Page 77: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 76

Einige Ansatze

Ziel heuristisch motivierter Ansatze ist es, C moglichst “in der Nahe von A” zu wahlen,

wobei allerdings die Losung von Cw = r nicht zu aufwandig sein darf.

1. Skalierungs-Vorkonditionierer

2. Polynomiale Vorkonditionierer

3. Unterraum-Korrektur-Methoden

Der zusatzliche Rechenaufwand bei Prakonditionierung besteht in der Berechnung von

Cwk = rk, oder in Variationsformulierung

(Cwk, z) = (b, z)− (Axk, z) = 〈f, z〉+ a(xk, z) ∀z ∈ lRn (VII.23)

Fur den “perfekten” Vorkonditionierer C = A fuhrt dies auf

a(wk, z) = 〈f, z〉+ a(xk, z) ∀z ∈ lRn (VII.24)

Eine entscharfte Variante besteht darin, diese Variationsgleichung auf einem sehr viel

niedriger-dimensionalen Teilraum V ⊂ lRn zu losen. In diesem Fall ist wk ∈ V zu

bestimmen so, dass

a(wk, z) = 〈f, z〉+ a(xk, z) ∀z ∈ V. (VII.25)

In konkreten Fallen zerlegt man lRn in p Teilraume Vi, i = 1, . . . , p, bestimmt in jedem

Teilraum die Korrektur w(i)k und setzt

xi+1 = xk + τ ·p∑i=1

w(i)k . (VII.26)

Zu diesem Typ von Methoden gehoren beispielsweise die in der Literatur zu findenden

Schwarz-Methoden.

Page 78: NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN ......NUMERIK PARTIELLER DIFFERENTIALGLEICHUNGEN Elliptische und parabolische Probleme Prof. Dr. Hans Babovsky Technische Universit at Ilmenau

Prof. Dr. H. Babovsky, Num. PDE, SS 09 77

Literatur

[1] Ch. Großmann und H.-G. Roos. Numerik partieller Differentialgleichungen. Teubner,

Stuttgart, 1992.

[2] W. Hackbusch. Theorie und Numerik elliptischer Differentialgleichungen. Teubner,

Stuttgart, 1986.

[3] J.J.I.M. van Kan und A. Segal. Numerik partieller Differentialgleichungen fur Inge-

nieure. Teubner, Stuttgart, 1995.

[4] W. Zulehner. Numerische Mathematik. Eine Einfuhrung anhand von Differential-

gleichungsproblemen. Bd. 1: Stationare Probleme. Birkhauser, Basel, 2008.