Numerische Mathematik 2 - uni-due.de · Kapitel 1 Nichtlineare Gleichungssysteme und Ausgleichsprobleme 1.1 Wiederholung zum Newton-Verfahren und Erweiterung In Numerik I haben wir

Prof. Dr. Irwin Yousept Universität Duisburg-Essen

Numerik gewöhnlicher DifferentialgleichungenTypeset und Layout: Roman HändlerFassung vom 4. März 2017

Inhaltsverzeichnis

1 Nichtlineare Gleichungssysteme und Ausgleichsprobleme 11.1 Wiederholung zum Newton-Verfahren und Erweiterung . . . . . . . . . 1

1.1.1 Konvergenztests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.2 Erweiterung des Konvergenzbereichs . . . . . . . . . . . . . . . . 5

1.2 Newton-Verfahren und Nullstellen von Polynomen . . . . . . . . . . . . 61.3 Nichtlineares Ausgleichsproblem . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Gauß-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 111.3.2 Levenberg-Marquardt-Verfahren . . . . . . . . . . . . . . . . . . . 12

1.4 Konvergenzanalyse des Gauß-Newton-Verfahrens . . . . . . . . . . . . . 141.5 Parameterabhängige nichtlineare Gleichungssysteme . . . . . . . . . . . 18

1.5.1 Beispiel: Innere-Punkte-Methode für lineare Optimierung . . . . 181.5.2 Fortsetzungsmethode . . . . . . . . . . . . . . . . . . . . . . . . . 201.5.3 Natürlicher Monotonietest zur Schrittweitenbestimmung bei Fort-

setzungsmethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.5.4 Homotopiemethode . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2 Eigenwertprobleme 292.1 Vorbetrachtungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2 Nullstellen von gestörten reellen Polynomen . . . . . . . . . . . . . . . . 302.3 Die Schur-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 Störungssätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442.5 Rayleigh-Ritz-Quotient und Courant-Fischer-Variationsprinzip . . . . . 522.6 Numerische Behandlung von Eigenwerten . . . . . . . . . . . . . . . . . 58

2.6.1 Vektoriterationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582.6.2 Das QR-Verfahren zur Eigenwertbestimmung . . . . . . . . . . . 62

3 Das GMRES-Verfahren 713.1 Arnoldi-Prozess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.1.1 Matrixversion des Arnoldi-Prozesses . . . . . . . . . . . . . . . . 733.2 Definition des GMRES-Verfahrens . . . . . . . . . . . . . . . . . . . . . . 753.3 Vorgehensweise zur Lösung der Minimierungsprobleme beim GMRES-

Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773.3.1 Detaillierte Beschreibung der QR-Zerlegungen . . . . . . . . . . . 78

iii

4 Numerische Lösung gewöhnlicher Differentialgleichungen 834.1 Einführung zu gewöhnlichen Differentialgleichungen . . . . . . . . . . . 834.2 Bekannte numerische Lösungsverfahren . . . . . . . . . . . . . . . . . . . 85

4.2.1 Das explizite Euler-Verfahren (Polygonzug-Verfahren) . . . . . . 854.2.2 Das implizite Euler-Verfahren . . . . . . . . . . . . . . . . . . . . 854.2.3 Trapezmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864.2.4 Einfache Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.3 Theorie der expliziten Einschrittverfahren . . . . . . . . . . . . . . . . . . 884.3.1 Explizites Einschrittverfahren der Konsistenzordnung p = 1 . . . 924.3.2 Explizite Einschrittverfahren höherer Konsistenzordnung . . . . 93

4.4 Mehrschrittverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944.4.1 Definition des Mehrschrittverfahrens . . . . . . . . . . . . . . . . 944.4.2 Konvergenzaussage . . . . . . . . . . . . . . . . . . . . . . . . . . 964.4.3 Lemma von Gronwall . . . . . . . . . . . . . . . . . . . . . . . . . 994.4.4 Beschränktheit der Folge {

∥∥Ak∥∥

∞}∞k=0 . . . . . . . . . . . . . . . . 102

4.4.5 Adams-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1064.4.6 BDF-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Kapitel 1Nichtlineare Gleichungssysteme

und Ausgleichsprobleme

1.1 Wiederholung zum Newton-Verfahren undErweiterung

In Numerik I haben wir das Newton-Verfahren zur Lösung von

F(x) = 0, F : Rn → Rn

behandelt. Ausgehend von der aktuellen Iterierten xk ∈ Rn löst man das lineareGleichungssystem

F′(xk)dk = −F(xk)

und dann definiert man

xk+1 = xk + dk ⇔ xk+1 = xk − F′(xk)−1F(xk).

Beachte, dass F′(xk) = (∂iFj(xk)) ∈ Rn×n die Jacobi-Matrix von F an der Stelle xk

bezeichnet.Satz 1.1. Es sei D ⊂ Rn offen und konvex, F : Rn ⊃ D → Rn stetig differenzierbar mitJacobi-Matrix F′(x), welche für alle x ∈ D regulär (invertierbar) ist. Es existiere eine Konstanteω > 0, so dass gilt

‖F′(x)−1(F′(x + sv)− F′(x))v‖2 ≤ sω ‖v‖22 (1.1)

für alle x ∈ D, v ∈ Rn mit x + v ∈ D, s ∈ [0, 1]. Es sei F(x) = 0, x ∈ D, und der Startwertx0 ∈ D so gewählt, dass

ρ := ‖x− x0‖2 <2ω

und Bρ(x) ⊂ D.

Dann erzeugt das Newton-Verfahren eine eindeutig definierte Folge {xk} ⊂ Bρ(x) mit

limk→∞

xk = x.

Weiter gilt‖xk+1 − x‖2 ≤

ω

2‖xk − x‖2

2 (quadratische Konvergenz).

1

1.1 Wiederholung zum Newton-Verfahren und Erweiterung

Bemerkung 1.2.

(i) Eine andere äquivalente Variante des Satzes haben wir bereits in Numerik Ibewiesen.

(ii) Die Voraussetzung (1.1) sieht etwas kompliziert aus. Eingängiger ist die Folgende:F′(x) sei regulär und F′ sei lokal Lipschitz-stetig, das heißt es existieren Θ, L > 0,so dass ∥∥F′(x)− F′(y)

∥∥2 ≤ L ‖x− y‖2 ∀x, y ∈ BΘ(x).

Da F′(x) regulär ist, gibt es ein ε > 0, so dass die Jacobi-Matrizen

F′(x) ∈ Rn×n ∀x ∈ Bε(x)

regulär sind und

‖F′(x)−1‖2 ≤ 2‖F′(x)−1‖2 ∀x ∈ Bε(x).

Es gilt also

‖F′(x)−1(F′(x + sv)− F′(x))v‖2 ≤ ‖F′(x)−1‖2∥∥(F′(x + sv)− F′(x))v

∥∥2

≤ ‖F′(x)−1‖2∥∥F′(x + sv)− F′(x)

∥∥2 ‖v‖2

≤ 2‖F′(x)−1‖2L ‖sv‖2 ‖v‖2

= s 2‖F′(x)−1‖2L︸︷︷︸=:ω

‖v‖22

für alle x ∈ Bε(x) und v ∈ Rn mit x + v ∈ Bε(x), s ∈ [0, 1] mit ε := min{ε, Θ}.Wählen wir nun D = Bε(x), so sehen wir, dass (1.1) erfüllt ist.

Beispiele 1.3.

(i) Berechnung von√

2. Definiere F(x) := x2 − 2. Dann ist eine Nullstelle von F(x)gegeben durch x =

√2. Wir erhalten die Ableitung F′(x) = 2x, welche global

Lipschitz ist mit F′(x) = 2√

2 6= 0.

x =√

2

F′(x) 6= 0

2


(ii) F(x) = arctan(x).

π2

−π2

F hat genau eine Nullstelle bei x = 0. Die Newtonvorschrift lautet

xk+1 = xk + dk = xk − F′(xk)−1F(xk)

= xk − (1 + xk2) arctan(xk),

denn

F′(x) =1

1 + x2 .

Gilt arctan(|x0|) ≥ 2|x0|1+x02 , so divergiert das Newton-Verfahren und bei „>“ gilt

limk→∞|xk| = ∞.

Bei arctan(|x0|) = 2|x0|1+x02 (o.B.d.A. arctan(x0) = 2x0

1+x02 ) gilt

x1 = x0 + d0 = x0 − (1 + x02)

2x0

1 + x02 = −x0

und

x2 = x1 − (1 + x12) arctan(x1) = −x0 + (1 + x02

) arctan(x0) = x0.

In diesem Fall gilt xk = (−1)kx0.

Das obige Beispiel zeigt, dass das Newton-Verfahren im Allgemeinen nur lokal kon-vergiert. Bei der numerischen Umsetzung kann man nicht von vornherein wissen, obman im Einzugsbereich des Verfahrens liegt. Deshalb benötigt man Konvergenztestsund Strategien zur Erweiterung des Konvergenzbereiches.

3


1.1.1 Konvergenztests

Intuitiv nimmt man an, dass die aktuelle Iterierte umso näher an der Lösung x ist,je kleiner das Residuum ‖F(xk)‖2 ist. Um ‖F(xk)‖2 zu minimieren, wäre deshalb einmonotoner Abstieg

‖F(xk+1)‖2 ≤ ϑ‖F(xk)‖2 „Standard-Monotonietest“

mit einer positiven Zahl 0 < ϑ < 1 wünschenswert. Verletzt das Verfahren dieseBedingung, so bricht man ab. Ein anderer Monotonietest ist wie folgt:

‖F′(xk)−1F(xk+1)‖2 ≤ ϑ‖F′(xk)−1F(xk)‖2 „Natürlicher Monotonietest.“

Der natürliche Monotonietest lässt sich wie folgt motivieren:

xk+1 − xk = dk = −F′(xk)−1F(xk) „Newton-Korrektur.“

Die neue Newton-Korrektur lautet

dk+1 = −F′(xk+1)−1F(xk+1).

Wir verwenden aber die vereinfachte Newton-Korrektur

dk+1 = −F′(xk)−1F(xk+1).

Dann lautet der natürliche Monotonietest

‖dk+1‖2 ≤ ϑ‖dk‖2.

Zur Durchführung des natürlichen Monotonietests müssen wir das lineare Gleichungs-system

F′(xk)dk+1 = −F(xk+1)

lösen. Das ist aber bei dem aktuellen Schritt einfach zu lösen, denn zur Lösung von

F′(xk)dk = −F(xk)

hat man bereits eine LR-Zerlegung F′(xk) = LR gefunden. Also ist

F′(xk)dk+1 = −F(xk+1)

äquivalent zu

LRdk+1 = −F(xk+1).

Daraus ergibt sich

Ly = −F(xk+1) „Vorwärtssubstitution“

Rdk+1 = y „Rückwärtssubstitution“.

Als Abbruchkriterium verwendet man oft1: if

∥∥dk+1∥∥

2 > 12

∥∥dk∥∥

2 then2: STOP3: end if

4


1.1.2 Erweiterung des Konvergenzbereichs

In der Praxis verwendet man als Standardmethode die Dämpfung des Newton-Verfahrens. An Stelle von

xk+1 = xk + dk (voller Newton-Schritt)

verwendet manxk+1 = xk + λkdk

mit Dämpfungsfaktor λk ∈ (0, 1]. Man geht vorsichtig vor, um ein „Überschießen“ wiebeim arctan-Beispiel zu vermeiden.Idee: Natürlicher Konvergenztest mit

ϑ := (1− λk2).

Großer Schritt: λk ≈ 1 und ϑ ≈ 12 (enges Abbruchkriterium).

Vorsichtiger Schritt: λk � 1 und ϑ ≈ 1.Gesucht ist nun ein geeignetes λk aus (0, 1] mit

‖F′(xk)−1F(xk + λkdk)‖2 ≤ (1− λk2)‖dk‖2.

Daraus ergibt sich das folgende Verfahren:

Algorithmus 1.1 Gedämpftes Newton-Verfahren mit natürlichem Konvergenztest

(S0) Wähle einen Startwert x0 ∈ Rn und setze λ0 = 1, k = 0.(S1) Abbruchkriterium:

1: if∥∥F(xk)

∥∥2 = 0 then

2: STOP3: end if

(S2) Bestimme dk ∈ Rn als Lösung von

F′(xk)dk = −F(xk).

(S3) Monotonietest:4: while

∥∥F′(xk)−1F(xk + λkdk)∥∥

2 > (1− λk2 )∥∥dk∥∥

2 do5: λk = 0.5λk6: end while

(S4) Setze xk+1 = xk + λkdk und

λk+1 = min{1, 2λk},

gehe zu (S1).

5

1.2 Newton-Verfahren und Nullstellen von Polynomen

Bemerkung 1.4.

(i) Zur Bestimmung von dk verwendet man zum Beispiel eine LR-Zerlegung fürF′(xk). Die gespeicherte LR-Zerlegung wird dann für den Monotonietest in (S3)verwendet.

(ii) Hier kann man auch das vereinfachte Newton-Verfahren verwenden (Abschnitt5.3, Numerik I).

(iii) Weglassen von kleinen unwichtigen Elementen in F′(xk) („sparsing“).

(iv) Fortsetzungsmethoden behandeln wir später.


Die Nullstellenbestimmung von Polynomen ist überaus wichtig für die Berechnungvon Eigenwerten. In diesem Abschnitt zeigen wir, wie man die größte reelle Nullstelleeines reellen Polynoms durch das Newton-Verfahren berechnen kann.Satz 1.5 (Größte Nullstelle). Es sei p ∈ Πn ein reelles Polynom vom Grad n ∈N, welcheseine reelle Nullstelle λ1 ∈ R besitze, so dass gilt:

Re ζ ≤ λ1

für alle anderen Nullstellen ζ ∈ C von p. Dann konvergiert das Newton-Verfahren für jedenStartwert x0 > λ1 streng monoton fallend gegen λ1.

Illustration 1.6.

λ1 x0

6


Beweis. Wir zählen die Nullstellen von p wie folgt:

λ1 ≥ λ2 ≥ . . . ≥ λl reelle Nullstellen,ζ1, ζ1, . . . , ζm, ζm zueinander konjugierte komplexe Paare von Nullstellen /∈ R.

Daraus folgt

p(x) =l

∏k=1

(x− λk)m

∏k=1

(x− ζk)(x− ζk). (1.2)

Für die Ableitung f ′(x) eines Produkts

f (x) =n

∏k=1

(x− ηk)

machen wir uns klar, dass

f ′(x) =n

∑k=1

n

∏j=1j 6=k

(x− ηj) =

(n

∑k=1

1(x− ηk)

)n

∏j=1

(x− ηj)

=

(n

∑k=1

1(x− ηk)

)f (x)

gilt. Nach diesem Prinzip erhalten wir für p′:

p′(x) =

(l

∑k=1

1(x− λk)

+ 2m

∑k=1

x− Re ζk

(x− ζk)(x− ζk)

)p(x), (1.3)

denn (x− ζk)(x− ζk) = x2 − 2x Re(ζk) + |ζk|2, also

ddx

= 2(x− Re ζk) (x ist reell).

Weiter gilt

(x− ζk)(x− ζk) = x2 − 2x Re(ζk) + |ζk|2

≥ x2 − 2x Re(ζk) + (Re ζk)2

= (x− Re ζk)2

≥ 0.

Somit liefert (1.2)-(1.3):

p(x) > 0 und p′(x) > 0 für x > λ1,

denn laut Voraussetzung gilt Re ζ ≤ λ1 für alle Nullstellen ζ. Hieraus ergibt sich

x− p(x)p′(x)

< x für x > λ1.

7


Andererseits gilt auch für x > λ1:(l

∑k=1

1x− λk

+ 2m

∑k=1

x− Re ζk


)>

1x− λ1

,

also folgt mit (1.3)

p′(x)p(x)

=

(l

∑k=1

1x− λk

+ 2m

∑k=1

x− Re ζk


)⇔ p(x)

p′(x)< x− λ1

und somit

x− p(x)p′(x)

> x− (x− λ1) = λ1.

Insgesamt gilt

λ1 < x− p(x)p′(x)

< x für x > λ1. (1.4)

Sei nun x0 > λ1 beliebig aber fest gewählt. Dann erzeugt das Newton-Verfahren

xk+1 = xk − p(xk)

p′(xk)

eine beschränkte und streng monoton fallende Folge {xk}k∈N. Somit ist diese Folgekonvergent. Für den Grenzwert x ∈ R gilt zum einen:

x ≥ λ1 wegen (1.4).

Nun zeigen wir, dass x eine Nullstelle ist. Dazu gilt

p′(xk)(xk − xk+1) = p(xk) (Newton-Iteration).

Daraus folgt mit der Stetigkeit von p und p′:

p(x) = limk→∞

p(xk) = limk→∞

p′(xk)(xk − xk+1) = p′(x) · 0 = 0.

Also ist x eine Nullstelle. Nach Voraussetzung gilt nun x ≤ λ1 und insgesamt ergibtsich x = λ1.

Die Anwendbarkeit des Satzes verdeutlicht die folgende Situation für ein Polynomvom Grad 5:

λ1λ2

ζ1

ζ1

λ3

8

1.3 Nichtlineares Ausgleichsproblem

Die Nullstelle λ1 berechnet sich wie im Satz, falls x0 > λ1. Für λ2 verwendet man dasdeflationierte Polynom

p(x) :=p(x)

x− λ1.

Daraus lässt sich λ2 berechnen. Für λ3 kann man den Satz nicht anwenden.Bemerkung 1.7. Die Nullstelle λ1 ist a priori nicht bekannt. Daher ist es unklar, wieman x0 sinnvoll wählen sollte. Dazu hilft die folgende Aussage:Das reelle Polynom p ∈ Πn

p(x) = a0 + a1x + . . . + anxn mit an 6= 0

habe Nullstelle ζ /∈ C. Dann gilt

|ζ| ≤ max

{1,

n−1

∑k=0

∣∣∣∣ akan

∣∣∣∣}

.


Bei nichtlinearen Ausgleichsproblemen wendet man in der Regel nicht das Newton-Verfahren an, sondern das einfache Gauß-Newton-Verfahren.Definition 1.8. Es sei F : Rn → Rm eine Funktion, die hinreichend oft stetig differen-zierbar ist mit m ≥ n. Als nichtlineares Ausgleichsproblem bezeichnet man die folgendeAufgabe:

minx∈Rn

‖F(x)‖22 . (P)

Bemerkung 1.9.

(i) Ist x ∈ Rn eine Lösung von (P), so muss F(x) nicht notwendigerweise verschwin-den.

(ii) Ist F : Rn ⊃ D → Rm nur auf dem Definitionsbereich D definiert, so heißt dieAufgabe

minx∈D‖F(x)‖2

2

nichtlineares restringiertes Ausgleichsproblem. In dieser Vorlesung betrachtenwir nur den Fall D = Rn.

Beispiel 1.10. Die gedämpfte Schwingung wird durch die Differentialgleichung

u′′(t) +bm

u′(t) +Dm

u(t) = 0

beschrieben. Hieraus erhält man eine Lösung der Gestalt

u(t) = u0e−δt sin(ωt + ϕ0),

9


wobei

u(t) : Auslenkung zum Zeitpunkt t,u0 : Anfangswert,ω : Frequenz,δ : Abklingskonstante,

ϕ0 : Anfangsphase der Schwingung.

Liegen die Werte u0, ϕ0, ω, δ nicht vor, so lassen sich diese mittels einem nichtlinearenAusgleichsproblem approximieren. Angenommen sind

(ti, ui), i = 1, . . . , m

m-verschiedene Messwerte der Auslenkung ui zum Zeitpunkt ti. Wir definieren dieFehlerfunktion F : R4 → Rm durch

F(u0, δ, ω, ϕ0) :=

u0eδt1 sin(ωt1 + ϕ0)− u1...

u0eδtm sin(ωtm + ϕ0)− um

.

Die Lösung des nichtlinearen Ausgleichproblems

min(u0,δ,ω,ϕ0)∈R4

‖F((u0, δ, ω, ϕ0))‖22

liefert eine Approximation für die tatsächlichen physikalischen Werte u0, δ, ω, ϕ0.

Idee zur Lösung von nichtlinearen Ausgleichsproblemen:Es sei F : Rn → Rm zweimal stetig differenzierbar. Wir setzen

g : Rn → R, g(x) := ‖F(x)‖22 = (F(x), F(x))Rm .

Somit ist das nichtlineare Ausgleichsproblem (P) äquivalent zu

minx∈Rn

g(x).

Gesucht ist ein (lokales) Minimum von g. Die notwendige Optimalitätsbedingunglautet

∇g(x) = 0 ⇔ F′(x)TF(x) = 0.

Idee: Anwendung des Newton-Verfahrens auf die Gleichung

F′(x)TF(x) = 0.

Dazu setzen wirG : Rn → Rn, G(x) := F′(x)TF(x).

10


Die Newton-Vorschrift lautet {G′(xk)dk = −G(xk)

xk+1 = xk + dk

mit der Jacobi-Matrix G′(xk) ∈ Rn×n mit

G′(xk) = F′(xk)TF′(xk) +m

∑i=1

Fi(xk)F′′i (xk),

wobei F′′i (xk) ∈ Rn×n die Hesse-Matrix der Funktion Fi : Rn → R bezeichnet.

1.3.1 Gauß-Newton-Verfahren

Beim Gauß-Newton-Verfahren vernachlässigen wir den zweiten Term in der Ableitungvon G. An Stelle von

G′(xk)dk = −G(xk)

lösen wir die einfachere Aufgabe{F′(xk)TF′(xk)dk = −F′(xk)TF(xk),xk+1 = xk + dk.

Bemerkung 1.11. Die numerische Realisierung von ∑mi=1 Fi(xk)F′′i (xk) ist sehr aufwen-

dig. Dieser Term ist oft klein und deshalb ist das Gauß-Newton-Verfahren sinnvoll.

Algorithmus 1.2 Gauß-Newton-Verfahren

(S0) Wähle einen Startwert x0 ∈ Rn und setze k = 0.(S1) Abbruchkriterium:

1: if k > 0 und∥∥dk∥∥

2 = 0 then2: STOP3: end if

(S2) Bestimme dk ∈ Rn als Lösung von

F′(xk)TF′(xk)dk = −F′(xk)TF(xk).

(S3) Setze xk+1 = xk + dk und k = k + 1 und gehe zu (S1).

Das folgende Lemma beantwortet die Frage, ob Algorithmus 1.2 immer durchführbarist.Lemma 1.12. Es sei F : Rn → Rm differenzierbar. Dann ist das Gauß-Newton-Verfahrendurchführbar. Mit anderen Worten besitzt

F′(xk)TF′(xk)dk = −F′(xk)TF(xk)

für jedes k = 0, 1, 2, . . . eine Lösung dk ∈ Rn.

11


Beweis. Sei k ∈N∪ {0}. Wir setzen

A := F′(xk) ∈ Rm×n

b := −F(xk) ∈ Rm.

Betrachte nun das lineare Ausgleichsproblem

mindk∈Rn

‖Adk − b‖2.

Aus Numerik I wissen wir, dass die obige Aufgabe stets eine Lösung dk ∈ Rn besitzt.Die notwendige und hinreichende Bedingung lautet

AT Adk = ATb,

also in unserem FallF′(xk)TF′(xk)dk = −F′(xk)TF(xk).

Folgerung 1.13. Das Gauß-Newton-Verfahren ist äquivalent zu einer Folge von linea-ren Ausgleichsproblemen min

dk∈Rn

∥∥F(xk) + F′(xk)dk∥∥2

2

xk+1 = xk + dk.

Bemerkung 1.14. Die Matrix F′(xk)TF′(xk) ∈ Rn×n ist im Allgemeinen nur symme-trisch und positiv semidefinit, so dass die Lösung dk ∈ Rn von

F′(xk)TF′(xk)dk = −F′(xk)TF(xk)

im Allgemeinen nicht eindeutig ist.

1.3.2 Levenberg-Marquardt-Verfahren

Wir haben gesehen, dass das Gauß-Newton-Verfahren die lineare Approximation

‖F(x)‖22 ≈ ‖F(xk) + F′(xk)(x− xk)‖2

2

verwendet. Diese Approximation ist nur für x nahe bei xk bzw. für kleine Zuwächse dk

gut. Daher sollte die Lösung dk ∈ Rn von

mindk∈Rn

‖F(xk) + F′(xk)dk‖22

klein bleiben, das heißt‖dk‖2 ≤ ε.

12


Dies erreicht man durch Addition von µ‖dk‖22 mit µ > 0 „klein“ im Gauß-Newton-

Verfahren:min

dk∈Rn‖F(xk) + F′(xk)dk‖2

2 + µ‖dk‖22.

Je größer µ wird, desto kleiner wird∥∥dk∥∥

2. Man kann µ = 0 wählen, falls∥∥dk∥∥

2 ≤ ε,ansonsten µ > 0. Beim Levenberg-Marquardt-Verfahren löst man also

(F′(xk)TF′(xk) + µI)︸︷︷︸s.p.d. für µ>0

dk = −F′(xk)TF(xk).

Beachte, dass die obige Gleichung genau eine Lösung dk ∈ Rn besitzt, denn die Matrix

(F′(xk)TF′(xk) + µI) ∈ Rn×n

ist symmetrisch und positiv definit.Lemma 1.15. Es sei F : Rn → Rm differenzierbar und xk ∈ Rn. Dann gilt:

(i) Für jedes µ ∈ R+ ist die Matrix (F′(xk)TF′(xk) + µI) ∈ Rn×n symmetrisch undpositiv definit.

(ii) Die Abbildung

Φ : (0, ∞)→ [0, ∞), Φ(µ) = ‖(F′(xk)TF′(xk) + µI)−1F′(xk)TF(xk)‖2

ist stetig und monoton fallend mit

limµ→∞

Φ(µ) = 0.

(iii) Ist F′(xk)TF′(xk) ∈ Rn×n regulär, so gilt

limµ→0

(F′(xk)TF′(xk) + µI)−1F′(xk)F(xk) = (F′(xk)TF′(xk))−1F′(xk)TF(xk).

Beweis.

(i) Klar, da F′(xk)TF′(xk) ∈ Rn×n symmetrisch und positiv semidefinit ist.

(ii) Die Matrix F′(xk)TF′(xk) ist symmetrisch und positiv semidefinit, und somit exis-tiert eine Orthonormalbasis {vj}n

j=1 ⊂ Rn aus Eigenvektoren vj von F′(xk)TF′(xk)zu den Eigenwerten λj ≥ 0. Folglich gilt

F′(xk)TF(xk) =n

∑j=1

cjvj

mit cj = vTj F′(xk)TF(xk) ∈ R, da (vj , vi)Rn = δij. Also ist

(F′(xk)TF′(xk) + µI)−1F′(xk)TF(xk) =n

∑j=1

cj

λj + µvj,

13

1.4 Konvergenzanalyse des Gauß-Newton-Verfahrens

da vj Eigenvektor von (F′(xk)TF′(xk) + µI)−1 zum Eigenwert 1λj+µ ist. Daher ist

∥∥∥(F′(xk)TF′(xk) + µI)−1F′(xk)TF(xk)∥∥∥2

2=

∥∥∥∥∥ n

∑j=1

cj

λj + µvj

∥∥∥∥∥2

2

=

(n

∑j=1

cj

λj + µvj ,

n

∑k=1

ckλk + µ

vk

)Rn

=n

∑j=1

(cj

λj + µ

)2

.

Nun ist also

Φ(µ) =

√√√√ n

∑j=1

(cj

λj + µ

)2

und somit ist Φ : (0, ∞)→ [0, ∞) stetig und monoton fallend. Mit µ→ ∞ ist

limµ→∞

Φ(µ) = 0.

(iii) Übungsaufgabe.


In Numerik I haben wir das folgende Resultat gezeigt:Lemma 1.16. Es seien A, B ∈ Rn×n mit ‖I − BA‖2 < 1. Dann sind A und B regulär undes gilt

‖A−1‖2 ≤‖B‖2

1− ‖I − BA‖2.

Korollar 1.17. Es sei G : Rn → Rn×n stetig. Ferner sei x ∈ Rn, so dass G(x) ∈ Rn×n

invertierbar ist. Dann existiert ein δ > 0, so dass die Matrizen

G(x) ∈ Rn×n ∀x ∈ Bδ(x)

invertierbar sind mit

‖G(x)−1‖2 ≤ 2‖G(x)−1‖2 ∀x ∈ Bδ(x).

Beweis. Da die Abbildung G : Rn → Rn×n stetig ist, existiert ein δ > 0, so dass

‖G(x)− G(x)‖2 ≤1

2 ‖G(x)−1‖2∀x ∈ Bδ(x).

14


Folglich gilt

‖I − G(x)−1G(x)‖2 ≤ ‖G(x)−1(G(x)− G(x))‖2

≤ ‖G(x)−1‖2‖G(x)− G(x)‖2

≤ 12∀x ∈ Bδ(x).

Das obige Lemma mitB := G(x)−1 und A := G(x)

liefert, dass G(x) für alle x ∈ Bδ(x) invertierbar sind mit

‖G(x)−1‖2 ≤∥∥G(x)−1

∥∥2

1− ‖I − G(x)−1G(x)‖2≤ 2‖G(x)−1‖2.

Die folgende Aussage haben wir auch bereits in Numerik I gezeigt.Lemma 1.18. Es sei F : Rn → Rm differenzierbar. Dann besitzt das Restglied

r(x, y) := F(y)− F(x)− F′(x)(y− x) ∀x, y ∈ Rn

die folgende Integraldarstellung:

r(x, y) =∫ 1

0F′(x + t(y− x))(y− x)− F′(x)(y− x)dt ∀x, y ∈ Rn.

Satz 1.19 (Lokale Konvergenz des Gauß-Newton-Verfahrens im Falle F(x) = 0). Es seiF : Rn → Rm stetig differenzierbar und x ∈ Rn eine Nullstelle von F. Ferner sei

F′(x)TF′(x) ∈ Rn×n

invertierbar. Dann existiert ein ε > 0, so dass das Gauß-Newton-Verfahren für jeden Startwertx0 ∈ Bε(x) superlinear gegen x konvergiert.

Beweis. Da F′(x)TF′(x) ∈ Rn×n invertierbar ist und die Abbildung x 7→ F′(x)TF′(x)stetig ist, existiert laut Korollar ein ε1 > 0, so dass die Matrizen F′(x)TF′(x) für allex ∈ Bε1(x) invertierbar sind mit

‖(F′(x)TF′(x))−1‖2 ≤ 2‖(F′(x)TF′(x))−1‖2 ∀x ∈ Bε1(x). (1.5)

Die Stetigkeit der Abbildung x 7→ F′(x) liefert die Existenz einer positiven Zahl M > 0,so dass gilt

‖F′(x)T‖2 ≤ M ∀x ∈ Bε1(x). (1.6)

Sei nun α ∈ (0, 1) beliebig aber fest. Da F : Rn → Rm stetig differenzierbar ist, existiertein ε2 > 0 mit∫ 1

0

∥∥F′(x + t(x− x))− F′(x)∥∥

2 dt ≤ α

2 ‖(F′(x)TF′(x))−1‖2 M∀x ∈ Bε2(x).

15


Aus dem vorherigen Lemma folgt nun

‖r(x, x)‖2 ≤∫ 1

0

∥∥F′(x + t(x− x))− F′(x)∥∥

2 dt ‖x− x‖2

≤ α

2 ‖(F′(x)TF′(x))−1‖2 M‖x− x‖2 ∀x ∈ Bε2(x). (1.7)

Wir setzen ε := min{ε1, ε2}. Sei xk ∈ Bε(x) und xk+1 ∈ Rn die durch das Gauß-Newton-Verfahren erzeugte neue Iterierte. Dann gilt

xk+1 − x = (F′(xk)TF′(xk))−1(F′(xk)TF′(xk))(xk+1 − xk︸︷︷︸=dk

+xk − x)

= (F′(xk)TF′(xk))−1((−F′(xk)TF(xk))

+ (F′(xk)TF′(xk))(xk − x) + F′(xk) F(x)︸︷︷︸=0

)

= (F′(xk)TF′(xk))−1F′(xk)T(F(x)− F(xk)− F′(xk)(x− xk))︸︷︷︸=r(xk,x)

.

Daher ist mit (1.5)-(1.7)

‖xk+1 − x‖2 ≤ ‖(F′(xk)TF′(xk))−1‖2‖F′(xk)T‖2‖r(xk, x)‖2‖xk − x‖2

≤ α‖xk − x‖2

mit α ∈ (0, 1). Ist x0 ∈ Bε(x), so folgt aus der obigen Ungleichung

xk ∈ Bε(x) ∀k ∈N (denn ‖xk − x‖2 ≤ αk‖x0 − x‖2 < ε)

und‖xk+1 − x‖2 ≤ α‖xk − x‖2 ∀k ∈N.

Somit konvergiert die Folge {xk} gegen x linear mit Konvergenzrate α ∈ (0, 1), fallsx0 ∈ Bε(x). Die superlineare Konvergenz erfolgt wie beim Newton-Verfahren, dasheißt

limk→∞

∥∥xk+1 − x∥∥

2∥∥xk − x∥∥

2= 0.

In der Praxis kann man leider nicht mehr erwarten, dass eine Lösung x ∈ Rn von demAusgleichsproblem

minx∈Rn

‖F(x)‖22

der Bedingung F(x) = 0 genügt. Ist ‖F(x)‖2 hinreichend klein und ist die Abbildung

(F′)T : Rn → Rn×m

zusätzlich lokal Lipschitz-stetig in x, so können wir zeigen, dass das Gauß-Newton-Verfahren lokal gegen x konvergiert.

16


Satz 1.20 (Lokale Konvergenz des Gauß-Newton-Verfahrens im Fall F(x) 6= 0). Es seiF : Rn → Rm stetig differenzierbar und x ∈ Rn, so dass

F′(x)TF(x) = 0 und F′(x)TF′(x) ∈ Rn×n

invertierbar ist. Es existieren δ, L > 0, so dass gilt

‖F′(x)T − F′(x)T‖2 ≤ L ‖x− x‖2 ∀x ∈ Bδ(x). (lokale Lipschitzsannahme) (A1)

Es gebe eine weitere Konstante β ∈ (0, 1), so dass gilt

‖F(x)‖2 ≤β

2L ‖(F′(x)TF′(x))−1‖2. (A2)

Dann existiert ein ε > 0, so dass das Gauß-Newton-Verfahren für jeden Startwert x0 ∈ Bε(x)linear gegen x konvergiert.

Bemerkung 1.21. Anders als beim vorherigen Satz benötigen wir nun zusätzlich dielokale Lipschitzannahme (A1) und die Bedingung (A2). Beachte auch, dass der Satznur die lokale lineare Konvergenz sichert.

Beweis. Es sei α ∈ (0, 1) mit γ := α + β ∈ (0, 1). Aus Stetigkeitsgründen existiert einε > 0, so dass gilt

∥∥(F′(x)TF′(x))−1∥∥

2 ≤ 2∥∥(F′(x)TF′(x))−1

∥∥2 ∀x ∈ Bε(x),∥∥F′(x)T

∥∥2 ≤ M ∀x ∈ Bε(x),

‖r(x, x)‖2 ≤ α2‖(F′(x)T F′(x))−1‖2

M‖x− x‖2 ∀x ∈ Bε(x).

(1.8)

Wir setzen ε := min{ε, δ}. Sei xk ∈ Bε(x) und xk+1 ∈ Rn die durch das Gauß-Newton-Verfahren erzeugte neue Iterierte. Dann gilt

xk+1 − x = (F′(xk)TF′(xk))−1(F′(xk)TF′(xk))(xk+1 − xk︸︷︷︸=dk

+xk − x)

= (F′(xk)TF′(xk))−1(−F′(xk)TF(xk) + F′(xk)TF′(xk)(xk − x)

+ F′(x)TF(x)− F′(xk)TF(x) + F′(xk)TF(x))

= (F′(xk)TF′(xk))−1F′(xk)T(F(x)− F(xk) + F′(xk)(xk − x))

+ (F′(xk)TF′(xk))−1(F′(x)T − F′(xk)T)F(x).

Daraus ergibt sich

‖xk+1 − x‖2 ≤ ‖(F′(xk)TF′(xk))−1‖2‖F′(xk)T‖2‖r(xk, x)‖2

+ ‖(F′(xk)TF′(xk))−1‖2‖F′(x)T − F′(xk)T‖2‖F(x)‖2

(1.8)≤ α‖xk − x‖2 + 2‖(F′(x)TF′(x))−1‖2

· L‖xk − x‖2β(2L‖(F′(x)TF′(x))−1‖2)−1

= (α + β)‖xk − x‖2.

17

1.5 Parameterabhängige nichtlineare Gleichungssysteme

Ist x0 ∈ Bε(x), so folgt aus der obigen Abschätzung{xk ∈ Bε(x) ∀k ∈N,∥∥xk+1 − x

∥∥ ≤ γ∥∥xk − x

∥∥ ∀k ∈N.

Somit haben wir gezeigt, dass das Gauß-Newton-Verfahren gegen x linear mit Konver-genzrate γ ∈ (0, 1) konvergiert, wenn der Startwert klein genug ist.


Wir untersuchen ein nichtlineares Problem der Gestalt

F(x, λ) = 0

mit einer Funktion F : Rn ×Rp ⊃ D → Rn, die von einem Parametervektor λ ∈ Rp

abhängt. Beispielsweise kann folgende Situation vorliegen:Eigentlich ist man interessiert an der Lösung von G(x) = 0, aber dieses System lässtsich schwer lösen. Man bettet dieses Problem ein in

F(x, λ) = 0

mit λ ∈ [0, 1] mit F(x, 0) = G(x) und F(x, 1) = 0 leicht lösbar.

1.5.1 Beispiel: Innere-Punkte-Methode für lineare Optimierung

Es seien A ∈ Rm×n, b ∈ Rm und c ∈ Rn gegeben. Gesucht ist eine Lösung vonmin (c , x)Rn

bei Ax = b,xi ≥ 0 ∀i = 1, . . . , n.

(PP)

Wir definieren die Lagrange-Funktion wie folgt:

L : Rn ×Rm → R, L (x, µ) := (c , x)Rn + (b− Ax , µ)Rm .

Hierbei heißt µ ∈ Rn Lagrangescher Multiplikator.Es gilt

(PP) ⇔ minx≥0

(maxµ∈Rn

L (x, µ)),

dennmaxµ∈Rn

L (x, µ) = +∞, falls Ax 6= b.

18


Durch Vertauschung von min und max kommt man auf das sogenannte Dualproblem

maxµ∈Rn

(minx≥0

L (x, µ)) (DP)

= maxµ∈Rn

(minx≥0

(c , x)Rn + (b− Ax , µ)Rm)

= maxµ∈Rn

(minx≥0

(c− ATµ , x)Rn + (b , µ)Rm).

Somit ist (DP) äquivalent zu maxµ∈Rn

(b , µ)Rm

bei ATµ ≤ c.

Durch Einführung eines Schlupfvektors s ≥ 0 ergibt sichmaxµ∈Rn

(b , µ)Rm

bei ATµ + s = c,s ≥ 0.

(DP)

Aus der Optimierungsvorlesung ist bekannt, dass x∗ ∈ Rn genau dann das Pri-malproblem (PP) löst, wenn zusammen mit einer Lösung des Dualproblems (DP),(µ∗, s∗) ∈ Rm ×Rn, die sogenannten komplementären Schlupfbedingungen

x∗ ≥ 0,s∗ ≥ 0,(x∗ , s∗)Rn = 0 ⇔ x∗i s∗i = 0 ∀i = 1, . . . , n

erfüllt sind. Insgesamt ergibt sich das folgende notwendige und hinreichende Optima-litätssystem

x∗ ∈ Rn löst (PP) ⇔

Ax∗ = b,ATµ∗ + s∗ = c,x∗i s∗i = 0 ∀i = 1, . . . , n,x∗ ≥ 0, s∗ ≥ 0.

Dieses System bezeichnen wir mit (KKT), von Karush-Kuhn-Tucker.

Innere-Punkte-Methode

Wir führen λ ∈ R als Parameter ein, und weichen (KKT) etwas auf.

(IPMλ) =

Ax∗ = b,ATµ∗ + s∗ = c,x∗i s∗i = λ ∀i = 1, . . . , n,x∗ > 0, s∗ > 0.

19


Wir starten mit λ� 0 und lösen das System (IPMλ). Dann verkleinern wir λ schritt-weise, um den Wert λ = 0 zu approximieren. Das ist ein Beispiel für ein parameterab-hängiges nichtlineares Gleichungssystem. Wir setzen also z = (x, s, µ) und

F : R2n+m ×R ⊃ D → R2n+m, F(z, λ) :=

Ax− bATµ + s− c

XSe− λe

mit X = diag(x1, . . . , xn), S = diag(s1, . . . , sn), und e = (1, . . . , 1)T. Der Definitionsbe-reich ist

D = Rn+ ×Rn

+ ×Rm ×R+.

Es gilt also(IPMλ) ⇔ F(z, λ) = 0.

1.5.2 Fortsetzungsmethode

Im Folgenden sei D ⊂ Rn offen, λ ∈ [a, b] mit a ≤ b, und F : D× [a, b]→ Rn sei stetigdifferenzierbar. Wir betrachten das parameterabhängige nichtlineare Gleichungssystem

F(x, λ) = 0.

Definition 1.22. Die Menge der Lösungen der Gleichung F(x, λ) = 0

S := {(x, λ) ∈ Rn × [a, b] | F(x, λ) = 0}heißt Lösungsstruktur.

Beispiel 1.23. Es sei D = R und [a, b] = [−1, 1]. Ferner sei

F(x, λ) = x(x3 − x− λ).

Es giltF(x, λ) = 0 ⇔ x = 0 oder λ = x3 − x ∈ [−1, 1].

Somit ergeben sich zwei unterschiedliche Lösungsstrukturen:

S0 := {(x, λ) | x = 0 und λ ∈ [−1, 1]}S1 := {(x, λ) | x ∈ R und λ = x3 − x ∈ [−1, 1]}.

λ

x

S0

S1

−1 1

20


Beachte, dass sich die Lösungskurven S0 und S1 im Nullpunkt schneiden. Der Null-punkt ist somit ein Verzweigungspunkt. Im Nullpunkt gilt

∂F∂x

(0, 0) = x3 − x− λ + x(3x2 − 1)∣∣∣(0,0)

= 0.

Daher ist der Satz über implizite Funktionen im Nullpunkt nicht anwendbar (sonstgäbe es dort keine Verzweigung).

Im Folgenden nehmen wir an, dass

Fx(x, λ) ∈ Rn×n

für alle (x, λ) ∈ D × [a, b] invertierbar ist. Somit kann man den Satz über impliziteFunktionen anwenden. Unser paramterabhängiges nichtlineares Gleichungssystemlautet

F(x, λ) = 0.

Dabei ist das nichtlineare Problem

F(x, a) = 0

einfach zu lösen undF(x, b) = 0

ist die schwierigere Aufgabe. Es geht also darum, ausgehend von einem gewissen Wertfür λ sukzessive weitere Punkte der Kurve F(x, λ) = 0 zu berechnen.

λ

x

a bλ0 λ1 λ2

x0 x1

x2

S = {(x, λ) ∈ D× [a, b] | F(x, λ) = 0}

Idee:

(i) Lösung für λ = λ0:

Wir nehmen an, dass für einen Startwert λ = λ0 das Newton-Verfahren{Fx(xk, λ0)dk = −F(xk, λ0)

xk+1 = xk + dk

zu einer Lösung x = x0 der Aufgabe F(x0, λ0) = 0 konvergiert.

21


(ii) Fortsetzung λ1 > λ0:

Nun soll eine Lösung vonF(x, λ1) = 0

mit λ1 > λ0 bestimmt werden. Es treten hier zwei Schwierigkeiten auf:

– Wie weit darf λ1 von λ0 entfernt sein, damit das Newton-Verfahren zurBestimmung von x1 konvergiert.

– Welchen Anfangswert x0 sollen wir im Newton-Verfahren für

F(x, λ1) = 0

wählen?

Wir wollen nun zwei Ansätze untersuchen. Dazu nehmen wir an, dass λ1 geschicktgewählt sei, so dass alles gut geht. Nun klären wir, wie man den Startwert für dasNewton-Verfahren wählen kann.1. Ansatz: Klassische Fortsetzungsmethode (Poincaré, 1892, Himmelsmechanik)Man wählt x := x0 = x0 als Anfangswert für das Newton-Verfahren zur Lösung vonF(x, λ1) = 0.

λ

x

λ0 λ1

x0

x1

x

F(x, λ) = 0

2. Ansatz: Methode der tangentialen Fortsetzung

λ

x

λ0 λ1

x0x1

x

F(x, λ) = 0

22


Die Lösungskurve hat die Darstellung (x(t), λ0 + t) mit x(0) = x0. Dann ergibt sichals Tangentialvektor im Punkt (x0, λ0), das heißt t = 0, der folgende Vektor:(

x′(0)1

).

Daher ergibt sich die Wahl des Startwertes x für das Newton-Verfahren wie folgt:(x

λ1

)=

(x0λ0

)+

(x′(0)

1

) (λ1 − λ0

).

Alsox = x0 + x′(0)(λ1 − λ0) (tangentiale Fortsetzung).

Die Berechnung von x′(0) erfolgt über implizites Differenzieren:

F(x(t), λ0 + t) = 0 ∀t ≥ 0

| ddt , x(·)∈C1

⇒ Fx(x(t), λ0 + t)x′(t) + Fλ(x(t), λ0 + t) = 0 ∀t ≥ 0.

Im Nullpunkt t = 0 ergibt sich

Fx(x(0)︸︷︷︸=x0

, λ0)x′(0) = −Fλ(x(0)︸︷︷︸=x0

, λ0).

Das ist ein lineares Gleichungssystem, welches aufgrund unserer Annahme eindeutiglösbar ist.Bemerkung 1.24. Man beachte, dass beide Ansätze aus zwei Teilschritten bestehen:

1. Wahl der Schrittweiteτ := λ1 − λ0 > 0

und Wahl des Startwerts für das Newton-Verfahren

x := x0 „klassische Fortsetzungsmethode“x := x0 + τx′(0) „Methode der tangentialen Fortsetzung“.

2. Newton-Verfahren mit dem Startwert x zur Lösung von

F(x, λ1) = 0.

Der erste Teilschritt heißt Prädikator-Schritt. Der zweite Teilschritt heißt Korrektor-Schritt (Newton-Verfahren bis zurück auf die Lösungskurve zum Punkt (x1, λ1)).Der Gesamtprozess heißt Prädikator-Korrektor-Verfahren.Hauptschwierigkeit: Wahl der Schrittweite τ

• τ zu klein: langsam zum Endziel λ = b.

23


• τ zu groß: keine Konvergenz im Newton-Verfahren.

Lemma 1.25. Es sei ε > 0 und x(·) ∈ C1([0, ε], Rn). Dann gilt

‖x(t)− x(0)‖2 ≤ ηt ∀t ∈ [0, ε]

mit η := max0≤t≤ε

‖x′(t)‖2.

Beweis. Es sei t ∈ [0, ε]. Dann gilt

x(t)− x(0) =∫ t

0x′(τ)dτ

und daher

‖x(t)− x(0)‖2 ≤∫ t

0

∥∥x′(τ)∥∥

2︸︷︷︸≤max

0≤t≤ε‖x′(t)‖2

dτ ≤∫ t

0η dτ = tη.

Lemma 1.26. Es sei ε > 0 und x(·) ∈ C2([0, ε], Rn). Ferner sei

x(t) := x(0) + tx′(0) ∀t ∈ [0, ε].

Dann gilt‖x(t)− x(t)‖2 ≤ ηt2 ∀t ∈ [0, ε]


12 ‖x′′(t)‖2.

Beweis. Es sei t ∈ [0, ε]. Dann gilt

x(t)− x(t) = x(t)− x(0)− tx′(0)

=∫ t

0x′(τ)dτ − tx′(0)

=∫ 1

0tx′(τt)dτ − tx′(0)

=∫ 1

0t(x′(τt)− x′(0))dτ

=∫ 1

0t∫ τt

0x′′(σ)dσ dτ.

Daraus ergibt sich

‖x(t)− x(t)‖2 ≤∫ 1

0t∫ τt

02η dσ dτ

=∫ 1

02ητt2 dτ

= 2ηt2∫ 1

0τ dτ = ηt2.

24


Satz 1.27 (Wahl der Schrittweite τ > 0 für die klassische Fortsetzung). Es sei D ⊂Rn offen und konvex, F : D × [a, b] → Rn stetig differenzierbar mit auf ganz D × [a, b]invertierbarer Matrix Fx(x, λ) ∈ Rn×n. Es existiere ein ω > 0, so dass

‖Fx(x, λ)−1(Fx(x + sv, λ)− Fx(x, λ))v‖2 ≤ sω ‖v‖22 (1.9)

für alle x ∈ D, λ ∈ [a, b], v ∈ Rn mit x + v ∈ D, und s ∈ [0, 1] gilt. Es sei x(·) ∈C1([0, ε], Rn) mit ε > 0, so dass gilt

x(0) := x0 und F(x(t), λ0 + t) = 0 ∀t ∈ [0, ε].

Ist

0 < τ < τmax := min

ε,2

ω max0≤t≤ε

‖x′(t)‖2

,

so konvergiert das Newton-Verfahren zum Startwert

x := x0 (klassische Fortsetzungsmethode)

gegen die Lösung x(τ) vonF(x(τ), λ0 + τ) = 0.

Beweis. Wir verwenden den Konvergenzsatz des Newton-Verfahrens aus Abschnitt 1.1auf die Aufgabe

F(x) := F(x, λ0 + τ) = 0.

Wir müssen also verifizieren, dass alle Voraussetzungen des genannten Satzes erfülltsind. Die Lipschitz-Bedingung mit ω > 0 ist bereits als Annahme (1.9) gefordert. Esbleibt also nur noch zu zeigen, dass

‖x− x0‖2 <2ω

gilt. Bei uns sindx = x(τ) und x0 = x = x0 = x(0).

Also müssen wir die Ungleichung

‖x(τ)− x(0)‖2 <2ω

nachweisen. Aus dem (ersten) vorherigen Lemma wissen wir aber

‖x(τ)− x(0)‖2 ≤ ητ


‖x′(t)‖2. Somit folgt die Konvergenz des Newton-Verfahrens gegen x(τ)aus

‖x(τ)− x(0)‖2 ≤ ητ < ητmax ≤ η2

ωη=

2ω

.

25


Satz 1.28 (Wahl der Schrittweite τ > 0 für die tangentiale Fortsetzung). Es sei D ⊂Rn offen und konvex, F : D × [a, b] → Rn stetig differenzierbar mit auf ganz D × [a, b]invertierbarer Matrix Fx(x, λ) ∈ Rn×n. Es existiere ein ω > 0, so dass

‖Fx(x, λ)−1(Fx(x + sv, λ)− Fx(x, λ))v‖2 ≤ sω ‖v‖22

für alle x ∈ D, λ ∈ [a, b], v ∈ Rn mit x + v ∈ D, und s ∈ [0, 1] gilt. Es sei x(·) ∈C2([0, ε], Rn) mit ε > 0, so dass gilt

x(0) := x0 und F(x(t), λ0 + t) = 0 ∀t ∈ [0, ε].

Ist

0 < τ < τmax := min

ε,

√√√√ 4ω max

0≤t≤ε‖x′′(t)‖2

,

so konvergiert das Newton-Verfahren zum Startwert{x := x(0) + τx′(0)Fx(x0, λ0)x′(0) = −Fλ(x0, λ0)

gegen die Lösung x(τ) vonF(x(τ), λ0 + τ) = 0.

Beweis. Analog zum vorheringen Satz müssen wir nur noch zeigen, dass

‖x(τ)− x‖2 <2ω

gilt. Aus dem (zweiten) vorherigen Lemma folgt

‖x(τ)− x‖2 ≤ ητ2 < ητ2max = η

4ω2η

=2ω

.

Mit den beiden Sätzen hätten wir das Problem analytisch gelöst. Aber wir haben dabeifolgendes Problem:Die Konstanten

ε > 0, ω > 0, max0≤t≤ε

∥∥x′(t)∥∥

2 (bzw.∥∥x′′(t)

∥∥2)

sind unbekannt. Im nächsten Abschnitt wollen wir eine numerische Strategie zurSchrittweitensteuerung betrachten, welche nur numerisch verfügbare Größen verwen-det.

26


1.5.3 Natürlicher Monotonietest zur Schrittweitenbestimmung beiFortsetzungsmethoden

Ausgehend von einer Lösung (x0, λ0) ∈ D× [a, b] mit

F(x0, λ0) = 0

suchen wir eine Schrittweite τ > 0, so dass das Newton-Verfahren zur Lösung von

F(x, λ0 + τ) = 0

konvergiert. Unsere Idee besteht darin, den natürlichen Monotonietest anzuwenden:

‖dk+1‖2 ≤ ϑ‖dk‖2 (0 < ϑ < 1, z.B. ϑ =12),

wobei dk ∈ Rn bzw. dk+1 ∈ Rn die Newton-Korrektur bzw. vereinfachte Newton-Korrektur bezeichnen. Also:{

Fx(xk, λ0 + τ)dk = −F(xk, λ0 + τ),Fx(xk, λ0 + τ)dk+1 = −F(xk+1, λ0 + τ).

Gilt irgendwann

‖dk+1‖2 > ϑ‖dk‖2

für ein k ∈ N, so war der Schritt des Prädiktors zu weit, das heißt τ ist zu groß. Indiesem Fall verkleinern wir die Schrittweite, etwa wie

τ = βτ

mit einem Verkleinerungsfaktor β ∈ (0, 1), z.B. β = 12 , und starten den Newton-Prozess

neu.Aber τ > 0 kann auch zu klein sein. Man könnte das annehmen, wenn

‖d1‖ ≤ ϑ

2‖d0‖2, (nur bei Start des Newton-Verfahrens)

so sollte man τ vergrößern, etwa

τ =1β

τ

und neu starten. Weitere Algorithmen findet man im Buch von Deufelhard undHohmann.

27


1.5.4 Homotopiemethode

Gegeben seien F : Rn → Rn und G : Rn → Rn. Wir betrachten die nichtlineareAufgabe {

F(x) = 0,G(x) = 0.

Dabei ist die Aufgabe F(x) = 0 schwer zu lösen, während G(x) = 0 leicht ist. Die Ideeist, sich in einer Folge zu lösender Probleme an F(x) = 0 heranzutasten. Mit anderenWorten konstruiert man ein parameterabhängiges nichtlineares Problem

H(x, λ) = 0,

wobei H : Rn × [0, 1]→ Rn, mit der Eigenschaft

H(x, 0) = G(x) und H(x, 1) = F(x).

Dann löst man H(x, λ) = 0 mit Hilfe der Fortsetzungsmethode, angefangen mit λ0 = 0,also die einfache Aufgabe

H(x, 0) = G(x) = 0.

Definition 1.29. Ein solches H heißt Einbettung des Problems F(x) = 0 oder auchHomotopie.

Beispiel 1.30.H(x, λ) := (1− λ)G(x) + λF(x).

Beispiel 1.31. Es seiF : R10 → R10, F(x) = x− φ(x)

mit

φ(x) =

φ1(x)...

φ10(x)

mit φi(x) = exp

(cos

(i

10

∑j=1

xj

)).

Mögliche Einbettungen sind dann gegeben durch

1. H(x, λ) = x− λφ(x).

2. H(x, λ) =

H1(x, λ)...

H10(x, λ)

mit

Hi(x, λ) = xi − exp

(λ cos

(i

10

∑j=1

xj

)).

28

Kapitel 2Eigenwertprobleme

2.1 Vorbetrachtungen

Im Folgenden sei A ∈ Cn×n bzw. A ∈ Rn×n eine Matrix, von welcher wir alle Eigen-werte und Eigenvektoren bestimmen wollen. Gesucht sind also die Zahlen λ ∈ C undVektoren x ∈ Cn \ {0}, so dass gilt

Ax = λx.

Definition 2.1. Die Menge aller Eigenwerte von A bezeichnen wir mit

Λ(A) := {λ ∈ C | ∃ x ∈ Cn \ {0} : Ax = λx} (Spektrum von A).

Bemerkung 2.2. Aus der linearen Algebra gilt

λ ∈ Λ(A) ⇔ PA(λ) := det(A− λI) = 0,

wobei PA das charakteristische Polynom von A bezeichnet. Dieses Polynom hat n (ggf.mehrfache) Nullstellen λ1, . . . , λn. Folglich ist

Λ(A) = {λ1, . . . , λn}.

Definition 2.3. Ist λ ∈ Λ(A) eine k-fache Nullstelle von PA, so heißt k die algebraischeVielfachheit von λ. Mit

EA(λ) := {x ∈ Cn : (A− λI)x = 0}

bezeichnen wir den zu λ gehörenden Eigenraum. Die Dimension des EigenraumsEA(λ) ist die geometrische Vielfachheit von λ.

Notation 2.4.

σ(A) = algebraische Vielfachheit,ρ(A) = geometrische Vielfachheit.

29

2.2 Nullstellen von gestörten reellen Polynomen

Aus der linearen Algebra giltρ(A) ≤ σ(A),

der Beweis erfolgt beispielsweise durch die Jordansche Normalform.Im Prinzip scheint die Bestimmung der Eigenwerte numerisch einfach zu sein, dennman braucht nur die Nullstellen von PA zu bestimmen. Es gibt jedoch wichtigeArgumente dagegen!

(i) Aufstellen von PA(λ) erfordert die Berechnung von det(A − λI), welches fürgroßes n sehr aufwendig ist.

(ii) Das Berechnen aller komplexen Nullstellen von PA ist schwierig.

(iii) Kleine Störungen des Polynoms PA führt zu großen Fehlern in den Eigenwerten.

Beispiel 2.5 (Wilkinson). Wir betrachten das Polynom

p(λ) = (λ− 1)(λ− 2) · . . . · (λ− 20).

Die Nullstellen sind also λk = k für k = 1, . . . , 20. Ausmultipliziert erhalten wir

p(λ) = a0 + a1λ + . . . + anλn

mit Größenordnungen der Koeffizienten 1, . . . , 1018(20!). Nun stören wir a19 um ε =2−23 ≈ 10−7 und betrachten das gestörte Polynom

p∗(λ) = a0 + a1λ + . . . + a18λ18 + (a19 − ε)λ19 + a20λ20 = p(λ)− ελ19.

Die (exakten) Nullstellen von p∗ sind:

1.000 2.000 3.000 4.000 4.9996.000 7.000 8.007 8.917 10.095± 0.643i11.793± 1.652i 13.992± 2.518i 16.730± 2.812i 19.502± 1.940i 20.846


Im Folgenden seip(λ) := λn + pn−1λn−1 + . . . + p1λ + p0

mit p0, . . . , pn−1 ∈ R. Ferner sei

p∗(λ) := p∗nλn + p∗n−1λn−1 + . . . + p∗1λ + p∗0

ein gestörtes Polynom mit Koeffizienten{p∗j := pj + εqj, j = 0, . . . , n− 1

p∗n := 1 + εqn

30


mit qj ∈ R für alle j = 0, . . . , n und ε ∈ R „klein“. Folglich ist

p∗(λ) = p(λ) + εq(λ)

mit

q(λ) =n

∑j=1

λjqj.

Wir nehmen an, dass p eine einfache reelle Nullstelle λ0 ∈ R habe:

p(λ0) = 0 und p′(λ0) 6= 0.

Wir wollen nun die Nullstelle von dem gestörten Polynom p∗ um λ0 untersuchen. Dasheißt, wir betrachten die Aufgabe

p∗(λ) = p(λ) + εq(λ) = 0

in Abhängigkeit von ε und λ. Dazu setzen wir

F : R×R→ R, F(λ, ε) := p(λ) + εq(λ).

Laut Voraussetzungen gilt

F(λ0, 0) = p(λ0) + 0q(λ0) = p(λ0) = 0.

Ferner gilt

∂F∂λ

(λ0, 0) = p′(λ0) + εq′(λ0)∣∣ε=0 = p′(λ0) + 0q′(λ0) = p′(λ0) 6= 0.

Somit liefert der Satz über implizite Funktionen die Existenz offener UmgebungenU ⊂ R um 0 und V ⊂ R um λ0 mit den folgenden Eigenschaften:

(i) Zu jedem ε ∈ U gibt es genau ein λ ∈ V, so dass gilt

F(λ, ε) = 0.

(ii) Die nach (i) eindeutig bestimmte Funktion λ : U → V mit

F(λ(ε), ε) = 0

ist stetig differenzierbar. Für jedes ε ∈ U ist also λ(ε) ∈ V eine Nullstelle von p∗.

(iii) Für jedes ε ∈ U gilt∂F∂λ

(λ(ε), ε) 6= 0.

31


Aus (i)-(ii) ergibt sichg(ε) := F(λ(ε), ε) = 0 ∀ε ∈ U.

Hieraus folgt

0 = g′(ε) = ∂εF(λ(ε), ε) = p′(λ(ε))λ′(ε) + εq′(λ(ε))λ′(ε) + q(λ(ε)) ∀ε ∈ U,

was äquivalent ist zu[p′(λ(ε)) + εq′(λ(ε))

]λ′(ε) = −q(λ(ε)) ∀ε ∈ U.

Folglich gilt

λ′(ε) =−q(λ(ε))

p′(λ(ε)) + εq′(λ(ε))∀ε ∈ U,

denn laut (iii) ist ∂F∂λ (λ(ε), ε) 6= 0 für alle ε ∈ U. Insbesondere gilt für ε = 0

λ′(0) =−q(λ0)

p′(λ0).

Somit ist

λ(ε) ≈ λ0 − εq(λ0)

p′(λ0),

falls ε ≈ 0, also sehr klein. Der Faktor ∣∣∣∣ q(λ0)

p′(λ0)

∣∣∣∣ist also wichtig. Ist dieser groß im Vergleich mit ε > 0, so erhält man einen großenFehler für die Nullstelle.Beispiel 2.6. Betrachte das Polynom

p(λ) = (λ− 1)(λ− 2) · . . . · (λ− 12).

Wir stören dieses Polynom nun wie folgt:

p∗(λ) = p(λ) + εpjλj = p(λ) + εq(λ)

mit q(λ) = pjλj und 0 ≤ j ≤ 12. Die Nullstellen von p sind

λk = k, k = 1, . . . , 12.

Wir wollen nun den Verstärkungsfaktor∣∣∣∣ q(λ0)

p′(λ0)

∣∣∣∣berechnen. Dazu ist

p′(λk) = p′(k) = (−1)12−k(k− 1)!(12− k)! für k = 1, . . . , 12.

32

2.3 Die Schur-Zerlegung

Daraus folgt

ckj :=∣∣∣∣ q(λk)

p′(λk)

∣∣∣∣ = |pj|kj

(k− 1)!(12− k)!für k = 1, . . . , 12, j = 0, . . . , 12.

Die Werte ckj können jedoch sehr groß sein:

j \ k 1 9 100 1.20 E01 1.98 E03 6.06 E023 3.54 E01 4.26 E06 1.95 E067 1.74 E−01 1.37 E08 9.54 E07

11 1.35 E−06 1.01 E07 1.07 E07

Im Vergleich mit anderen Werten liegt das Maximum bei k = 9 und j = 7. Also ist dieNullstelle λ9 = 9 bezüglich Störungen von p7 = −6926634 am sensibelsten. Betrachteeine kleine Störung

p∗7 = −6926634.001.

Dann ist

λ∗9 ≈ λ9 − εq(λ9)

p′(λ9)= 8.98

bei dem relativen Fehler der Störung

0.001|p7|

= 1.444 · 10−10.


In diesem Abschnitt wollen wir wichtige theoretische Grundlagen für numerischeBerechnung von Eigenwerten bereitstellen.Definition 2.7. Eine Menge S ⊂ Cn heißt invarianter Unterraum von A ∈ Cn×n, fallsgilt

Ax ∈ S ∀x ∈ S ⇔ AS ⊂ S.

In diesem Fall heißt S auch A-invarianter Unterraum.

Lemma 2.8. Es sei A ∈ Cn×n und λ ∈ C ein Eigenwert von A. Dann ist der zu λ gehörendeEigenraum

EA(λ) ⊂ Cn

A-invariant.

Beweis. Sei x ∈ EA(λ). Dann ist

(A− λI)x = 0 ⇔ 0 = A0 = A(A− λI)x = (A2 − λA)x = (A− λI)Ax

und daraus folgt die Behauptung.

33


Lemma 2.9. Es sei A ∈ Cn×n und X ∈ Cn×k. Existiert eine Matrix B ∈ Ck×k mit

AX = XB,

so ist das BildBild(X) = Span{X1, . . . , Xk}

A-invariant. Beachte, dass Xi, i = 1, . . . , k, den i-ten Spaltenvektor von X bezeichnet.

Beweis. Sei x ∈ Bild(X). Zu zeigen: Ax ∈ Bild(X). Es gilt

x ∈ Bild(X) ⇔ x = y1X1 + . . . + ykXk = Xy

mit y = (y1, . . . , yk)T ∈ Ck. Folglich ist

Ax = AXy = XBy

und daraus folgtAx = z1X1 + . . . + zkXk

und schließlichAx ∈ Bild(x).

Vertauschen wir die Rolle von B und X, so erhalten wir das folgende Resultat.

Lemma 2.10. Es seien A ∈ Cn×n und B ∈ Ck×k. Existiert eine Matrix X ∈ Cn×k mitRang(X) = k und

AX = XB,

so giltΛ(B) ⊂ Λ(A).

Beweis. Es sei λ ∈ Λ(B). Dann gibt es einen Vektor y ∈ Ck \ {0} mit

By = λy.

Unsere Annahme liefertAXy = XBy = λXy.

Da Rang(X) = k und y 6= 0 ist, so ist

Xy ∈ Cn \ {0}

und daraus folgtλ ∈ Λ(A).

34


Korollar 2.11. Es seien A, B ∈ Cn×n. Existiert eine reguläre Matrix X ∈ Cn×n mit

AX = XB,

so giltΛ(A) = Λ(B).

Beweis. Die InklusionΛ(B) ⊂ Λ(A)

ist bereits erfüllt. Die Voraussetzung liefert auch

X−1A = X−1AXX−1 = X−1XBX−1 = BX−1,

also mit anderen WortenBX−1 = X−1A.

Somit liefert das obige Lemma mit B = A die Aussage

Λ(A) ⊂ Λ(B).

Bemerkung 2.12. Die Voraussetzung AX = XB mit einer regulären Matrix X istäquivalent zu

B = X−1AX.

Definition 2.13. Zwei Matrizen A, B ∈ Cn×n heißen ähnlich, falls eine reguläre MatrixX ∈ Cn×n existiert mit

B = X−1AX.

Die TransformationT : A→ T−1AT

heißt Ähnlichkeitstransformation.

Folgerung 2.14. Sind A, B ∈ Cn×n ähnlich, so besitzen A und B die gleichen Eigen-werte.

Lemma 2.15. Sei A ∈ Cn×n. Es existiere B ∈ Ck×k, k ≤ n, und X ∈ Cn×k mit Rang(X) =k und

AX = XB.

Dann existiert eine unitäre Matrix Q ∈ Cn×n (das heißt Q∗Q = I), so dass gilt

Q∗AQ =

[T11 T120 T22

]und

Λ(T11) = Λ(A) ∩Λ(B) = Λ(B).

35


Beweis. Aus der linearen Algebra wissen wir, dass X eine volle QR-Zerlegung besitzt,also

X = Q[

R0

]mit einer unitären Matrix Q ∈ Cn×n und einer oberen Dreiecksmatrix R ∈ Ck×k.Hieraus folgt

AX = XB ⇒ AQ[

R0

]= Q

[R0

]B ⇒ Q∗AQ

[R0

]=

[RB0

]. (2.1)

Wir schreiben nun

Q∗AQ =

[T11 T12T21 T22

]. (2.2)

Wir zeigen zuerst, dass T21 = 0 ist. Wegen Rang(X) = k muss

R =

r11 ∗. . .

rkk

regulär sein, denn

X = Q[

R0

].

Aus (2.1)-(2.2) gilt [T11 T12T21 T22

] [R0

]=

[RB0

]⇔ T11R + 0 = RB

T21R + 0 = 0. (2.3)

Aufgrund der Regularität von R ist nun T21 = 0. Es bleibt nur noch zu zeigen:

Λ(T11) = Λ(A) ∩Λ(B).

Aus (2.3) wissen wirR−1T11R = B,

denn R ∈ Ck×k ist regulär. Mit anderen Worten sind T11, B ∈ Ck×k ähnlich. Somit gilt

Λ(T11) = Λ(B).

Außerdem istΛ(B) ⊂ Λ(A)

nach dem vorherigen Lemma. Insgesamt gilt

Λ(T11) = Λ(A) ∩Λ(B) = Λ(B).

36


Korollar 2.16. Sei A ∈ Cn×n. Es existieren B ∈ Ck×k, k ≤ n, X ∈ Cn×k mit Rang(X) = kund

AX = XB.

Dann existiert eine unitäre Matrix Q ∈ Cn×n mit

Q∗AQ =

[T11 T120 T22

]und

Λ(A) = Λ(T11) ∪Λ(T22).

Beweis. Aus dem vorherigen Lemma wissen wir bereits, dass es eine unitäre MatrixQ ∈ Cn×n gibt, so dass gilt

Q∗AQ =

[T11 T120 T22

]und Λ(T11) = Λ(A) ∩Λ(B).

Aus der Darstellung sind A ∈ Cn×n und

T =

[T11 T120 T22

]∈ Cn×n

ähnlich und somit sind die Eigenwerte von A und T gleich, das heißt

Λ(A) = Λ(T).

Also müssen wir nur noch nachweisen, dass

Λ(T) = Λ(T11) ∪Λ(T22)

gilt. Es sei λ ∈ Λ(T). Dann gilt

0 = PT(λ) ⇔ 0 = det(T − λI)

und

det([

T11 T120 T22

]− λI

)= 0

⇔ det([

T11 − λI T120 T22 − λI

])= 0

⇔ det(T11 − λI)det(T22 − λI) = 0⇔ λ ∈ Λ(T11) oder λ ∈ Λ(T22).

37


Satz 2.17 (Schur). Zu jeder Matrix A ∈ Cn×n existiert eine unitäre Matrix Q ∈ Cn×n, sodass gilt

Q∗AQ =

t11 ∗. . .

0 tnn

∈ Cn×n

undΛ(A) = {t11, . . . , tnn}.

Beweis durch Induktion.

Induktionsanfang n = 1: Q = (1).

Induktionsannahme Die Aussage gelte für n = m ∈ N. Wir zeigen nun, dass dieAussage für n = m + 1 gilt.

Sei A ∈ C(m+1)×(m+1) und sei λ ∈ Λ(A) beliebig aber fest. Dann existiert ein Eigen-vektor x ∈ Cm+1 \ {0} mit

Ax = λx.

Das obige Lemma mit B = (λ) ∈ C1×1 (das heißt k = 1) und X := x ∈ C(m+1)×1

(Rang(X) = 1) liefert die Existenz einer unitären Matrix U ∈ C(m+1)×(m+1), so dassgilt

U∗AU =

(T11 T120 T22

)mit

Λ(T11) = Λ(A) ∩Λ(B) = Λ(B) = {λ}.Somit ist T11 = (λ). Außerdem gilt

Λ(A) = {λ} ∪Λ(T22). (2.4)

Da T22 ∈ Cm×m ist, existiert laut Induktionsannahme eine unitäre Matrix U ∈ Cm×m

mit

U∗T22U =

λ1 ∗. . .

0 λm

und

Λ(T22) = {λ1, . . . , λm}. (2.5)

Wir setzen nun

Q := U(

1 00 U

)∈ C(m+1)×(m+1).

38


Folglich gilt

Q∗AQ =

(1 00 U∗

)U∗AU

(1 00 U

)=

(1 00 U∗

)(λ T120 T22

)(1 00 U

)=

(1 00 U∗

)(λ T12U0 T22U

)=

(λ T12U0 U∗T22U

)

=

λ ∗

λ1. . .

0 λm

und aufgrund von (2.4)-(2.5) gilt

Λ(A) = {λ, λ1, . . . , λm}

und daraus folgt die Behauptung.

Definition 2.18. Es sei A ∈ Cn×n. Dann heißt die Zerlegung

Q∗AQ =

t11 ∗. . .

0 tnn

∈ Cn×n

mit einer unitären Matrix Q ∈ Cn×n und der Eigenschaft, dass

Λ(A) = {t11, . . . , tnn}

gilt, Schur-Zerlegung von A. Die Spaltenvektoren von Q heißen Schur-Vektoren.

Bemerkung 2.19. Die Schur-Zerlegung ist nicht eindeutig.

Korollar 2.20. Es sei A ∈ Cn×n und q1, . . . , qn ∈ Cn Schur-Vektoren einer Schur-Zerlegung

Q∗AQ =

t11 ∗. . .

0 tnn

∈ Cn×n.

Dann istSk = Span{q1, . . . , qk} ⊂ Cn

für jedes k = 1, . . . , n A-invariant.

39


Bemerkung 2.21. Der vorherige Satz sichert die Existenz einer Schur-Zerlegung fürjede Matrix. Aus der Schur-Zerlegung kann man sofort die Eigenwerte von A ablesen.Leider kann man ohne weitere Annahme die dazugehörigen Eigenvektoren nichtbestimmen.

Definition 2.22. Eine Matrix A ∈ Cn×n heißt normal, falls gilt

A∗A = AA∗.

Beispiel 2.23. Jede unitäre Matrix ist normal, symmetrische reelle Matrizen sowiehermitsche Matrizen auch.

Lemma 2.24. Es sei A ∈ Cn×n eine quadratische Matrix und Q ∈ Cn×n eine unitäre Matrix.Dann ist A normal genau dann, wenn Q∗AQ normal ist.

Beweis.

„⇒“: Es sei A ∈ Cn×n normal. Dann gilt

(Q∗AQ)∗(Q∗AQ) = Q∗A∗QQ∗AQ = Q∗A∗AQ = Q∗AA∗Q = Q∗AQQ∗A∗Q= (Q∗AQ)(Q∗AQ)∗.

„⇐“: Analog.

Satz 2.25. Eine Matrix A ∈ Cn×n ist genau dann normal, wenn es eine unitäre MatrixQ ∈ Cn×n gibt, so dass gilt

Q∗AQ =

λ1 0. . .

0 λn

und

Λ(A) = {λ1, . . . , λn}.Insbesondere ist λi für jedes i = 1, . . . , n ein Eigenwert von A zum Eigenvektor Qei.

Beweis.

„⇐“: Es gebe eine unitäre Matrix Q ∈ Cn×n mit

Q∗AQ =

λ1 0. . .

0 λn

.

40


Dann gilt

A = Q

λ1 0. . .

0 λn

Q∗.

Daraus folgt

A∗A = Q

λ1 0. . .

0 λn

Q∗Q

λ1 0. . .

0 λn

Q∗

= Q

|λ1|2 0. . .

0 |λn|2

Q∗

= · · · = AA∗.

„⇒“: Es sei A normal. Wir haben bereits gezeigt, dass jede Matrix eine Schur-Zerlegung besitzt. Es existiere also eine unitäre Matrix Q ∈ Cn×n, so dass gilt

Q∗AQ =

t11 ∗. . .

0 tnn

=: T

undΛ(A) = {t11, . . . , tnn}.

Wir zeigen nun, dass dann tij = 0 für alle j > i gilt. Da A ∈ Cn×n normal ist undQ ∈ Cn×n unitär ist, so ist

T = Q∗AQ

ebenso normal, das heißtT∗T = TT∗.

Wir vergleichen nun die Diagonalelemente von T∗T und TT∗.

T∗T =

t11 0t12 t22t13 t23 t33...

...... . . .

t1n t2n t3n · · · tnn

t11 t12 t13 · · · t1n

t22 t23 · · · t2nt33 · · · t3n

. . . ...0 tnn

=

|t11|2 ∗

|t12|2 + |t22|2∑3

j=1 |tj3|2. . .

∗ ∑nj=1 |tjn|2

41


und

TT∗ =

t11 t12 t13 · · · t1n

t22 t23 · · · t2nt33 · · · t3n

. . . ...0 tnn

t11 0t12 t22t13 t23 t33...

...... . . .

t1n t2n t3n · · · tnn

=

∑n

j=1 |t1j|2 ∗∑n

j=2 |t2j|2∑n

j=3 |t2j|2. . .

∗ |tnn|2

.

Mit T∗T = TT∗ folgt

|t11|2 =n

∑j=1|t1j|2 ⇒ 0 =

n

∑j=2|t1j|2 ⇒ t1j = 0 ∀j > 1,

|t12|2 + |t22|2 =n

∑j=2|t2j|2 ⇒ 0 =

n

∑j=3|t2j|2 ⇒ t2j = 0 ∀j > 2,

|t13|2 + |t23|2 + |t33|2 =n

∑j=3|t3j|2 ⇒ 0 =

n

∑j=4|t3j|2 ⇒ t3j = 0 ∀j > 3,

und so weiter. Folglich gilttij = 0 ∀j > i

und daraus ergibt sich die Behauptung.

Bemerkung 2.26. Ist A ∈ Rn×n symmetrisch, so wissen wir bereits, dass A reelleEigenwerte besitzt. In diesem Fall existiert eine orthogonale Matrix Q ∈ Rn×n, so dassgilt

QT AQ =

λ1 0. . .

0 λn

und

Λ(A) = {λ1, . . . , λn}.Ist A nicht symmetrisch, dann ist diese Aussage im Allgemeinen nicht richtig.

Es sei λ ∈ C ein Eigenwert von A ∈ Rn×n mit Eigenvektor x ∈ Cn \ {0}. Dann gilt

Ax = λx ⇔ Ax = λx ⇔ Ax = λx,

42


da A ∈ Rn×n. Deshalb gilt

λ ∈ Λ(A) mit Eigenvektor x ⇔ λ ∈ Λ(A) mit Eigenvektor x.

Wir zerlegen

λ = µ + iβ, µ, β ∈ R,x = u + iv, u, v ∈ Rn.

Folglich haben wirA(u + iv) = (µ + iβ)(u + iv)

und daher {Re(A(u + iv)) = µu− βv,Im(A(u + iv)) = βu + µv,

sowie {Au = µu− βv,Av = βu + µv.

Schließlich erhalten wir

A(u v

)=(µu− βv βu + µv

)=(u v

) ( µ β

−β µ

). (2.6)

Korollar 2.27. Es sei A ∈ Rn×n und λ = µ + iβ ∈ Λ(A). Ist

x = u + iv, u, v ∈ Rn

ein Eigenvektor von A zum Eigenwert λ, so ist

Span{u, v} ⊂ Rn

A-invariant.

Beweis. Es sei z ∈ Span{u, v}. Das heißt

∃α1, α2 ∈ R : z = α1u + α2v =(u v

) (α1α2

).

Folglich gilt

Az = A(u v

) (α1α2

)(2.6)=(u v

) ( µ β

−β µ

)(α1α2

)=(u v

) ( µα1 + βα2−βα1 + µα2

)= (µα1 + βα2)u + (−βα1 + µα2)v ∈ Span{u, v}.

43

2.4 Störungssätze

Satz 2.28 (Reelle Schur-Form). Es sei A ∈ Rn×n. Dann existiert eine orthogonale MatrixQ ∈ Rn×n, so dass gilt

QT AQ =

R11 ∗. . .

0 Rmm

∈ Rn×n

mit Blockmatrizen Rjj ∈ Rkj×kj , k j ∈ {1, 2}, und ∑mj=1 k j = n. Dabei gilt für k j = 1, dass

Rjj ∈ Λ(A) und für k j = 2, dass Λ(Rjj) = {λ, λ} ⊂ Λ(A).

2.4 Störungssätze

Wir beginnen mit dem bekannten Satz über die Jordan-Normalform.Satz 2.29 (Jordansche-Normalform). Es sei A ∈ Cn×n. Dann existiert eine reguläre MatrixX ∈ Cn×n, so dass gilt

X−1AX =

J(λ1) 0. . .

0 J(λk)

mit den paarweise verschiedenen Eigenwerten λ1, . . . , λk. Die Jordan-Blöcke J(λl), l = 1, . . . , khaben die Form

J(λl) =

Jl,1 0. . .

0 Jl,ρ(λl)

, Jl,r =

λl 1 0

. . . . . .. . . 1

0 λl

∈ Cml,r×ml,r .

Es gilt ρ(λl) = σ(λl) genau dann, wenn ml,r = 1 für alle r = 1, . . . , ρ(λl) gilt.

Definition 2.30. Es sei A ∈ Cn×n und λ ∈ Λ(A).

(i) Ist ρ(λ) < σ(λ), so heißt λ defektiver Eigenwert.

(ii) Besitzt A einen defektiven Eigenwert, so heißt A defektiv.

(iii) Gilt ρ(λ) = σ(λ) für alle λ ∈ Λ(A), so heißt A diagonalisierbar.

Lemma 2.31. Die Inklusion

{A ∈ Cn×n | A ist diagonalisierbar} ⊂ Cn×n

ist dicht. Mit anderen Worten:

∀A ∈ Cn×n ∀δ > 0 ∃ Aδ ∈ Cn×n diagonalisierbar : ‖Aδ − A‖2 ≤ δ.

Notation:{A ∈ Cn×n | A ist diagonalisierbar}‖·‖2 = Cn×n.

44

2.4 Störungssätze

Beweis. Es sei A ∈ Cn×n. Ist Jl,r ein gegebener Jordan-Block zum mehrfachen Eigenwertλl

Jl,r =

λl 1 0

. . . . . .. . . 1

0 λl

,

so kann man durch Addition beliebig kleiner εi 6= 0, i = 1, . . . , ml,r, diesen Blockändern zu

Jl,r =

λl − ε1 1 0

. . . . . .. . . 1

0 λl − εml,r

,

welcher paarweise verschiedene Eigenwerte hat, wenn die εi unterschiedlich gewähltsind. So erzeugt man insgesamt durch beliebig kleine Änderung eine diagonalisierbareMatrix A ∈ Cn×n.

Folgerung 2.32. Jede Matrix ist numerisch diagonalisierbar.

Beispiel 2.33. Die Matrix

A =

(1 10 1

)ist defektiv (nicht diagonalisierbar), denn

ρ(A) = dim EA(1) = 1 < 2 = σ(1),

denn 1 ist zweifache Nullstelle von

det(A− λI) = 0 ⇔ (1− λ)2 = 0.

Die klein gestörte Matrix

A =

(1 1ε 1

)mit ε > 0 „klein“

ist diagonalisierbar, denn Λ(A) = {1 +√ε, 1−√ε}.

Es sei X ∈ Cn×n regulär. Wir betrachten die Transformation

T : A→ X−1AX.

Sei A eine gestörte Matrix, alsoA = A + E.

Dann gilt

T(A) = T(A) + T(E),

‖T(A)− T(A)‖2 = ‖T(E)‖2 ≤ ‖X−1‖2 ‖E‖2 ‖X‖2 = cond2(X) ‖E‖2 .

45

2.4 Störungssätze

Korollar 2.34. Ist X ∈ Cn×n unitär, so gilt

‖T(A)− T(A)‖2 ≤ ‖E‖2 = ‖A− A‖2

für alle Matrizen A, A ∈ Cn×n.

Beweis. Für die Spektralkondition gilt cond2(X) = ‖X−1‖2 ‖X‖2 = 1, denn

‖X‖2 =√

λmax(X∗X) = 1.

Satz 2.35 (Bauer-Fike). Es sei A ∈ Cn×n diagonalisierbar, das heißt es existiere eine reguläreMatrix X ∈ Cn×n, so dass gilt

X−1AX = D =

λ1 0. . .

0 λn

, Λ(A) = {λ1, . . . , λn}.

Ferner sei E ∈ Cn×n eine Störung und µ ∈ Λ(A + E). Dann gilt

minλ∈Λ(A)

|µ− λ| ≤ cond2(X) ‖E‖2 .

Beweis. Ist µ ∈ Λ(A + E) ∩Λ(A), dann ist die Aussage trivial. Nun sei µ ∈ Λ(A + E),aber µ /∈ Λ(A). Es gilt

X−1(A + E− µI)X = X−1AX + X−1EX− µI = D− µI + X−1EX.

Da µ /∈ Λ(A) = {λ1, . . . , λn} gilt, so ist

det(D− µI) = det

λ1 − µ 0. . .

0 λn − µ

6= 0.

Daher ist D− µI regulär. Folglich ist

X−1(A + E− µI)X = (D− µI)(I + (D− µI)−1X−1EX).

Berechnung der Determinante auf beiden Seiten liefert

det(D− µI)︸︷︷︸6=0

det(I + (D− µI)−1X−1EX) = det(X−1(A + E− µI)X)

= det(X−1)det(A + E− µI)︸︷︷︸=0

det(X),

46

2.4 Störungssätze

alsodet(I + (D− µI)−1X−1EX) = 0

und somit ist I + (D− µI)−1X−1EX nicht regulär. Dann existiert ein z ∈ Cn \ {0} mit

(I + (D− µI)−1X−1EX)z = 0.

Es folgt‖z‖2 = ‖(D− µI)−1(X−1EX)z‖2

und daher‖z‖2 ≤ ‖(D− µI)−1‖2‖X−1‖2 ‖E‖2 ‖X‖2 ‖z‖2 .

Mit ‖z‖2 6= 0 folgt1 ≤ ‖(D− µI)−1‖2 cond2(X) ‖E‖2 ,

also‖(D− µI)−1‖−1

2 ≤ cond2(X) ‖E‖2 .

Laut Definition ist aber

∥∥∥(D− µI)−1∥∥∥

2=√

λmax((D− µI)−∗(D− µI)−1) =

√√√√√√√λmax

1

|λ1−µ|2 0. . .

0 1|λn−µ|2

=√

min1≤i≤n

|λi − µ|−2

=1

min1≤i≤n

|λi − µ| ,

denn

(D− µI)−1 =

1

λ1−µ 0. . .

0 1λn−µ

.

Insgesamt giltmin

1≤i≤n|λi − µ| ≤ cond2(X) ‖X‖2 .

Korollar 2.36. Ist zusätzlich zu den Voraussetzungen des vorherigen Satzes die Matrix Anormal, dann gilt

minλ∈Λ(A)

|λ− µ| ≤ ‖E‖2 .

47

2.4 Störungssätze

Der Satz von Bauer-Fike liefert ein wichtiges Resultat der Rückwärtsanalyse:Es sei A ∈ Cn×n diagonalisierbar und zu lösen sei

Ax = λx.

Das numerische Verfahren liefert ein fehlerbehaftetes x und λ mit o.B.d.A. ‖x‖2 = 1und

Ax = λx + r

mit einem kleinen Fehler r 6= 0. Wäre r = 0, so wäre λ ∈ Λ(A) mit exaktem Eigenvektorx. Mit dem Satz von Bauer-Fike kann man zeigen, dass

minλ∈Λ(A)

|λ− λ| ≤ cond2(X) ‖r‖2 .

Beispiel 2.37. Es sei

A =

2 0 00 1 10 ε 1

.

Es gilt0 = det(A− λI) ⇔ (2− λ)((1− λ)2 − ε) = 0.

Somit istΛ(A) = {2, 1 +

√ε, 1−

√ε}.

Als Eigenvektoren erhält man ohne Normierung100

,

01√

ε

,

0−1√

ε

.

Die Matrix A ist nach Definition diagonalisierbar. Für

X =

1 0 00 1 −10√

ε√

ε

, X−1 =1

2√

ε

2√

ε 0 00

√ε 1

0 −√ε 1

gilt

X−1AX =

2 0 00 1 +

√ε 0

0 0 1−√ε

.

Daraus ergibt sich mit dem Satz von Bauer-Fike und µ ∈ Λ(A + E)

minλ∈Λ(A)

|λ− µ| ≤ cond2(X) ‖E‖2 → ∞ für ε↘ 0.

Beachte, dass die Berechnung des Eigenwerts 2 für obiges Beispiel eigentlich unproble-matisch ist. Aber der Satz von Bauer-Fike liefert nur eine allgemeine Aussage für alle

48

2.4 Störungssätze

Eigenwerte, so dass numerische Probleme wie oben für alle Eigenwerte angedeutetwerden.Daher wäre es sinnvoll, die Sensitivität eines Eigenwertes nur über seinen zugeordnetenEigenvektor zu untersuchen.

Satz 2.38 (Störung einfacher Eigenwerte). Es sei A ∈ Cn×n und λ0 ∈ Λ(A) mitσ(λ0) = 1, das heißt λ0 sei einfach. Ferner seien x0, y0 ∈ Cn \ {0} rechte bzw. linke normierteEigenvektoren zum Eigenwert λ0:

Ax0 = λ0x0 sowie y∗0 A = λ0y∗0 , ‖x0‖2 = ‖y0‖2 = 1.

Es sei E ∈ Cn×n eine Störung. Dann existiert eine stetig differenzierbare Abbildung

λ : (−ε, ε)→ Bδ(λ0) ⊂ C

mit ε, δ ∈ R+, so dass gilt

(i) λ(0) = λ0,

(ii) Λ(A + tE) ∩ Bδ(λ0) = {λ(t)} ∀t ∈ (−ε, ε),

(iii) σ(λ(t)) = 1 ∀t ∈ (−ε, ε),

(iv) λ′(0) = (y0,Ex0)Cn(y0,x0)Cn

.

Beweis. Laut Voraussetzung ist λ0 ∈ Λ(A) ein einfacher Eigenwert und daher ist λ0eine einfache Nullstelle des charakteristischen Polynoms

PA(λ) := det(A− λI).

Mit anderen Worten:PA(λ0) = 0 und P′A(λ0) 6= 0.

Wir definieren die Funktion

F : C×R→ C, F(λ, t) := det(A + tE− λI) = PA+tE(λ).

Diese Funktion ist unendlich oft differenzierbar mit

F(λ0, 0) = PA(λ0) = 0,Fλ(λ0, 0) = P′A(λ0) 6= 0.

Somit liefert der Satz über implizite Funktionen die Existenz von ε, δ ∈ R+, so dassgilt:

(i) Zu jedem t ∈ (−ε, ε) gibt es genau ein λ ∈ Bδ(λ0) ⊂ C, so dass gilt

F(λ, t) = 0.

49

2.4 Störungssätze

(ii) Die nach (i) eindeutig bestimmte Abbildung

λ : (−ε, ε)→ Bδ(λ) mit F(λ(t), t) = 0 ∀t ∈ (−ε, ε)

ist stetig differenzierbar.

Da Fλ(λ0, 0) = P′A(λ0) 6= 0 gilt und die Abbildung t → Fλ(λ(t), t) stetig ist, könnenwir ε verkleinern, so dass gilt

Fλ(λ(t), t) 6= 0 ∀t ∈ (−ε, ε) ⇔ P′A+tE(λ(t)) 6= 0 ∀t ∈ (−ε, ε).

Daher istσ(λ(t)) = 1 ∀t ∈ (−ε, ε).

Insgesamt erfüllt die Funktion λ : (−ε, ε)→ Bδ(λ0) die Eigenschaften:

(i) λ(0) = λ0,

(ii) Λ(A + tE) ∩ Bδ(λ0) = {λ(t)} ∀t ∈ (−ε, ε),

(iii) σ(λ(t)) = 1 ∀t ∈ (−ε, ε).

Es bleibt nur noch zu zeigen, dass

λ′(0) =(y0, Ex0)Cn

(y0, x0)Cn

gilt. Beachte, dass (y0, x0)Cn 6= 0 ist, da σ(λ0) = 1 ist (siehe Hausaufgabe). Daσ(λ(t)) = 1 für alle t ∈ (−ε, ε) gilt, so gibt es zu jedem t ∈ (−ε, ε) genau einennormierten (rechten) Eigenvektor

x = x(t) ∈ Cn \ {0} mit ‖x‖2 = 1

von A + tE zum Eigenwert λ(t). Laut Definition ist

(y0, Ax(t)− Ax0)Cn

t=

(A∗y0, x(t)− x0)Cn

t=

(λ0y0, x(t)− x0)Cn

t

=λ0(y0, x(t)− x0)Cn

t. (2.7)

Andererseits gilt

(y0, Ax(t)− Ax0)Cn

t=

(y0, (A + tE)x(t)− Ax0)Cn

t− (y0, tEx(t))Cn

t

=(y0, λ(t)x(t)− λ0x0)Cn

t− (y0, Ex(t))Cn

=λ(t)− λ0

t(y0, x0)Cn +

λ(t)t

(y0, x(t)− x0)Cn − (y0, Ex(t))Cn .

(2.8)

50

2.4 Störungssätze

Somit liefern (2.7)-(2.8)

(y0, Ex(t))Cn =λ(t)− λ0

t(y0, x0)Cn +

λ(t)− λ(0)t

(y0, x(t)− x0)Cn .

Mit t→ 0 erhalten wir

(y0, Ex(0))Cn = λ′(0)(y0, x0)Cn + λ′(0)(y0, 0)Cn

und mit (y0, x0)Cn 6= 0 folgt insgesamt

λ′(0) =(y0, Ex0)Cn

(y0, x0)Cn.

Beachte, dass man hier auch die Stetigkeit der Abbildung

x : (−ε, ε)→ Cn \ {0}

im Punkt 0 angewendet hat. In der Tat ist diese Abbildung stetig (siehe Hausaufgabe).Korollar 2.39. Es sei A ∈ Cn×n und λ0 ∈ Λ(A) einfach. Ferner seien x0, y0 ∈ Cn \ {0}rechte bzw. linke normierte Eigenvektoren von A zum Eigenwert λ0. Ferner sei E ∈ Cn×n eineStörung und

λ : (−ε, ε)→ Bδ(λ0)

die im vorherigen Satz wohldefinierte Abbildung der einfachen Eigenwerte mit

λ(0) = λ0, Λ(A+ tE)∩Bδ = {λ(t)} ∀t ∈ (−ε, ε) und σ(λ(t)) = 1 ∀t ∈ (−ε, ε).

Dann gilt

|λ(t)− λ(0)| ≤ |t||(y0, x0)Cn | ‖E‖2 + O(|t|).

Beweis. Die Abbildung λ : (−ε, ε)→ Bδ(λ0) ist differenzierbar und somit ist

λ(t) = λ(0) + λ′(0)t + O(|t|)

und nach dem vorherigen Satz gilt

λ(t)− λ(0) =t(y0, Ex0)Cn

(y0, x0)Cn+ O(|t|).

Insgesamt ergibt sich also

|λ(t)− λ(0)| ≤ |t| ‖y0‖2 ‖E‖2 ‖x0‖2|(y0, x0)Cn | + O(|t|)

und somit die Behauptung.

51

2.5 Rayleigh-Ritz-Quotient und Courant-Fischer-Variationsprinzip

Definition 2.40. Sei A ∈ Cn×n eine Matrix und λ0 ∈ Λ(A) einfach. Ferner seienx0, y0 ∈ Cn \ {0} rechte bzw. linke normierte Eigenvektoren von A zum Eigenwert λ0.Dann heißt

cond(λ0) :=1

|(y0, x0)Cn |Kondition des einfachen Eigenwerts λ0.

Bemerkung 2.41.

(i) Machen sie sich klar, dass cond(λ0) ∈ [1, ∞) gilt.

(ii) Ideal wäre cond(λ0) = 1. Dies gilt z.B. wenn A normal ist.

2.5 Rayleigh-Ritz-Quotient undCourant-Fischer-Variationsprinzip

Im Folgenden untersuchen wir Eigenwertprobleme mit hermiteschen Matrizen.Definition 2.42. Eine Matrix A heißt hermitesch, falls gilt

A = A∗ ⇔ aij = aji ∀i, j = 1, . . . , n.

Lemma 2.43. Jeder Eigenwert einer hermiteschen Matrix ist immer reell.

Beweis. Sei A ∈ Cn×n hermitesch und λ ∈ Λ(A) mit dem Eigenvektor x ∈ Cn \ {0}.Dann gilt

λ(x, x)Cn = (λx, x)Cn = (Ax, x)Cn = (x, A∗x)Cn = (x, Ax)Cn = (x, λx)Cn = λ(x, x)Cn .

Da ‖x‖2 6= 0 ist, folgt λ = λ.

Korollar 2.44. Eine Matrix A ∈ Cn×n ist genau dann hermitesch, wenn es eine unitäreMatrix Q ∈ Cn×n gibt, so dass gilt

Q∗AQ = diag(λ1, . . . , λn) ∈ Rn×n.

Definition 2.45. Es sei A ∈ Cn×n. Dann bezeichnen wir mit

R : Cn \ {0} → C, R(x) :=(x, Ax)Cn

‖x‖22

den zu A gehörigen Rayleigh-Ritz-Quotienten.

Es hat sich herausgestellt, dass der Rayleigh-Ritz-Quotient ein wichtiges analytischesWerkzeug zur Untersuchung von Eigenwertproblemen ist. Zunächst wollen wir einigeelementare Eigenschaften des Rayleigh-Ritz-Quotienten beweisen. Dazu definieren wirdas Bild von R wie folgt:

Bild(R) := {R(x) | x ∈ Cn \ {0}} .

52


Lemma 2.46. Es sei A ∈ Cn×n. Dann gilt

Λ(A) ⊂ Bild(R).

Beweis. Sei λ ∈ Λ(A) und x ∈ Cn \ {0} ein dazugehöriger Eigenvektor. Dann gilt

λ = λ(x, x)Cn

‖x‖22

=(x, λx)Cn

‖x‖22

=(x, Ax)Cn

‖x‖22

= R(x) ∈ Bild(R).

Daher ist Λ(A) ⊂ Bild(R).

Lemma 2.47. Es sei A ∈ Cn×n normal, das heißt

A∗A = AA∗.

Dann gilt

Bild(R) =

{n

∑j=1

ajλj | aj ∈ R, aj ≥ 0 ∀j = 1, . . . , n,n

∑j=1

aj = 1

},

wobei Λ(A) = {λ1, . . . , λn} ist. Mit anderen Worten ist das Bild von R nichts anderes als diekonvexe Hülle von Λ(A) = {λ1, . . . , λn}.

Beweis. Da A ∈ Cn×n normal ist, existiert eine unitäre Matrix Q ∈ Cn×n mit

Q∗AQ = D = diag(λ1, . . . , λn) ∈ Cn×n.

Hieraus ergibt sich

Bild(R) = {R(x) | x 6= 0} ={(x, Ax)Cn

(x, x)Cn| x 6= 0

}=

{x∗Axx∗x

| x 6= 0}

=

{x∗QDQ∗xx∗QQ∗x

| x 6= 0}

=

{y∗Dyy∗y

| y 6= 0}

=

{∑n

j=1 λj|yj|2∑n

j=1 |yj|2| y 6= 0

}

=

{n

∑j=1

ajλj | aj ∈ R, aj ≥ 0,n

∑j=1

aj = 1

}.

Daraus folgtBild(R) = konvexe Hülle von Λ(A).

53


Satz 2.48. Es sei A ∈ Cn×n hermitesch, das heißt A∗ = A. Dann gilt

Bild(R) = [λmin, λmax] ⊂ R

(das Bild ist ein abgeschlossenes Intervall in R (Kompaktum)) und

λmin = minx∈Cn\{0}

R(x), λmax = maxx∈Cn\{0}

R(x),

wobei λmin und λmax den kleinsten bzw. den größten Eigenwert von A bezeichnen.

Beweis. Da die Matrix A ∈ Cn×n hermitesch ist, besitzt diese nur reelle Eigenwerte

λmin := λ1 ≤ λ2 ≤ . . . ≤ λn =: λmax.

Außerdem wissen wir, dass jede hermitesche Matrix normal ist. Somit liefert dasvorherige Lemma

Bild(R) =

{n

∑j=1

ajλj | aj ∈ R, aj ≥ 0,n

∑j=1

aj = 1

}= [λmin, λmax].

Sind xmin, xmax ∈ Cn \ {0} Eigenvektoren von A zu Eigenwerten λmin und λmax, so gilt

R(xmin) =(xmin, Axmin)Cn

‖xmin‖22

=(xmin, λminxmin)Cn

(xmin, xmin)Cn= λmin

R(xmax) =(xmax, Axmax)Cn

‖xmax‖22

=(xmax, λmaxxmax)Cn

(xmax, xmax)Cn= λmax

und somit folgt insgesamt die Aussage.

Satz 2.49 (Variationsprinzip von Rayleigh-Ritz). Es sei A ∈ Cn×n hermitesch mit denreellen Eigenwerten

λ1 ≤ λ2 ≤ . . . ≤ λn

und zugehörigen Eigenvektoren y1, . . . , yn ∈ Cn \ {0} mit (yi, yj)Cn = δij. Dann gilt fürjedes j = 1, . . . , n:

λj =

min R(x)bei (x, yk)Cn = 0 ∀k = 1, . . . , j− 1

x ∈ Cn \ {0}

=

max R(x)bei (x, yk)Cn = 0 ∀k = j + 1, . . . , n

x ∈ Cn \ {0}.

54


Beweis. Sei j ∈ {1, . . . , n} und x ∈ Cn \ {0} mit (x, yk)Cn = 0 für alle k = 1, . . . , j− 1.Der Vektor x hat die Darstellung

x =n

∑k=1

akyk.

Daraus folgt

R(x) =(x, Ax)Cn

(x, x)Cn=

∑nk=1(x, ak Ayk)Cn

∑nk=1(x, akyk)Cn

=∑n

k=1 λkak(x, yk)Cn

∑nk=1 ak(x, yk)Cn

=∑n

k=j λkak(x, yk)Cn

∑nk=j ak(x, yk)Cn

≥ λj∑n

k=j |ak|2

∑nk=j |ak|2

= λj.

Also ergibt sichR(x) ≥ λj.

Für x = yj ergibt sich

R(yj) =(yj, Ayj)Cn∥∥yj

∥∥22

= λj.

Also ist

λj =


x ∈ Cn \ {0}.

Fazit 2.50. Ist die Matrix A hermitesch, so lassen sich alle reellen Eigenwerte von A alsMinimierungs- bzw. Maximierungsproblem mit dem Kostenfunktional R darstellen:

λ1 = minx∈Cn\{0}

R(x), λn = maxx∈Cn\{0}

R(x)

sowie

λj =


x ∈ Cn \ {0}

=

max R(x)bei (x, yk)Cn = 0 ∀k = j + 1, . . . , n

x ∈ Cn \ {0}.

55


Satz 2.51 (Variationsprinzip von Courant und Fischer). Es sei A ∈ Cn×n hermitesch mitEigenwerten

λ1 ≤ λ2 ≤ . . . ≤ λn.

Dann gilt für jedes j = 1, . . . , n:

λj = minV⊂Cn

dim(V)=j

maxx∈V\{0}

R(x) = maxV⊂Cn

dim(V)=n−j+1

minx∈V\{0}

R(x).

Beweis. Da A ∈ Cn×n hermitesch ist, existiert eine Orthonormalbasis {yk}nk=1 ⊂ Cn \

{0} aus Eigenvektoren von A zu Eigenwerten λk. Sei nun j ∈ {1, . . . , n} beliebig aberfest und V ⊂ Cn ein Unterraum mit dim(V) = j. Es gilt

V ∩ Span{yj, . . . , yn} 6= {0},

denn wäre V ∩ Span{yj, . . . , yn} = {0}, so wäre

dim(V +Span{yj, . . . , yn}) = dim(V)+dim(Span{yj, . . . , yn}) = j+n− j+ 1 = n+ 1.

Sei nun x ∈ V ∩ Span{yj, . . . , yn} mit x 6= 0. Dann gilt

x =n

∑k=j

akyk.

Folglich gilt

R(x) =(x, Ax)Cn

(x, x)Cn=

(∑nk=j akyk, ∑n

k=j ak Ayk)Cn

(∑nk=j akyk, ∑n

k=j akyk)Cn=

∑nk=j λk|ak|2

∑nk=j |ak|2

≥ λj.

Hieraus ergibt sichmax

x∈V\{0}R(x) ≥ λj.

Da diese Ungleichung für alle Unterräume V mit dim(V) = j gilt, so muss gelten

minV⊂Cn

dim(V)=j

maxx∈V\{0}

R(x) ≥ λj.

Um die andere Ungleichung zu zeigen, setzen wir

V = Span{y1, . . . , yj}

mit dim(V) = j. Dann gilt

minV⊂Cn

dim(V)=j

maxx∈V\{0}

R(x) ≤ maxx∈V\{0}

R(x) ≤ λj,

56


denn x ∈ V \ {0}. Daher hat x die Darstellung

x =j

∑j=1

akyk.

Also ist

R(x) =∑

jk=1 λk|ak|2

∑jk=1 |ak|2

≤ λj.

Insgesamt giltλj ≤ min

V⊂Cn

dim(V)=j

maxx∈V\{0}

R(x) ≤ λj.

Der zweite Teil des Satzes ist Hausaufgabe.

Eine Folgerung des Variationsprinzips von Courant und Fischer ist der folgendeStörungssatz.Satz 2.52. Es seien A, E ∈ Cn×n hermitesch. Für B ∈ {A, E, A + E} bezeichnen wir mit

λ1(B) ≤ λ2(B) ≤ . . . ≤ λn(B)

die monoton steigenden Eigenwerte von B. Dann gilt

λj(A) + λ1(E) ≤ λj(A + E) ≤ λj(A) + λn(E) ∀j = 1, . . . , n.

Beweis. Es sei j ∈ {1, . . . , n}. Das Variationsprinzip von Courant und Fischer liefert

λj(A + E) = minV⊂Cn

dim(V)=j

maxx∈V\{0}

R(x)

= minV⊂Cn

dim(V)=j

maxx∈V\{0}

(x, (A + E)x)Cn

(x, x)Cn

= minV⊂Cn

dim(V)=j

maxx∈V\{0}

((x, Ax)Cn

(x, x)Cn+

(x, Ex)Cn

(x, x)Cn

).

Da E ∈ Cn×n hermitesch ist, so ist

Bild(RE) =

{(x, Ex)Cn

(x, x)Cn| x ∈ Cn \ {0}

}= [λ1(E), λn(E)].

Daher ist

λj(A + E) = minV⊂Cn

dim(V)=j

maxx∈V\{0}

(x, (A + E)x)Cn

(x, x)Cn

≤ minV⊂Cn

dim(V)=j

maxx∈V\{0}

(x, Ax)Cn

(x, x)Cn+ λn(E)

= λj(A) + λn(E).

57

2.6 Numerische Behandlung von Eigenwerten

Analog gilt

λj(A + E) = maxV⊂Cn

dim(V)=n−j+1

minx∈V\{0}

(x, (A + E)x)Cn

(x, x)Cn

≥ maxV⊂Cn

dim(V)=n−j+1

minx∈V\{0}

(x, Ax)Cn

(x, x)Cn+ λ1(E)

= λj(A) + λ1(E).

Insgesamt gilt also

λj(A) + λ1(E) ≤ λj(A + E) ≤ λj(A) + λn(E) ∀j = 1, . . . , n.

Korollar 2.53. Es seien A, E ∈ Cn×n hermitesch. Dann gilt

|λk(A + E)− λk(A)| ≤ ‖E‖2 ∀k = 1, . . . , n.


2.6.1 Vektoriterationen

Die einfachste Idee geht auf Richard von Mises zurück:Ausgehend von einem Startvektor x0 ∈ Rn \ {0} iterieren wir

xk+1 = Axk, k = 0, 1, . . . ,

wobei A ∈ Rn×n symmetrisch ist. In der Literatur heißt dieses Verfahren „Power-method“.Satz 2.54. Es sei A ∈ Rn×n symmetrisch und λn ∈ Λ(A) ein einfacher Eigenwert mit

0 6= |λn| > |λn−1| ≥ . . . ≥ |λ1|

für alle Eigenwerte von A. Mit anderen Worten ist λn der betragsmäßig größte Eigenwert vonA. Ist der Startvektor x0 ∈ Rn \ {0} nicht orthogonal zum Eigenraum von λn, das heißt

(x0, y) 6= 0 ∀y ∈ EA(λn) \ {0},

dann konvergiert

yk :=xk∥∥xk∥∥

2sign(λn)

k, sign(λn) =λn

|λn|,

bei der Power-method xk+1 = Axk gegen einen normierten Eigenvektor zum Eigenwert λn,das heißt

limk→∞

yk = y∗, Ay∗ = λny∗, ‖y∗‖2 = 1.

58


Beweis. Da A ∈ Rn×n symmetrisch ist, existiert eine Orthonormalbasis {yj}nj=1 ⊂

Rn \ {0} aus Eigenvektoren von A zu Eigenwerten λj, das heißt

Ayj = λjyj ∀j = 1, . . . , n.

Sei x0 ∈ Rn \ {0} beliebig aber fest mit

(x0, yn)Cn 6= 0.

Wir schreiben nun x0 als Linearkombination von {yj}nj=1:

x0 =n

∑j=1

ajyj.

Da (x0, yn)Cn 6= 0 ist, so muss

0 6= (x0, yn)Cn =

(n

∑j=1

ajyj, yn

)Cn

= an

gelten, also ist an 6= 0. Andererseits ist

xk = Axk−1 = . . . = Akx0 = Akn

∑j=1

ajyj =n

∑j=1

aj Akyj︸︷︷︸=λk

j yj

und daher

xk =n

∑j=1

ajλkj yj.

Da aber an 6= 0 und λn 6= 0 ist, so erhalten wir

xk =n−1

∑j=1

ajλkj yj + anλk

nyn = anλkn

(n−1

∑j=1

aj

an

(λj

λn

)k

yj + yn

).

Der Term∣∣∣ λj

λn

∣∣∣ erfüllt ∣∣∣∣ λj

λn

∣∣∣∣ < 1 ∀j = 1, . . . , n− 1,

denn |λn| > |λn−1| ≥ . . . ≥ |λ1|. Hieraus folgt(n−1

∑j=1

aj

an

(λj

λn

)k

yj + yn

)→ yn für k→ ∞

und insgesamt

yk =xk∥∥xk∥∥

2sign(λn)

k → ±yn.

59


Bemerkung 2.55. Der Vektor xk muss nicht konvergieren, denn:Ist λn > 1, so ist

xk → ∞.

Nachteile:

(i) Die Methode berechnet nur den betragsmäßig größten Eigenwert von A und denzugehörigen Eigenvektor.

(ii) Die Konvergenzgeschwindigkeit hängt im Wesentlichen von der Größe∣∣∣λn−1

λn

∣∣∣ab. Liegen |λn| und |λn−1| dicht beieinander, dann konvergiert das Verfahrenlangsam.

Ein besseres Verfahren ist die inverse Vektoriteration1. Seine Idee ist wie folgt:Es sei A ∈ Rn×n symmetrisch und λ ∈ Λ(A) und λ /∈ Λ(A) mit

|λ− λ| < |λ− λ| ∀λ ∈ Λ(A) \ {λ}.Mit anderen Worten ist

|λ− λ|−1 > |λ− λ|−1 ∀λ ∈ Λ(A) \ {λ}.Also ist |λ− λ|−1 der betragsmäßig größte Eigenwert der Matrix (A− λI)−1. Beachte,dass λ als eine Approximation oder Störung des Eigenwerts λ ∈ Λ(A) interpretiertwerden kann. Da λ /∈ Λ(A) gilt, so ist

(A− λI)

regulär, denn det(A− λI) 6= 0. Das Verfahren der inversen Vektoriteration lautet

(A− λI)xk+1 = xk, k = 0, 1, 2, . . .

Satz 2.56 (Konvergenzaussage für inverse Vektoriterationen). Es sei A ∈ Rn×n symme-trisch. Ferner seien λ ∈ Λ(A), λ /∈ Λ(A) mit

|λ− λ| < |λ− λ| ∀λ ∈ Λ(A) \ {λ},und (λ− λ)−1 sei ein einfacher Eigenwert von (A− λI)−1. Genügt der Startvektor x0 ∈Rn \ {0} der Bedingung

(x0, y)Cn 6= 0 ∀y ∈ E(A−λI)−1((λ− λ)−1) \ {0},so konvergiert

yk :=xk∥∥xk∥∥

2sign((λ− λ)−1)k

bei der inversen Vektoriteration (A− λI)xk+1 = xk gegen einen normierten Eigenvektor vonA zum Eigenwert λ, das heißt

limk→∞

yk = y∗, Ay∗ = λy∗, ‖y∗‖2 = 1.

1Helmut Wielandt, 1945

60


Beweis. Das Verfahren der inversen Vektoriteration ist nichts anderes als

xk+1 = (A− λI)−1xk,

also die Power-method angewendet auf die Matrix (A− λI)−1. Alle Voraussetzungendes vorherigen Satzes sind erfüllt und somit konvergiert yk = xk

‖xk‖2sign(λn)k gegen

einen normierten Eigenvektor von (A− λI)−1, das heißt

limk→∞

yk = y∗, (A− λ)−1y∗ = (λ− λ)−1y∗, ‖y∗‖2 = 1.

Hieraus folgt

y∗ = (A− λI)(A− λI)−1y∗ = (A− λI)(λ− λ)−1y∗,

was äquivalent ist zu(λ− λ)y∗ = (A− λI)y∗,

also schließlichλy∗ − λy∗ = Ay∗ − λy∗

und somit die Behauptung.

Vorteile der Vektoriteration:

(i) Theoretisch ist es möglich, alle Eigenwerte von A mithilfe der inversen Vektorite-ration zu bestimmen.

(ii) Ist λ ≈ λ, dann ist |λ− λ| sehr klein im Vergleich mit

|λ− λ| ∀λ ∈ Λ(A) \ {λ}

und somit konvergiert das Verfahren recht schnell gegen λ, denn in diesem Fallgilt

maxλ∈Λ(A)\{λ}

∣∣∣∣∣ λ− λ

λ− λ

∣∣∣∣∣� 1.

Nachteil des Verfahrens ist:

(i) Man muss die Inverse (A− λI)−1 bestimmen.

Beispiel 2.57. Wir betrachten die Matrix

A =

(−1 3−2 4

).

Die Eigenwerte sind λ1 = 1 und λ2 = 2. Sei λ = 1− ε eine Approximation von λ1.Somit ist

(A− λI) =(−2 + ε 3−2 3 + ε

).

61


Diese Matrix ist fast singulär, denn

(A− λI)−1 =1

ε(ε + 1)

(3 + ε −3

2 −2 + ε

).

Bei ε → 0 ist (A− λI)−1 singulär (nicht regulär). Durch Normierung kürzt sich derFaktor 1

ε(ε+1) heraus. Folglich ist die Berechnung einer normierten Lösung von

(A− λI)x = b

gut konditioniert.

Bemerkung 2.58. Ist λ ≈ λ gewählt, so ist (A− λI) fast singulär. Wir rechnen abernicht den Eigenvektor x aus, sondern nur x

‖x‖2, also nur dessen Richtung (vgl. Deufel-

hard/Hohmann, Bsp. 2.33).

2.6.2 Das QR-Verfahren zur Eigenwertbestimmung

In Numerik I haben wir die folgende Aussage gezeigt.Satz 2.59 (Existenz und Eindeutigkeit der QR-Zerlegung). Es sei A ∈ Rn×n regulär.Dann besitzt A eine QR-Zerlegung

A = QR

mit einer orthogonalen Matrix Q ∈ Rn×n und einer oberen Dreiecksmatrix R ∈ Rn×n. Ist

A = QR

eine andere QR-Zerlegung, so existiert eine Diagonalmatrix

D =

±1 0. . .

0 ±1

,

so dassQ = QD und R = DR.

Bemerkung 2.60. Die QR-Zerlegung lässt sich zum Beispiel durch Householder-Spiegelungen bestimmen.

Das QR-Verfahren zur Eigenwertbestimmung sieht wie folgt aus.

Algorithmus 2.1 QR-Verfahren

(S0) Setze A0 := A und k = 0.(S1) Bestimme eine QR-Zerlegung von Ak

Ak = QkRk.

(S2) Setze Ak+1 = RkQk, k = k + 1, und gehe zu (S1).

62


Lemma 2.61. Es sei A ∈ Rn×n regulär. Dann ist der QR-Algorithmus durchführbar, und dieerzeugten Matrizen Ak erfüllen die folgenden Bedingungen:

(i) Alle Ak sind ähnlich zu A.

(ii) Ist A symmetrisch, so ist auch Ak symmetrisch für alle k ∈N.

Beweis. Da A ∈ Rn×n regulär ist, ist der Algorithmus durchführbar.

(i) Sei k = 0, 1, . . .. Dann gilt

Ak = QkRk,Ak+1 = RkQk.

Damit istQk Ak+1QT

k = QkRkQkQTk = QkRk = Ak,

also sind Ak+1 und Ak ähnlich für alle k ∈N. Insgesamt sind also alle Ak ähnlichzu A.

(ii) Mit (i) folgtQk Ak+1QT

k = Ak

und daherAk+1 = QT

k AkQk.

Ist Ak symmetrisch, so ist

ATk+1 = (QT

k AkQk)T = QT

k ATk Qk = QT

k AkQk = Ak+1.

Mit anderen Worten ist Ak+1 ebenso symmetrisch.

Insgesamt ergibt sich somit die Behauptung.

Satz 2.62 (Konvergenz des QR-Verfahrens). Sei A ∈ Rn×n regulär und diagonalisierbarmit reellen Eigenwerten, so dass gilt

|λ1| > |λ2| > |λ3| > . . . > |λn| > 0.

Die Inverse der MatrixT =

[y1 y2 · · · yn

]∈ Rn×n,

mit orthonormalen Eigenvektoren yj zu λj, besitze ohne Pivotisierung die LR-Zerlegung

T−1 = LR, L =

1 0. . .

∗ 1

∈ Rn×n, R =

∗ ∗. . .∗

∈ Rn×n.

63


Dann gilt für das QR-Verfahren:

Ak = SkUSk +O(qk) für k→ ∞

mit

q = maxj∈{1,...,n−1}

∣∣∣∣∣λj+1

λj

∣∣∣∣∣ ∈ (0, 1),

Sk = diag{Sk1 , . . . , Skn}, Skj ∈ {±1} ∀j = 1, . . . , n

und

U =

λ1 ∗. . .

0 λn

∈ Rn×n.

Bemerkung 2.63. Wir schreiben fk ∈ O(qk), bzw. fk = O(qk) für k→ ∞ genau dann,wenn

∃C > 0 ∀k ∈N : ‖ fk‖2 ≤ Cqk.

Da limk→∞

qk = 0, so folgt auch limk→∞

fk = 0.

Beweis. Für die Eigenvektormatrix T nehmen wir eine QR-Zerlegung vor:

T = QR (2.9)

mit einer Orthogonalmatrix Q ∈ Rn×n und einer oberen Dreiecksmatrix R ∈ Rn×n.Wir zeigen:

Ak = Sk(RDR−1)Sk +O(qk) für k→ ∞,

wobei Sk Vorzeichenmatrizen sind und D = diag(λ1, . . . , λn). Dann folgt die Aussagemit U = RDR−1.Schritt 1: Laut Voraussetzung gilt

T−1 = LR mit L =

1 0. . .

∗ 1

und R =

∗ ∗. . .

0 ∗

. (2.10)

Wir setzen

Lk := DkLD−k =

λk1 0

. . .0 λk

n

1

l21. . .

... . . .ln1 . . . ln,n−1 1

λ−k

1 0. . .

0 λ−kn

. (2.11)

64


Daraus ergibt sich

(Lk)ij =

(λi

λj

)k

lij =

1 für i = j0 für i < j(

λiλj

)klij für i > j

.

Es gilt für i > j ∣∣∣∣∣λi

λj

∣∣∣∣∣ ≤ maxl∈{1,...,n−1}

∣∣∣∣λl+1

λl

∣∣∣∣ = q ∈ (0, 1),

denn |λ1| > |λ2| > |λ3| > . . . > |λn| > 0. Hieraus folgt

Lk = DkLD−k = I +O(qk) für k→ ∞. (2.12)

Für jedes k ∈N ist Lk regulär, und somit ist

RLk ∈ Rn×n

ebenso regulär. Demzufolge hat RLk eine QR-Zerlegung

RLk = QkRk (2.13)

mit einer Orthogonalmatrix Qk ∈ Rn×n und einer oberen Dreiecksmatrix Rk ∈ Rn×n.Folglich gilt

QkRk = RLk(2.12)= R(I +O(qk)) für k→ ∞

= IR +O(qk) für k→ ∞.

Insbesondere giltlimk→∞

QkRk = IR.

Da die QR-Zerlegung stetig von der gewählten Matrix abhängt, liefert die obigeAussage

Qk = I +O(qk) für k→ ∞,

Rk = R +O(qk) für k→ ∞,

das heißt insbesondere

limk→∞

Qk = I,

limk→∞

Rk = R.

65


2. Schritt: Das QR-Verfahren lautetA1 := AAk := QkRk

Ak+1 := RkQk

.

Außerdem istTDT−1 = A ⇔ D = T−1AT.

Folglich gilt

A2 = AA = TDT−1TDT−1 = TD2T−1

...

Ak = TDkT−1

und daher

Ak (2.9)−(2.10)= QRDkLR = QRDkLD−kDkR

(2.11)= QRLkDkR

(2.13)= QQkRkDkR.

Insgesamt istAk = QQk︸︷︷︸

orthogonaleMatrix

RkDkR︸︷︷︸obere

Dreiecksmatrix

∀k ∈N.

Wir haben also eine QR-Zerlegung für Ak gefunden. Wir berechnen nun eine andereQR-Zerlegung für Ak anhand des QR-Verfahrens. Dazu setzen wir

Q1···k := Q1Q2 · . . . ·Qk ∈ Rn×n orthogonal,Rk···1 := RkRk−1 · . . . · R1 ∈ Rn×n obere Dreiecksmatrix.

Nun giltAk+1 = RkQk = QT

k QkRkQk = QTk AkQk ∀k ∈N.

Also ist

Ak+1 = QTk QT

k−1 · . . . ·QT1 AQ1 · . . . ·Qk

= (Q1 · . . . ·Qk)T A(Q1 · . . . ·Qk)

= QT1···k AQ1···k

und somitQ1···k Ak+1 = AQ1···k.

Das heißtQ1···k−1Ak = AQ1···k−1 ∀k ∈N.

66


Somit ist

Q1···kRk···1 = Q1 · . . . ·QkRk · . . . · R1

= Q1···k−1AkRk−1···1= AQ1···k−1Rk−1···1 ∀k ∈N.

Wir erhalten

Q1···2R2···1 = AQ1R1 = AA1 = AA = A2

Q1···3R3···1 = AQ1···2R2···1 = A3

...

Q1···kRk···1 = Ak ∀k ∈N.

Das heißt wir haben eine zweite QR-Zerlegung für Ak gefunden:

Ak = Q1···kRk···1 ∀k ∈N.

Insgesamt gilt

Ak = QQkRkDkR ∀k ∈N,

Ak = Q1···kRk···1 ∀k ∈N.

Somit liefert der Satz über die Eindeutigkeit der QR-Zerlegung eine Vorzeichenmatrix

Sk+1 = diag(±1, . . .± 1), k ∈N,

so dass gilt

Q1···k = QQkSk+1 ∀k ∈N,

Rk···1 = Sk+1RkDkR ∀k ∈N.

Diese Identitäten liefern zum Einen

QT1···k−1 = SkQT

k−1QT (2.14)

und zum AnderenQ1 · . . . ·Qk = Q1···k = QQkSk+1

und somit

Qk = QTk−1 · . . . ·QT

1 QQkSk+1

= (Q1 · . . . ·Qk−1)TQQkSk+1

= QT1···k−1QQkSk+1. (2.15)

67


Aus (2.14)-(2.15) ergibt sich

Qk = QT1···k−1QQkSk+1

= SkQTk−1QTQQkSk+1

= SkQTk−1QkSk+1.

Analog gilt

Rk = Rk···1R−1k−1···1

= Sk+1RkDkRR−1(D−1)k−1R−1k−1Sk

= Sk+1RkDR−1k−1Sk.

Insgesamt giltAk = QkRk = SkQT

k−1QkSk+1Sk+1RkDR−1k−1Sk.

Aus Schritt 1 erhalten wir

Ak = SkRDR−1Sk +O(qk) für k→ ∞.

Bemerkung 2.64.

(i) Die Voraussetzung an T ist a priori nicht nachprüfbar, weil man die Eigenvektorennicht kennt. Man wendet das Verfahren an und hofft, dass alles gut geht.

(ii) Der Satz gilt nicht mehr für komplexe Eigenwerte.

(iii) Entscheidend für die Geschwindigkeit des Verfahrens ist

q = maxj∈{1,...,n−1}

∣∣∣∣∣λj+1

λj

∣∣∣∣∣ ∈ (0, 1).

Liegen die Eigenwerte |λj+1| und |λj| dicht beieinander, so ist

q ≈ 1

und wir erhalten eine langsame Konvergenz.

Korollar 2.65. Unter den Voraussetzungen des vorherigen Satzes gilt

limk→∞

(Ak)jj = λj ∀j = 1, . . . , n.

68


Beweis. Im vorherigen Satz haben wir gezeigt:

Ak = SkUSk +O(qk) für k→ ∞

mit Sk = diag{±1, . . . ,±1}, q ∈ (0, 1) und

U =

λ1 ∗. . .

0 λn

.

Hieraus ergibt sich

SkUSk =

Sk1 0. . .

0 Skn

λ1 ∗

. . .0 λn

Sk1 0

. . .0 Skn

=

λ1S2k1 ∗

. . .0 λnS2

kn

=

λ1 ∗. . .

0 λn

.

Mit qk → 0 für k→ ∞ ergibt sich insgesamt

limk→∞

(Ak)jj = λj ∀j = 1, . . . , n.

69

Kapitel 3Das GMRES-Verfahren

In diesem Abschnitt untersuchen wir das GMRES-Verfahren (Generalized MinimalResidual Method) zur Lösung von linearen Gleichungssystemen der Form

Ax = b

mit einer Matrix A ∈ Rn×n und b ∈ Rn \ {0}. Dieses Problem lässt sich zum Beispieldurch das CG-Verfahren lösen, wie wir bereits in Numerik I gelernt haben. AlsVoraussetzung für die Konvergenz benötigt das CG-Verfahren symmetrische undpositiv definite Matrizen. Im Gegensatz dazu benötigt das GMRES-Verfahren dieseAnnahmen nicht.

3.1 Arnoldi-Prozess

Die folgende Definition kennen wir aus Numerik I.Definition 3.1 (Krylov-Raum). Es seien A ∈ Rn×n und b ∈ Rn. Dann heißt die Menge

Km(A, b) = Span{b, Ab, A2b, . . . , Am−1b}

Krylov-Raum.

Es ist klar, dassKm ⊂ Km+1

für alle m ∈N gilt. Als Nächstes wiederholen wir das Gram-Schmidt-Verfahren.Sei {aj}m

j=1 ⊂ Rn \ {0} linear unabhängig. Wir setzen

qj = aj −j−1

∑i=1

(qi, aj)qi ∀j = 1, . . . , m,

qj =qj∥∥qj∥∥

2

.

Insbesondere gilt für j = 1:q1 = a1, q1 =

a1

‖a1‖2.

71

3.1 Arnoldi-Prozess

Dann folgt(qi, qj) = δij ∀i, j ∈ {1, . . . , m}.

Definition 3.2. Es seien A ∈ Rn×n und b ∈ Rn \ {0}. Der Arnoldi-Prozess ist definiertwie folgt:(S0) q1 := b

‖b‖2und setze m = 1.

(S1) qm+1 := Aqm −∑mk=1(Aqm, qk)qk

(S2) Abbruchkriterium:1: if qm+1 = 0 then2: STOP3: end if

(S3) Setze qm+1 = qm+1‖qm+1‖2

(Normierung), m = m + 1, und gehe zu (S1).

Beim Arnoldi-Prozess wird also geprüft, ob mit nochmaliger Anwendung der MatrixA nach b, Ab, . . . noch eine neue Dimension ins Spiel kommt. Im Folgenden bezeichnenwir mit m∗ ∈ {1, . . . , n} den Abbruchindex, das heißt den kleinsten Index mit

qm∗+1 = 0 ⇔ Aqm∗ ∈ Span{q1, . . . , qm∗}.

Lemma 3.3. Die vom Arnoldi-Prozess erzeugten Vektoren q1, . . . , qm∗ sind paarweise orthogo-nal, und es gilt

Span{q1, . . . , qm} = Span{q1, . . . , qm−1, Aqm−1} = Km(A, b) ∀m ∈ {1, . . . , m∗}.

Ist A regulär, so giltx∗ = A−1b ∈ Km∗(A, b).

Beweis. Es sei m ∈ {1, . . . , m∗}. Nach Definition sind q1, . . . , qm paarweise orthogonalund

Span{q1, . . . , qm} = Span{q1, . . . , qm−1, Aqm−1}. (3.1)

Mit Induktion zeigen wir nun die andere Identität

Span{q1, . . . , qm} = Km(A, b). (3.2)

Induktionsanfang m = 1: Span{q1} = Span{b} = K1(A, b).

Induktionsannahme: Es gelte

Span{q1, . . . , qm} = Km(A, b)

für ein m ∈ {1, . . . , m∗ − 1}. Wir zeigen nun, dass die Aussage für m + 1 gilt.

72

3.1 Arnoldi-Prozess

Dazu betrachten wir

Aqm = A

(m

∑i=1

λi Ai−1b

)=

m

∑i=1

λi Aib ∈ Km+1(A, b).

Nun gilt

Span{q1, . . . , qm+1}(3.1)= Span{q1, . . . , qm, Aqm} ⊂ Km+1(A, b)

und die Gleichheit folgt unmittelbar aus Dimensionsgründen:

m + 1 = dim(Span{q1, . . . , qm+1}) ≤ dim(Km+1(A, b)) = m + 1.

Es sei nun A regulär. Nach Definition ist m∗ der Abbruchindex, und somit haben wir

Aqm∗ ∈ Span{q1, . . . , qm∗} = Km∗(A, b).

Außerdem gilt für j ∈ {1, . . . , m∗ − 1}:

Aqj ∈ Span{q1, . . . , qj, Aqj} = Span{q1, . . . , qj+1} = Kj+1(A, b) ⊂ Km∗(A, b).

Daraus folgtAqj ∈ Km∗(A, b) ∀j ∈ {1, . . . , m∗}

und somitA(Km∗(A, b))

(3.2)= A(Span{q1, . . . , qm∗}) ⊂ Km∗(A, b).

Das heißt, die Funktion

F : Km∗(A, b)→ Km∗(A, b), F(x) = Ax,

ist wohldefiniert und bijektiv, da A regulär ist. Daher gilt

x∗ = A−1b ∈ Km∗(A, b),

da b ∈ Km∗(A, b).

3.1.1 Matrixversion des Arnoldi-Prozesses

Wir führen nun die Matrixversion des Arnoldi-Prozesses wie folgt ein.Definition 3.4. Es seien A ∈ Rn×n und b ∈ Rn \ {0}. Ferner seien q1, . . . , qm∗ die vomArnoldi-Prozess erzeugten Vektoren mit dem Abbruchindex m∗ ∈ {1, . . . , n}. Wirdefinieren

hkm := (Aqm, qk), k = 1, . . . , m,hm+1,m := ‖qm+1‖2 , m = 1, . . . , m∗ − 1.

73

3.1 Arnoldi-Prozess

Nach Definition des Arnoldi-Prozesses haben wir für jedes m ∈ {1, . . . , m∗ − 1}:

hm+1,mqm+1 = ‖qm+1‖2 qm+1 = qm+1 = Aqm −m

∑k=1

(Aqm, qk)︸︷︷︸=hkm

qk.

Folglich gilt

Aqm =m+1

∑k=1

hkmqk.

Also sind

Aq1 = h11q1 + h21q2

Aq2 = h12q1 + h22q2 + h32q3

...Aqm = h1mq1 + . . . + hm+1,mqm+1

und wir erhalten

A[q1 · · · qm

]︸︷︷︸∈Rn×m

=[q1 · · · qm+1

]︸︷︷︸∈Rn×(m+1)

h11 · · · · · · h1m

h21. . . .... . . . . . ...

. . . hmm0 hm+1,m

︸︷︷︸

∈R(m+1)×m

.

Bei m = m∗ ist laut Definition qm∗+1 = 0 und somit haben wir

A[q1 · · · qm∗

]︸︷︷︸∈Rn×m∗

=[q1 · · · qm∗

]︸︷︷︸∈Rn×m∗

h11 · · · · · · h1m∗

h21. . . .... . . . . . ...

0 hm∗,m∗−1 hm∗m∗

︸︷︷︸

∈Rm∗×m∗

.

Somit haben wir den folgenden Satz bewiesen:

Satz 3.5. Es seien A ∈ Rn×n und b ∈ Rn \ {0}. Ferner seien q1, . . . , qm∗ und hij die vomArnoldi-Prozess erzeugten Größen. Dann gilt

AQm = Qm+1Hm ∀m = 1, . . . , m∗ − 1,AQm∗ = Qm∗Hm∗

74

3.2 Definition des GMRES-Verfahrens

mit

Qm :=[q1 · · · qm

]∈ Rn×m,

Hm :=

h11 · · · · · · h1m

h21. . . .... . . . . . ...

. . . hmm0 hm+1,m

∈ R(m+1)×m,

Hm∗ :=

h11 · · · · · · h1m∗

h21. . . .... . . . . . ...

0 hm∗,m∗−1 hm∗m∗

∈ Rm∗×m∗ .

Definition 3.6. Eine Matrix A ∈ Rn×n der Gestalt

A =

∗ · · · · · · ∗∗ . . . ...

. . . . . . ...0 ∗ ∗

heißt obere Hessebergmatrix.

Korollar 3.7. Gilt m∗ = n, das heißt der Arnoldi-Prozess bricht nicht vorzeitig ab, so gilt

QTn AQn = Hn.

Mit anderen Worten ist A in diesem Fall ähnlich zur Hessebergmatrix Hn.


Grundidee: Zur Lösung des Gleichungssystems

Ax = b

werden schrittweise die Minimierungsaufgaben

minx∈Km(A,b)

‖Ax− b‖2 , m = 1, . . . , m∗

gelöst. Man sucht also xm ∈ Km(A, b), so dass

‖Axm − b‖2 = minx∈Km(A,b)

‖Ax− b‖2

75


gilt. Mit anderen Worten minimiert xm das Residuum

r = Ax− b auf Km(A, b) = Span{b, Ab, . . . , Am−1b}.

Daher kommt der Name

Generalized Minimal Residual Method

als Verallgemeinerung von MinRes-Verfahren (diese funktionieren für symmetrischeMatrizen).Lemma 3.8. Es seien A ∈ Rn×n und b ∈ Rn \ {0}. Mit den Bezeichnungen aus demArnoldi-Prozess gelten für die vom GMRES-Verfahren erzeugten Vektoren xm ∈ Km(A, b),m = 1, . . . , m∗, die Darstellungen

xm = Qmzm, m = 1, . . . , m∗,

und xm ∈ Km(A, b) löst genau dann

minx∈Km(A,b)

‖Ax− b‖2 ,

wenn zm ∈ Rm die Aufgabeminz∈Rm

‖Hmz− cm‖2

löst mit

cm =

‖b‖2

0...0

∈ Rmin{m∗,m+1}.

Beweis.

(i) xm ∈ Km(A, b) heißt xm ∈ Span{q1, . . . , qm}, das heißt

xm =m

∑i=1

qizi =: Qmzm.

(ii) Sei m ∈ {1, . . . , m∗ − 1}. Dann gilt

‖Axm − b‖2 = ‖AQmzm − b‖2 = ‖Qm+1Hmzm − b‖2

=∥∥∥Qm+1Hmzm −Qm+1QT

m+1b∥∥∥

2

=∥∥∥Qm+1(Hmzm −QT

m+1b)∥∥∥

2

= ‖Qm+1(Hmzm − cm)‖2

= ‖Hmzm − cm‖2 ,

76

3.3 Vorgehensweise zur Lösung der Minimierungsprobleme beim GMRES-Verfahren

denn als Matrix mit orthonormalen Spaltenvektoren hat Qm+1 die Isometrieei-genschaft ‖Qm+1y‖2 = ‖y‖2.Nebenrechnungen:

QTm+1b =

qT1...

qTm+1

b =

qT1...

qTm+1

q1 ‖b‖2 =

‖b‖2

0...0

= cm,

weil (qi, qk) = δik. Hieraus folgt auch

Qm+1QTm+1b =

[q1 · · · qm+1

]‖b‖2

0...0

= q1 ‖b‖2 = b.

Für m = m∗ bekommen wir analog

‖Axm∗ − b‖2 = ‖Qm∗(Hm∗zm∗ − cm∗)‖2 = ‖Hm∗zm∗ − cm∗‖2 .

Insgesamt gilt

‖Axm − b‖2 = ‖Hmzm − cm‖2 ∀m ∈ {1, . . . , m∗}.

3.3 Vorgehensweise zur Lösung derMinimierungsprobleme beim GMRES-Verfahren

Es sei m ∈ {1, . . . , m∗ − 1}. Wir wissen bereits:

minx∈Km(A,b)

‖Ax− b‖2 ⇔ minz∈Rm

‖Hmz− cm‖2

mit

Hm =

h11 · · · · · · h1m

h21. . . .... . . . . . ...

. . . hmm0 hm+1,m

∈ R(m+1)×m, cm =

‖b‖2

0...0

∈ Rm+1.

Wir bestimmen die volle QR-Zerlegung der Matrix Hm

Hm = Tm

[Rm0T

]

77


mit einer Orthogonalmatrix Tm ∈ R(m+1)×(m+1) und einer oberen Dreiecksmatrix Rm ∈Rm×m, sowie 0 ∈ Rm. Mit der QR-Zerlegung lässt sich das obige Minimierungsproblemeinfach lösen:

(i) ‖Hmz− cm‖2 =

∥∥∥∥Tm

[Rm0T

]z− cm

∥∥∥∥2=

∥∥∥∥Tm

[Rmz0T

]− TmTT

mcm

∥∥∥∥2

=

∥∥∥∥[Rmz0T

]− TT

mcm

∥∥∥∥2

.

(ii) Partitionierung:

TTmcm =

(b1b2

).

(iii) LöseRmz = b1 (Rückwärtssubstitution).

Aus der daraus resultierenden Lösung zm erhalten wir

xm = Qmzm.

Für m = m∗ macht man analog wie oben

Hm∗ =

h11 · · · · · · h1m∗

h21. . . .... . . . . . ...

0 hm∗,m∗−1 hm∗m∗

= Tm∗Rm∗

mit einer Orthogonalmatrix Tm∗ ∈ Rm∗×m∗ und einer oberen Dreiecksmatrix Rm∗ ∈Rm∗×m∗ .

3.3.1 Detaillierte Beschreibung der QR-Zerlegungen

Die obigen QR-Zerlegungen der Matrizen Hm lassen sich sehr effizient erledigen,indem jeweils die vorangegangene Zerlegung verwendet wird.

(i) Initialzerlegung m = 1 (Annahme m∗ 6= 1):

Für m = 1, m∗ 6= 1, gilt

H1 =

[h11h21

]mit

h11 = (Aq1, q1) = (Ab, b)1

‖b‖22

h21 = ‖q2‖2 6= 0 (da m∗ 6= 1 ist).

78


Wir suchen eine Orthogonalmatrix T1 ∈ R2×2 mit

T1 =

[T11 T12T21 T22

], H1 = T1

[r110

]bzw. TT

1 H1 =

[r110

]mit r11 6= 0. Hier können wir die Orthogonalmatrix T1 ∈ R2×2 mittels Householder-Spiegelungen bestimmen.

(ii) m− 1→ m ∈ {1, . . . , m∗ − 1}:Es seien nun Tm−1, Rm−1 bereits bestimmt, das heißt

Hm−1 = Tm−1

[Rm−1

0T

]mit einer Orthogonalmatrix Tm−1 ∈ Rm×m und einer oberen DreiecksmatrixRm−1 ∈ R(m−1)×(m−1). Wir machen den Ansatz

Tm =

Tm−1 0

0T 1

∈ R(m+1)×(m+1).

Es ist klar, dass Tm ∈ R(m+1)×(m+1) orthogonal ist. Laut Definition wissen wirauch

R(m+1)×m 3 Hm =

h11 · · · · · · h1m

h21. . . .... . . . . . ...

0 . . . hmm

0T hm+1,m

=

Hm−1

h1m...

hmm

0T hm+1,m

.

Daraus folgt

TTmHm =

TTm−1 0

0T 1

Hm−1

h1m...

hmm

0T hm+1,m

=

TT

m−1Hm−1 TTm−1

h1m

...

hmm

0T hm+1,m

=

Rm−1

r1m...

0T rmm

0T rm+1,m

79


mit r1m...

rmm

= TTm−1

h1m...

hmm

und rm+1,m = hm+1,m.

Leider ist rm+1,m = hm+1,m = ‖qm+1‖2 6= 0, da m < m∗ ist. Deshalb erfüllt derAnsatz mit Tm noch nicht die gewünschte Eigenschaft. Aus diesem Grund suchenwir eine 2× 2 Orthogonalmatrix

Wm =

[w11 w12w21 w22

],

so dass gilt

Wm

(rmm

rm+1,m

)=

(∗0

).

Insgesamt haben wir

Im−1 0 0

0TWm

0T

TT

m−1 0

0T 1

Hm =

Im−1 0 0

0TWm

0T

Rm−1r1m

...

0T rmm

0T rm+1,m

=

[Rm0T

],

mit einer oberen Dreiecksmatrix Rm ∈ Rm×m, denn es ist

Wm

(rmm

rm+1,m

)=

(∗0

).

Zusammengefasst erhalten wir

Hm = Tm

[Rm0T

], TT

m =

Im−1 0 00T

Wm0T

TTm.

(iii) Der Fall m = m∗:

Hier ist Hm∗ ∈ Rm∗×m∗ also eine quadratische Matrix. Es gilt dann

Hm∗ =

Hm∗−1

h1m∗...

hm∗m∗

80


und daraus folgt

TTm∗−1Hm∗ =

TTm∗−1Hm∗−1

r1m∗...

rm∗m∗

=

Rm∗−1r1m∗

...0T rm∗m∗

,

mit r1m∗...

rm∗m∗

= TTm∗−1

h1m∗...

hm∗m∗

.

Insgesamt erhalten wirTm∗ = Tm∗−1.

81

Kapitel 4Numerische Lösung

gewöhnlicher DGL

4.1 Einführung zu gewöhnlichenDifferentialgleichungen

Definition 4.1. Es sei f : [a, b]×Rn → Rn und y0 ∈ Rn. Ein Anfangswertproblem fürein System von n gewöhnlichen Differentialgleichungen erster Ordnung ist von derForm:

y′(t) = f (t, y(t)) ∀t ∈ (a, b), (DGL)y(a) = y0. (AB)

Gesucht ist also eine differenzierbare Funktion y : [a, b]→ Rn, die das Anfangswert-problem (DGL)-(AB) erfüllt. Die Funktion heißt Lösung von (DGL)-(AB).

Bemerkung 4.2.

(i) Die Aufgabe (DGL) heißt gewöhnliche Differentialgleichung, weil die gesuchteFunktion y nur von einer Variablen t ∈ [a, b] abhängt.

(ii) Die Schreibweisey′(t) = f (t, y(t))

ist äquivalent zu

y′1(t) = f1(t, y1(t), y2(t), . . . , yn(t))y′2(t) = f2(t, y1(t), y2(t), . . . , yn(t))

...y′n(t) = fn(t, y1(t), y2(t), . . . , yn(t)).

(iii) Viele Anwendungsprobleme lassen sich als Anfangswertproblem (DGL)-(AB) auf-fassen, wie beispielsweise die Newtonsche-Bewegungsgleichung, die Berechnungder Flugbahn, das Wachstum einer Population, und vieles mehr.

83

4.1 Einführung zu gewöhnlichen Differentialgleichungen

Satz 4.3 (Existenz und Eindeutigkeit). Es sei f : [a, b]×Rn → Rn stetig und erfülle dieLipschitz-Bedingung:Es existiere eine Konstante L > 0, so dass gilt

‖ f (t, v)− f (t, w)‖2 ≤ L ‖v− w‖2 ∀t ∈ [a, b] und v, w ∈ Rn.

Dann hat das Anfangswertproblem (DGL)-(AB) mit y0 ∈ Rn genau eine stetig differenzierbareLösung y ∈ C1([a, b], Rn). Für Lösungen y, y : [a, b]→ Rn von{

y′(t) = f (t, y(t)) in (a, b)y(a) = y0

,

{y′(t) = f (t, y(t)) in (a, b)y(a) = y0

gilt die Abschätzung

‖y(t)− y(t)‖2 ≤ eL(t−a) ‖y0 − y0‖ ∀t ∈ [a, b].

Bemerkung 4.4.

(i) Dieser Satz geht zurück auf Picard-Lindelöf. Der Beweis ist zum Beispiel im Buchvon Heuser „Gewöhnliche Differentialgleichungen“ zu finden.

(ii) Die Abschätzung

‖y(t)− y(t)‖2 ≤ eL(t−a) ‖y0 − y0‖ ∀t ∈ [a, b]

bedeutet, dass die Lösung y stetig von dem Anfangswert abhängt.

Lemma 4.5. Es sei y : [a, b] → Rn eine stetig differenzierbare Lösung von (DGL)-(AB).Dann erfüllt y die Integralgleichung

y(t) = y0 +∫ t

af (s, y(s))ds

für alle t ∈ [a, b].

Beweis. Laut Voraussetzung erfüllt y : [a, b]→ Rn die folgende Gleichung:

y′(t) = f (t, y(t)) =: g(t) ∀t ∈ [a, b].

Demzufolge ist y : [a, b]→ Rn die Stammfunktion von g : [a, b]→ Rn. Die Funktion gist außerdem laut Annahme stetig. Somit liefert der Hauptsatz der Differential- undIntegralrechnung: ∫ t

ag(s)ds = y(t)− y(a) ∀t ∈ [a, b].

Wir erhalten also insgsamt

y(t) = y(a) +∫ t

ag(s)ds = y0 +

∫ t

af (s, y(s))ds ∀t ∈ [a, b].

84

4.2 Bekannte numerische Lösungsverfahren


Um das Anfangswertproblem (DGL)-(AB) numerisch zu lösen, müssen wir zunächstdas Zeitintervall [a, b] diskretisieren. Am einfachsten verwenden wir die äquidistanteZerlegung

a := t0 < t1 < . . . < tN =: b,

tj = a + jh mit h =b− a

N(Schrittweite).

Gesucht sind nun Approximationen

uj ≈ y(tj) ∀j = 0, . . . , N.

4.2.1 Das explizite Euler-Verfahren (Polygonzug-Verfahren)

Ist y : [a, b]→ Rn eine Lösung von (DGL)-(AB), so gilt

y(tj) = y(tj−1 + h) = y(tj−1) + y′(tj−1)h + O(h) = y(tj−1) + f (tj−1, y(tj−1))h + O(h).

Daraus ergibt sich das Verfahren{uj = uj−1 + f (tj−1, uj−1)h, j = 1, . . . , N,u0 = y0.

Beachte, dass es sich beim expliziten Euler-Verfahren um die Vorwärtsdifferenz handelt:

y′(tj−1) ≈y(tj)− y(tj−1)

h≈ uj − uj−1

h.

4.2.2 Das implizite Euler-Verfahren

Beim impliziten Euler-Verfahren erhalten wir

y(tj−1) = y(tj − h) = y(tj) + y′(tj)(−h) + O(h) = y(tj)− h f (tj, y(tj)) + O(h).

Das ist äquivalent zu

y(tj) = y(tj−1) + h f (tj, y(tj))− O(h).Daraus ergibt sich {

uj = uj−1 + h f (tj, uj), j = 1, . . . , N,u0 = y0.

Es handelt sich also um eine Rückwärtsdifferenz:

y′(tj) ≈y(tj)− y(tj−1)

h≈ uj − uj−1

h.

Im Gegensatz zum expliziten Euler-Verfahren ist das implizite Euler-Verfahren schwie-riger zu lösen, denn der gesuchte Vektor uj taucht sowohl links als auch rechts imArgument der Funktion f auf. Dieses Verfahren ist im Allgemeinen besser (stabiler)als die explizite Version.

85


4.2.3 Trapezmethode

Wir verwenden die Integralgleichung

y(t) = y0 +∫ t

af (s, y(s))ds ∀t ∈ [a, b].

Diese Integralgleichung liefert die folgende Darstellung

y(tj+1) = y0 +∫ tj+1

af (s, y(s))ds = y0 +

∫ t

af (s, y(s))ds +

∫ tj+1

tf (s, y(s))ds

= y(tj) +∫ tj+1

tf (s, y(s))ds ∀j = 0, . . . , N − 1.

Wird das Integral mit der Trapezregel approximiert, so ergibt sich

uj+1 = uj +h2[ f (tj, uj) + f (tj+1, uj+1)] ∀j = 0, . . . , N − 1.

4.2.4 Einfache Beispiele

Beispiel 4.6. Betrachte das Anfangswertproblem{y′(t) = −2ty2(t), t ∈ (0, 1),y(0) = 1.

Es ist leicht zu sehen, dass

y : [0, 1]→ R, y(t) =1

t2 + 1

die exakte Lösung ist (y ∈ C1([0, 1], R)). Wir verwenden die Schrittweite h = 0.1.Explizites Euler-Verfahren:

u0 = y0 = 1,u1 = u0 + h f (t0, u0) = 1 + 0.1 · 0 = 1,

u2 = u1 + h f (t1, u1) = 1 + 0.1 · (−2 · 0.1 · 12) = 0.98,...

Implizites Euler-Verfahren:

u0 = y0 = 1,

u1 = u0 + h f (t1, u1) = 1 + 0.1 · (−2 · 0.1 · u21) = 1− 0.02u2

1,

⇒ u21 + 50u1 = 500,

⇒ u1 = 0.98076211 (die andere Nullstelle kommt nicht in Betracht)u2 = u1 + h f (t2, u2)

⇒ u2 = 0.94503822,...

86


Die exakte Lösung lautet:

y(t0) = y0 = 1,

y(t1) = (0.12 + 1)−1 = 0.99009901,

y(t2) = (0.22 + 1)−1 = 0.96153846.

Beispiel 4.7. Betrachte das Anfangswertproblem{y′(t) = λy(t) ∀t ∈ (0, 1),y(0) = 1

mit λ ∈ R. Die exakte Lösung ist y(t) = eλt. Wir wählen die Schrittweite h = 0.1.Explizites Euler-Verfahren:

u0 = 1,u1 = u0 + h f (t0, u0) = u0 + hλu0 = 1 + λh,

u2 = u1 + h f (t1, u1) = 1 + λh + hλ(1 + λh) = (1 + λh)2,...

uj = (1 + λh)j.

Implizites Euler-Verfahren:

u0 = 1,

u1 = u0 + h f (t1, u1) = 1 + λhu1 ⇒ u1 =1

(1− λh),

u2 = u1 + h f (t2, u2) = (1− λh)−1 + λhu2 ⇒ u2 =1

(1− λh)2 ,

...

uj =1

(1− λh)j .

λ = 1, h = 0.1 λ = −21, h = 0.1

t Explizit Implizit Exakt Explizit Implizit Exakt

0 1.0 1.0 1.0 1.0 1.0 1.00.1 0.9 0.909 0.9048 −1.1 0.3225 0.12250.2 0.81 0.826 0.8187 1.21 0.104 0.015...1 0.349 0.385 0.3679 2.6 1.2 · 10−5 7.6 · 10−10

87

4.3 Theorie der expliziten Einschrittverfahren


Im Folgenden sei y ∈ C1([a, b], Rn) die eindeutige Lösung des Anfangswertproblems(DGL)-(AB): {

y′(t) = f (t, y(t)) ∀t ∈ [a, b],y(0) = y0.

Wir betrachten eine allgemeine Zerlegung (Diskretisierung) des Zeitintervalls [a, b] wiefolgt:

a = t0 < t1 < t2 < . . . < tN = b

mit der Schrittweite

hj = tj+1 − tj, j = 0, . . . , N − 1,

hmax = max0≤j≤N−1

hj.

Definition 4.8. Ein explizites Einschrittverfahren zur Approximation des Anfangswert-problems (DGL)-(AB) ist von der Gestalt{

uj+1 = uj + hj ϕ(tj, uj, hj), j = 0, . . . , N − 1,u0 = y0,

(EV)

mit einer Verfahrensfunktion

ϕ : [a, b]×Rn ×R+0 → Rn (R+

0 := {x ∈ R | x ≥ 0}).

Beispiel 4.9. Das explizite Euler-Verfahren{uj+1 = uj + hj f (tj, uj), j = 0, . . . , N − 1,u0 = y0.

ist ein explizites Einschrittverfahren mit der Verfahrensfunktion

ϕ(t, u, h) = f (t, u) ∀t ∈ [a, b], u ∈ Rn, h ∈ R+0 .

Bemerkung 4.10. Die Approximation uj+1 hängt nur von uj ab. Deshalb heißt dieseMethode explizites Einschrittverfahren.

Bemerkung 4.11. Das implizite Euler-Verfahren lässt sich nicht als ein explizites Ein-schrittverfahren auffassen.

Im nächsten Abschnitt untersuchen wir implizite Einschrittverfahren gemeinsam mitMehrschrittverfahren.

88


Definition 4.12 (Verfahrensfehler). Es sei ϕ : [a, b]×Rn ×R+0 → Rn eine Verfahrens-

funktion für das explizite Einschrittverfahren (EV). Dann heißt

η(t, h) = y(t) + hϕ(t, y(t), h)︸︷︷︸Verfahrensvorschrift

−y(t + h) für t ∈ [a, b] und h ∈ [0, b− t]

lokaler Fehler im Punkt (t + h, y(t + h)) bezüglich der Schrittweite h.

Definition 4.13 (Konsistenz). Das explizite Einschrittverfahren (EV) zur Lösung von(DGL)-(AB) besitzt die Konsistenzordnung p ≥ 1, falls für den lokalen Fehler dieUngleichung

‖η(t, h)‖2 ≤ Chp+1 ∀t ∈ [a, b], h ∈ [0, b− t]

mit einer von t und h unabhängigen Konstanten C > 0 erfüllt ist.

Die Konsistenzordnung ist entscheidend für die Konvergenz von (EV). Zusammen mitder Lipschitz-Annahme für die Verfahrensfunktion ϕ liefert die Konsistenzordnungdie Konvergenz mit p als Konvergenzgeschwindigkeit.Lipschitz-Annahme: Es existiere eine Konstante L > 0, so dass gilt

‖ϕ(t, u, h)− ϕ(t, v, h)‖2 ≤ L ‖u− v‖2 ∀u, v ∈ Rn, t ∈ [a, b], h ∈ [0, b− t].

Beachte, dass L unabhängig von u, t und h ist.

Satz 4.14 (Konvergenz des expliziten Einschrittverfahrens). Das explizite Einschrittverfah-ren besitze die Konsistenzordnung p ≥ 1, und die Verfahrensfunktion ϕ : [a, b]×Rn×R+

0 →Rn erfülle die Lipschitz-Annahme. Dann konvergiert (EV) gegen die Lösung y ∈ C1([a, b], Rn)des Anfangswertproblems (DGL)-(AB) mit der Konvergenzrate p. Genauer gilt

max0≤j≤N

∥∥uj − y(tj)∥∥

2 ≤ Chpmax

mit der Konstanten

C :=CL(eL(b−a) − 1).

Lemma 4.15. Für reelle Zahlen L > 0, ξ ≥ 0, hj > 0 und κ ≥ 0 sei

ξ j+1 ≤ (1 + Lhj)ξ j + hjκ ∀j = 0, . . . , N − 1

erfüllt. Dann gilt

ξ j ≤eLxj − 1

Lκ + eLxj ξ0 mit xj =

j−1

∑k=0

hk, x0 := 0, x1 := h0

für alle j = 0, . . . , N.

89


Beweis durch Induktion.

Induktionsanfang j = 0: Es istx0 = 0,

und daraus folgt

ξ0 =eLx0 − 1

L︸︷︷︸=0

κ︸︷︷︸≥0

+ eLx0︸︷︷︸=1

ξ0 = ξ0.

Induktionsannahme: Die Aussage gelte für alle j = 0, . . . , m mit m ∈ {0, . . . , N − 1}.

Dann gilt

ξm+1 ≤ (1 + Lhm)ξm + hmκ

≤ (1 + Lhm)

[eLxm − 1

Lκ + eLxm ξ0

]+ hmκ

=(1 + Lhm)eLxm − (1 + Lhm)

Lκ + (1 + Lhm)eLxm ξ0 + hmκ

=(1 + Lhm)eLxm − 1

Lκ + (1 + Lhm)eLxm ξ0

≤ eLhm eLxm − 1L

κ + eLhm eLxm ξ0

=eL(xm+hm) − 1

Lκ + eL(xm+hm)ξ0

=exm+1 − 1

Lκ + exm+1ξ0.

Dabei haben wir bei der letzten Abschät-zung verwendet, dass

1 + x ≤ ex

für alle x ∈ R gilt.

g(x) = 1 + x

f (x) = ex

90


Beweis des Satzes. Wir setzen

ej := uj − y(tj), j = 0, . . . , N − 1.

Laut Definition ist{uj+1 = uj + hj ϕ(tj, uj, hj), j = 0, . . . , N − 1,u0 = y0,

undη(tj, hj) = y(tj) + hj ϕ(tj, y(tj), hj)− y(tj + hj︸︷︷︸

tj+1

), j = 0, . . . , N − 1.

Somit gilt für jedes j = 0, . . . , N − 1:

ej+1 = uj+1 − y(tj+1)

= uj + hj ϕ(tj, uj, hj)− y(tj+1)

= uj − y(tj) + hj(ϕ(tj, uj, hj)− ϕ(tj, y(tj), hj)) + η(tj, hj).

Mit der Dreiecksungleichung ergibt sich nun∥∥ej+1∥∥

2 ≤∥∥uj − y(tj)

∥∥2 + hj

∥∥ϕ(tj, uj, hj)− ϕ(tj, y(tj), hj)∥∥

2 +∥∥η(tj, hj)

∥∥2 .

Die Konsistenzordnung und die Lipschitz-Annahme liefern∥∥ej+1∥∥

2 ≤∥∥ej∥∥

2 + hjL∥∥uj − y(tj)

∥∥2 + Chp+1

j

= (1 + Lhj)∥∥ej∥∥

2 + Chp+1j ∀j = 0, . . . , N − 1.

Mit hj ≤ hmax folgt∥∥ej+1∥∥

2︸︷︷︸=:ξ j+1

≤ (1 + Lhj)∥∥ej∥∥

2︸︷︷︸=:ξ j

+ Chpmax︸︷︷︸

=:κ

hj ∀j = 0, . . . , N − 1

und das vorherige Lemma liefert

∥∥ej∥∥

2 ≤(

eLxj − 1L

)Chp

max + eLxj ξ0.

Insgesamt folgt

∥∥ej∥∥

2 ≤(

eL(b−a) − 1L

)C︸︷︷︸

=:C

hpmax ∀j = 0, . . . , N − 1,

91


denn e0 = u0 − y(0) = u0 − y0 = 0 und

xj =j−1

∑k=0

hk = hj−1 + hj−2 + . . . + h0 = (tj − tj−1) + (tj−1 − tj−2) + . . . + (t1 − t0)

= tj − t0

≤ b− a.

4.3.1 Explizites Einschrittverfahren der Konsistenzordnung p = 1

Unter milden Voraussetzungen hat das explizite Euler-Verfahren die Konsistenzord-nung p = 1. Zur Erinnerung ist das explizite Euler-Verfahren wie folgt definiert:{

uj+1 = uj + hj f (tj, uj), j = 1, . . . , N − 1,u0 = y0.

Satz 4.16. Erfüllt die Lösung des Anfangswertproblems (DGL)-(AB) die Regularität

y ∈ C2([a, b], Rn),

so besitzt das explizite Euler-Verfahren die Konsistenzordnung p = 1, das heißt es existiert einC > 0 mit

‖η(t, h)‖2 ≤ Ch2

für alle t ∈ [a, b] und h ∈ [0, b− t].

Beweis. Da y ∈ C2([a, b], Rn) ist, so liefert der Satz von Taylor für jedes t ∈ [a, b] undh ∈ [0, b− t]:

yi(t + h) = yi(t) + y′i(t)h + y′′i (ξi)h2

2∀i = 1, . . . , n

mit Zwischenstellen ξi ∈ [a, b] für alle i = 1, . . . , n. Dies ist äquivalent zu

y(t + h) = y(t) + y′(t)h + (y′′i (ξi))ni=1

h2

2. (4.1)

Somit ergibt sich für jeden lokalen Verfahrensfehler:

η(t, h) = y(t) + hϕ(t, y(t), h)− y(t + h)Euler= y(t) + h f (t, y(t))− y(t + h)

(DGL)= y(t) + hy′(t)− y(t + h)

(4.1)= y(t) + hy′(t)− y(t)− y′(t)h− (y′′(ξ))n

i=1h2

2

= −(y′′(ξi))ni=1

h2

2.

92


Insgesamt folgt nun

‖η(t, h)‖2 ≤ Ch2 ∀t ∈ [a, b], h ∈ [0, b− t]

mitC =

12

maxa≤t≤b

∥∥y′′(t)∥∥

∞ .

Korollar 4.17. Es existiere eine Konstante L > 0, so dass gilt

‖ f (t, u)− f (t, v)‖2 ≤ L ‖u− v‖2 ∀t ∈ [a, b], u, v ∈ Rn.

Ferner erfülle die Lösung des Anfangswertproblems (DGL)-(AB) die Regularität

y ∈ C2([a, b], Rn).

Dann konvergiert das explizite Euler-Verfahren mit der Konvergenzrate p = 1. Genauer gilt

max0≤j≤N

∥∥uj − y(tj)∥∥

2 ≤ Chmax

mit

C =CL(eL(b−a) − 1) =

12L

maxa≤t≤b

∥∥y′′(t)∥∥

∞ (eL(b−a) − 1).

Beweis. Gemäß dem Satz zur Konvergenz des expliziten Einschrittverfahrens impli-zieren die Lipschitz-Annahme und die Konsistenzordnung p = 1 die Konvergenz mitRate p.

4.3.2 Explizite Einschrittverfahren höherer Konsistenzordnung

Unter Differenzierbarkeitsannahme lassen sich explizite Einschrittverfahren mit einerhöheren Konsistenzordnung p > 1 konstruieren.

(i) Das modifizierte Euler-Verfahren:Hier verwenden wir die Verfahrensfunktion

ϕ(t, u, h) := f (t +h2

, u +h2

f (t, u)) ∀t ∈ [a, b], u ∈ Rn, h ∈ [0, b− t].

Die Verfahrensvorschrift lautetu0 = y0,

uj+ 12= uj +

hj2 f (tj, uj), ∀j = 0, . . . , N − 1,

uj+1 = uj + hj f (tj +hj2 , uj+ 1

2), ∀j = 0, . . . , N − 1.

Unter gewisser Differenzierbarkeitsannahme hat dieses Verfahren die Konsisten-zordnung p = 2.

93

4.4 Mehrschrittverfahren

(ii) Das klassische Runge-Kutta-Verfahren: Die Verfahrensfunktion lautet

ϕ(t, u, h) =16(K1 + 2K2 + 2K3 + K4) ∀t ∈ [a, b], u ∈ Rn, h ∈ [0, b− t]

mit

K1 = f (t, u),

K2 = f (t +h2

, u +h2

K1),

K3 = f (t +h2

, u +h2

K2),

K4 = f (t +h2

, u + hK3).

Unter gewisser Differenzierbarkeitsannahme hat das klassische Runge-Kutta-Verfahren die Konsistenzordnung p = 4.


4.4.1 Definition des Mehrschrittverfahrens

Wir betrachten zur Vereinfachung eine äquidistante Zerlegung des Intervalls [a, b]:a = t0 < t1 < . . . < tN = b,tj = a + jh, j = 0, . . . , N,h = b−a

N .

Definition 4.18. Ein m-Schrittverfahren, m ∈ N, zur numerischen Lösung des An-fangswertproblems {

y′(t) = f (t, y(t)), t ∈ [a, b],y(0) = y0

ist von der Form:m

∑k=0

akuj+k = hϕ(tj, uj, uj+1, . . . , uj+m, h) ∀j = 0, . . . , N −m (MV)

mit Koeffizienten ak ∈ R, am 6= 0, und einer Verfahrensfunktion

ϕ : [a, b]× (Rn)m+1 ×R+0 → Rn.

Ein m-Schrittverfahren wird im allgemeinen als Mehrschrittverfahren bezeichnet.

Bemerkung 4.19. Das m-Schrittverfahren benötigt Startwerte u0, . . . , um−1 ∈ Rn. Übli-cherweise setzt man u0 = y0 und bestimmt um−1, . . . , u1 durch ein anderes Verfahren(z. B. Einschrittverfahren).

94


Beispiel 4.20. Das implizite Euler-Verfahren{uj+1 = uj + h f (tj+1, uj+1), j = 0, . . . , N − 1,u0 = y0

ist ein 1-Schrittverfahren (Mehrschrittverfahren). Die Verfahrensfunktion lautet

ϕ(tj, uj, uj+1, h) = f (tj + h, uj+1)

und die Koeffizienten sinda0 = −1, am = 1.

Das implizite Euler-Verfahren ist nichts anderes als

1

∑k=0

akuj+k = hϕ(tj, uj, uj+1, h) ∀j = 0, . . . , N − 1.

Beispiel 4.21. Die Mittelpunktregel

uj+2 = uj + 2h f (tj+1, uj+1) ∀j = 0, . . . , N − 2

ist ein 2-Schrittverfahren (Mehrschrittverfahren) mit der Verfahrensfunktion

ϕ(tj, uj, uj+1, uj+2, h) = 2 f (tj + h, uj+1)

und Koeffizientena0 = −1, a1 = 0, a2 = 1.

Definition 4.22 (lokaler Verfahrensfehler). Für ein Mehrschrittverfahren (MV) zurLösung des Anfangswertproblems (DGL)-(AB) bezeichnet

η(t, h) =m

∑k=0

aky(t + kh)− hϕ(t, y(t), y(t + h), . . . , y(t + mh), h)

für t ∈ [a, b], h ∈ [0, b−tm ] den lokalen Verfahrensfehler im Punkt (t, y(t)) der Schrittweite

h.

Definition 4.23 (Konsistenzordnung). Ein Mehrschrittverfahren (MV) besitzt die Kon-sistenzordnung p ≥ 1, falls es Konstanten C > 0 und h > 0 gibt, so dass gilt

‖η(t, h)‖2 ≤ Chp+1, t ∈ [a, b], h ∈[

0, min{

h,b− t

m

}].

Lipschitz-Annahme: Es existiere eine Konstante L > 0, so dass gilt∥∥∥ϕ(t, u0, u1, . . . , um, h)− ϕ(t, v0, v1, . . . , vm, h)∥∥∥

2≤ L

(m

∑k=0

∥∥∥uk − vk∥∥∥

2

)für alle t ∈ [a, b], u0, . . . , um, v0, . . . , vm ∈ Rn, h ∈ [0, b− t].Bei expliziten Einschrittverfahren sind die Konsistenzordnung p ≥ 1 und die Lipschitz-Annahme hinreichend für die Konvergenz mit Rate p. Beim Mehrschrittverfahrenbraucht man eine weitere Voraussetzung, und zwar die sogenannte Nullstabilität.

95


Definition 4.24 (Nullstabilität). Das m-Schrittverfahren (MV) heißt nullstabil, falls dasPolynom

p(x) := a0 + a1x + . . . + amxm

der Bedingung{p(x) = 0 ⇒ |x| ≤ 1,p(x) = 0 und |x| = 1 ⇒ x ist einfache Nullstelle von p

genügt.

4.4.2 Konvergenzaussage

Satz 4.25. Ein m-Schrittverfahren (MV) für das Anfangswertproblem (DGL)-(AB) sei nullsta-bil und die Verfahrensfunktion erfülle die Lipschitz-Annahme. Dann existieren zwei KonstantenK > 0 und h > 0, so dass gilt

max0≤j≤N

∥∥uj − y(tj)∥∥

2 ≤ K

max0≤k≤m−1

‖uk − y(tk)‖2︸︷︷︸Fehler der Startwerte

+1h

maxt∈[a, b−mh]

‖η(t, h)‖2

∀h ∈ (0, h).

Beweis. Wir zeigen die Aussage o.B.d.A. für am = 1 (sonst teilen wir (MV) durcham 6= 0) und n = 1. Wir setzen

ej := uj − y(tj), j = 0, . . . , N,

ηj := η(tj, h), j = 0, . . . , N −m.

Laut Definition istm

∑k=0

akuj+k = hϕ(tj, uj, . . . , uj+m, h), j = 0, . . . , N −m,

m

∑k=0

aky(tj + kh) = hϕ(tj, y(tj), . . . , y(tj + mh, h) + η(tj, h), j = 0, . . . , N −m.

Folglich giltm

∑k=0

akej+k = h(ϕ(tj, uj, . . . , uj+m, h)− ϕ(tj, y(tj), . . . , y(tj + mh), h))− η(tj, h)

=: δj − ηj, j = 0, . . . , N −m.

Diese Gleichung lässt sich wie folgt darstellen: Sei j ∈ {0, . . . , N −m} fest, so gilt

ej+1...

ej+m

︸︷︷︸=:Ej+1

=

0 1

0 1. . . . . .

0 1−a0 · · · −am−2 −am−1

︸︷︷︸

=:A

ej...

ej+m−1

︸︷︷︸

=:Ej

+

0...0

δj − ηj

︸︷︷︸

=:Fj

(4.2)

96


mit der Matrix A ∈ Rm×m und den Vektoren Ej, Ej+1, Fj ∈ Rm. Mittels vollständigerInduktion zeigen wir:

Ej = AjE0 +j−1

∑k=0

Aj−1−kFk, j = 0, . . . , N −m + 1. (4.3)

Induktionsanfang j = 0: E0 = IE0 + 0 = E0.

Induktionsannahme: Die Aussage gelte für j ∈ {0, . . . , N −m}.Mit (4.2) folgt

Ej+1 = AEj + Fj = A(AjE0 +j−1

∑k=0

Aj−1−kFk) + Fj

= Aj+1E0 +j−1

∑k=0

Aj−kFk + Fj

= Aj+1E0 +j

∑k=0

Aj−kFk

und daraus folgt die Aussage (4.3).Mit der Nullstabilität zeigen wir später, dass eine Konstante C > 0 existiert, so dassgilt ∥∥∥Ak

∥∥∥∞≤ C ∀k ∈N.

Die Beschränktheit der Folge {∥∥Ak

∥∥∞}∞

k=1 ⊂ R+0 zusammen mit (4.3) liefert

∥∥Ej∥∥

∞ ≤∥∥∥Aj

∥∥∥∞‖E0‖∞ +

j−1

∑k=0

∥∥∥Aj−1−k∥∥∥

∞‖Fk‖∞

≤ C

(‖E0‖∞ +

j−1

∑k=0‖Fk‖∞

), j = 0, . . . , N −m + 1. (4.4)

Laut Definition ist

‖Fk‖∞ = |δk − ηk| ≤ hLm

∑l=0|uk+l − y(tk+l)|+ |ηk|

≤ hLm

∑l=0|ek+l|+ max

0≤k≤N−m|ηk|.

Andererseits istm

∑l=0|ek+l| = |ek|︸︷︷︸

≤‖Ek‖∞

+ |ek+1|︸︷︷︸≤‖Ek‖∞

+ . . . + |ek+m−1|︸︷︷︸≤‖Ek‖∞

+ |ek+m|︸︷︷︸≤‖Ek+1‖∞

≤ m ‖Ek‖∞ + ‖Ek+1‖∞ .

97


Insgesamt gilt

‖Fk‖∞ ≤ hL(m ‖Ek‖∞ + ‖Ek+1‖∞) + max0≤k≤N−m

|ηk| ∀k = 0, . . . , N −m.

Somit haben wirj−1

∑k=0‖Fk‖∞ ≤ h L(m + 1)︸︷︷︸

=:c1

(j−1

∑k=0‖Ek‖∞

)+ hL

∥∥Ej∥∥

∞ + j max0≤k≤N−m

|ηk|

≤ hc1

(j−1

∑k=0‖Ek‖∞

)+ hL

∥∥Ej∥∥

∞ + N max0≤k≤N−m

|ηk| ∀j = 0, . . . , N −m + 1

und mit (4.4) folgt

∥∥Ej∥∥

∞ ≤ C

(‖E0‖∞ + N max

0≤k≤N−m|ηk|+ hc1

j−1

∑k=0‖Ek‖∞

)+ ChL

∥∥Ej∥∥

∞ .

Ist h <1

CL, so folgt

(1− ChL)︸︷︷︸>0

∥∥Ej∥∥

∞ ≤ C

(‖E0‖∞ + N max


j−1

∑k=0‖Ek‖∞

)

und daraus ergibt sich

∥∥Ej∥∥

∞ ≤C

1− ChL

(‖E0‖∞ + N max


j−1

∑k=0‖Ek‖∞

).

Wir verwenden nun die diskrete Version des Lemmas von Gronwall:Für reelle Zahlen v0, . . . , vr ∈ R, positive reelle Zahlen h0, . . . , hr−1 ∈ R+, und α, β ≥ 0seien |v0| ≤ α, |vj| ≤ α + β ∑

j−1k=0 hk|vk| für alle j = 1, . . . , r. Dann ist

|vj| ≤ α exp

(β

j−1

∑k=0

hk

)∀j = 0, . . . , r.

Das Lemma von Gronwall liefert dann∥∥Ej∥∥

∞ ≤C

1− ChL

(‖E0‖∞ + N max

0≤k≤N−m|ηk|)

exp(

Cc1

1− ChLhj)

für alle j = 0, . . . , N −m + 1 und daraus folgt∥∥Ej∥∥

∞ ≤C

1− ChLexp

(Cc1

1− ChLhj)(

max0≤k≤m−1

|uk − y(tk)|+b− a

hmax

0≤k≤N−m|ηk|)

≤ C1− ChL

exp(

Cc1

1− ChLb− a

NN)·

·max{1, b− a}(

max0≤k≤m−1

|uk − y(tk)|+1h

maxt∈[a, b−mh]

|η(t, h)|)

,

98


denntN−m = a + (N −m)h = a + Nh−mh = a + b− a−mh = b−mh.

Diese Aussage gilt für jedes h <1

CL. Wählen wir nun ein festes h <

1CL

, so folgt

∥∥Ej∥∥

∞ ≤ K(

max0≤k≤m−1

|uk − y(tk)|+ maxt∈[a, b−mh]

|η(t, h)|)

für alle h ∈ (0, h) und für alle j = 0, . . . , N −m + 1 mit

K :=C

1− ChLexp

(Cc1(b− a)

1− ChL

)max{1, b− a}.

4.4.3 Lemma von Gronwall

Im Beweis des Konvergenzsatzes haben wir das Lemma von Gronwall verwendet. DasLemma von Gronwall ist in der Tat ein überaus wichtiges Werkzeug zur Untersuchungvon partiellen Differentialgleichungen, insbesondere von Evolutionsgleichungen.Lemma von Gronwall in der Integraldarstellung. Es seien α ∈ R, β ∈ R+. Ferner seif : [0, T]→ R eine Riemann-integrierbare Funktion mit

f (t) ≤ α + β∫ t

0f (s)ds ∀t ∈ [0, T].

Dann giltf (t) ≤ α exp(βt) ∀t ∈ [0, T].

Beweis. Wir definierenM := sup

t∈[0,T]f (t) < ∞,

da f : [0, T] → R laut Annahme Riemann-integrierbar ist, also ist f insbesonderebeschränkt. Mittels vollständiger Induktion zeigen wir:

f (t) ≤ α

(n

∑j=0

(βt)j

j!

)+ M

(βt)n+1

(n + 1)!∀t ∈ [0, T] ∀n ∈N∪ {0}. (4.5)

Induktionsanfang n = 0: Es gilt laut Voraussetzung

f (t) ≤ α + β∫ t

0f (s)ds ≤ α + β

∫ t

0M ds

= α + βM∫ t

0ds

= α + Mβt ∀t ∈ [0, T].

99


Induktionsannahme: Die Aussage (4.5) gelte für n− 1, mit n ∈N.

Dann gilt für t ∈ [0, T]:

f (t) ≤ α + β∫ t

0f (s)ds

≤ α + β

(α

n−1

∑j=0

βj

j!

∫ t

0sj ds + M

βn

n!

∫ t

0sn ds

)

= α + β

(α

n−1

∑j=0

βj

j!1

j + 1tj+1 + M

βn

n!1

n + 1tn+1

)

= α + α

(n−1

∑j=0

(βt)j+1

(j + 1)!

)+ M

(βt)n+1

(n + 1)!

= α + α

(n

∑j=1

(βt)j

j!

)+ M

(βt)n+1

(n + 1)!

= α

(n

∑j=0

(βt)j

j!

)+ M

(βt)n+1

(n + 1)!

und daraus folgt die Behauptung (4.5). Der Übergang zum Grenzwert n→ ∞ in (4.5)liefert

f (t) ≤ limn→∞

(α

(n

∑j=0

(βt)j

j!

)+ M

(βt)n+1

(n + 1)!

)= α exp(βt).

Lemma 4.26 (Diskrete Version des Lemmas von Gronwall). Für reelle Zahlen v0, . . . , vr ∈R, positive reelle Zahlen h0, . . . , hr−1 ∈ R+, und α, β ≥ 0 seien

|v0| ≤ α, |vj| ≤ α + βj−1

∑k=0

hk|vk| ∀j = 0, . . . , r.

Dann gilt

|vj| ≤ α exp

(β

j−1

∑k=0

hk

)∀j = 0, . . . , r.

Beweis. Für eine Menge M ⊂ [0, T] definieren wir die charakteristische Funktion

χM(t) =

{1, falls t ∈ M,0, falls t /∈ M.

100


Wir setzen

x0 := 0,

xj :=j−1

∑k=0

hk, j = 0, . . . , r,

T := xr.

Wir definieren die folgende Treppenfunktion

f : [0, T]→ R, f (t) =r−1

∑j=0

χ[xj,xj+1)(t)|vj|+ χ{xr}(t)|vr|.

Für jedes k ∈ {0, . . . , r− 1} gilt∫ xk+1

xk

f (s)ds =∫ xk+1

xk

1|vk|ds = |vk|(xk+1 − xk) = |vk|hk. (4.6)

Außerdem gibt es zu jedem t ∈ [0, T] ein j ∈ {0, . . . , r− 1} mit

t ∈ [xj, xj+1)

oder j = r mit t = xr = T. Demzufolge gilt für jedes t ∈ [0, T]:

f (t) = |vj| für ein j ∈ {0, . . . , r}

≤ α + βj−1

∑k=0

∫ xk+1

xk

f (s)ds

= α + β

(∫ x1

x0

f (s)ds +∫ x2

x1

f (s)ds + . . . +∫ xj

xj−1

f (s)ds

)= α + β

∫ xj

0f (s)ds

≤ α + β∫ t

0f (s)ds.

Insgesamt gilt also

f (t) ≤ α + β∫ t

0f (s)ds ∀t ∈ [0, T].

Mit dem Lemma von Gronwall folgt nun

f (t) ≤ α exp(βt) ∀t ∈ [0, T]

und mit t = xj folgt schließlich

|vj| = f (xj) ≤ α exp(βxj) = α exp

(β

j−1

∑k=0

hk

)∀j = 0, . . . , r.

101


4.4.4 Beschränktheit der Folge {∥∥Ak

∥∥∞}∞

k=0

Im Konvergenzsatz haben wir behauptet, dass für die Matrix

A =

0 1

0 1. . . . . .

0 1−a0 · · · −am−2 −am−1

∈ Rm×m

die Folge {∥∥Ak

∥∥∞}∞

k=0 ⊂ R+0 beschränkt ist. Wir wollen diese Aussage nun beweisen.

Dazu ist die Nullstabilität des Mehrschrittverfahrens (MV) hinreichend.

Lemma 4.27. Das m-Schrittverfahren (MV) (o.B.d.A. am = 1) sei nullstabil, das heißt dasPolynom

p(x) = a0 + a1x + . . . + am︸︷︷︸=1

xm

erfülle die Bedingung

{p(x) = 0 ⇒ |x| ≤ 1,p(x) = 0 und |x| = 1 ⇒ x ist einfache Nullstelle von p.

Dann gilt für alle Eigenwerte der Matrix A

{|λk| ≤ 1 ∀k = 1, . . . , m,|λk| = 1 ⇒ σ(λk) = 1.

Beweis. Es genügt zu zeigen:

det(λI − A) = PA(λ) = p(λ).

102


Laut Definition ist

det(λI − A)

= det

λ −1

λ −1. . . . . .

λ −1a0 · · · am−2 λ + am−1

= a0(−1)m+1 det

−1λ −1

. . . . . .λ −1

+ a1(−1)m+2 det

λ

−1

λ. . .. . . . . .

λ −1

+ a2(−1)m+3 det

λ −1λ

−1

λ. . .. . . . . .

λ −1

+ . . .+

+ (λ + am−1)(−1)m+m det

λ −1

. . . . . .. . . −1

λ

= a0(−1)m+1(−1)m−1 + a1(−1)m+2λ(−1)m−2 + a2(−1)m+3λ2(−1)m−3 + . . .+

+ (λ + am−1)(−1)m+mλm−1

= (−1)2m(a0 + a1λ + a2λ2 + . . . + am−1λm−1 + λm) = p(λ).

Lemma 4.28. Das m-Schrittverfahren mit o.B.d.A. am = 1 sei nullstabil. Dann gibt es eineKonstante C > 0, so dass gilt ∥∥∥Ak

∥∥∥∞≤ C ∀k = 0, 1, 2, . . . .

Dann ist die Folge {∥∥Ak

∥∥∞}∞

k=0 insbesondere beschränkt.

Beweis. Wir verwenden die Jordansche Normalform: Es existiere eine reguläre Matrix

103


X ∈ Cm×m mit

X−1AX = J =

J(λ1) 0. . .

0 J(λk)

mit paarweise verschiedenen Eigenwerten λ1, . . . , λk sowie den Jordan-Blöcken

J(λl) =

λl 1

. . . . . .. . . 1

λl

∈ Cml×ml .

Im vorherigen Lemma haben wir gezeigt:{|λk| ≤ 1 ∀k = 1, . . . , m,|λk| = 1 ⇒ σ(λk) = 1 ⇒ J(λl) = (λl) ∈ C1×1.

Wir wählen ε > 0 hinreichend klein, so dass für jedes l ∈ {1, . . . , k} mit

|λl| < 1

gilt, dass|λl|+ ε ≤ 1

ist. Wir definieren

J := D−1 JD mit D = diag(1, ε1, ε2, . . . , εm−1) ∈ Rm×m.

Somit haben wir

J =

J(λ1) 0. . .

0 J(λk)

,

mit

J(λl) =

λl ε 0

. . . . . .. . . ε

λl

, falls |λl| < 1,

J(λl) = (λl), falls |λl| = 1.

Demzufolge gilt‖ J‖∞ = max

1≤l≤k‖ J(λk)‖∞ ≤ 1,

104


denn

max1≤l≤k

‖ J(λl)‖∞ = ‖ J(λj)‖∞ =

{|λj|+ ε, falls |λl| < 1,|λj|, falls |λl| = 1,

wobei j der Index sei, in dem das Maximum angenommen wird. Folglich ist

‖ Jn‖∞ ≤ ‖ J‖∞ · ‖ J‖∞ · . . . · ‖ J‖∞︸︷︷︸n-mal

= ‖ J‖n∞ ≤ 1 ∀n ∈N.

Andererseits ist

X−1AX = J = DJD−1

⇒ A = (XD) J(XD)−1

⇒ AA = (XD) J(XD)−1(XD) J(XD)−1 = (XD) J2(XD)−1

...

⇒ An = (XD) Jn(XD)−1 ∀n ∈N.

Demzufolge ist

‖An‖∞ = ‖(XD) Jn(XD)−1‖∞ ≤ ‖XD‖∞‖ Jn‖∞‖(XD)−1‖∞

≤ ‖XD‖∞‖(XD)−1‖∞ =: C ∀n ∈N.

Somit ist die Konvergenzaussage von Abschnitt 4.4.2 vollständig bewiesen. Als Folge-rung erhalten wir das folgende Korollar:Korollar 4.29. Das m-Schrittverfahren (MV) sei nullstabil und besitze die Konsistenzordnungp ≥ 1. Ferner erfülle die Verfahrensfunktion ϕ die Lipschitz-Annahme. Existiert eine KonstanteC0 > 0, so dass für die Startwerte u0, . . . , um−1 gilt

max0≤j≤m−1

‖uj − y(tj)‖2 ≤ C0hp ∀h > 0,

dann existieren Konstanten K > 0 und h > 0, so dass gilt

max0≤j≤N

‖uj − y(tj)‖2 ≤ Khp ∀h ∈ (0, h).

Beweis. Die Nullstabilität und die Lipschitz-Annahme liefern zwei Konstanten K > 0und h > 0, so dass gilt

max0≤j≤N

∥∥uj − y(tj)∥∥

2 ≤ K[

max0≤k≤m−1

‖uk − y(tk)‖2 +1h

maxt∈[a, b−mh]

‖η(t, h)‖2

]∀h ∈ (0, h).

Die Annahme für die Startwerte und die Konsistenzordnung p ≥ 1 liefern

max0≤j≤N

∥∥uj − y(tj)∥∥

2 ≤ K(C0hp +1h

Chp+1) = Khp

mitK := K(C0 + C).

105


4.4.5 Adams-Verfahren

Wir betrachten in diesem Abschnitt das bekannte m-Schrittverfahren von Adams.Eine Grundlage hierzu ist die Integraldarstellung der Lösung y ∈ C1([a, b], Rn) desAnfangswertproblems (DGL)-(AB):

y(t) = y0 +∫ t

af (s, y(s))ds ∀t ∈ [a, b].

Hieraus ergibt sich

y(tj+m)− y(tj+m−1) = y0 +∫ tj+m

af (s, y(s))ds− y0 −

∫ tj+m−1

af (s, y(s))ds

=∫ tj+m

tj+m−1

f (s, y(s))ds.

Durch Ersetzen des Integranden durch geeignete Polynome p erhalten wir das Verfah-ren von Adams.

4.4.5.1 Adams-Bashfort-Verfahren

Wir erklären die Methode für m = 4. Wir betrachten die äquidistante Zerlegunga = t0 < t1 < . . . < tN = b,tj = a + jh, j = 0, . . . , N,h = b−a

N .

Sei j ∈ {0, . . . , N − 1}. Wir nehmen an, dass die Werte

f j := f (tj, uj), f j+1 := f (tj+1, uj+1),

f j+2 := f (tj+2, uj+2), f j+3 := f (tj+3, uj+3)

berechnet worden sind. Mit diesen vier Stützstellen soll das Integral∫ tj+4

tj+3

f (s, y(s))ds

mit dem Lagrangeschen Interpolationspolynom approximiert werden.

t

f

tj tj+1 tj+2 tj+3 tj+4

f j

f j+1

f j+2f j+3 Lagrangesche

Interpolationspolynom

106


Wir approximieren ∫ tj+4

tj+3

f (s, y(s))ds ≈∫ tj+4

tj+3

p(t)dt

mit

p(t) =3

∑k=0

f j+kLj+k(t).

Somit lautet das Verfahren von Adams-Bashfort für m = 4 wie folgt:

uj+4 − uj+3 =3

∑k=0

∫ tj+4

tj+3

f j+kLj+k(t)dt.

Die Integrale lassen sich explizit berechnen, zum Beispiel bei k = 0:

I0 =∫ tj+4

tj+3

(t− tj+3)(t− tj+2)(t− tj+1)

(tj − tj+3)(tj − tj+2)(tj − tj+1)dt

=∫ tj+4

tj+3

(t− tj+3)(t− tj+2)(t− tj+1)

(−3h)(−2h)(−h)dt.

Wir verwenden die Substitution

t = tj+3 + sh, dt = hds, s ∈ [0, 1],

und daraus erhalten wir

I0 = h∫ 1

0

(sh) · (s + 1)h · (s + 2)h(−3h)(−2h)(−h)

ds = −h∫ 1

0

s(s + 1)(s + 2)6

ds

− h6

∫ 1

0s3 + 3s2 + 2s ds

= −h6

(14+ 1 + 1

)= − 9

24h.

Analog berechnen sich I1, I2, I3. Insgesamt erhält man das „4-Schrittverfahren vonAdams-Bashfort“:

uj+4 = uj+3 +h

24(55 f j+3 − 59 f j+2 + 37 f j+1 − 9 f j) ∀j = 0, . . . , N − 4.

Analog leitet man das allgemeine m-Schrittverfahren von Adams-Bashfort her:

m = 1 : uj+1 = uj + h f j, j = 0, . . . , N − 1,

m = 2 : uj+2 = uj+1 +h2(3 f j+1 − f j), j = 0, . . . , N − 2,

m = 3 : uj+3 = uj+2 +h

12(23 f j+2 − 16 f j+1 + 5 f j), j = 0, . . . , N − 3,

und so weiter.Bemerkung 4.30. Für m = 1 ist das Adams-Bashfort-Verfahren nichts anderes als dasexplizite Euler-Verfahren.

107


4.4.5.2 Adams-Moulton-Verfahren

Bei dem Adams-Bashfort-Verfahren verwendet man den unbekannten Wert uj+mnicht. Somit sind Verfahren dieser Klasse explizit. Nun soll bei der Konstruktion desInterpolationspolynoms p des Adams-Moulton-Verfahrens der Wert

f j+m := f (tj+m, uj+m)

mit verwendet werden. Somit hat man bei m-Schrittverfahren von Adams-Moultonm + 1 Stützstellen (statt m bei Adams-Bashfort).

t

f

tj tj+1 tj+m−1 tj+m

f j

f j+1

f j+m−1f j+m

Adams-Bashfort pAB

Adams-Moulton pAM

Mit dem Interpolationspolynom

pAM(tj+k) = f j+k ∀k = 0, . . . , m

setzen wir

uj+m − uj+m−1 =∫ tj+m

tj+m−1

pAM(t)dt ∀j = 0, . . . , N −m.

Dieses Verfahren bezeichnen wir als m-Schrittverfahren von Adams-Moulton.

Beispiele 4.31.

m = 1: uj+1 = uj +h2 ( f j+1 + f j) ∀j = 0, . . . , N − 1.

m = 2: uj+2 = uj+1 +h

12(5 f j+2 + 8 f j+1 − f j) ∀j = 0, . . . , N − 2.

m = 3: uj+3 = uj+2 +h

24(9 f j+3 + 19 f j+2 − 5 f j+1 − f j) ∀j = 0, . . . , N − 3.

m = 4: uj+4 = uj+3 +h

720(251 f j+4 + 646 f j+3− 264 f j+2 + 106 f j+1− 19 f j) ∀j = 0, . . . , N−4.

108


4.4.6 BDF-Verfahren

Wir präsentieren das bekannte BDF-Verfahren zur numerischen Lösung des Anfangs-wertproblems (DGL)-(AB). Es handelt sich um ein implizites Verfahren der Art:


tj+m−1

pBDF(t)dt ∀j = 0, . . . , N −m,

mit dem Interpolationspolynom{pBDF(tj+k) = uj+k ∀k = 0, . . . , m,p′BDF(tj+m) = f (tj+m, uj+m).

t

u

tj tj+1 tj+2 tj+m−1 tj+m

uj

uj+1uj+2

uj+m−1uj+m

p′BDF(tj+m) = f j+m

pBDF

Das m-schrittige BDF-Verfahren lässt sich eindeutig wie folgt darstellen:

m

∑k=0

akuj+k = h f (tj+m, uj+m).

Beispiele 4.32.

m = 1: uj+1 − uj = h f (tj+1, uj+1) ∀j = 0, . . . , N − 1.

m = 2: 13(3uj+2 − 4uj+1 + uj) = h f (tj+2, uj+2) ∀j = 0, . . . , N − 2.

m = 3: 16(11uj+3 − 18uj+2 + 9uj+1 − 2uj) = h f (tj+3, uj+3) ∀j = 0, . . . , N − 3.

m = 4: 112(25uj+4− 48uj+3 + 36uj+2− 16uj+1 + 3uj) = h f (tj+4, uj+4) ∀j = 0, . . . , N−

4.

Bemerkung 4.33. BDF steht für „Backward Differentiation Formula“.

Fazit 4.34.Adams-Bashfort:


tj+m−1

pAB(t)dt

109


mitpAB(tj+k) = f j+k ∀k = 0, . . . , m− 1.

Adams-Moulton:uj+m − uj+m−1 =

∫ tj+m

tj+m−1

pAM(t)dt

mitpAM(tj+k) = f j+k ∀k = 0, . . . , m.

BDF-Verfahren:uj+m − uj+m−1 =

∫ tj+m

tj+m−1

pBDF(t)dt

mit {pBDF(tj+k) = uj+k ∀k = 0, . . . , m,p′BDF(tj+m) = f (tj+m, uj+m).

Bei m = 1 im Adams-Bashfort-Verfahren erhält man das explizite Euler-Verfahren,m = 1 im BDF-Verfahren liefert das implizite Euler-Verfahren.

110

Stichwortverzeichnis

A

Abbruchindex. . . . . . . . . . . . . . . . . . . . . . . 73Adams-Bashfort-Verfahren . . . . . . . . . 106Adams-Moulton-Verfahren. . . . . . . . .108Adams-Verfahren . . . . . . . . . . . . . . . . . . 106ähnlich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Ähnlichkeitstransformation . . . . . . . . . 35algebraische Vielfachheit . . . . . . . . . . . . 29Arnoldi-Prozess . . . . . . . . . . . . . . . . . . . . . 71

B

Bauer-Fike . . . . . . . . . . . . . . . . . . . . . . . . . . 46BDF-Verfahren . . . . . . . . . . . . . . . . . . . . . 109

C

charakteristische Polynom . . . . . . . . . . 29

D

defektiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44defektiver Eigenwert . . . . . . . . . . . . . . 44

diagonalisierbar . . . . . . . . . . . . . . . . . . . . . 44

E

Einbettung . . . . . . . . . . . . . . . . . . . . . . . . . . 28Explizites Einschrittverfahren . . . . . . . 88

Konsistenzordnung . . . . . . . . . . . . . . . 89Lokaler Verfahrensfehler . . . . . . . . . . 89

Explizites Euler-Verfahren. . . . . . . . . . .85

F

Fortsetzungsmethoden . . . . . . . . . . . . . . 20Klassische Fortsetzungsmethode . . 22

Methode der tangentialen Fortset-zung . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

G

Gauß-Newton-Verfahren . . . . . . . . . . . . 11Lokale Konvergenz . . . . . . . . . . . . . . . 15

Gedämpfte Newton-Verfahren . . . . . . . 5geometrische Vielfachheit . . . . . . . . . . . 29GMRES-Verfahren . . . . . . . . . . . . . . . . . . 71

H

hermitesch . . . . . . . . . . . . . . . . . . . . . . . . . . 52Hessebergmatrix . . . . . . . . . . . . . . . . . . . . 75Homotopiemethode . . . . . . . . . . . . . . . . . 28

I

Implizites Euler-Verfahren . . . . . . . . . . 85Innere-Punkte-Methode . . . . . . . . . . . . . 18invarianter Unterraum . . . . . . . . . . . . . . 33Inverse Vektoriteration . . . . . . . . . . . . . . 60

J

Jordan-Block . . . . . . . . . . . . . . . . . . . . . . . . 44Jordansche-Normalform . . . . . . . . . . . . 44

K

Kondition eines einfachen Eigenwerts52Konvergenztests . . . . . . . . . . . . . . . . . . . . . 4Krylov-Raum . . . . . . . . . . . . . . . . . . . . . . . 71

L

Lösungsstruktur . . . . . . . . . . . . . . . . . . . . 20Lemma von Gronwall . . . . . . . . . . . . . . . 99Levenberg-Marquardt-Verfahren . . . . 13

111

M

Mehrschrittverfahren. . . . . . . . . . . . . . . .94Konsistenzordnung . . . . . . . . . . . . . . . 95Lokaler Verfahrensfehler . . . . . . . . . . 95

Monotonietest . . . . . . . . . . . . . . . . . . . . . . . . 4Natürlicher Monotonietest . . . . . . . . . 4Standard-Monotonietest . . . . . . . . . . . 4

N

Newton-Korrektur . . . . . . . . . . . . . . . . . . . 4Nichtlineares Ausgleichsproblem. . . . .9normal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

P

Parameterabhängige nichtlineare Glei-chungssysteme . . . . . . . . . . . . . . . . . 18

Picard-Lindelöf . . . . . . . . . . . . . . . . . . . . . 84Potenzmethode . . . . . . . . . . . . . . . . . . . . . 58

Q

QR-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 62

QR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . 62

R

Rayleigh-Ritz-Quotienten . . . . . . . . . . . 52Runge-Kutta-Verfahren . . . . . . . . . . . . . 94

S

Schur-Zerlegung . . . . . . . . . . . . . . . . . . . . 39Reelle Schur-Form . . . . . . . . . . . . . . . . 44

Spektrum . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Störungssätze . . . . . . . . . . . . . . . . . . . . . . . 44

T

Trapezmethode . . . . . . . . . . . . . . . . . . . . . 86

V

Variationsprinzip von Courant und Fi-scher . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

Variationsprinzip von Rayleigh-Ritz . 54Vektoriterationen. . . . . . . . . . . . . . . . . . . .58

112

Documents

Numerische Mathematik 2 - uni-due.de · Kapitel 1 Nichtlineare Gleichungssysteme und Ausgleichsprobleme 1.1 Wiederholung zum Newton-Verfahren und Erweiterung In Numerik I haben wir