Numerische Verfahren zurLosung parabolischer partieller

Differentialgleichungen

Masterarbeit

von Jalo Liljo

Heinrich-Heine-Universitat Dusseldorf

Lehrstuhl fur Angewandte Mathematik

September 2006

Inhaltsverzeichnis

1 Einleitung 1

2 Exponentielle Integratoren 3

2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2.1 Exponentielle Euler-Methode . . . . . . . . . . . . . . . 6

2.2.2 EXP4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.3 Explizite exponentielle Runge-Kutta-Verfahren . . . . . . 10

3 RKC 19

3.1 Stabilitatsbereiche und Stabilitatsfunktionen . . . . . . . . . . . 19

3.2 Vorbemerkungen . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.3 Die Runge-Kutta-Chebyshev-Formeln, Stabilitatsbedingungenund Konvergenzresultate . . . . . . . . . . . . . . . . . . . . . . 21

3.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.4.1 Fehlerkontrolle . . . . . . . . . . . . . . . . . . . . . . . 26

3.4.2 Schrittweitenwahl und Berechnung des Spektralradius . . 30

4 Vorkonditionierte Lanczos-Approximation 33

4.1 Idee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Fehlerabschatzungen und die Wahl des Shifts . . . . . . . . . . . 34

4.3 Losen des Gleichungssystems . . . . . . . . . . . . . . . . . . . . 40

4.4 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5 Numerische Vergleiche 47

1

1 Einleitung

Das Ziel dieser Arbeit ist die Losung parabolischer partieller Differentialglei-chungen mit numerischen Verfahren. Hierzu werden verschiedene Verfahren zurLosung großer Systeme gewohnlicher Differentialgleichungen, welche bei derOrtsdiskretisierung parabolischer Differentialgleichungen auftreten, betrach-tet.

Nach der Diskretisierung erhalt man ein System von Anfangswertproblemender Form

y′(t) = f(t, y(t)), y(t0) = y0. (1.1)

Eine spezielle Klasse sind semilineare parabolische Differentialgleichungen

y′(t) + Ay(t) = g(t, y(t)), y(t0) = y0, (1.2)

mit einer konstanten Matrix A und nichtlinearen Termen die in g enthaltensind. A ist dabei positiv semidefinit oder sektoriell. Eine Matrix heißt sektoriell,wenn alle Eigenwerte in der komplexen Ebene betrachtet in einem Sektor S =z ∈ C : |arg(z)| ≤ α um die positive reelle Achse liegen, wobei 0 ≤ α < π

2.

Wenn nicht anders angegeben, ist in dieser Arbeit vorausgesetzt, dass A sym-metrisch und positiv semidefinit ist und, dass die Jacobi-Matrix J = ∂f(t,y)

∂yder

Differentialgleichung (1.1) symmetrisch und negativ semidefinit ist.

Zunachst werden in Kapitel 2 einige exponentielle Integratoren und die we-sentlichen Aspekte vorgestellt. Exponentielle Integratoren sind dadurch cha-rakterisiert, dass Matrixfunktionen verwendet werden. Die Idee die Exponen-tialfunktion einer Matrix zu verwenden, geht in die 60er Jahre zuruck undgalt lange als nicht praktikabel. Neue Methoden und Verbesserungen in derBerechnung des Produkts einer Matrixexponentialfunktion mit einem Vektorhaben das Interesse in den letzten Jahren wieder verstarkt.

In Kapitel 3 wird ein Verfahren vorgestellt, welches auf einer Familie vonRunge-Kutta-Chebyshev-Formeln basiert und 1980 von Sommeijer und Ver-wer vorgestellt wurde [15]. 1997 wurde dann ein Fortran-Code veroffentlicht,[17], welcher im Rahmen dieser Arbeit in Matlab implementiert wurde. Es wer-den die wichtigsten Optionen und Aspekte des Matlab-Codes erlautert und inKapitel 5 numerische Vergleiche mit anderen Verfahren aufgefuhrt.

Um das Produkt der Matrixexponentialfunktion mit einem Vektor zu be-rechnen, haben sich Krylov-Verfahren als effizient herausgestellt. Dies wol-len wir in Kapitel 2 kurz motivieren und in Kapitel 4 ein vorkonditioniertesLanczos-Verfahren vorstellen. Durch die Vorkonditionierung soll die Anzahlder Lanczos-Schritte reduziert werden, um die Berechnung zu beschleunigen.Auch hierzu werden Beispiele betrachtet.

In Kapitel 5 werden die Verfahren dann an einigen Beispielen getestet.

2

Besonderer Dank gilt Prof. Dr. M. Hochbruck und J. Niehoff fur die hilfreichenDiskussionen.

3

2 Exponentielle Integratoren

In diesem Kapitel wird zunachst die Verwendung der Matrixexponentialfunk-tion in numerischen Verfahren zur Integration von Differentialgleichungssyste-men und die Verwendung von Krylov-Verfahren motiviert. Anschließend wer-den einige exponentielle Integratoren behandelt. Zum einem der in [6] vonHochbruck, Lubich und Selhofer vorgestellte Integrator exp4 auf welchen wirdann in Abschnitt 4 wieder eingehen werden, zum anderen eine Klasse expli-ziter exponentieller Runge-Kutta-Verfahren.

2.1 Motivation

Betrachtet man die Differentialgleichung

y′(t) + Ay(t) = 0, y(0) = y0,

so ist die Losung durch y(t) = exp(−tA)y0 gegeben. Fur das inhomogeneProblem

y′(t) + Ay(t) = b, y(0) = y0,

mit einer konstanten Matrix A und konstantem Vektor b ist die Losung durch

y(t) = y0 + tϕ(−tA)(Ay0 + b),

mit der analytischen Funktion

ϕ(λ) = (exp(λ)− 1)/λ

gegeben. Daher liegt die Idee nahe, die Matrixexponentialfunktion in numeri-schen Integratoren zu verwenden.

Die Verwendung von Krylov-Verfahren ist folgendermaßen motiviert, wobeiwesentlich ist, dass man f(A) nicht explizit benotigt, sondern nur das Produktmit einem Vektor v. Die Cauchy-Integralformel besagt, dass fur eine in einemGebiet Ω ⊂ C analytische Funktion

f(a) =1

2πi

∫

Γ

f(λ)(λ− a)−1dλ

gilt, wobei Γ eine einfach geschlossene Kurve in Ω und a ∈ C ein Punkt ist,der nicht auf Γ liegt und genau einmal von Γ in positiver Richtung umlaufenwird. Die Cauchy-Integralformel kann auch auf quadratische Matrizen verall-gemeinert werden und man kann zeigen, dass

f(A) =1

2πi

∫

Γ

f(λ)(λI − A)−1dλ

4

gilt, wobei verlangt wird, dass die Kurve Γ den Wertebereich

F(A) = xHAx : x ∈ Cn, ‖x‖ = 1im Inneren enthalt.

Um f(A)v zu approximieren wird ausgenutzt, dass fur jedes λ ∈ Γ in derCauchy-Integralformel

f(A)v =1

2πi

∫

Γ

f(λ)(λI − A)−1vdλ =1

2πi

∫

Γ

f(λ)x(λ)dλ

die Losung eines linearen Gleichungssytems auftritt. Das Gleichungssystem

(λI − A)x(λ) = v (2.1)

konnen wir naherungsweise mit einem Krylov-Verfahren losen.

Zunachst konstruiert man eine Basis Vm des m-dimensionalen Krylovraumes.Ist Vm eine Basis von Km(A, v), so gilt

AVm = VmHm + βmvm+1eTm, mit Vme1 = v und V H

m Vm = I,

wobei Hm eine Matrix in Hessenbergform ist und tridiagonal, falls A symme-trisch ist. Ist Hm tridiagonal, so schreiben wir im Folgenden Tm.

Aus Km(A, v) = Km(λI − A, v) fur alle λ ∈ C folgt, dass Vm auch Basis derverschobenen Krylovraume ist. Also gilt auch

(λI − A)Vm = Vm(λI −Hm)− βmvm+1eTm

und die Galerkin-Iterierte zu (2.1) ist daher durch

xm(λ) = Vm(λI −Hm)−1‖v‖e1

gegeben. Dabei ist die Galerkin-Iterierte xm(λ) ∈ Km(A, v) durch rm(λ) ⊥Km(A, v) definiert, wobei

rm(λ) = v − (λI − A)xm(λ)

das Residuum bezeichnet. Sie existiert fur jedes m, da Γ wegen F(Hm) ⊂ F(A)den Wertebereich von Hm umschließt.

Setzt man dies in die Integraldarstellung ein, so erhalt man:

f(A)v =1

2πi

∫

Γ

f(λ)(λI − A)−1vdλ

≈ 1

2πi

∫

Γ

f(λ)xm(λ)dλ

=1

2πi

∫

Γ

f(λ)Vm(λI −Hm)−1(‖v‖e1)dλ (2.2)

= Vm1

2πi

∫

Γ

f(λ)(λI −Hm)−1dλ(‖v‖e1)

= Vmf(Hm)(‖v‖e1)

5

Die Matrix Hm hat kleinere Dimension und f(Hm) kann man zum Beispieldurch Diagonalisierung oder Pade-Approximation berechnen.

Fur die Funktion exp(λ), v mit ‖v‖ = 1 und eine Matrix A mit λ(A) ∈ [−4ρ, 0],wobei λ(A) die Eigenwerte von A bezeichnet, gilt beispielsweise, [5]:

‖eτAv − VmeτHme1‖ ≤

10e−m2/(5ρτ)√

4ρτ ≤ m ≤ 2ρτ10(ρτ)−1e−ρτ ( eρτ

m)m m ≥ 2ρτ .

In [5] findet man weitere Resultate fur symmetrische und schief symmetrischeMatrizen, sowie fur Matrizen, deren Eigenwerte in einem Kreissektor liegen.Gallopolous und Saad zeigten, dass der Fehler der m-ten Iterierten proportio-nal zu ‖τA‖m/m! ist, was superlineare Konvergenz fur m À ‖τA‖ bedeutet. In[5] wird gezeigt, dass dies fur negativ definite symmetrische Matrizen bereitsfur m ≥

√‖τA‖ der Fall ist, wohingegen bei schief symmetrischen Matrizen

mit gleichmaßig verteilten Eigenwerten m nah bei ‖τA‖ liegt. Fur eine ge-wisse Klasse von Matrizen, deren Eigenwerte in einem Kreissektor enthaltensind, wird eine schnelle Fehlerreduktion fur m ¿ ‖τA‖ gezeigt. Weiterhinkonvergieren Krylov-Verfahren fur ϕ(τA)v fast so schnell wie fur exp(τA)v, dader Fehler der Approximation an ϕ(τA)v vom Fehler der Approximation anexp(τA)v abhangt:

‖ϕ(τA)v − Vmϕ(τHm)e1‖ = ‖1

τ

∫ τ

0

eσAvdσ − 1

τ

∫ τ

0

VmeσHme1dσ‖

≤ 1

τ

∫ τ

0

‖eσAv − VmeσHme1‖dσ

≤ maxσ∈[0,τ ]

‖eσAv − VmeσHme1‖.

2.2 Verfahren

Ein haufig verwendeter Ansatz zur Konstruktion exponentieller Verfahren, aufwelchen wir spater nochmals eingehen werden, ist die Variation-der-Konstanten-Formel, welche besagt, dass fur die Losung von (1.2)

y(tn + h) = e−hAy(tn) +

∫ h

0

e−(h−τ)Ag(tn + τ, y(tn + τ))dτ (2.3)

gilt. Hieraus ergibt sich sofort eine erste einfache Methode, die exponentielleEuler-Methode.

6

2.2.1 Exponentielle Euler-Methode

Aus (2.3) folgt

y(tn + h) = e−hAy(tn) +

∫ h

0

e−(h−τ)Ag(tn + τ, y(tn + τ))dτ

= e−hAy(tn) + hϕ(−hA)g(tn, y(tn)) + dn+1,

wobei

ϕ(−hA) =1

h

∫ h

0

e−(h−τ)Adτ. (2.4)

Mit f(tn + τ) = g(tn + τ, y(tn + τ)) gilt

y(tn + h) = e−hAy(tn) +

∫ h

0

e−(h−τ)A

(f(tn) +

∫ tn+τ

tn

f ′(s)ds

)

(2.5)

und daher

dn+1 =

∫ h

0

e−(h−τ)A

(∫ tn+τ

tn

f ′(s)ds

)dτ.

Woraus

‖dn+1‖ ≤∫ h

0

‖e−(h−τ)A‖∫ tn+τ

tn

‖f ′(s)‖dsdτ ≤ Ch

∫ tn+h

tn

‖f ′(s)‖ds,

mit einer Konstanten C, folgt.

Durch Approximationen an g(tn + τ, y(tn + τ)) kann man unterschiedliche Me-thoden konstruieren, wie wir spater sehen werden. Die triviale Approximationg(tn + τ, y(tn + τ)) ≈ g(tn, y(tn)) liefert die exponentielle Euler-Methode

yn+1 = e−hAyn + hϕ(−hA)g(tn, yn),

welche klassische Ordnung 2 hat und fur lineare Probleme exakt ist.

Im nachsten Abschnitt betrachten wir das in [6] vorgestellte Verfahren exp4,welches zu einer in [5] vorgestellten Klasse von exponentiellen Integratorengehort.

2.2.2 EXP4

In diesem Abschnitt betrachten wir eine Klasse von numerischen Verfahrenzur Losung von großen, steifen Systemen nichtlinearer Anfangswertproblemein autonomer Form

y′(t) = f(y(t)), y(t0) = y0. (2.6)

7

Die hier angefuhrten Verfahren verwenden Matrix-Vektor Multiplikationenϕ(τJ)v, wobei J = ∂f

∂ydie Jacobi-Matrix von f bezeichnet und τ von der

Schrittweite abhangt. Dabei ist ϕ die gleiche Funktion wie in (2.4)

ϕ(z) =ez − 1

z. (2.7)

Bei der ursprunglichen Form berechnet man ausgehend von einer Naherung y0

an y(t0), y1 = y(t0 + h) folgendermaßen:

ki = ϕ(γhJ)

(f(ui) + hJ

i−1∑j=1

γijkj

), i = 1, ..., s

ui = y0 + h

i−1∑j=1

αijkj (2.8)

y1 = y0 + h

s∑i=1

biki

Hierbei sind γ, γij, αij und bi Koeffizienten, die sich aus Ordnungsbedingungenergeben, welche man in [6] findet. Fur i ≤ j gilt γij = αij = 0. Setzt man J = 0folgt ϕ(z) ≡ 1 und man hatte ein explizites Runge-Kutta-Verfahren, und mitder Wahl ϕ(z) = 1/(1− z) ein Rosenbrock-Wanner-Verfahren.

Bei einem Schritt nach dem numerischen Schema (2.8) mussen s Multiplika-tionen von ϕ(γhJ) mit s unterschiedlichen Vektoren berechnet werden. Wenndiese Produkte mit Krylov-Methoden approximiert werden, mussen in jedemSchritt s Krylov-Raume konstruiert werden, was die Berechnung zu teuermacht. Durch geschickte Wahl der Koeffizienten kann man die Anzahl derMultiplikationen reduzieren. Grundlage hierfur ist, dass man ϕ(jz), j = 2, 3, ...rekursiv aus ϕ(z) berechnen kann.

Es gilt:

8

ϕ(2z) =e2z − 1

2z=

1

2

e2z − 2ez + 1

z+

ez − 1

z=

(1

2z

(ez − 1

z

)2

+ez − 1

z

)

= (1

2zϕ(z) + 1)ϕ(z)

ϕ(3z) =e3z − 2e2z + ez

3z+

2e2z − 2ez

3z+

ez − 1

3z

=2

3ez

(1

2

e2z − 2ez + 1

z+

ez − 1

z

)+

1

3

ez − 1

z

=2

3

(zez − 1

z+ 1

)(1

2zez − 1

z+ 1

)ez − 1

z+

1

3

ez − 1

z

=2

3(zϕ(z) + 1)ϕ(2z) +

1

3ϕ(z)

ϕ(4z) = ...

In [6] wird γ = 1/n gewahlt und gezeigt, dass man durch geschickte Koeffizi-entenwahl die Anzahl der Multiplikationen um den Faktor n reduzieren kann.Mit γ = 1/3 wird hierzu folgender Ansatz verwendet.

Zunachst wahlen wir α2,1 = α3,1 = α3,2 = 0 woraus u1 = u2 = u3 = y0 folgt.Es gilt

k1 = ϕ(1

3hJ)f(u1) und k2 = ϕ(

1

3hJ)

(f(u1) + hJγ2,1ϕ(

1

3hJ)f(u1)

).

Mit γ2,1 = 1/6 und der Rekursion folgt

k2 = ϕ(1

3hJ)

(1 +

1

2

hJ

3ϕ(

1

3hJ)

)f(u1) = ϕ(

2

3hJ)f(u1).

Auf diese Weise erhalt man mit s = 7 folgende Methode, die mit 3 f -Auswertungenin jedem Schritt auskommt:

9

k1 = ϕ(13hJ)f(y0)

k2 = ϕ(23hJ)f(y0)

k3 = ϕ(hJ)f(y0)

w4 = − 7300

k1 + 97150

k2 − 37300

k3

u4 = y0 + hw4

d4 = f(u4)− f(y0)− hJw4

k4 = ϕ(13hJ)d4

k5 = ϕ(23hJ)d4

k6 = ϕ(hJ)d4

w7 = 59300

k1 − 775

k2 + 269300

k3 + 23(k4 + k5 + k6)

u7 = y0 + hw7

d7 = f(u7)− f(y0)− hJw7

k7 = ϕ(13hJ)d7

y1 = y0 + h(k3 + k4 − 43k5 + k6 + 1

6k7)

(2.9)

Hierbei sind wi und di Hilfsvektoren. Die Methode, die im Folgenden mit exp4bezeichnet wird, hat klassische Ordnung 4 fur Differentialgleichungen der Form(2.6) und ist exakt fur lineare Differentialgleichungen. In [6] wird gezeigt, dass(2.8) auch auf differentiell-algebraische Gleichungen erweitert werden kann,und es wird eine Ordnungsbedingung fur differentiell-algebraische Gleichungenangegeben, welche auch fur steife Differentialgleichungen von Bedeutung ist.Fur differentiell-algebraische Gleichungen hat exp4 Ordnung 3. Weiterhin wirdangegeben, dass eine fur Rosenbrock-Verfahren bekannte Fehlerschranke auchfur exponentielle Verfahren gezeigt werden kann. Daher ist exp4 auch fur steifeDifferentialgleichungen geeignet.

Sei ‖v‖ = 1. Dann folgt mit

ϕ(τJ)v ≈ Vmϕ(τHm)e1

aus der obigen Rekursionsformel

ϕ(2τJ)v ≈ Vmϕ(2τHm)e1 = Vm

(1

2τHmϕ(τHm) + Im

)ϕ(τHm)e1

und

ϕ(3τJ)v ≈ Vm

(2

3(τHmϕ(τHm) + Im)ϕ(−2τHm) +

1

3ϕ(τHm)

)e1.

Zur Schrittweitensteuerung werden zwei eingebettete Verfahren verwendet undman wahlt eine Naherung des lokalen Fehlers als Minimum der lokalen Feh-

10

lerschatzungen dieser beiden Verfahren. Dies fuhrt dann mit Hilfe eines Schritt-weitenwahlverfahrens von Gustafsson [4] auf eine Schrittweite herr.

Weiterhin wird eine vom Krylov-Verfahren abhangige Schrittweite bestimmt.Hierzu wahlt man ein Intervall [µ,M ] fur die Anzahl der Krylov-Schritte m undeine darin enthaltene erstrebenswerte Anzahl mopt. Die aktuelle Schrittweite hwird beibehalten, wenn m ∈ [µ,M ] liegt. Falls m > M wird die neue Schritt-weite solange reduziert, bis die gewunschte Genauigkeit mit einem m ∈ [µ,M ]erreicht wird. Falls m < µ wird

hkry = h(mopt

m

)α

gesetzt, wobei α = 1/3 vorgeschlagen wird. Man kann sogar, falls m mehrals zwei Schritte hintereinander vergleichsweise klein ist, die Schrittweite nochweiter vergroßern. Es wird

hkry = 2j−1h

vorgeschlagen, falls m < 4 in den letzten j Zeitschritten war. Letztendlichwahlt man dann die neue Schrittweite als

hnew = minherr, hkry.

2.2.3 Explizite exponentielle Runge-Kutta-Verfahren

Explizite exponentielle Runge-Kutta-Verfahren zur Losung der Differentialglei-chung (1.2) sind in den letzten Jahren viel diskutiert worden. Unter anderemstellten Cox und Matthews [2], Hochbruck und Ostermann [8] und Krogstad[10] einige Verfahren vor. Eine ubersichtliche Zusammenfassung der bestenVerfahren findet man in [8]. Dort werden die Verfahren in einem abstraktemBanachraum fur sektorielle Operatoren und lokal Lipschitz-stetigen Nichtli-nearitaten analysiert. Weiterhin werden die Ordnungsbedingungen, sowohl furden nicht steifen als auch den steifen Fall aufgefuhrt und die Konvergenz furVerfahren bis zur Ordnung 4 gezeigt. In diesem Abschnitt sollen kurz die Kon-struktionsidee exponentieller Runge-Kutta-Verfahren, sowie 3 explizite Verfah-ren und die steifen Ordnungsbedingungen vorgestellt werden.

Die Grundlage fur die Konstruktion exponentieller Runge-Kutta-Verfahren ist,dass fur die Losung der Differentialgleichung (1.2) die Variation-der-Konstan-ten-Formel (2.3) gilt. Um nun eine Naherung yn+1 an y(tn + h) zu erhalten,wird der Term g(tn + τ, y(tn + τ)) durch ein Polynom gn approximiert. Hierzuwahlt man Kollokationsknoten c1,. . .,cs.

Hat man Approximationen

yn ≈ y(tn) und Yni ≈ y(tn + cih),

11

definiert man gn(cih) = g(tn + cih, Yni) = Gni, so dass

gn(τ) =s∑

j=1

lj(τ)Gnj,

wobei lj das Lagrange-Interpolationspolynom

lj(τ) =∏

m6=j

τ/h− cm

cj − cm

bezeichnet.

Dadurch ergibt sich die Naherung zur Zeit tn+1 als

yn+1 = e−hAyn +

∫ h

0

e−(h−τ)Agn(τ)dτ

= e−hAyn +

∫ h

0

e−(h−τ)A

s∑j=1

lj(τ)Gnj

= e−hAyn + h

s∑j=1

bi(−hA)Gnj

mit

bi(−hA) = h−1

∫ h

0

e−(h−τ)Ali(τ)dτ

Um eine Approximation an Yni zu erhalten, wird derselbe Ansatz benutzt. Esfolgt

Yni = e−cihAyn + h

s∑j=1

aij(−hA)Gnj,

mit

aij(−hA) = h−1

∫ cih

0

e−(cih−τ)Ali(τ)dτ.

Da die Polynome lj hochstens vom Grad s−1 sind, kann man die Koeffizientenbi(−hA) und aij(−hA) als Linearkombination der Funktionen

ϕk(−tA) = t−k

∫ t

0

e−(t−τ)A τ k−1

(k − 1)!dτ, 1 ≤ k ≤ s (2.10)

schreiben, welche wir spater benotigen. Es gilt ϕ0(z) = ez, sowie

ϕk+1(z) =ϕk(z)− 1/k!

z, ϕk(0) =

1

k!.

12

Das numerische Schema der Klasse von exponentiellen Runge-Kutta-Verfahrenist dann durch

yn+1 = e−hAyn + h

s∑i=1

bi(−hA)Gni

Yni = e−cihAyn + h

s∑j=1

aij(−hA)Gnj (2.11)

Gnj = g(tn + cjh, Ynj)

gegeben.

Eine wunschenswerte Eigenschaft numerischer Verfahren ist, dass sich Punktey∗, die sich im Gleichgewicht befinden, erhalten bleiben. Zwei Punkte befin-den sich im Gleichgewicht, wenn an den Punkten y′ = 0 gilt. Aus der Dif-ferentialgleichung folgt dann Ay = g(t, y). Dies lasst sich mit der ForderungYni = yn = y∗ fur alle i, n ≥ 0 und (2.11) folgendermaßen formulieren:

y∗ = e−hAy∗ + h

s∑i=1

bi(−hA)Ay∗

y∗ = e−cihAy∗ + h

s∑i=1

aij(−hA)Ay∗

Diese Forderung ist genau dann erfullt, wenn

s∑j=1

bj(z) =ez − 1

z= ϕ(z)

unds∑

j=1

aij(z) =eciz − 1

z= ciϕ(ciz) i = 1, . . . , s

gilt. Die erste Gleichung liefert

e−hA = I − hA

s∑i=1

bi(−hA)

woraus

yn+1 = (I − hA

s∑i=1

bi(−hA))yn + h

s∑i=1

bi(−hA)Gni

= yn + h

s∑i=1

bi(−hA)(Gni − Ayn)

folgt.

13

Analog folgt

Yni = yn + h

s∑j=1

aij(−hA)(Gnj − Ayn).

Also kann man das numerische Schema (2.11) als

yn+1 = yn + h

s∑i=1

bi(−hA)(Gni − Ayn)

Yni = yn + h

s∑j=1

aij(−hA)(Gnj − Ayn) (2.12)

Gnj = g(tn + cjh, Ynj)

schreiben.

Ein wesentlicher Aspekt sind die Ordnungsbedingungen fur den Fall einer stei-fen Differentialgleichung. Bevor wir diese angeben, betrachten wir die Fehleren = yn− y(tn) und Eni = Yni− y(tn + cih). Hierzu setzen wir der Einfachheithalber f(t) = g(t, y(t)) und entwickeln f in eine Taylorreihe. Es gilt

f(tn + τ) =

q∑j=1

τ j−1

(j − 1)!f (j−1)(tn) +

∫ τ

0

(τ − σ)q−1

(q − 1)!f (q)(tn + σ)dσ. (2.13)

Setzt man dies in die Variation-der-Konstanten-Formel ein, folgt

y(tn + cih) = e−cihAy(tn) +

qi∑j=1

(cih)j(cih)−j

∫ cih

0

e−(cih−τ)A τ j−1

(j − 1)!f (j−1)(tn)

+

∫ cih

0

e−(cih−τ)A

∫ τ

0

(τ − σ)qi−1

(qi − 1)!f (qi)(tn + σ)dσdτ

= e−cihAy(tn) +

qi∑j=1

(cih)jϕj(−cihA)f (j−1)(tn)

+

∫ cih

0

e−(cih−τ)A

∫ τ

0

(τ − σ)qi−1

(qi − 1)!f (qi)(tn + σ)dσdτ. (2.14)

Setzt man nun die exakte Losung in das numerische Schema ein, ergibt sich

y(tn + cih) = e−cihAy(tn) + h

i−1∑j=1

aij(−hA)f(tn + cjh) + ∆ni (2.15)

und

y(tn+1) = e−hAy(tn) + h

s∑i=1

bi(−hA)f(tn + cih) + δn+1 (2.16)

14

mit den Defekten ∆ni und δn+1, deren Darstellung man aus (2.14) und (2.15)bzw. (2.16) erhalt.

Die Fehlerrekursion erhalt man nun indem man (2.15) bzw. (2.16) von (2.11)subtrahiert.

Eni = e−cihAen + h

i−1∑j=1

aij(−hA) (g(tn + cjh, Unj − f(tn + cjh))−∆ni (2.17)

en+1 = e−hAen + h

s∑i=1

bi(−hA) (g(tn + cih, Uni − f(tn + cih))− δn+1 (2.18)

Die explizite Darstellung der Defekte wollen wir hier nicht angeben, sie ent-halten die Funktionen

ψj,i(−hA) = ϕ(−cihA)cji −

i−1∑

k=1

aik(−hA)cj−1k

(j − 1)!(2.19)

und

ψj(−hA) = ϕj(−hA)−s∑

k=1

bk(−hA)cj−1k

(j − 1)!, (2.20)

welche fur die Ordnungsbedingungen benotigt werden. Weiterhin seien im Fol-genden

Jn =∂g

∂y(tn, y(tn))

und

Kn =∂2g

∂t∂y(tn, y(tn)).

Hiermit konnen wir jetzt die steifen Ordnungsbedingungen angeben. Fur einedetailliertere Herleitung sei auf [8] verwiesen.

15

Num. Ordnung Bedingung

1 1 ψ1(−hA) = 0

2 2 ψ2(−hA) = 0

3 2 ψ1,i(−hA) = 0

4 3 ψ3(−hA) = 0

5 3∑s

i=1 bi(−hA)Jψ2,1(−hA) = 0

6 4 ψ4(−hA) = 0

7 4∑s

i=1 bi(−hA)Jψ3,i(−hA) = 0

8 4∑s

i=1 bi(−hA)J∑i−1

j=2 aij(−hA)Jψ2,j(−hA) = 0

9 4∑s

i=1 bi(−hA)ciKψ2,i(−hA) = 0

Tabelle 2.1: Steife Ordnungsbedingungen fur explizite exponentielleRunge-Kutta-Verfahren

Um Bedingung 6 zu erfullen, muss

s∑i=2

bi(−hA)c3i = 6ϕ4(−hA)

gelten, aber nach ([8], Theorem 4.7) ist es ausreichend die Bedingung in derabgeschwachten Form ψ4(0) = 0 zu erfullen, d.h.

s∑i=2

bi(0)c3i =

1

4.

Im Folgenden werden 3 Verfahren angegeben, die von den Autoren als Ver-fahren 4-ter Ordnung vorgestellt wurden. Die ersten beiden Verfahren wurdenkonstruiert bevor obige Ordnungsbedingungen bekannt waren, und wir wer-den sehen, dass diese nicht alle erforderlichen Bedingungen erfullen. Dahertritt eine Ordnungsreduktion auf.

16

Um die Verfahren darzustellen, werden hier Butcher-Tableaus verwendet unddas Argument der Koeffizientenfunktionen aij und bi weggelassen. Ein Butcher-Tableau eines expliziten Verfahrens hat die Form

c1 = 0 0 · · · · · · 0

c2 a21. . .

......

.... . . . . .

...cs as1 · · · as,s−1 0

b1 · · · · · · bs

.

Weiterhin werden in den Tableaus die Abkurzungen

ϕi,j = ϕi,j(−hA) = ϕi(−cjhA), 2 ≤ j ≤ s.

benutzt.

Cox und Matthews schlagen in [2] ein 4-stufiges Verfahren vor, welches durchdas Tableau

012

12ϕ1,2

12

0 12ϕ1,3

1 12ϕ1,3(ϕ0,3 − 1) 0 ϕ1,3

ϕ1 − 3ϕ2 + 4ϕ3 2ϕ2 − 4ϕ3 2ϕ2 − 4ϕ3 4ϕ3 − ϕ2

gegeben ist. Dieses Verfahren erfullt die Bedingungen 1-4 und Bedingung 6in der abgeschwachten Form ψ4(0) = 0. Die Bedingungen 5 und 9 sind nurin einer abgeschwachten Form erfullt, ψ2,2(0) + ψ2,3(0) = 0 und ψ2,4(0) = 0.Bedingungen 7 und 8 in einer ganz schwachen Form, wo A = 0 gesetzt wird.Dies fuhrt im schlechtesten Fall zu einer Ordnungsreduktion auf Ordnung 2.

Ein weiteres 4-stufiges Verfahren wurde von Krogstad in [10] vorgeschlagen.Es ist durch das Tableau

012

12ϕ1,2

12

12ϕ1,3 − ϕ2,3 ϕ2,3

1 ϕ1,4 − 2ϕ2,4 0 2ϕ2,4

ϕ1 − 3ϕ2 + 4ϕ3 2ϕ2 − 4ϕ3 2ϕ2 − 4ϕ3 4ϕ3 − ϕ2

gegeben. Dieses Verfahren erfullt Bedingungen 1-5 und 9, sowie die abge-schwachte Bedingung 6. Die Bedingungen 7 und 8 sind auch hier nur in derganz schwachen Form erfullt. Daher fuhrt die Ordnungreduktion im schlech-testen Fall auch nur auf Ordnung 3.

17

Mit 4 Stufen ist es auch nicht moglich ein Verfahren zu konstruieren, dassOrdnung 4 fur allgemeine parabolische Probleme der Form (1.2) hat. Daherbetrachten wir ein 5-stufiges Verfahren, welches von Hochbruck und Ostermannin [8] vorgeschlagen wurde. Es ist durch das Tableau

012

12ϕ1,2

12

12ϕ1,3 − ϕ2,3 ϕ2,3

1 ϕ1,4 − 2ϕ2,4 ϕ2,4 ϕ2,412

12ϕ1,5 − 2a5,2 − a5,4 a5,2 a5,2

14ϕ2,5 − a5,2

ϕ1 − 3ϕ2 + 4ϕ3 0 0 4ϕ3 − ϕ2 4ϕ2 − 8ϕ3

gegeben. Dabei ist

a5,2 =1

2ϕ2,5 − ϕ3,4 +

1

4ϕ2,4 − 1

2ϕ3,5.

Dieses Verfahren wurde unter Berucksichtigung der steifen Ordnungsbedingun-gen konstruiert und hat Ordnung 4.

Bei den numerischen Vergleichen in Kapitel 5 wird das Verfahren von Krogstadverwendet. Die verwendete Version arbeitet mit konstanter Schrittweite undbeinhaltet eine geschickt angewandte QR-Zerlegung, um Rechenzeit einzuspa-ren. Die Idee wird hier kurz erlautert. Fur Details sei auf [9] verwiesen.

Benotigt man das das Produkt von ϕ(−hA) mit unterschiedlichen Vektoren

ϕ(−hA)bj, bj = f(t + cjh), 1 ≤ j ≤ s,

berechnet man

QR = [b1, . . . , bs], mit Q = [q1, . . . , qs] und R ∈ Rs,s,

wobei Q orthogonal ist und R obere Dreicksform hat. Dann verwendet manKm(A, qj) anstelle von Km(A, bj), um zj = ϕ(−hA)qj zu approximieren. Danngilt

ϕ(−hA)bj = ϕ(−hA)[q1, . . . , qj]R1:j,j = [z1, . . . , zj]R1:j,j.

18

19

3 RKC

In diesem Kapitel betrachten wir ein explizites Runge-Kutta-Chebyshev-Ver-fahren zur Berechnung einer Losung von (1.1). 1997 wurde von Sommeijer [17]ein Fortran Programm vorgestellt, welches, genau wie die bisher vorgestelltenVerfahren, zur Integration steifer Systeme gewohnlicher Differentialgleichun-gen dient, die bei der Ortsdiskretisierung parabolischer partieller Differenti-algleichungen auftreten. Hier werden die wesentlichen Aspekte des Verfahrensund des Fortran-Codes vorgestellt und die Optionen des erstellten Matlab Pro-gramms erlautert. In Kapitel 5 findet man die numerischen Resultate. Bevorwir das Verfahren betrachten, benotigen wir eine kurze Vorbereitung.

3.1 Stabilitatsbereiche und Stabilitatsfunktionen

Ein allgemeines s-stufiges Runge-Kutta-Verfahren angewandt auf (1.1) ist vonder Form

Yi = yn + h

s∑j=1

aijY′j

Y ′i = f(tn + cih, Yi)

yn+1 = yn + h

s∑i=1

biY′i

mit den Kollokationsknoten ci, den Gewichten bi und den Koeffizienten aij.Fur ein explizites Runge-Kutta-Verfahren angewandt auf die Testgleichung

y′(t) = λy(t) (3.1)

erhalt man also

Yi = yn + h

i−1∑j=1

aijY′j

Y ′i = λYi

yn+1 = yn + h

s∑i=1

biY′i

und daher

yn+1 = P (hλ)yn (3.2)

mit einem Polynom P vom Grad ≤ s. P wird als Stabilitatsfunktion bezeich-net.

20

Der Stabilitatsbereich eines Runge-Kutta-Verfahrens ist definiert als

S = z ∈ C | z = hλ; das Verfahren liefert eine beschrankte Losung (yn)n≥0,

wenn es mit Schrittweite h auf y′ = λy, y(0) = y0 angewandt wird..Aus (3.2) folgt fur ein explizites Runge-Kutta-Verfahren

S = z ∈ C | |P (z)| ≤ 1.Die Stabilitatsbereiche expliziter Runge-Kutta-Verfahren umfassen typischer-weise einen Bereich um die negative reelle Achse.

3.2 Vorbemerkungen

Die Konstruktion des Verfahrens beruht auf einer geschickten Wahl der Stabi-litatsfunktion. Wie wir in Abschnitt 3.3 sehen werden, werden hierzu Cheby-shev-Polynome gewahlt.

Im Gegensatz zu exponentiellen Integratoren wird bei dem Verfahren nicht dieJacobi-Matrix ∂f(t,y)

∂ybenotigt, sondern nur eine obere Schranke fur den Spek-

tralradius dieser. Das Verfahren hat Ordnung 2 und verwendet eine variableStufenanzahl s, welche so mit der Schrittweite angepasst wird, dass die erfor-derliche Stabilitatsbedingung erfullt ist, worauf wir in Abschnitt 3.3 eingehenwerden.

RKC ist geeignet fur Probleme deren Jacobi-Matrix fast normal ist und derenEigenwerte alle nah an der negativen reellen Achse liegen. Dies ist sicherlichder Fall, wenn ∂f(t,y)

∂ysymmetrisch und negativ definit ist, was bei der Diskre-

tisierung elliptischer Operatoren haufig der Fall ist. Die Formeln, die in RKCverwendet werden, sind Erweiterungen einer in [18] vorgeschlagenen Familieexpliziter Runge-Kutta-Chebyshev-Formeln. Die Stabilitatsbereiche aller For-meln beinhalten einen schmalen Streifen um die negative reelle Achse. Eingroßer Vorteil ist, dass um die Formeln auszuwerten nur wenige Vektoren ge-speichert werden mussen, unabhangig von der Anzahl der Stufen. Ein weitererVorteil ist, dass die lokalen Fehler fur alle Formeln die gleichen sind. Daherkann RKC zuerst die effizienteste Schrittweite wahlen, um dann den Spektral-radius zu approximieren und die effizienteste Formel zu wahlen, welche fur dieSchrittweite stabil ist.

Beispielsweise konnen Reaktions-Diffusions-Systeme

y′ = ∇ · (K∇y) + f(y, x, t), x ∈ Rd

effizient mit RKC gelost werden, wenn der Reaktionsterm f nicht zu steif ist.Falls f zu großer Steifheit fuhrt, kann RKC auch in einem Splitting-Verfahrenverwendet werden, wo der Reaktionsterm an den Gitterpunkten mit einem

21

Standard-Integrator fur steife Probleme behandelt wird. Hierunter fallen auchTransportprobleme wie

y′ +∇ · (ay) = ∇ · (K∇y) + f(y, x, t), x ∈ Rd,

welche z.B. bei der Untersuchung der Umweltverschmutzung auftreten, [16].

3.3 Die Runge-Kutta-Chebyshev-Formeln, Stabilitats-bedingungen und Konvergenzresultate

Das Ziel ist Formeln zu konstruieren, die auf einem moglichst großen Bereichum die negative reelle Achse stabil sind. Die Lange dieses Bereichs wird imFolgenden mit β(s) bezeichnet und ist proportional zu s2, wie wir spater sehenwerden.

Hat man eine Naherung yn an y(tn) und bezeichnet mit h die Schrittweite, soverwendet man folgenden Ansatz fur das Runge-Kutta-Schema:

Y0 = yn,Y1 = Y0 + µ1hf0,Yj = (1− µj − νj)Y0 + µjYj−1 + νjYj−2 + µjhfj−1 + γjhf0,

yn+1 = Ys,

(3.3)

mit j = 2, ..., s und fj = f(tn + cjh, Yj).

Eine Formel fur die Knoten cj erhalt man aus der Entwicklung von Yj ≈y(tn + cjh).

Yj ≈ y(tn + cjh) = y(tn) + cjhy′(tn) +O(h2). (3.4)

Vernachlassigt man nun die Terme der Großenordnung O(h2) und setzt (3.3)und (3.4) gleich, erhalt man sofort c0 = 0, c1 = µ1 und

y(tn) + cjhy′(tn) = (1− µj − νj)Y0 + µjYj−1 + νjYj−2 + µjhfj−1 + γjhf0.

Mit Yj−1 ≈ y(tn + cj−1h), Yj−2 ≈ y(tn + cj−2h) und f(tn + cj−1h, Yj−1) =y′(tn + cj−1h) folgt

y(tn) + cjhy′(tn) = (1− µj − νj)yn + µjy(tn + cj−1h) + νjy(tn + cj−2h)

+ µjhy′(tn + cj−1h) + γjhy′(tn)

und daher

y(tn) + cjhy′(tn) = (1− µj − νj)yn + µjy(tn) + µjcj−1hy′(tn) + νjy(tn)

+ νjcj−2hy′(tn) + µjhy′(tn) + γjhy′(tn)

Mit yn ≈ y(tn) folgt

cjhy′(tn) = µjcj−1hy′(tn) + νjcj−2hy′(tn) + µjhy′(tn) + γjhy′(tn)

22

und die Rekursion

c0 = 0, c1 = µ1, cj = µjcj−1 + νjcj−2 + µj + γj, 2 ≤ j ≤ s.

Setzt man rekursiv in (3.3) ein, so erhalt man die Standardform eines Runge-Kutta-Verfahrens

Yj = yn + h

j−1∑

l=0

ajlf(tn + clh, Yl)

und es gilt die bei Runge-Kutta-Verfahren ubliche Bedingung

cj =

j−1∑

l=0

ajl.

Auf Seite 27 findet man eine Formel fur die Koeffizienten ajl.

Ursprunglich wurde eine RKC-Methode der Ordnung 1 und eine der Ordnung2 konstruiert. Da die Methode der Ordnung 2 effizienter ist, wird nur diesehier beschrieben.

Die einzige Bedingung, um Konsistensordnung 1 zu erhalten, ist cs = 1. Umdie Bedingung fur Konsistenzordnung 2 zu erhalten, entwickeln wir (3.4) umeine Potenz weiter

Yj = y(tn) + cjhy′(tn) + Xjh2y′′(tn) +O(h3). (3.5)

Setzt man dies in das numerische Schema (3.3) ein erhalt man

X0 = X1 = 0, Xj = µjXj−1 + νjXj−2 + µjcj−1, 2 ≤ j ≤ s.

Also hat die RKC-Methode Konsistenzordnung 2 in jeder Stufe, falls Xj = 12c2j ,

fur 2 ≤ j ≤ s gilt. Hieraus erhalt man

c22 = 2µ2c1, c2

3 = µ3c22 + 2µ3c2

undc2j = µjc

2j−1 + νjc

2j−2 + 2µjcj−1, 4 ≤ j ≤ s,

was sich leicht durch Induktion uberprufen lasst. In [15] wird gezeigt, dassdiese Bedingungen erfullbar sind. Eine weitere Forderung ist, dass alle Punktetn + cjh im Intervall [tn, tn+1] liegen und

0 = c0 < c1 < . . . < cs = 1

erfullen.

Um den Stabilitatsbereich und die Formeln fur die Koeffizienten des Verfahrenszu erhalten, betrachten wir die Testgleichung y′(t) = λy(t). Dies liefert

yn+1 = Ps(z)yn, z = hλ,

23

wobei Ps(z) die Stabilitatsfunktion vom Grad s ist. Mit (3.3) ergibt sich dierekursive Darstellung

P0(z) = 1, P1(z) = 1 + µ1z,

Pj(z) = (1−µj−νj)+ γjz +(µj + µjz)Pj−1(z)+νjPj−2(z), 2 ≤ j ≤ s. (3.6)

Nun wahlt man die Koeffzienten µj, νj, µj und γj in (3.6), so dass die Stabi-litatsschranke

β(s) = max−z|z ≤ 0, |Ps(z)| ≤ 1so groß wie moglich ist.

Die Idee ist, die Stabilitatsfunktionen Pj(z) durch Chebyshev-Polynome dar-zustellen, welche durch

Ts(x) = cos(s arccos(x)), −1 ≤ x ≤ 1

definiert sind, und dann die Koeffizienten der Rekursion fur die gewahlten Po-lynome und denen von der Rekursion (3.6) anzupassen. Beispielsweise erfullendie Polynome Pj(z) = Tj(1 + z/s2) die Rekursion

P0(z) = 1, P1(z) = 1 +z

s2,

Pj(z) = 2(1 +

z

s2

)Pj−1(z)− Pj−2(z)

und ein Koeffizientenvergleich mit (3.6) liefert sofort

µ1 =1

s2, µj = 2, µj =

2

s2, νj = −1, γj = 0, 2 ≤ j ≤ s.

Fur die RKC-Formeln wird

Pj(z) = aj + bjTj(w0 + w1z), 0 ≤ j ≤ s,

mit

aj = 1− bjTj(w0), bj =T ′′

j (w0)

(T ′j(w0))2

, 2 ≤ j ≤ s,

w0 = 1 +ε

s2, w1 =

T ′s(w0)

T ′′s (w0)

, a0 = 1− b0, a1 = 1− b1w0, b0 = b1 = b2

gewahlt, [16]. w0 wird dabei verwendet, um Ps(z) im Intervall [−1 + ε, 1 − ε]alternieren zu lassen. Fur den Parameter ε wird 2

13vorgeschlagen.

Mit der Rekursionsformel fur Chebyshev-Polynome

Tj(x) = 2xTj−1(x)− Tj−2(x)

24

und der Beziehung

Tj(w0 + w1z) =1

bj

(Pj(z)− (1− bjTj(w0))

)

folgt

Pj(z) = 1− bjTj(w0) + bjTj(w0 + w1z)

= 1− bjTj(w0) + bj

(2(w0 + w1z)Tj−1(w0 + w1z)− Tj−2(w0 + w1z)

)

= 1− bj

(2w0Tj−1(w0)− Tj−2(w0)

)

+ bj

(2(w0 + w1z)

1

bj−1

(Pj−1(z)− (1− bj−1Tj−1(w0))

)

− 1

bj−2

(Pj−2(z)− (1− bj−2Tj−2(w0))

))

=(1− 2bjw0

bj−1

+bj

bj−2

)−

(2bjw1

bj−1

− 2bjw1Tj−1(w0))z

+(2bjw0

bj−1

+2bjw1

bj−1

z)Pj−1(z)− bj

bj−2

Pj−2(z)

+(−2bjw0Tj−1(w0) + bjTj−2(w0) + 2bjw0Tj−1(w0)− bjTj−2(w0)

).

Also erfullen die Polynome die Rekursion

P0(z) = 1, P1(z) = 1 + b1w1z,

Pj(z) =

(1− 2bjw0

bj−1

− −bj

bj−2

)− (1− bj−1Tj−1(w0))

2bjw1

bj−1

z

+

(2bjw0

bj−1

+2bjw1

bj−1

z

)Pj−1(z) +

−bj

bj−2

Pj−2(z).

Der Koeffizientenvergleich mit (3.6) liefert:

µ1 = b1w1, µj =2bjw0

bj−1

, νj =−bj

bj−2

, µj =2bjw1

bj−1

,

γj = −(1− bj−1Tj−1(w0))µj

fur 2 ≤ j ≤ s.

Fur diese Wahl der Parameter gilt

β(s) ≈ (w0 + 1)T ′′s (w0)

T ′s(w0)

≈ 2

3(s2 − 1)(1− 2

15ε), ε → 0, (3.7)

[18].

25

Fur die Stabilitatsbetrachtung wird die Semidiskretisierung einer linearen par-tiellen Differentialgleichung

y′(t) = Ay(t) + g(t), 0 < t ≤ T

betrachtet und vorausgesetzt, dass A symmetrisch ist und negative Eigenwerteλi(M) besitzt.

Da A normal ist, gilt ‖A‖ = σ(A), wobei σ den Spektralradius bezeichnet.Wenn hλ die Werte des Spektrums von hA durchlauft, dann nimmt das Spek-trum des Matrixpolynoms P (hA) die Werte P (hλ) an. Da P (hA) auch normalist, gilt

‖P (hA)‖ = σ(P (hA)) = maxhλ

|P (hλ)|und wegen der Voraussetzung an A

−hσ(A) ≤ hλi(A) ≤ max(hλi(A)) ≤ 0.

Daher gilt ‖Ps(hA)‖ ≤ 1, wenn man die Schrittweite und die Stufenanzahl sowahlt, dass die Stabilitatsbedingung

hσ(A) ≤ β(s) (3.8)

erfullt ist.

Um die Konvergenzresultate angeben zu konnen, betrachten wir zunachst dieAuswirkungen von Storungen wie z.b. Rundungsfehlern. Dazu fugen wir indem Schema (3.3) eine Storung rj hinzu

Y0 = yn,

Y1 = Y0 + µ1hf0 + r1,

Yj = (1− µj − νj)Y0 + µjYj−1 + νjYj−2 + µjhfj−1 + γjhf0 + rj,

yn+1 = Ys,

wobei fj = fj(t+cjh, Yj). Fur den Fehler en = yn−yn wird folgende Abschatzunggezeigt, ([21], Theorem 3.1):

Satz 3.1 Sind h und s so gewahlt, dass die Bedingung hσ(A) ≤ β erfullt ist.Dann gilt

‖en+1‖ ≤ ‖en‖+ C

s∑

k=1

(s− k + 1)‖rk‖ ≤ ‖en‖+1

2s(s + 1)C max

k‖rk‖, (3.9)

wobei die Konstante C moderate Große hat und unabhangig von A, h und sist.

Die Abschatzung (3.9) und die Betrachtung der lokalen Defekte, welche auftre-ten wenn man die exakte Losung in das Runge-Kutta-Schema einsetzt, liefern

26

dann eine Schranke fur den globalen Fehler. Die lokalen Defekte leitet manuber die Differentialgleichung

y′l(t) = f(t, yl(t)) + αl(t), 0 < t ≤ T.

her, worauf wir hier nicht naher eingehen wollen. Dabei ist yl(t) eine exakteLosung auf einem Gitter mit Gitterweite l, αl(t) der lokale Abschneidefehlerund es gilt

Satz 3.2 Unter den Voraussetzungen yl ∈ C3[0, T ] und hσ(A) ≤ β fur dasungedampfte (ε = 0 fur w0) Verfahren gilt fur den globalen Fehler

‖en‖ ≤ C(s−3h max0≤t≤T

‖y(2)l (t)‖+ h2 max

0≤t≤T‖y(3)

l (t)‖+ max0≤t≤T

‖αl(t)‖),

mit n = 1, 2, . . . und nh ≤ T ([21], Theorem 5.2). Dabei ist C > 0 eine von A,h und s unabhangige Konstante.

Diese Abschatzung zeigt, dass das Verfahren ’fast’ Ordnung 2 hat, wenn s−3 ≈h gilt. Weiterhin sieht man, dass der globale und auch lokale Fehler hauptsach-lich von der dritten Ableitung der Losung abhangen und weitgehend unabhan-gig von s sind.

3.4 Implementation

Der von Sommeijer vorgestellte Fortran-Code wahlt genau wie Adams, BDFund Extrapolations-Verfahren die zu verwendende Formel dynamisch. Die meis-ten Verfahren fur Anfangswertprobleme schatzen in jedem Schritt den lokalenFehler und passen die Schrittweite so an, dass das Problem effizient gelost wird.Die großte Schwierigkeit die effizienteste Formel auszuwahlen, ist es die rich-tige Schrittweite fur diese Formel zu wahlen. RKC approximiert zunachst denSpektralradius der Jacobi-Matrix und ermittelt dann die effizienteste Formel,die mit der jeweiligen Schrittweite im Sinne von (3.8) stabil ist. In 3.4.1 wirddie Fehlerkontrolle beschrieben und in 3.4.2 die Schrittweitenwahl, sowie dieBerechnung des Spektralradius.

3.4.1 Fehlerkontrolle

Fur eine glatte Funktion f ist die Taylorentwicklung der Losung bei t = tndurch

yn+1 = y + hy′ +h2

2y′′ +

h3

6y′′′ +O(h4)

gegeben. Aus der Runge-Kutta-Theorie ist bekannt, dass man die Ableitungendurch elementare Differentiale ausdrucken kann. Dabei gilt

y(k)(t0) =∑

κ∈Υ,ρ(κ)=k

α(κ)F (κ)(y0),

27

wobei Υ die Menge aller Baume bezeichnet, F die elementaren Differentialeund α(κ) eine von der Differentialgleichung unabhangige Konstante ist.

Die elementaren Differentiale bis zur Ordnung 3 sind durch

y′ = f, y′′ = f ′y′ = f ′f und y′′′ = f ′′(f, f) + f ′f ′f

gegeben. Setzt man dies nun in die Taylorentwicklung ein, so ergibt sich

yn+1 = y + hy′ +h2

2y′′ + C1,sh

3f ′f ′f + C2,sh3f ′′(f, f) +O(h4), s ≥ 2,

wobei die Konstanten C1,s und C2,s von der Formel und der Anzahl der Stu-fen s abhangen. In [17] wird angegeben, dass beide Konstanten fur wachsen-des s nahe bei 1/10 liegen. Um dies zu uberprufen, verwenden wir die ausder Runge-Kutta-Theorie bekannten Beziehungen. Betrachtet man ein Runge-Kutta-Tableau

ci ai,j

bi

so gilt

C1,s =1

2

s∑

i,j,k

biai,j ai,k und C2,s =s∑

i,j,k

biai,j aj,k.

Die Runge-Kutta-Koeffizienten ai,j und bi kann man aus der Standardformeines Runge-Kutta-Verfahrens ablesen. Um diese zu erhalten, betrachten wirden Ubergang von Yj−1 nach Yj in (3.3). Es gilt

Yj = yn + hµj

j−2∑

k=0

aj−1,kfk + hνj

j−3∑

k=0

aj−2,kfk + hµjfj−1 + hγjf0

= yn + h

j−1∑

k=0

aj,kfk. (3.10)

Hieraus liest man die Rekursion

aj,0 = µj aj−1,0 + νj aj−2,0 + γj

aj,k = µj aj−1,k + νj aj−2,k

aj,j−1 = µj (3.11)

ab und aus yn+1 = Ys folgt bi = as,i. Berechnet man nun die beiden Konstanten,so ergibt sich

C1,200 ≈ 0.1011410626225052, C1,300 ≈ 0.1011452066261325

28

und

C2,200 ≈ 0.1011410626153832, C2,300 ≈ 0.1011452066252039.

In den Abbildungen 3.1 und 3.2 sind |C1,s − C1,300| und |C2,s − C2,300| furs = 2, . . . , 300 dargestellt.

0 50 100 150 200 250 30010

−8

10−6

10−4

10−2

100

Abb. 3.1: |C1,s − C1,300| als Funktion der Stufenanzahl s.

0 50 100 150 200 250 30010

−8

10−6

10−4

10−2

100

Abb. 3.2: |C2,s − C2,300| als Funktion der Stufenanzahl s.

Bezeichnet man nun mit Err(tn+1) die Naherung an den fuhrenden Term derTaylorentwicklung des lokalen Fehlers und ersetzt die von s abhangigen Kon-stanten durch ihre Grenzwerte, so gilt

Err(tn+1) =h3

15y′′′(tn).

29

Dieser Ausdruck wird durch

Estn+1 =1

15

(12(yn − yn+1) + 6h

(f(yn) + f(yn+1)

))(3.12)

approximiert. Um dies einzusehen, betrachten wir die Gleichung

h3y′′′(tn) = ayn + byn+1 + chf(yn) + dhf(yn+1)

= ay(tn) + by(tn + τ) + chy′(tn) + dhy′(tn + h)

und stellen ein lineares Gleichungssystem fur die Koeffizienten a, b, c und dauf. Mit Taylorentwicklung folgt

h3y′′′(tn) = ay(tn) + by(tn + h) + chy′(tn) + dhy′(tn + h)

= ay(tn) + by(tn) + hby′(tn) +h2

2by′′(tn) +

h3

6by′′′(tn)

+ hcy′(tn) + hdy′(tn) + h2dy′′(tn) +h3

2dy′′′(tn) +O(h4)

≈ (a + b)y(tn) + (b + c + d)hy′(tn) +(1

2b + d

)h2y′′(tn)

+(1

6b +

1

2d)h3y′′′(tn). (3.13)

Um (3.13) zu erfullen, mussen

1

6b +

1

2d = 1,

1

2b + d = 0, b + c + d = 0 und a + b = 0

gelten. Hieraus folgt a = 12, b = −12, c = 6 und d = 6, was (3.12) bestatigt.

Der Benutzer kann zwei Toleranzen vorgeben. Zum einen die relative Tole-ranz rtol als Skalar, und zum anderen die absolute Toleranz atol, welche manals Skalar angeben kann, aber auch als Vektor, dessen Komponenten danndie Genauigkeit in der zugehorigen Komponente der Losung vorgeben. DieseToleranzen gehen dann in eine gewichtete Norm ein

‖Estn+1‖ = ‖w−1Estn+1‖2, w =√

m diag(Tol1, ..., T olm).

Dabei ist

Tolk = atolk + rtol|yn+1,k|,m die Dimension des Problems und yn+1,k die k-te Komponente von yn+1.Falls ‖Estn+1‖ ≤ 1, wird der Schritt akzeptiert und sonst wiederholt. DieFehlerkontrolle beinhaltet eine Art relaxation, wie wir sie in Kapitel 4 auchsehen werden. In [13] wird gezeigt, dass sich der Fehler ungefahr um den Faktor0.2 reduziert, wenn man die Toleranzen mit 0.1 multipliziert.

30

3.4.2 Schrittweitenwahl und Berechnung des Spektralradius

Da es teuer ist einen Schritt zu wiederholen, wird versucht die Anzahl der ver-worfenen Schritte moglichst gering zu halten, indem die optimale Schrittweitevorhergesagt wird. Hierzu wird wie bei exp4 ein Verfahren von Gustafsson [4]verwendet.

Hier wird nach einem erfolgreichen Schritt die neue Schrittweite als

hnew = min(10, max(0.1, fac))h

gewahlt, wobei

fac = 0.8

( ‖Estn‖1/(p+1)

‖Estn+1‖1/(p+1)

hn

hn−1

)1

‖Estn+1‖1/(p+1).

Nach einem verworfenen Schritt wird

fac = 0.81

‖Estn+1‖1/(p+1)

verwendet. Hier wird p = 2 gewahlt.

In jedem Schritt wahlt RKC eine Schrittweite und anschließend eine mit dieserSchrittweite stabile Formel, um den lokalen Fehler zu steuern. Die Stabilitats-bereiche der Formeln beinhalten einen Bereich um die negative reelle Achse.Die Lange β(s) dieses Bereichs kann mit (3.7) durch 0.653s2 abgeschatzt wer-den. Um Stabilitat fur die Schrittweite zu erhalten, reicht es eine obere Schran-ke des Spektralradius der Jacobi-Matrix zu kennen, sofern die Eigenwerte indem jeweiligen Segment liegen. Daher wird

hσ

(∂f(t, y)

∂y

)≤ 0.653s2 (3.14)

als Auswahlkriterium fur die Anzahl der Stufen verwendet.

Der Spektralradius wird mit einer Potenzmethode approximiert, welche ubli-cherweise das Produkt der Matrix mit einem Vektor verwenden. Da die Jacobi-Matrix J im gesamten Verfahren nicht verwendet wird, wird dies auch hierumgangen. Dazu approximiert man das Produkt Jv durch einen Differenzen-quotienten

Jv ≈ f(yn + εv)

ε≈ ∂f

∂v.

Literaturhinweise hierzu findet man in [17]. Abbildung 3.3 zeigt den Algorith-mus bei dem der Differenzenquotient zusatzlich durch Normen skaliert ist. Daeine obere Schranke fur den Spektralradius benotigt wird, wird die Schatzungsicherheitshalber etwas vergroßert. Der Parameter ε wird als

√ε gewahlt, wobei

31

ε die Maschinengenauigkeit bezeichnet. Dies hat sich als praktikabel heraus-gestellt, um Rundungsfehler gering zu halten. Da die Berechnung wiederumSpeicherplatz und Rechenzeit in Anspruch nimmt, kann der Benutzer einegenerell gultige Schranke fur den Spektralradius angeben oder eine andereBerechnung vornehmen, was leicht eingebaut werden kann. Fur Probleme mitkonstanter Jacobi-Matrix wird der Spektralradius nur einmal berechnet, sofernder Benutzer dies angibt.

Eingabe: tn, yn, fn = f(tn, yn), ε =√

ε und derStartvektor v, wobei v = fn beim ersten Aufruf

v = yn + (‖yn‖ε/‖v‖)v;σ = 0;for i = 1 :n

fv = f(tn, v);σ1 = σ;σ2 = ‖fv − fn‖/‖yn‖ε;σ = 1.2 ∗ σ2;if i ≥ 2 und |σ2 − σ1| ≤ 0.01 ∗max(σ2, 1/hmax)

v = v − yn; STOPendv = yn + (‖yn‖ε/‖fv − fn‖)(fv − fn);

end

Abb. 3.3: Potenzmethode zur Berechnung des Spektralradius

Ein weiterer Aspekt ist, dass bei expliziten Runge-Kutta-Verfahren Rundungs-fehler bei einer großen Anzahl von Stufen eine Rolle spielen konnen. Falls RKCein sehr große Stufenanzahl fur die aktuelle Schrittweite benotigt, wird dieSchrittweite so weit verkleinert, dass das resultierende s akzeptabel und dieStabilitatsbedingung (3.14) erfullt ist.

32

33

4 Vorkonditionierte Lanczos-Approximation

In Kapitel 2 haben wir gesehen, dass in exponentiellen Integratoren das Matrix-Vektor-Produkt

w(τ) = ϕ(−τA)v,

wobei ϕ die in (2.7) definierte Funktion ist, benotigt wird. In diesem Kapi-tel soll ein vorkonditioniertes Lanczos-Verfahren vorgestellt werden, um diesesProdukt zu approximieren, wobei hier ‖v‖ = 1 vorausgesetzt ist. Das Ziel ist,durch die Vorkonditionierung die Anzahl der benotigten Lanczos-Schritte zuverringern. In diesem Kapitel ist A als symmetrisch und positiv semidefinitvorausgesetzt.

4.1 Idee

Meistens finden Lanczos-Verfahren sehr schnell Naherungen an Eigenwerte, diein gewissem Sinne gut voneinander getrennt sind. Die Idee ist das Spektrumder Matrix A so zu transformieren, dass das Lanczos-Verfahren auch die Ei-genwerte und zugehorigen Eigenvektoren schnell findet, die nah beieinanderliegen. Dazu wendet man das Lanczos-Verfahren auf die Matrix (I + γA)−1

mit einem Shift γ > 0 an. Die Lanczos-Relation fur die transformierte Matrixist dann durch

(I + γA)−1Vm = VmTm + βmvm+1eTm wobei Vme1 = v und V H

m Vm = I

gegeben. Definiert man die Funktion

f τγ (t) = ϕ((1− t−1)τ/γ) fur t ∈ (0, 1] und f τ

γ (0) = 0,

so ist f τγ ((I + γA)−1) = ϕ(−τA) und man erhalt

w(τ) ≈ wm(τ) = Vmf τγ (Tm)e1 = Vmϕ(τ Tm)e1 mit Tm =

1

γ(T−1

m − I). (4.1)

Analoge Rechnung kann man auch fur die Funktion exp(·) anstelle von ϕ(·)durchfuhren. Der Einfachheit halber betrachten wir im Folgenden Approxima-tionen an

y(τ) = exp(−τA)v,

fur welche man in der Literatur viele Konvergenzaussagen findet. In der Praxisstellt man fest, dass Naherungen an ϕ(−τA)v fast genauso schnell konvergierenwie an exp(−τA)v.

Um den Vorteil der Transformation des Spektrums einzusehen, betrachten wirein Maß, welches die Trennung der Eigenwerte beschreibt. Fur den zum kleins-ten Eigenwert gehorenden invarianten Unterraum ist dieses durch

λn − λ1

λ2 − λ1

(4.2)

34

gegeben, wobei λn den großten Eigenwert bezeichnet. Dieses Maß tritt auchin Aussagen uber die Konvergenzgeschwindigkeit von Lanczos-Verfahren auf.Fur die transformierte Matrix gilt

(1 + γλ1)−1 − (1 + γλn)−1

(1 + γλ1)−1 − (1 + γλ2)−1≤ (1 + γλ1)

−1

(1 + γλ1)−1 − (1 + γλ2)−1=

1 + γλ2

γ(λ2 − λ1).

Beispielsweise beim eindimensionalen Poisson-Problem mit Dirichlet-Randbe-dingungen ist (4.2) unbeschrankt, wohingegen der Wert bei transformiertemSpektrum durch (1 + γ4π2)/(3γπ2) beschrankt ist.

Daher liegt die Vermutung nahe, dass das Lanczos-Verfahren durch diese Trans-formation schneller konvergiert. Naturlich kommt weiterer Rechenaufwand hin-zu, da in jedem Schritt ein lineares Gleichungssystem gelost werden muss. Wei-terhin stellt sich die Frage wie der Shift γ zu wahlen ist und wie man den Fehlerder Approximation abschatzen kann.

4.2 Fehlerabschatzungen und die Wahl des Shifts

Um eine obere Schranke fur den Fehler der Approximation (4.1) zu erhalten,schreiben wir die Lanczos-Relation zunachst als

Vmf τγ (Tm)e1 = p((I + γA)−1)v = (I + γA)−(m−1)q(A)v

mit p, q ∈ Πm−1, wobei Πm−1 den Raum aller Polynome bis zum Grad m − 1bezeichnet. Dies folgt sofort aus ([11], Lemma 3.1 und 3.2) und der Defini-ton von f τ

γ (t). Also kann man die Approximation auch als Konstruktion einerrationalen Funktion aus dem Raum

Rji = p(t)(1 + γt)−i|p ∈ Πj

auffassen.

Die Aussage von ([11], Lemma 3.1) ist, dass fur jede beliebige Matrix A undVm, Hm resultierend aus dem Lanczos-Verfahren und jedes Polynom p ∈ Πm−1

p(A)v = Vmp(Hm)e1 (4.3)

gilt, was im Folgenden noch benotigt wird.

Grundlegend fur den Beweis des Konvergenzresultates ist

Lemma 3.1 A sei eine beliebige Matrix, Vm, Hm die aus dem Lanczos-Verfah-ren resultierenden Matrizen und f eine beliebige Funktion, so dass f(A) undf(Hm) definiert sind. Weiterhin sei p ein Polynom vom Grad ≤ m−1, welchesf approximiert und rm(z) = f(z)− p(z). Dann gilt mit ‖v‖ = β

f(A)v − βVmf(Hm)e1 = β(rm(A)v − Vmrm(Hm)e1),

35

([11], Theorem 4.1).

Definiert man nun

Eji (γ) = inf

r∈Rji

supt≥0

|r(t)− exp(−t)|,

erhalt man folgendes Resultat ([19], Lemma 3.1):

Lemma 3.2

Sei µ so gewahlt, dass A− µI positiv semidefinit ist. Dann gilt

||Vmf τγ (Tm)e1 − exp(−τA)v|| ≤ 2 exp(−τµ)Em−1

m−1(γ) mit γ =γ

τ(1 + γµ).

Beweis: Sei A = (I + γA)−1. Da Tm die Matrix aus dem Lanczos-Verfahren

mit A ist, folgt mit exp(−τA) = f τγ (A) und Lemma 3.1

‖Vmf τγ (Tm)e1 − exp(−τA)v‖

= ‖Vmf τγ (Tm)e1 − f τ

γ (A)v‖= ‖Vmrm(Tm)e1 − rm(A)v‖≤ ‖rm(Tm)‖+ ‖rm(A)‖= max

λ∈σ(Tm)|rm(λ)|+ max

λ∈σ( eA)|rm(λ)|

≤ 2 supλ∈F( eA)

|rm(λ)|

≤ 2 infp∈Πm−1

supt∈(0,(1+γµ)−1]

|f τγ (t)− p(t)|

= 2 infp∈Πm−1

supt∈(0,1]

|f τγ (

t

(1 + γµ))− p(t)|

= 2 infp∈Πm−1

supt∈(0,1]

| exp((1− 1

t

τ(1 + γµ)

γ− µτ)− p(t)|

= 2 infp∈Πm−1

supt∈(0,1]

| exp(−µτ) exp((1− 1

t

τ(1 + γµ)

γ)− p(t)|

= 2 exp(−µτ)Em−1m−1(γ).

2

Wichtig ist, dass diese Abschatzung unabhangig von der Norm von A ist. Daalle Eigenwerte von A großer sind als µ, spielt nur der kleinste Eigenwert vonA eine Rolle.

Lemma 3.2 zeigt, dass der Fehler klein wird, wenn man Em−1m−1(γ) minimiert.

Hieraus erhalt man einen Wert fur γ bzw. γ. Im Folgenden nehmen wir ohneEinschrankung τ = 1 und µ = 0 an woraus γ = γ folgt.

36

j Ejj (γopt) γopt j Ej

j (γopt) γopt

1 6.7 · 10−2 1.73 · 100 11 4.0 · 10−6 9.90 · 10−2

2 2.0 · 10−2 4.93 · 10−1 12 1.6 · 10−6 1.19 · 10−1

3 7.3 · 10−3 2.64 · 10−1 13 6.1 · 10−7 1.00 · 10−1

4 3.1 · 10−3 1.75 · 10−1 14 2.5 · 10−7 8.64 · 10−2

5 1.4 · 10−3 1.30 · 10−1 15 1.0 · 10−7 7.54 · 10−2

6 4.0 · 10−4 1.91 · 10−1 16 4.0 · 10−8 8.67 · 10−2

7 1.6 · 10−4 1.44 · 10−1 17 1.6 · 10−8 7.63 · 10−2

8 6.5 · 10−5 1.90 · 10−1 18 6.6 · 10−9 6.78 · 10−2

9 2.4 · 10−5 1.47 · 10−1 19 2.7 · 10−9 7.62 · 10−2

10 9.7 · 10−6 1.19 · 10−1 20 1.1 · 10−9 6.82 · 10−2

Tabelle 4.1: Numerische Approximation an den optimalen Wert fur γ und denzugehorigen Wert Ej

j (γopt), [19].

Naherungen an Em−1m−1(γ) konnen z.b. durch die Methode von Remez gewon-

nen werden, indem man eine optimale polynomiale Approximation an f 1γ (t) in

[0, 1] berechnet. Dies fuhrt auf die in Tabelle 4.1 angegebenen Werte fur γ beider angegebenen gewunschten Genauigkeit. Wenn man beispielsweise an einerGenauigkeit von 10−5 interessiert ist, wahlt man γ = 0.119τ . In [19] werdenauch andere Wahlen fur den Shift γ zitiert, auf welche wir hier nicht eingehenwollen. Sie basieren auf Approximationen an e−z durch rationale Funktionenmit reellen Polen, [1, 12].

Um einen Fehlerschatzer herzuleiten, schreiben wir zunachst die Lanczos-Rela-tion fur (I + γA)−1 um. Aus

(I + γA)−1Vm = VmTm + βmvm+1eTm

folgt

VmT−1m = (I+γA)Vm+βmvm+1z

Tm, vm+1 = (I+γA)vm+1, zm = T−1

m em.

WorausVm(T−1

m − I) = γAVm + βmvm+1zTm

und schließlich

VmTm = AVm +βm

γvm+1z

Tm, Tm =

1

γ(T−1

m − I) (4.4)

folgt.

Aus ym(t) = Vm exp(−tTm)e1 und (4.4) folgt dann

y′m(t) = −VmTm exp(−tTm)e1 = −Aym(t) + gm(t), ym(0) = v,

mit

gm(t) = −βm

γvm+1z

Tm exp(−tTm)e1.

37

Fur die exakte Losung gilt

y′(t) = −Ay(t), y(0) = v

und fur den Fehler em(t) = ym(t)− y(t) gilt daher

e′m(t) = y′m(t)− y′(t) = −Aem(t) + gm(t), em(0) = 0.

Mit der Variation-der-Konstanten-Formel folgt

em(τ) =

∫ τ

0

exp(−(τ − t)A)gm(t)dt

= −βm

γ

∫ τ

0

exp(−(τ − t)A)vm+1zTm exp(−tTm)e1dt.

Dies kann mit

Xm =

∫ τ

0

eTm(I + γTm) exp(−tTm)e1 exp(−(τ − t)A)(I + γA)dt

als

em(τ) = −βm

γXmvm+1

geschrieben werden. Setzt man

exp(−(τ − t)A) = I − (τ − t)A +1

2(τ − t)2A2 + . . .

ein, so folgt

em(τ) = −βm

γ

∫ τ

0

(I − (τ − t)A +1

2(τ − t)2A2 + . . .)vm+1z

Tm exp(−tTm)e1dt

und daher

em(τ) = −βm

γ

∞∑j=0

zTmφj+1(−τ Tm)e1(−A)j(I + γA)vm+1

mit

φj(−τA) =1

(j − 1)!

∫ τ

0

(τ − j)j−1 exp(−tA)dt.

Testbeispiele zeigen, dass die Norm des ersten Summanden

‖em(t)‖ ≈ βm

γ|zT

mφ1(−τ Tm)e1| ‖(I + γA)vm+1‖ (4.5)

bereits eine gute Schranke fur den Fehler ist.

38

Eine weitere Moglichkeit besteht darin den Fehler durch zwei bereits berech-nete Naherungen abzuschatzen. Hierzu nimmt man an, dass fur den relativenFehler δm im m-ten Schritt

‖ym(τ)− y(τ)‖‖y(τ)‖ = δm ≈ δm =

‖ym(τ)− ym−1(τ)‖‖ym(τ)‖

gilt. Aus

δm‖y(τ)‖ ≈ δm‖y(τ)‖ = ‖ym(τ)− y(τ)‖ ≥ ‖y(τ)‖ − ‖ym(τ)‖

folgt dann

‖y(τ)‖ . 1

1− δm

‖ym(τ)‖

und daher gilt fur den absoluten Fehler

‖em(τ)‖ = ‖ym(τ)− y(τ)‖ = δm‖y(τ)‖ ≈ δm‖y(τ)‖ . δm

1− δm

‖ym(τ)‖. (4.6)

Da (4.6) in den ersten Schritten etwas zu optimistisch sein konnte, kann mandas Minimum von (4.6) und der Schranke ‖em(τ)‖ ≤ 1 + ‖ym(τ)‖ wahlen.

Um die beiden Fehlerschatzer zu vergleichen, berechnen wir ϕ(jτA)v fur j =1, 2, 3 und wahlen A als die aus der Warmeleitungsgleichung

∂u

∂t= α

(∂2u

∂x2+

∂2u

∂y2

), u(x, y, 0) = u0(x, y), (4.7)

mit 0 ≤ x, y ≤ 1 und Neumann-Randbedingungen resultierende Matrix, wennman die Gleichung mit finiten Differenzen und 50 Gitterpunkten in jede Rich-tung diskretisiert. Hier ist α = 1 gewahlt.

39

0 5 10 15 20 25 3010

−15

10−10

10−5

100

Lanczos−Schritte

Fehl

erj=1j=2j=3(4.6)(4.5)

Abb. 4.1: Fehler der vorkonditionierten Lanczos-Approximation fur τ = 1/10.

0 5 10 15 20 25 3010

−15

10−10

10−5

100

Lanczos−Schritte

Fehl

er

j=1j=2j=3(4.6)(4.5)

Abb. 4.2: Fehler der vorkonditionierten Lanczos-Approximation fur τ = 1/100.

Die beiden Abbildungen zeigen fur 2 unterschiedliche Werte von τ den Fehlerder Approximation an ϕ(jτA)v, j = 1, 2, 3, wobei der Shift als γoptτ gewahlt

40

wurde. Sowie die Fehlerschatzer (4.5) und (4.6). Zum einen ist zu sehen, dassin beiden Fallen der Fehler bei ϕ(3τA)v am großten ist, daher wird bei beidenFehlerschatzern der Faktor 3 mit einbezogen. Zum anderen sieht man, dassbeide Fehlerschatzer gute obere Schranken fur den gesamten Fehler sind, wobei(4.6) eine genauere Naherung liefert.

4.3 Losen des Gleichungssystems

Durch die Vorkonditionierung ist im j-ten Schritt des Lanczos-Verfahrens einlineares Gleichungssystem von der Form

(I + γA)cj = vj

zu losen. Wir betrachten hier zwei Moglichkeiten.

Zum einem losen wir das Gleichungssystem direkt, wobei eine LU -Zerlegungverwendet wird. Da die Matrizen L und U bei der LU -Zerlegung einer dunnbe-setzten Matrix oft prozentual mehr von Null verschiedene Elemente enthaltenals die Ausgangsmatrix, ist es sinnvoll die Matrix geeignet zu permutieren be-vor man die LU -Zerlegung berechnet. Wird in dem jeweiligen Verfahren mitkonstanter Schrittweite gearbeitet und ist die Jacobi-Matrix konstant, so mussman im gesamten Verfahren nur einmal

LU = P T (I + γA)P

berechnen. Da der Shift γ von der Schrittweite abhangt, muss bei jedem Auf-ruf des Lanczos-Verfahrens eine neue Zerlegung berechnet werden sobald dieSchrittweite sich andert.

Zum anderen kann man das Gleichungssystem auch mit einem iterativen Ver-fahren losen. Hier betrachten wir das vorkonditionierte cg-Verfahren und ver-wenden die unvollstandige LU -Zerlegung zur Vorkonditionierung. Naturlichmuss man dem cg-Verfahren eine Toleranz vorgeben. In [19] findet man eineStrategie wie man ohne Verlust der geforderten Genauigkeit diese Toleranz an-heben kann, um schneller an eine Losung zu gelangen. Dies wird im folgendenkurz erlautert.

Wir sind an einer Losung wm(τ) mit ‖w(τ)−wm(τ)‖ ≤ ε interessiert. Um dasGleichungssystem zu losen, geben wir dem Loser im j-ten Schritt des Lanczos-Verfahrens eine Toleranz ηj vor. Wenn cj die Naherung an die Losung desGleichungsystems ist, gilt

‖rj‖ ≤ ηj mit rj = vj − (I + γA)cj.

Die Idee ist, dass es in spateren Schritten des Lanczos-Verfahren reicht einegeringere Genauigkeit ηj zu fordern, um trotzdem eine gewunschte Genauigkeit

41

von ε zu erreichen. Dies liegt daran, dass die ersten Schritte des Lanczos-Verfahrens die entscheidenden sind.

Um dies einzusehen, betrachten wir die Lanczos-Relation unter Einbeziehungdes Fehlers, der durch Losen des Gleichungssystem entsteht. Definiert mandie Matrix Fm durch Fmej = rj, d.h. die j-te Spalte der Matrix Fm enthaltdas Residuum des linearen Gleichungssystem, welches im j-ten Schritt desLanczos-Verfahren gelost wird, erhalt man die Relation

AVm = VmTm − βm

γvm+1z

Tm −

1

γFmT−1

m .

Diese ist ahnlich zu (4.4), wobei zu beachten ist, dass sowohl Vm als auch Tm

nicht die gleichen wie in der fehlerfreien Relation sind. Es ist nicht einmalgarantiert, dass die Matrix Vm orthogonal ist. Vernachlassigt man Rundungs-fehler und fuhrt die gleiche Rechnung wie im vorigen Abschnitt durch, erhaltman, unter Verwendung der gleichen Notation, aus dieser Relation

‖em(τ)‖ ≤ βm

γ‖Xmvm+1‖+

1

γ‖

∫ τ

0

exp(−(τ − t)A)FmT−1m exp(−tTm)e1dt‖.

Unter der Voraussetzung ηj = ε folgt mit der Cauchy-Schwarz-Ungleichung diegrobe Abschatzung

1

γ‖

∫ τ

0

exp(−(τ − t)A)FmT−1m exp(−tTm)e1dt‖ ≤ ‖T−1

m e1‖√

mτ

γε. (4.8)

Dies folgt zum einen aus

‖Fm‖ = supx 6=0

‖Fmx‖‖x‖ = max

‖x‖=1‖Fmx‖ = max

‖x‖=1‖Fme1x1 + . . . + Fmemxm‖ ≤

√mε,

wobei eingeht, dass aus ηj = ε, ‖Fmej‖ = ‖rj‖ ≤ ε folgt. Zum anderen daraus,dass fur eine symmetrische Matrix A eine orthogonale Matrix Q mit A =QΛQT , wobei Λ die Eigenwerte als Diagonalelemente enthalt, existiert unddaher

‖ exp(A)‖ = ‖Q exp(Λ)QT‖ = ‖ exp(Λ)‖ = maxλ∈σ(A)

| exp(λ)|

gilt. Dies motiviert die exp(·) Terme in (4.8) grob durch 1 abzuschatzen.

Daher gilt

‖em(τ)‖ ≤ βm

γ‖Xmvm+1‖+ ‖(I + γTm)e1‖

√mτ

γε.

Der Term zTmφj+1(−τ Tm)e1 aus (4.5) nimmt, aufgefasst als Funktion der Itera-

tionsschritte m, mit wachsendem m ab. Woraus folgt, dass die Norm ‖Xmvm+1‖

42

viel kleiner als ε wird bevor sie stagniert. Dies hat zur Folge, dass die Genau-igkeit vom zweiten Term abhangt. Fur weitere Details sei auf [19] verwiesen.

Approximiert man Matrix-Vektor-Produkte mit Krylov-Methoden ist es wich-tig, in den ersten Iterationsschritten die gewunschte Genauigkeit zu fordern,aber in spateren Schritten genugt eine geringere Genauigkeit, [3, 14, 20].

In [19] wird gezeigt, dass diese Strategie auch auf den hier vorliegenden Fallangewandt werden kann, und es wird die folgende relaxation strategie vorge-schlagen:

ηj =ε

‖ej−1(τ)‖+ ε(4.9)

4.4 Beispiele

Als Beispiel betrachten wir wieder die Warmeleitungsgleichung (4.7) mit α =0.5 und 50 Gitterpunkten in jede Richtung. Hierzu berechnen wir zum einenϕ(jτA)v fur j = 1, 2, 3, um den gesamten Verlauf in einem Lanczos-Schrittbeobachten zu konnen. Des Weiteren werden unterschiedliche Werte fur τgewahlt. Zum anderen losen wir die Gleichung mit dem Integrator exp4, umdie Auswirkung der relaxation auf den gesamten Fehler und die Anzahl derIterationen zu vergleichen.

Die Abbildungen 4.3 − 4.6 zeigen die Ergebnisse. Hierbei sind die Fehler derdrei zu berechnenden Vektoren in unterschiedlichen Farben dargestellt, ϕ(τA)vin blau, ϕ(2τA)v in grun und ϕ(3τA)v in rot. Die durchgezogenen Linien ge-hen aus der Berechnung ohne die relaxation hervor und die gestrichelten ausder mit relaxation. Fur beide ist zusatzlich der Fehlerschatzer mit (o) gekenn-zeichnet und die beim vorkonditioniertem cg-Verfahren verwendete Toleranzmit (+), wobei einmal ηj = ε und einmal ηj wie in (4.9) verwendet wurde.

Lost man die Gleichung mit exp4 und fordert eine Genauigkeit von 10−6 erge-ben sich folgende Werte:

ohne relaxation mit relaxation

Fehler Iterationen Fehler Iterationen7.2 · 10−8 3475 6.8 · 10−8 2132

43

0 50 100 150

10−5

100

pcg Iterationen

Fehl

er

Abb. 4.3: Auswirkungen der relaxation strategie fur τ = 1/100.

0 50 100 150 200 250

10−5

100

pcg Iterationen

Fehl

er

Abb. 4.4: Auswirkungen der relaxation strategie fur τ = 1/50.

44

0 100 200 300 400

10−5

100

pcg Iterationen

Fehl

er

Abb. 4.5: Auswirkungen der relaxation strategie fur τ = 1/10.

0 100 200 300 400

10−5

100

pcg Iterationen

Fehl

er

Abb. 4.6: Auswirkungen der relaxation strategie fur τ = 1/2.

Die Abbildungen zeigen, dass die gewunschte Genauigkeit bei beiden Strate-gien erreicht wird und bei der relaxation strategie durch das Anheben der

45

Toleranz Iterationen eingespart werden. Weiterhin beobachtet man eine an-steigende Anzahl der Iterationen fur wachsendes τ . Dies liegt daran, dass dieNorm der Matrix τA fur großere τ großer ist.

Bei den numerischen Vergleichen in Kapitel 5 wird das lineare Gleichungssys-tem mittels der LU -Zerlegung gelost, da sich dies als effizienter herausgestellthat. Das Losen des Gleichungssystems mit einem iterativen Loser kann, un-ter Verwendung eines effizienteren Verfahrens als des cg-Verfahrens und derrelaxation strategie, auch von Vorteil sein.

Eine weitere gute Eigenschaft des vorkonditionierten Lanczos-Prozess ist, dasseine Verfeinerung der Ortsdiskretisierung keinen großen Einfluß auf die An-zahl der benotigten Lanczos-Schritte hat. In [19] wird dies am Beispiel derzweidimensionalen Warmeleitungsgleichung gezeigt. Hier wird die Differenti-algleichung

∂u

∂t=

∂2u

∂x2+

1

1 + u2, u(x, 0) = u0(x),

mit 0 ≤ x ≤ 1 fur 0 ≤ t ≤ 1 und homogenen Dirichlet-Randbedingungen be-trachtet. In Tabelle 4.2 sind die Anzahl der Gitterpunkte und die der Lanczos-Schritte aufgefuhrt. Die geforderte Genauigkeit von 10−6 wurde immer erreicht.

N Lanczos Schritte100 1498200 1578400 1673800 16251600 16973200 17646400 183212800 191625600 200851200 2085102400 2201204800 3532

Tabelle 4.2: Anzahl der Gitterpunkte und der Lanczos-Schritte.

46

47

5 Numerische Vergleiche

In diesem Abschnitt werden die vorgestellten Verfahren miteinander vergli-chen. Alle Beispiele wurden in Matlab mit einem 1,86 GHz Prozessor und1GB Arbeitsspeicher berechnet. Als erstes Beispiel betrachten wir die Diffe-rentialgleichung

∂u

∂t(x, t) =

∂2u

∂x2(x, t) +

1

1 + u(x, t)2, u(x, 0) = u0(x), (5.1)

mit 0 ≤ x ≤ 1 fur 0 ≤ t ≤ 1 und homogenen Dirichlet-Randbedingungen. Umden Fehler berechnen zu konnen, wurde eine Referenzlosung mit dem Verfahrenradau5 und einer absoluten und relativen Toleranz von 10−12 berechnet.

Wir losen die Gleichung mit den exponentiellen Integratoren exp4 und demVerfahren von Krogstad (krog), dem Matlab Loser ode15s und rkc. Bei denbeiden exponentiellen Integratoren wurde die Gleichung mit und ohne Vorkon-ditionierung gelost. In den Tabellen 5.1-5.6 sind die geforderten Toleranzen,der Fehler gemessen in der Maximumsnorm, die Rechenzeit, die Anzahl derZeitschritte von t = 0 bis t = 1 und bei exp4 bzw. krog, die Anzahl der Krylov-Schritte aufgelistet, sowie die durchschnittliche Anzahl der Krylov-Schritte proZeitschritt, wenn man Gleichung (5.1) mit 400 Gitterpunkten bezuglich desOrtes diskretisiert. Das beim vorkonditioniertem Lanczos-Prozess auftretendetridiagonale Gleichungssystem wurde mit Hilfe der LU -Zerlegung direkt gelost,was auch bei den weiteren Beispielen der Fall ist. Zur Veranschaulichung istin Abbildung 5.1 der Fehler, gemessen in der Maximumsnorm, als Funktionder Rechenzeit aufgetragen. In Abbildung 5.2 sieht man eine Vergroßerung vonAbbildung 5.1.

Wie in Kapitel 2 erlautert, verwendet exp4 eine Schrittweitensteuerung. Dadas Produkt ϕ(−τA)v von der Schrittweite abhangt, muss bei der vorkon-ditionierten Variante in jedem Zeitschritt eine neue LU -Zerlegung berechnetwerden. Die hier verwendete Implementierung des Verfahrens von Krogstad ar-beitet mit einer konstanten Schrittweite und daher muss nur eine einzige LU -Zerlegung berechnet werden. Die Schrittweite bei dem Verfahren von Krogstadwurde hier so gewahlt, dass die geforderte Genauigkeit erreicht wurde. Wieman in den Tabellen 5.3 und 5.4 sieht, reicht fur geringe Genauigkeiten eineinziger Zeitschritt aus.

In Tabelle 5.1 sieht man, dass exp4 die geforderte Genauigkeit teilweise nichterreicht. Dies liegt daran, dass hier die maximale Anzahl der Krylov-Schrittepro Zeitschritt fur alle geforderten Genauigkeiten fest auf 100 gesetzt wurde.Durch andere Wahlen der maximalen Krylov-Schritte lasst sich die Genauig-keit steuern. In einigen Fallen ist es von Vorteil die Anzahl zu beschrankenund in anderen diese hochzusetzen, denn wenn in einem Durchlauf des Krylov-Verfahrens die maximale Anzahl erreicht wurde, wird die Schrittweite auto-

48

matisch verkleinert und der Zeitschritt, mit geringerem Aufwand, wiederholt.

0 20 40 60 8010

−15

10−10

10−5

100

Zeit

Fehl

er

krogkrogpreexp4exp4preode15srkc

Abb. 5.1: Fehler als Funktion der Rechenzeit fur Gleichung (5.1).

1 2 3 4 5 6 7

10−10

10−5

100

Zeit

Fehl

er

krogkrogpreexp4exp4preode15srkc

Abb. 5.2: Vergroßerung von Abb. 5.1.

49

In den Tabellen 5.1 und 5.2, sowie 5.3 und 5.4 sieht man, dass sich durch dieVorkonditionierung die Anzahl der Krylov-Schritte stark reduziert. Dadurchspart man, trotz Berechnung der LU -Zerlegung, Rechenzeit ein.

Beim Verfahren von Krogstad wurden, wie man in Tabelle 5.3 sieht, sehr vie-le Krylov-Schritte pro Zeitschritt benotigt, was zu einer langen Rechenzeitfuhrt. In einem Zeitschritt werden 4 Krylov-Raume konstruiert, d.h. wenn 200Krylov-Schritte gemacht werden, hat jeder durschnittlich die Dimension 50,was bei einem Problem der Dimension 400 nicht zufriedenstellend ist. Daherist es hier nicht sinnvoll das Produkt der ϕ-Funktionen mit einem Vektor durchKrylov-Methoden zu approximieren.

Abbildung 5.1 und 5.2 veranschaulichen, dass bei diesem Beispiel nur diebeiden vorkonditionierten exponentiellen Integratoren mit dem Matlab Loserode15s konkurieren konnen. rkc kann den Vorteil ohne die Jacobi-Matrix zuarbeiten bei diesem eindimensionalen Beispiel nicht ausnutzen.

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 6.00 · 10−1 1.31 49 481 9.810−2 9.53 · 10−1 0.97 47 563 12.010−3 1.52 · 10−2 1.63 78 1150 14.710−4 5.44 · 10−4 1.58 79 1038 13.110−5 1.60 · 10−3 2.36 81 2302 28.410−6 1.91 · 10−4 3.00 83 3353 40.410−7 1.55 · 10−6 3.86 82 4495 54.810−8 1.40 · 10−8 4.89 108 5945 55.0

Tabelle 5.1: Ergebnisse der Losung von Gleichung (5.1) mit exp4

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 1.91 · 10−5 0.25 5 18 3.610−2 3.42 · 10−7 0.22 6 37 6.210−3 2.91 · 10−7 0.25 7 58 8.310−4 9.00 · 10−8 0.31 9 88 9.810−5 1.70 · 10−8 0.36 11 147 13.410−6 4.66 · 10−9 0.53 14 252 18.010−7 3.05 · 10−10 0.88 20 488 24.410−8 9.61 · 10−11 1.42 30 885 29.5

Tabelle 5.2: Ergebnisse der Losung von Gleichung (5.1) mit exp4 und Vorkonditionierung

50

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 1.01 · 10−1 0.41 1 21 2110−2 4.55 · 10−3 3.70 1 160 16010−3 8.11 · 10−4 7.30 1 195 19510−4 2.07 · 10−4 14.75 1 384 38410−5 7.25 · 10−6 17.00 2 403 201.510−6 2.13 · 10−6 45.06 5 1186 237.210−7 9.57 · 10−8 57.48 7 1656 236.610−8 1.70 · 10−9 61.63 10 1975 197.5

Tabelle 5.3: Ergebnisse der Losung von Gleichung (5.1) mit krog und vorgegebenerSchrittweite

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 1.92 · 10−4 0.09 1 6 610−2 1.92 · 10−4 0.06 1 7 710−3 1.92 · 10−4 0.05 1 9 910−4 1.92 · 10−4 0.06 1 9 910−5 1.82 · 10−6 0.09 2 19 9.510−6 1.86 · 10−6 0.09 2 24 1210−7 2.39 · 10−7 0.14 3 38 12.710−8 2.53 · 10−8 0.19 5 67 13.4

Tabelle 5.4: Ergebnisse der Losung von Gleichung (5.1) mit krog, vorgegebenerSchrittweite und Vorkonditionierung

Toleranz Fehler Zeit in s Zeitschritte10−1 1.79 · 10−5 0.34 1610−2 5.90 · 10−6 0.19 2010−3 7.74 · 10−6 0.16 2810−4 2.13 · 10−6 0.20 4310−5 2.78 · 10−6 0.25 6610−6 2.59 · 10−7 0.33 10110−7 2.19 · 10−8 0.42 14510−8 4.90 · 10−9 0.58 204

Tabelle 5.5: Ergebnisse der Losung von Gleichung (5.1) mit ode15s

51

Toleranz Fehler Zeit in s Zeitschritte10−1 1.45 · 10−2 3.30 810−2 9.36 · 10−5 3.40 1310−3 1.13 · 10−4 3.94 2110−4 1.60 · 10−5 4.28 2910−5 3.14 · 10−6 6.27 5210−6 6.47 · 10−7 8.16 10110−7 1.40 · 10−7 11.67 21110−8 2.93 · 10−8 17.31 450

Tabelle 5.6: Ergebnisse der Losung von Gleichung (5.1) mit rkc

Als nachstes Beispiel betrachten wir das semilineare parabolische Problem

∂u

∂t(x, y, z, t) =

(∂2u

∂x2+

∂2u

∂y2+

∂2u

∂z2

)(x, y, z, t) + g(x, y, z, t), (5.2)

fur 0 ≤ x, y, z ≤ 1, 0 ≤ t ≤ 1 und homogenen Dirichlet-Randbedingungen.Dabei ist g so gewahlt, dass die exakte Losung durch

u(x, y, z, t) = x(1− x)y(1− y)z(1− z)et

gegeben ist. Die Losung u ist ein Polynom 2. Grades und es tritt kein Fehlerin der Ortsdiskretisierung auf, da der Diskretisierungsfehler von der drittenAbleitung der Losung abhangt. Als Anfangswert wurde u(x, y, z, 0) gewahlt.

Wir losen die Gleichung mit dem exponentiellen Integrator von Krogstad, so-wie dem Matlab Loser ode15s und rkc. Dazu ist der Laplace-Operator in(5.2) mit 20 Punkten in jede Richtung durch einen zentralen Differenzen-quotienten zweiter Ordnung diskretisiert, woraus sich ein System von 8000gewohnlichen Differentialgleichungen ergibt. Die Jacobi-Matrix ist dann durch4x−2(1, . . . , 1, . . . , 1, . . . ,−6, . . . , 1, . . . , 1, . . . , 1) gegeben, wobei ′′ . . .′′ fur Nul-len steht. Mit dem Satz von Gershgorin folgt, dass alle Eigenwerte in dem In-tervall [ −4

4x2+4y2+4z2 , 0] liegen, wobei hier 4x = 4y = 4z = 120+1

. Hier wirdexp4 nicht betrachtet, da das Verfahren fur autonome Probleme ist und dieFunktion g von t abhangt.

In Abbildung 5.3 ist der Fehler, gemessen in der Maximumsnorm, als Funktionder Rechenzeit aufgetragen. In den Tabellen 5.7-5.10 findet man die gefordertenToleranzen, den Fehler, die Rechenzeit in Sekunden, die Anzahl der Zeitschrit-te und bei krog die Anzahl der Krylov-Schritte, sowie die durchschnittlicheAnzahl der Krylov-Schritte pro Zeitschritt.

52

0 20 40 60 80 100 12010

−10

10−8

10−6

10−4

10−2

Zeit

Fehl

errkcode15skrogkrogpre

Abb. 5.3: Fehler als Funktion der Rechenzeit fur Gleichung (5.2)

Sowohl das Verfahren von Krogstad, als auch rkc benotigen weniger Rechenzeitals der Matlab Loser ode15s. Hier kann rkc deutlich den Vorteil nutzen, dass dieJacobi-Matrix im Verfahren nicht explizit verwendet wird. Bei dem Verfahrenvon Krogstad wurde die Schrittweite wieder so gewahlt, dass die geforderteToleranz erreicht wurde und man sieht wieder, dass nur wenige Zeitschrittebenotigt werden. Die vorkonditionierte Variante benotigt hier mehr Rechen-zeit als die Variante mit einfachem Lanczos-Verfahren. Dies liegt daran, dassdie Anzahl der Krylov-Schritte nicht so stark reduziert wird wie in Beispiel(5.1). Es wird zwar nur eine einzige LU -Zerlegung berechnet, was bei diesemBeispiel ungefahr 3.5 Sekunden dauert, aber es muss in jedem Krylov-Schrittein Gleichungssystem gelost werden, was hier ungefahr 0.1 Sekunden dauert.

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 3.57 · 10−4 0.28 1 4 410−3 1.75 · 10−4 0.41 2 22 1110−5 5.32 · 10−6 0.51 3 48 1610−6 1.51 · 10−6 1.30 5 125 2510−7 1.38 · 10−7 3.09 10 269 26.910−8 2.86 · 10−8 4.61 15 372 24.810−9 1.76 · 10−9 9.45 30 742 24.710−10 1.55 · 10−10 16.63 55 1319 24.0

Tabelle 5.7: Ergebnisse der Losung von Gleichung (5.2) mit krog und vorgegebenerSchrittweite

53

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 7.21 · 10−5 4.53 1 4 410−5 1.73 · 10−5 6.16 2 14 710−6 1.51 · 10−6 10.34 5 39 9.810−7 1.38 · 10−7 18.66 10 94 9.410−8 2.86 · 10−8 27.20 15 151 10.110−9 1.76 · 10−9 54.20 30 334 11.110−10 1.55 · 10−10 102.88 55 670 12.2

Tabelle 5.8: Ergebnisse der Losung von Gleichung (5.2) mit krog, vorgegebenerSchrittweite und Vorkonditionierung

Toleranz Fehler Zeit in s Zeitschritte10−1 4.66 · 10−5 18.84 1010−2 2.53 · 10−6 27.34 1010−4 4.48 · 10−8 36.23 1110−7 5.68 · 10−10 64.45 2410−9 1.15 · 10−10 83.83 37

Tabelle 5.9: Ergebnisse der Losung von Gleichung (5.2) mit ode15s

Toleranz Fehler Zeit in s Zeitschritte10−3 1.37 · 10−4 0.38 310−3 1.20 · 10−4 0.41 310−5 1.71 · 10−6 0.84 1110−7 8.00 · 10−8 1.53 3410−9 4.03 · 10−9 3.28 14210−10 8.32 · 10−10 4.97 29910−11 1.08 · 10−10 6.86 590

Tabelle 5.10: Ergebnisse der Losung von Gleichung (5.2) mit rkc

Als letztes Beispiel betrachten wir Gleichung (5.1) in 3 Ortsvariablen

∂u

∂t(x, y, z, t) =

(∂2u

∂x2+

∂2u

∂y2+

∂2u

∂z2

)(x, y, z, t) +

1

1 + u(x, y, z, t)2, (5.3)

mit 0 ≤ x, y, z ≤ 1 fur 0 ≤ t ≤ 1 und homogenen Dirichlet-Randbedingungen.Um den Fehler berechnen zu konnen, wurde wieder eine Referenzlosung mitdem Verfahren radau5 berechnet.

Die Gleichung wurde mit den gleichen Verfahren wie das eindimensionale Bei-spiel (5.1) gelost und der Laplace-Operator wie im vorigen Beispiel diskreti-siert. Die Ergebnisse findet man in den Tabellen 5.11-5.16 und eine graphischeDarstellung in den Abbildungen 5.4 und 5.5.

54

Wie auch bei Beispiel (5.2) benotigt der Matlab Loser ode15s die meiste Re-chenzeit, um die Gleichung zu losen. Dies ist darauf zuruckzufuhren, dass wieauch im vorigen Beispiel Gleichungssysteme mit der 8000×8000 Jacobi-Matrixzu losen sind. Da bei den vorkonditionierten exponentiellen Integratoren, wiein Abschnitt 4 beschrieben, eine Permutation in der LU -Zerlegung verwen-det wurde, wurde auch hier eine Variante von ode15s getestet, die mit einerUmsortierung arbeitet, aber dadurch hat sich die Rechenzeit nicht verbessert.Dennoch ist zu vermuten, dass sich dies auch fur ode15s in großeren Dimensio-nen auszahlen wurde. In Tabelle 5.15 sieht man, dass das Verfahren bereits beigeringen geforderten Genauigkeiten hohe Genauigkeiten erzielt. Es sind auchnur diese angegeben, da hohere geforderte Genauigkeiten teilweise geringereoder unwesentlich bessere Genauigkeiten liefern.

exp4pre erreicht genau wie ode15s bereits bei geringen geforderten Genau-igkeiten gute Approximationen. Daher sind hier auch nur diese angegeben.Vergleicht man in den Tabellen 5.11 und 5.12 die Anzahl der Krylov-Schritteund die der Zeitschritte, stellt man fest, dass hier nichts eingespart wird. Dain jedem Zeitschritt die LU -Zerlegung berechnet werden muss und in jedemKrylov-Schritt ein Gleichungssystem gelost wird, benotigt die vorkonditionier-te Variante viel mehr Rechenzeit.

In den Tabellen 5.13 und 5.14 sieht man, dass bei krog durch die Vorkondi-tionierung viele Krylov-Schritte eingespart werden konnen, aber trotzdem istdie Variante ohne Vorkonditionierung schneller, da die Berechnung der LU -Zerlegung und das Losen des Gleichungssystems den Rechenaufwand domi-nieren. Auch krogpre erzielt hohere Genauigkeiten als gefordert. Hier wurdewieder die Schrittweite dann verkleinert, wenn die geforderte Genauigkeit miteiner großeren Schrittweite nicht erreicht wurde.

Fur geringe geforderte Genauigkeiten liefert auch rkc schnell gute Approxi-mationen an die Losung, wohingegen die Rechenzeit, um hohere zu erreichen,schnell ansteigt.

55

0 20 40 60 80 10010

−15

10−10

10−5

100

Zeit

Fehl

erexp4exp4preode15srkckrogkrogpre

Abb. 5.4: Fehler als Funktion der Rechenzeit fur Gleichung (5.3).

0 10 20 30 4010

−15

10−10

10−5

100

Zeit

Fehl

er

exp4krogkrogprerkc

Abb. 5.5: Vergroßerung von Abb. 5.4.

56

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 1.40 · 10−3 0.53 8 43 5.410−2 3.26 · 10−4 0.91 10 79 7.910−3 2.41 · 10−5 1.23 11 97 8.810−4 7.26 · 10−7 1.34 12 130 10.810−5 2.44 · 10−8 1.94 14 217 15.510−6 2.56 · 10−9 3.41 18 365 20.310−7 4.36 · 10−10 5.06 27 556 20.610−8 2.06 · 10−11 7.59 44 829 18.8

Tabelle 5.11: Ergebnisse der Losung von Gleichung (5.3) mit exp4

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 5.69 · 10−8 38.56 9 46 5.110−2 1.00 · 10−8 49.92 11 81 7.410−4 3.55 · 10−10 66.83 13 170 13.1

Tabelle 5.12: Ergebnisse der Losung von Gleichung (5.3) mit exp4 und Vorkonditionierung

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 1.49 · 10−3 0.44 1 28 2810−2 3.60 · 10−4 0.36 1 40 4010−3 7.47 · 10−5 0.48 1 54 5410−4 7.16 · 10−5 0.72 1 70 7010−5 6.94 · 10−5 1.02 1 98 9810−6 1.70 · 10−6 1.66 2 145 72.510−7 4.85 · 10−10 2.59 3 223 74.310−8 2.37 · 10−10 3.20 3 267 89

Tabelle 5.13: Ergebnisse der Losung von Gleichung (5.3) mit krog und vorgegebenerSchrittweite

Toleranz Fehler Zeit in s Zeitschritte Krylov-Schritte Krylov-SchritteZeitschritte

10−1 6.93 · 10−5 4.89 1 7 710−2 6.92 · 10−5 5.02 1 8 810−3 6.92 · 10−5 5.22 1 10 1010−4 6.93 · 10−5 5.31 1 11 1110−5 3.49 · 10−7 6.98 2 22 1110−6 3.99 · 10−7 7.42 2 26 1310−7 8.90 · 10−11 9.61 3 42 1410−8 3.51 · 10−13 14.25 5 77 15.4

Tabelle 5.14: Ergebnisse der Losung von Gleichung (5.3) mit krog, vorgegebenerSchrittweite und Vorkonditionierung

57

Toleranz Fehler Zeit in s Zeitschritte10−1 2.36 · 10−8 54.17 2110−2 1.42 · 10−10 81.63 35

Tabelle 5.15: Ergebnisse der Losung von Gleichung (5.3) mit ode15s

Toleranz Fehler Zeit in s Zeitschritte10−1 1.50 · 10−3 0.98 1310−2 6.76 · 10−4 1.23 1910−3 1.91 · 10−4 1.36 2510−4 1.53 · 10−5 2.23 4510−5 1.58 · 10−6 3.83 9010−6 2.06 · 10−7 7.55 18910−7 3.21 · 10−8 15.36 40710−8 1.89 · 10−9 32.64 887

Tabelle 5.16: Ergebnisse der Losung von Gleichung (5.3) mit rkc

58

Literatur

[1] J.-E. Andersson. Approximation of e−x by rational functions with con-centrated negative poles. J. Approx. Theory, 32(2), 85-95, 1981

[2] S. Cox und P. Matthews. Exponential time differencing for stiff systems,Journal of Computational Physics, 176, 430-455, 2002

[3] G. H. Golub, Z. Zhang und H. Zha. Large sparse symmetric eigenvalueproblems with homogeneous linear constraints: the Lanczos process withinner-outer iterations. Linear Algebra Apll., 309(1-3), 289-306, 2000

[4] K. Gustafsson, M. Lundh und G. Soderlind, A PI stepsize control for thenumerical solution of ordinary differential equations. BIT 28, 270-287,1988

[5] M. Hochbruck und Ch. Lubich. On Krylov subspace approximations tothe matrix exponential operator. SIAM J. Num. Anal., 34, 1911-1925,1997

[6] M. Hochbruck, Ch. Lubich und H. Selhofer. Exponential integrators forlarge systems of differential equations. SIAM J. Num. Anal., 19, 1552-1574, 1998

[7] M. Hochbruck, Skripte zu Numerik Vorlesungen. Heinrich-Heine-Universitat Dusseldorf

[8] M.Hochbruck, A. Ostermann. Explicit exponentiel Runge-Kutta me-thods for semilinear parabolic problems, SINUM 2005

[9] J. Niehoff, Dissertation. Heinrich-Heine-Universitat Dusseldorf, 2006

[10] S. Krogstad, Generalized integrating factor methods for stiff PDEs, J.Comput. Phys., 203(1), 72-88, 2005

[11] Y. Saad, Analysis of some Krylov subspace approximations to the matrixexponential operator, SIAM J. Numer. Anal., 29(1), 209-228, 1992

[12] E.B. Saff, A. Schonhage und R. S. Varga. Geometric convergence toe−z by rational functions with real poles. Numer. Math., 25(3), 307-322,1975/76

[13] L.F. Shampine, Numerical Solution of the Ordinary Differential Equati-ons, Chapman and Hall, New York, 1994

[14] V. Simoncini und D. B. Szyld. Theory of inexact Krylov subspace me-thods and applications to scientific computing. SIAM J. Sci. Comput.,25(2), 454-477, 2003

59

[15] B.P. Sommeijer und J.G. Verwer, A perfomance evaluation of a classof Runge-Kutta-Chebyshev methods for solving semi-discrete parabolicdifferential equations, Report NW91/80, Mathematisch Centrum, Ams-terdam, 1980

[16] B.P. Sommeijer, RKC, a nearly-stiff ODE solver. Available from net-lib@ornl.gov, send rkc.f from ode, 1991

[17] B.P. Sommeijer, L.F. Shampine, J.G. Verwer, RKC: An explicit solverfor parabolic PDEs. J. Comput. Appl. Math. 88, 315-326, 1997

[18] P.J. van der Houwen und B.P. Sommeijer, On the internal stability ofexplicit m-stage Runge-Kutta methods for large values of m, ZAMM 60,479-485, 1980

[19] J. van den Eshof und M. Hochbruck: Preconditioning Lanczos approxi-mations to the matrix exponentiell, SIAM J. Sci. Comput., 27, 1438-1457,2006

[20] J. van den Eshof und G. L. G. Sleijpen. Inexact Krylov subspace methodsfor linear systems, SIAM J. Matrix Anal. and Appl., 26(1), 125-153, 2004

[21] J.G. Verwer, W.H. Hundsdorfer und B.P. Sommeijer, Convergence pro-perties of the Runge-Kutta-Chebyshev method, Numer. Math. 57, 157-178, 1990

[22] H.A. Watts, Step size control in ordinary differential equation solvers,Trans. Soc. for Computer Simulation 1, 15-25, 1984

Ich versichere hiermit, dass ich die vorgelegte Hausarbeit selbststandig verfasstund nur die angegebenen Quellen verwendet habe.

Jalo Liljo