Skript zur Vorlesung - Fakultät für Mathematik · Skript zur Vorlesung Numerische Methoden für die Fachrichtungen Elektrotechnik, Meteorologie, Geodäsie und Geoinformatik Prof

Skript zur Vorlesung

Numerische Methoden

für die Fachrichtungen Elektrotechnik,Meteorologie, Geodäsie und Geoinformatik

Prof. Dr. Wolfgang ReichelInstitut für Analysis, Fakultät für Mathematik, KIT

Unter Verwendung von Skripten von

Prof. Dr. Wilhelm Niethammer

Institut für angewandte und numerische Mathematik, Fakultät für Mathematik, KIT

Gehalten von Dr. Semjon Wugalter

Institut für Analysis, Fakultät für Mathematik, KIT

Sommersemester 2017

Inhaltsverzeichnis

1 Direkte Verfahren 4

1.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Das Eliminationsverfahren von Gauß und die LR-Zerlegung . . . . . . . 6

1.3 Die Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.4 Die QR-Zerlegung (Ergänzung) . . . . . . . . . . . . . . . . . . . . . . 20

2 Eigenwertprobleme 29

2.1 Begriffe und Definitionen . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2 Die von-Mises Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3 Die inverse Iteration von Wielandt . . . . . . . . . . . . . . . . . . . . 33

2.4 Das LR-Verfahren und das QR-Verfahren für Eigenwertprobleme (Er-gänzung) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5 Die Reduktionsmethode von Householder aufHessenberg- bzw. Tridiagonalform (Ergänzung) . . . . . . . . . . . . . 48

3 Lineare Optimierung 54

4 Fehleranalyse 60

4.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

4.2 Fehlerfortpflanzung bei linearen Gleichungssystemen . . . . . . . . . . . 62

5 Newton-Verfahren 69

6 Quadratur 72

6.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.2 Die Trapezregel und die Rechteckregel . . . . . . . . . . . . . . . . . . 76

6.3 Interpolatorische Quadraturformeln . . . . . . . . . . . . . . . . . . . . 79

6.4 Newton-Côtes-Formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

7 Numerische Lösung von Anfangswertproblemen 84

7.1 Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

1

INHALTSVERZEICHNIS 2

7.2 Einführung in die Lösungstheorie von Anfangswertproblemen . . . . . . 88

7.3 Das Eulersche Polygonzugverfahren . . . . . . . . . . . . . . . . . . . . 89

7.4 Einschrittverfahren - Definition und grundlegende Eigenschaften . . . . 91

7.5 Die Methode des Taylorabgleichs . . . . . . . . . . . . . . . . . . . . . 92

7.6 Runge-Kutta-Verfahren der Konsistenzordnung 2 . . . . . . . . . . . . 92

7.7 Allgemeine Runge-Kutta-Verfahren . . . . . . . . . . . . . . . . . . . . 93

7.8 Konvergenz von Einschrittverfahren und eine Fehlerabschätzung . . . . 97

7.9 Abschließende Bemerkungen . . . . . . . . . . . . . . . . . . . . . . . . 98

8 Finite Differenzen für Randwertprobleme 99

8.1 Diskretisierung bei Randwertproblemen für gewöhnliche DGlen . . . . . 99

8.2 Diskretisierung bei Randwertproblemen für partiellen Differentialglei-chungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

9 Finite Elemente 107

9.1 Schwache Formulierung von Randwertaufgaben . . . . . . . . . . . . . 107

9.2 Ritz-Galerkin Approximation . . . . . . . . . . . . . . . . . . . . . . . 108

9.3 Umsetzung des Ritz-Galerkin-Verfahrens . . . . . . . . . . . . . . . . . 109

Vorwort

Dieses Skript entstand anläßlich der Vorlesung Numerische Mathematik für die Fach-richtung Elektroingenieurwesen im Sommersemester 2009 und wurde zum Sommerse-mester 2010 in seine erste Form gebracht. Als Vorlage dienten einerseits die Notizenvon Prof. Dr. Michael Plum und andererseits die in vielen Semestern erprobten und de-tailliert ausgearbeiteten Numerik-Skripten von Prof. Dr. Wilhelm Niethammer. BeidenKollegen danke ich sehr für die Zurverfügungstellung ihres Materials. Ebenso danke ichherzlich Frau Dipl.-Math. Susanne Pohlig, Frau Dipl.-Math. Dorothee Frey und HerrnDipl.-Math.techn. Rainer Mandel für die Arbeit, das Skript zu tippen, die Bilder zuerstellen und das Ergebnis Korrektur zu lesen.

Beginnend mit dem Sommersemester 2011 wurde das Skript neu angepasst. Insbeson-dere fielen aus der numerischen linearen Algebra (Kapitel 1 und Kapitel 2) die QR-Zerlegung und das QR-Verfahren heraus. Anstatt dessen beschränkte ich mich bei denEigenwertverfahren in Kapitel 2 auf die sogenannte Potenzmethode (bzw. Vektoritera-tion oder von-Mises-Iteration). Innerhalb des Skriptes finden sich die Verfahren zwarweiterhin — sie sind aber nicht Gegenstand der aktuellen Konzeption der Vorlesungund sind als sogenannte Ergänzungen kenntlich gemacht.

Durch diese Verkürzung wird in der Vorlesung Platz geschaffen für eine ausführlicherBehandlung der finite-Differenzen- und der finite-Elementeverfahren zur Lösung parti-eller Differentialgleichungen.

Karlsruhe, im Sommersemester 2014

Wolfgang Reichel

3

Kapitel 1

Direkte Verfahren zur Auflösunglinearer Gleichungssysteme

1.1 Einleitung

In diesem Paragraphen befassen wir uns mit direkten Methoden zur Auflösung linea-rer Gleichungssysteme. Als direkt (im Gegensatz zu iterativ) bezeichnet man diejenigenVerfahren, welche es im Prinzip gestatten, die Lösung eines linearen Gleichungssystemsin endlich vielen Schritten zu berechnen. Auf lineare Gleichungssyteme stößt man inder Praxis an vielen Stellen. Wir befassen uns hier nur mit einigen besonders typischenSituationen.

Elektrische Netzwerke lassen sich mit Hilfe der Kirchhoffschen Regeln beschreiben.(Ähnliche Zusammenhänge findet man auch in der Statik, etwa bei der Behandlungvon Fachwerken.) Wir betrachten ein Netzwerk mit Spannungsquellen und Widerstän-den des folgenden, in Abbildung 1.1 dargestellten Typs.

Es gelten folgende Regeln, die das Netzwerk vollständig beschreiben:

• Knotenregel : An jedem Knotenpunkt ist die Summe der zufließenden Strömegleich der der abfließenden Ströme, d.h. es gilt (unter Berücksichtigung der Strom-richtung): ∑

Ik = 0.

• Maschenregel : In jedem beliebig herausgegriffenen, in sich geschlossenen Strom-kreis („Masche“) ist die Summe der Spannungsabfälle in den einzelnen Zweigengleich der Summe der vorhandenen elektromotrischen Kräfte:∑

IkRk =∑

Uk.

Bei gegebenen Widerständen Rk und elektromotorischen Kräften Uk erhält man of-fensichtlich ein lineares Gleichungssystem für die Ströme Ik, wenn man alle Knotenund Maschen betrachtet. Möglicherweise ergeben sich dabei mehr Gleichungen als Un-bekannte; eventuell redundante (d.h. von anderen linear abhängige) Gleichungen sinddann zu streichen.

4

KAPITEL 1. DIREKTE VERFAHREN 5

A

D

B

C

I

I

I

I

I

I

U

R

R

RR

R

R

6

3

4 5

1

21

2

3

54

6

Abbildung 1.1: Schaltbild eines elektrischen Netzwerkes

Wir diskutieren exemplarisch das in Abbildung 1.1 dargestellte Netzwerk. Die Kirch-hoffschen Regeln ergeben je vier Knoten- und Maschengleichungen für die unbekanntenStröme I1, ..., I6. Es wird sich zeigen, dass von diesen acht Gleichungen zwei redundantsind. Im einzelnen gilt:

Knoten A : I1 −I3 +I4 = 0Knoten B : −I2 +I3 −I5 = 0Knoten C : −I1 +I2 +I6 = 0Knoten D : −I4 +I5 −I6 = 0

Maschen ADC: R1I1 −R4I4 +R6I6 = UMaschen BCD: R2I2 −R5I5 −R6I6 = 0Maschen ABD: R3I3 +R4I4 +R5I5 = 0Maschen ABC: R1I1 +R2I2 +R3I3 U

Wir stellen das System in Matrix-Vektor-Schreibweise dar:

1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1

0 0 0 −1 1 −1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0R1 R2 R3 0 0 0

I1

I2

I3

I4

I5

I6

=

0000U00U

Man erkennt, dass die Gleichungen z.T. voneinander linear abhängig sind, und zwar


die vierte von den drei ersten und die letzte von der fünften, sechsten und siebten.Diese linear abhängigen (redundanten) Gleichungen können wir streichen und erhaltenso das System (mit genauso vielen Gleichungen wie Unbekannten):

1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0

I1

I2

I3

I4

I5

I6

=

000U00

Wir notieren uns typische Eigenschaften dieses Gleichungssystems:

• Die Zeilen der Koeffizienten, welche von den Knotengleichungen herstammen,enthalten nur die Werte -1, 0, 1. Dies rührt von der topologischen Struktur desNetztes her; man erkennt, welche Knoten direkt miteinander verbunden sind. DieKnotengleichungen sind außerdem homogen.

• Die Maschengleichungen sind inhomogen, wobei die Inhomogenitäten von denelektromotorischen Kräften herstammen.

• Das System hat eine eindeutig bestimmte Lösung zu jeder rechten Seite. Mankann diesen Sachverhalt physikalisch „beweisen“: Wenn keine elektromotorischeKraft U anliegt, fließen keine Ströme Ik; also hat das homogene System nur dietriviale Lösung und jedes zugehörige System ist folglich auf genau eine Weiselösbar.

1.2 Das Eliminationsverfahren von Gauß und die LR-Zerlegung

In der linearen Algebra ist Ihnen das Prinzip des Gaußschen Eliminationsverfahrensmöglicherweise schon begegnet. Wir verwenden dieses Verfahren zur Lösung eines ge-gebenen linearen Gleichungssystems. Wir gehen aus von einem System

Ax = b;

dabei sei A eine gegebene reguläre Matrix mit m Zeilen und m Spalten, x der gesuchteLösungsvektor und b ein gegebener Vektor, also A ∈ Km×m, x ∈ Km, b ∈ Km, wobei Kden Körper der reellen oder der komplexen Zahlen bezeichne. A

x

=

b

.

Das Ziel des Eliminationsverfahrens von Gauß ist es, dieses Ausgangssystem so umzu-formen, dass die Komponenten des Lösungsvektors x sich leicht berechnen lassen. Man


versucht zu diesem Zweck, aus dem gegebenen System ein äquivalentes System (d.h.eines mit gleicher Lösungsmenge) aufzubauen, dessen Koeffizientenmatrix A Dreiecks-gestalt hat:

Ax = b ⇔ Ax = b

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗... . . . . . . ...... . . . . . . ...... . . . . . . ∗0 . . . . . . . . . 0 ∗

︸︷︷︸

A

∗............∗

︸︷︷︸

x

=

∗............∗

︸︷︷︸

b

(* bezeichnet Elemente, die möglicherweise von Null verschieden sind.)

Diese Reduktion auf Dreiecksgestalt kann man dadurch erreichen, dass man Gleichun-gen vertauscht und Vielfache von Gleichungen zu anderen Gleichungen addiert.

Aufgabe 1.1.Man bringe das Gleichungssystem 0 5 2

4 2 −16 −5 10

x1

x2

x3

=

61

36

auf Dreiecksgestalt und ermittle dann die Lösung.

Die Vertauschung und die Linearkombination von Gleichungen können wir durch Mul-tiplikation mit speziellen Matrizen erreichen. Zu diesem Zweck führen wir folgendeBezeichnungen ein.

Definition 1.2 (Permutationsmatrix).Eine Matrix P , die in jeder Zeile und jeder Spalte genau eine Eins und sonst nur Nullenenthält heißt Permutationsmatrix.

Wir listen einige Permutationsmatrizen auf:

m=1: [1]

m=2:[

1 00 1

],

[0 11 0

]

m=3:

1 0 00 1 00 0 1

, 1 0 0

0 0 10 1 0

, 0 1 0

1 0 00 0 1

, 0 1 0

0 0 11 0 0

, 0 0 1

1 0 00 1 0

, 0 0 1

0 1 01 0 0


Da die Spalten einer Permutationsmatrix durch Permutation der Spalten der Einheits-matrix entstehen, existieren genau m! Permutationsmatrizen in Km×m.Man macht sich nun leicht klar, dass

• Multiplikation einer Matrix von links mit einer Permutationsmatrix eine Permu-tation der Zeilen bewirkt,

• Multiplikation einer Matrix von rechts mit einer Permutationsmatrix eine Per-mutation der Spalten bewirkt.

Definition 1.3 (elementare untere Dreiecksmatrix).Eine Matrix des Typs

Λi =

1 0. . .

1

λi+1,i. . .

... . . .0 λm,i 0 1

m×m

die sich von der Einheitsmatrix nur in der i-ten Spalte unterhalb der Diagonalen un-terscheidet, bezeichnen wir als elementare untere Dreiecksmatrix.

Elementare untere Dreiecksmatrizen lassen sich auf einfache Weise invertieren. Diessollen Sie in der folgenden Aufgabe zeigen.

Aufgabe 1.4 (Die Inverse einer elementaren unteren Dreiecksmatrix).Man zeige: Für

Λi =

1 0. . .

1

λi+1,i. . .

... . . .0 λm,i 0 1

m×m

gilt

Λ−1i =

1 0. . .

1

−λi+1,i. . .

... . . .0 −λm,i 0 1

m×m

.

Wir kehren nun zur Ausgangssituation zurück und betrachten das System

Ax = b,


das in Komponentenschreibweise die folgende Gestalt hat:a11 a12 . . . . . . a1m

a21 a22 . . . . . . a2m...

......

......

...am1 am2 . . . . . . amm

x1.........xm

=

b1.........bm

Dieses System formen wir in einem rekursiven Prozess um. Wir setzten dabei zunächst

A(1) := A, b(1) := b,

wobei A invertierbar sei. Dann existiert in der ersten Spalte von A(1) ein von Nullverschiedenes Element a(1)

k1 , 1 ≤ k ≤ m. Durch Vertauschung der ersten mit der k-tenZeile erreichen wir, dass in der Position (1, 1) ein von Null verschiedenes Element steht.Diesen Vertauschungsprozess leistet die Linksmultiplikation mit der Permutationsma-trix

P1 =

0 . . . . . . 0 1... 1 0 0... . . . ... O0 0 1

...1 0 . . . . . . 0 . . . . . . . . . . . .

... 1 0

O ... . . .... . . .... 0 1

← k.

↑k

(Ist k = 1, so hat man P1 = E =Einheitsmatrix zu wählen.) (O steht hier und imFolgenden für die Nullmatrix.)

Für

A(1) := P1A(1), b(1) := P1b

(1)

gilt alsoa

(1)11 6= 0.

Jetzt adieren wir zur zweiten Zeile das − a(1)21

a(1)11

-fache der ersten,..., allgemein zur k-ten

Zeile das − a(1)k1

a(1)11

-fache der ersten Zeile, k = 2, ...,m. Dann stehen in der ersten Spalte


unterhalb der Diagonalen nur Nullen:a

(1)11 a

(1)12 . . . . . . a

(1)1m

0 ∗ . . . . . . ∗...

......

......

...0 ∗ . . . . . . ∗

x1.........xm

=

b

(1)1

∗......∗

.

Diese (m− 1)-malige Linearkombination lässt sich aber gerade als Linksmultiplikationmit der elementaren unteren Dreicksmatrix

L1 :=

1 0 . . . . . . 0−l21 1 0... . . .... . . .−lm1 0 1

interpretieren, wobei

lk1 :=a

(1)k1

a(1)11

, k = 2, ...,m

gesetzt wurde.Aus

A(1)x = b(1)

erhalten wir also

L1P1A(1)x = L1P1b

(1)

Wir setzen abkürzend

A(2) := L1P1A(1), b(2) := L1P1b

(1).

Dann hat A(2) die gewünschten Nullen in den Positionen (k, 1), k = 2, ...,m. Dabeiist das ursprüngliche Gleichungssystem Ax = b äquivalent zum modifizierten SystemA(2)x = b(2).

Auf A(2) wendet man nun einen entsprechenden Eliminationsprozess an, der die ersteSpalte festlässt und die zweite Spalte unterhalb der Diagonalen annulliert. Dies istmöglich, da A als invertierbar vorausgesetzt wurde. Rekursive Fortführung liefert in


m− 1 Schritten ein äquivalentes Gleichungssystem in Dreiecksform:

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗0 0 ∗ . . . . . . ∗... . . . . . . ...... 0

. . . . . . ...0 . . . . . . . . . 0 ∗

︸︷︷︸

A(m)

x1

x2

x3......

xm

︸︷︷︸

x

=

∗∗∗......∗

︸︷︷︸b(m)

.

Hieraus kann die Lösung x, wie am Ende dieses Paragraphen beschrieben, durch „Rücks-ubstitution“ berechnet werden.

Bemerkung 1.5 (Spaltenpivotisierung).Man beachte, dass die Regularität von A nicht ausreicht, in jedem Schritt das Nicht-verschwinden des Diagonalelements zu sichern.

triviales Beispiel:[

0 11 0

]Man muss also eventuell Gleichungen vertauschen, um ein nichtverschwindendes Dia-gonalelement (Pivot-Element, von engl. pivot: Türangel, Drehpunkt) zu erhalten. Eserweist sich als besonders günstg, wenn man möglichst betragsgroße Pivot-Elementewählt, da dann bei der Division zur Bildung der lνµ möglichst betragsgroße Nennerentstehen. Es empfiehlt sich deshalb in jedem Schritt eine Spalten-Pivot-Suche durch-zuführen, die darin besteht, dass man in der Spalte, die gerade dem Eliminationsprozessunterworfen wird, ein betragsgrößtes Element unterhalb der Diagonalen (einschließlichdes Diagonalelements) als Pivot-Element wählt.

Wir fassen unser Vorgehen algorithmisch.

Algorithmus 1.6 (Gauß-Eliminationsverfahren mit Spaltenpivotisierung).Es sei

A(1) = (a(1)ik ) := A = (aik)i,k=1,...,m,

A invertierbar,b(1) = (b

(1)i ) := b = (bi)i=1,...m.

Für ν = 1, ..,m− 1 bilde man A(ν+1) = (a(ν+1)ik )i,k=1,....m auf folgende Weise aus A(ν):

Zunächst bestimmt man ein Pivot-Element a(ν)µν , µ ∈ ν, ...,m, in der ν-ten Spalte

gemäß|a(ν)µν | = max

ν≤i≤m|a(ν)iν |.

Durch Vertauschung der ν-ten mit der µ-ten Gleichung des Systems

A(ν)x = b(ν)

erhält man das System


A(ν)x = b(ν)

wobeia(ν)νν 6= 0

ist.Anschließend werden die Elemente der ν-ten Spalte unterhalb der Diagonalen mit Hilfeder folgenden Transformationsformel eliminiert:Für i = ν + 1, ν + 2, ...,m setze:

liν :=a

(ν)iν

a(ν)νν

,

a(ν+1)iν := 0,

a(ν+1)ik := a

(ν)ik − liν a

(ν)νk , k = ν + 1, ...,m,

b(ν+1)i := b

(ν)i − liν b(ν)

ν ,

Sonst setze man

a(ν+1)ik := a

(ν)ik , b

(ν+1)i := b

(ν)i

Die Vertauschung leistet eine Linksmultiplikation mit der Permutationsmatrix

Pν =

1 0. . .

10 . . . . . . . . . 1... 1

...... . . . ...... 1

...1 . . . . . . . . . 0

1. . .

0 1

← ν

← µ

↑ν

↑µ

A(ν) := PνA(ν), b

(ν)i := Pb(ν).

Der Übergang von A(ν) nach A(ν+1) lässt sich durch Linksmultiplikation mit der ele-mentaren unteren Dreiecksmatrix

Lν :=

1 0. . .

1

−lν+1,ν. . .

... . . .0 −lm,ν 0 1


deuten, wobei

liν :=a

(ν)iν

a(ν)νν

, i = ν + 1, ...,m,

gesetzt wurde.Die Matrix

A(m) = Lm−1Pm−1Lm−2Pm−2 · · ·L1P1A

ist eine obere Dreiecksmatrix:

∗ ∗ ∗ . . . . . . ∗0 ∗ ∗ . . . . . . ∗0

. . . ∗ . . . . . . ∗... . . . . . . ...... 0

. . . . . . ...0 . . . . . . . . . 0 ∗

︸︷︷︸

A(m)

x1

x2

x3......

xm

︸︷︷︸

x

=

∗∗∗......∗

︸︷︷︸b(m)

.

Resultat 1.7 (LR-Zerlegung).Das Gaußsche Eliminationsverfahren liefert die sogenannte „LR-Zerlegung“

PA = LR

wobie P eine Permutationsmatrix, L ein untere und R eine obere Dreiecksmatrix ist,die sich wie folgt ergeben:

A(m) = Lm−1Pm−1Lm−2Pm−2 · · ·L1P1A

= Lm−1(Pm−1Lm−2Pm−1)(Pm−1Pm−2Lm−3Pm−2Pm−1) · · ·· · · (Pm−1Pm−2 · · · P2L1P2 · · ·Pm−2Pm−1) · (Pm−1Pm−2 · · · P2P1)︸︷︷︸

=:P

A

= Lm−1Lm−2 · · · L1PA

mit elementaren Dreiecksmatrizen Lm−1, Lm−2, . . . , L1. D.h.

PA = L−11 · · · L−1

m−2L−1m−1︸︷︷︸

=:L

A(m)︸︷︷︸:=R

Aufgabe 1.8. Man löse das lineare Gleichungssystem2 3 −1 0−6 −5 0 2

2 −5 6 −64 6 2 −3

x1

x2

x3

x4

=

20−45−358

und bestimme explizit die Permutationsmatrix Pν sowie die elementaren unteren Drei-ecksmatrizen Lν,ν = 1, ...,m−1, die bei der Gauß-Elimination mit spaltenweiser Pivot-Suche auftreten.


Bemerkung 1.9 (diagonale Pivot-Wahl).Falls keine Vertauschungen von Gleichungen notwendig sind (diagonale Pivot-Wahl),hat man die Darstellung

A(m) = Lm−1 · · ·L1A

oder

A = L−11 · · ·L−1

m−1A(m).

In Aufgabe 1.4 hatten wir gezeigt, dass L−1ν , ν = 1, ..,m − 1, ebenfalls eine elemen-

tare untere Dreiecksmatrix ist, die sich von Lν nur im Vorzeichen in der ν-ten Spalteunterhalb der Diagonalen unterscheidet. Man kann leicht zeigen, dass das Produktvon elementaren unteren Dreiecksmatrizen eine untere Dreiecksmatrix ist, die in derDiagonalen nur Einsen enthält. Wir folgern dies aus

Aufgabe 1.10.Die unteren Dreiecksmatrizen mit normierter Diagonale

∆ :=

1 0

∗ . . .... . . . . . .... . . . . . .∗ . . . . . . ∗ 1

m×m

bilden bezüglich der Multiplikation eine Gruppe.

Die Matrix

A = L−11 · · ·L−1

m−1A(m)

ist somit zerlegt in das Produkt einer unteren Dreiecksmatrix mit normierter Diagonale

L := L−11 · · ·L−1

m−1 = L−11 + L−1

2 + ...+ L−1m−1 − (m− 2)E

= −(L1 + L2 + ...+ Lm−1) +mE

und einer oberen Dreiecksmatrix

R := A(m), also:

∗ . . . . . . ∗...

......

...∗ . . . . . . ∗

︸︷︷︸

A

=

1 0

∗ . . .... . . . . . .∗ . . . ∗ 1

︸︷︷︸

L

∗ . . . . . . ∗

. . . .... . . ...

0 ∗

︸︷︷︸

R


Resultat 1.11 (LR-Zerlegung bei diagonaler Pivot-Wahl).Ist diagonale Pivot-Wahl möglich, so liefert das Gaußsche Eliminationsverfahren die„LR-Zerlegung“

A = LR

der Matrix A. Hierbei ergibt sich L aus den im Verlauf des Verfahrens verwendetenelementaren unteren Dreiecksmatrizen gemäß

L = mE − (L1 + L2 + ...+ Lm−1).

Wir haben gesehen, dass Algorithmus 1.6 ein reguläres Gleichungssystem

Ax = b

in ein äquivalentes Gleichungssystem

A(m)x = b(m)

mit oberer Dreiecksmatrix A(m) transformiert. Ein solches System löst man durchRücksubstitution:

Algorithmus 1.12 (Rücksubstitution).Es gelte

A(m)x = b(m)

mit regulärer oberer Dreiecksmatrix A(m) = (a(m)ik )m×m, b

(m) = (b(m)i ). Dann erhält man

die Komponenten xi, i = 1, ..,m, von x durch Rücksubstitution:Iteration: für i = m,m− 1, ..., 1 berechne

xi =1

a(m)ii

b

(m)i −

m∑k=i+1

a(m)ik xk

.

Zusammenfassung:

In diesem Abschnitt wurde Ihnen das von der Schule her bekannte Eliminationsver-fahren in systematischer, für die Programmierung geeigneter Form vorgestellt. Hierbeiwurde die Notwendigkeit der Spaltenpivotisierung betont. Damit lässt sich ein Glei-chungssytem mit regulärer Matrix in ein äquivalentes System umformen, das durchRücksubstitution einfach gelöst werden kann.

Bemerkung 1.13 (gestaffeltes Gleichungssystem - Informationselement).Wenn man ein lineares Gleichungssystem auflösen will, wird man in der Regel direkt dasEliminationsverfahren aus Abschnitt 1.2 anwenden und nicht explizit die LR-Zerlegungaufstellen.


Sind dagegen mehrere Gleichungssysteme hintereinander mit derselben Koeffizienten-matrix A zu lösen, so empfiehlt es sich, die LR-Zerlegung von A zu ermitteln und dannjeweils das gestaffelte System

Ly = b,

Rx = y

zu lösen. Dabei bestimmt man y durch das sogenannte Vorwärtseinsetzen (erst y1 be-rechnen, dann y2 usw.) und danach x durch Rücksubstitution (erst xm berechnen, dannxm−1 usw.).Die LR-Zerlegung spielt ebenfalls eine wichtige Rolle bei der Berechnung von Eigen-werten nach dem LR-Verfahren, darauf werden wir später noch eingehen.

Vorteile bietet die LR-Zerlegung auch bei Matrizen speziellen Typs, inbesondere beiBandmatrizen.

Bezeichnung 1.14 (Band-Matrix der Bandbreite d - Tridiagonalmatrix).Eine Matrix des Typs

A =

∗ ∗ . . . ∗ 0

∗ . . . . . . . . .... . . . . . . . . . ∗∗ . . . . . . . . . ...

. . . . . . . . . ∗0 ∗ . . . ∗ ∗

,

wobei aik = 0 für |i−k| ≥ d gilt, bezeichnet man als Bandmatrix der Bandbreite d. Spe-zielle Bandmatrizen sind die Diagonalmatrizen mit d = 1 und die Tridiagonalmatrizenmit d = 2.

Bei der LR-Zerlegung ohne Pivotsuche bleibt die Bandstruktur erhalten. Dies zeigtman in:

Aufgabe 1.15.Für eine Bandmatrix A der Bandbreite d haben die zugehörigen Matrizen L und R dieBandbreite d.

Zusammenfassung:In diesem Abschnitt wurde festgestellt, dass bei diagonaler Pivot-Wahl die Bandbreiteeiner Matrix bei der LR-Zerlegung erhalten bleibt.

1.3 Die Cholesky-Zerlegung

Beim Gaußschen Eliminationsverfahren muss man i.A. Zeilen- (bzw. ggf. auch Spalten-) vertauschungen vornehmen, um das Nichtverschwinden des Diagonalelementes zusichern. Diagonale Pivot-Wahl ist nur bei speziellen Matrizen möglich. Wir zeigen diesin diesem Abschnitt für positiv definite, Hermitesche Matrizen. Dazu erinnern wir unsan folgende Definition aus der Linearen Algebra.


Definition 1.16 (Hermitesche und positiv definite Matrizen).Eine Matrix A = (aik)m×m heißt

• Hermitesch, falls AH = A

• positiv definit, falls xHAx > 0 für alle 0 6= x ∈ Cm

Dabei bezeichnet x 7→ xH bzw. A 7→ AH den Übergang zu konjugiert-transponiertenVektoren bzw. Matrizen.

Satz 1.17.Die Diagonalelemente einer positiv definiten Matrix sind sämtlich positiv.

Beweis:Es sei ei = (0, ..., 0, 1, 0, ..., 0)t, i = 1, ..,m, der i-te Einheitsvektor. Dann gilt wegenDefinition 1.16

0 < etiAei = aii.

Eine weitere wichtige Eigeschaft betrifft die Eigenwerte. Dies ist Inhalt der folgendenAufgabe.

Aufgabe 1.18.Die Eigenwerte einer positiv definiten Matrix A sind positiv.

Bei einer positiv definiten Matrix A können wir versuchen, den Gauß-Algorithmussymmetrisch durchzuführen. Dies ergibt dann das so genannte Cholesky-Verfahren.Wir gehen aus von

A(1) := A

und beachten, dass a11 > 0 und A(1) Hermitesch ist. Wir eliminieren nun sowohl dieNichtdiagonalglieder in der ersten Zeile als auch in der ersten Spalte, indem wir

A(2) := L1A(1)LH1

mit

L1 :=

1 0 . . . . . . . . . 0

−a(1)21

a(1)11

1. . . ...

... 0. . . . . . ...

...... . . . . . . . . . 0

...... . . . 1 0

−a(1)m1

a(1)11

0 . . . . . . 0 1


bilden. A(2) hat dann die Form

A(2) =

a

(1)11 0 . . . . . . 00 . . . . . . . . ....

......

... B(2)

0...

, a(1)11 = a11.

Wegen(A(2))H = L1(A(1))HLH1 = L1A

(1)LH1 = A(2)

ist A(2) und damit auch B(2) Hermitesch. A(2) ist sogar positiv definit: Denn für jedenVektor 0 6= x ∈ Cm gilt wegen der Regularität von LH1

y := LH1 x 6= 0;

folglich ergibt sich

xHA(2)x = xHL1A(1)LH1 x

= (LH1 x)HA(1)(LH1 x)

= yHA(1)y > 0

wegen der positiven Definitheit von A(1). Mit A(2) ist aber offensichtlich auch B(2)

positiv definit. Wegen Satz 1.17 gilt dann

a(2)22 > 0,

und die symmetrische Dreieckzerlegung lässt sich in der beschriebenen Weise auf B(2)

statt A(1) anwenden. Nach m− 1 Schritten erhält man die Zerlegung

Lm−1 · · · L1ALH1 · · · LHm−1 =

a

(1)11 0

a(2)22

. . .. . .

0 a(m)mm

︸︷︷︸

=:diag(a(1)11 ,...,a

(m)mm)

.

Wir setztenD := diag(a

(1)11 , .., a

(m)mm)

und √D := diag(

√a

(1)11 , ...,

√a

(m)mm).

Man beachte, dass√D wegen a(i)

ii > 0, i = 1, ...,m, wohldefiniert ist.Dann gilt

D =√D√D


Insgesamt haben wir die Darstellung

A = L−11 ...L−1

m−1

√D√D(LHm−1)−1...(LH1 )−1

gefunden. Wir setzen

L := L−11 ...L−1

m−1

√D,

LH =√D(L−1

m−1)−1...(LH1 )−1

Es resultiert dann die Cholesky-Zerlegung

A = LLH ;

dabei ist L eine untere Dreiecksmatrix. Man beachte, dass die Diagonalelemente von Ljetzt (im Gegensatz zur LR-Zerlegung beim Gaußschen Eliminationsverfahren) nichtmehr notwendig den Wert Eins haben.

Wir fassen zusammen:

Satz 1.19 (Cholesky-Zerlegung einer positiv definiten, Hermiteschen Matrix).Eine positiv definite, Hermitesche Matrix A lässt sich zerlegen in das Produkt einerunteren Dreiecksmatrix L mit ihrer konjugiert-transponierten:

A = LLH .

Wir verwenden zur expliziten Bestimmung der Elemente lik, i = 1, ...,m, k = 1, ..., i,eine geeignete Reihenfolge. Hier geht man am einfachsten zeilenweise vor.Aus

A = LLH

erhält man

aik =m∑µ=1

liµlkµ, i, k = 1, ...,m,

woraus wegen der Dreiecksgestalt von L die Darstellung

aik =

min(i,k)∑µ=1

liµlkµ, i, k = 1, ..,m,

folgt. Insgesamt ergibt sich so:

Algorithmus 1.20 (Cholesky-Verfahren).Für i = 1, ...,m:

1. Für k = 1, ..., i− 1 berechne

lik :=1

lkk

aik −

k−1∑µ=1

liµlkµ

.

2. Berechne

lii :=

√√√√aii −i−1∑µ=1

|liµ|2.


Der Rechenaufwand beim Cholesky-Verfahren ist wesentlich niedriger als beim Gauß-Algorithmus. Wir lösen in diesem Zusammenhang folgende Aufgabe.

Aufgabe 1.21.Man bestimme den Rechenaufwand, der bei der Cholesky-Zerlegung einer positiv defi-niten (m×m)-Matrix erforderlich ist

Zusammenfassung:In diesem Abschnitt haben Sie eine symmetrische Variante des Gaußschen Eliminati-onsverfahrens für positiv definite Matrizen kennengelernt. Dieses sogenannte Cholesky-Verfahren ist insbesondere auch numerisch weniger aufwendig.

1.4 Die QR-Zerlegung (Ergänzung)

Der Gauß-Algorithmus liefert mit Hilfe elementarer Dreiecksmatrizen die LR-Zerlegungeiner regulären Matrix; dabei wird ein gegebenes System Ax = b auf (obere) Dreiecks-gestalt gebracht. Wir werden bei der Fehleranalyse des Gauß-Algorithmus feststellen,dass die LR-Zerlegung u.U. ein ungünstiges Fehlerverhalten zeigen kann. In gewissenFällen kann es daher angebracht sein, die Reduktion auf Dreiecksgestalt mit Hilfe uni-tärer (oder orthogonaler) Matrizen durchzuführen. Zu diesem Zweck erinnern wir unsan das Orthogonalisierungsverfahren von E. Schmidt, das Ihnen in der Lineare Algebravorgestellt wurde.

Aufgabe 1.22 (Orthogonalisierung nach E. Schmidt).Es seien a1, .., am m linear unabhängige Vektoren aus Cm (oder aus Rm). Man kon-struiere dazu rekursiv eine Orthonormalbasis q1, ..., qm, d.h. für q1, ..., qm gelte

(qν , qµ) = δνµ, ν, µ = 1, ...,m undaν ∈ span(q1, ..., qν), ν = 1, ...,m,

wenn (., .) das kanonische Skalarprodukt in Cm (oder in Rm) bezeichnet.

Die in dieser Aufgabe hergeleiteten Formeln, welche die Vektoren aν mit den qν , ν =1, ...,m, verbinden, sind vom Typ

a1 = r11q1,

a2 = r12q1 + r22q2,...

am = r1mq1 + r2mq2 + ...+ rmmqm

(Beachten Sie, dass die sich hier ergebende Dreiecksform vom rekursiven Aufbau desSchmidtschen Orthogonalisierungsverfahren herrührt.) Wenn wir jetzt die Vektorena1, ..., am und q1, ..., qm jeweils als Spaltenvektoren einer Matrix A und einer Matrix Qauffassen, können wir die Orthogonalisierungsformeln in der Form

(a1, ..., am) = (q1, ..., qm)

r11 . . . r1m

. . . ...0 rmm


schreiben. Komponentenweise mit

aν =: (a1ν , a2ν , ..., amν)t, ν = 1, ...,m

qν =: (q1ν , q2ν , ..., qmν)t, ν = 1, ...,m

gilt dann

A := (aµν)µ=1,...,mν=1,...,m

=

q11 . . . q1m...

...qm1 . . . qmm

︸︷︷︸

:=Q

r11 . . . r1m

. . . ...0 rmm

︸︷︷︸

:=R

Resultat 1.23 (QR-Zerlegung von A).Das Orthogonalisierungsverfahren nach E. Schmidt liefert die Darstellung

A = QR („QR-Zerlegung“);

dabei ist Q eine unitäre Matrix, d.h.

QHQ = E, Q−1 = QH ,

und R eine obere Dreiecksmatrix.

Mit Hilfe der QR-Zerlegung ist die Auflösung eines linearen Gleichungssystems

Ax = b

auf die Auflösung eines „gestaffelten“ Systems

Rx = Q−1b = QHb

zurückgeführt, die sich rekursiv durch Rücksubstitution wie bei

Ly = b,

Rx = y

ergibt.

Bemerkung 1.24.In der Praxis stößt man beim Orthogonalisierungsverfahren nach E. Schmidt auf Schwie-rigkeiten, falls die Ausgangsvektoren ai „fast“ linear abhängig sind. Hier können schongeringe Rundungsfehler eine starke Störung der Orthogonalität der berechneten Vekto-ren q1, ..., qm verursachen.

Günstiger lässt sich die QR-Zerlegung mit Hilfe von geeigneter Spiegelung, den soge-nannten Householder-Transformationen, gewinnen.

Hierzu betrachten wir einen Vektor w ∈ Cm der euklidischen Länge 1, d.h. es geltewHw = 1. Ist E die Einheitsmatrix der Dimension m, so ist die (m×m)-Matrix

Hw := E − 2wwH

wegen(E − 2wwH)H = EH − 2(wwH)H = E − 2wwH

Hermitesch.


Definition 1.25 (elementare Hermitesche Matrix - Householder-Transformation).Eine Matrix des Typs

Hw := E − 2wwH , w ∈ Cm, wHw = 1, E = m×m-Einheitsmatrix

heißt elementare Hermitesche Matrix; die durch Hw vermittelte Abbildung des RaumesCm in sich bezeichnet man als Householder-Transformation.

Wir stellen einige wichtige Eigenschaften elementarer Hermitescher Matrizen zusam-men:

Satz 1.26.Es sei Hw eine elementare Hermitesche (m×m)-Matrix.Dann ist Hw

1. unitär: H−1w = HH

w ,

2. involutorisch: (Hw)2 = E, und

3. die Abbildung x 7→ Hwx entspricht einer Spiegelung von x an der zu w orthogo-nalen Hyperebene L.

Beweis:

1. Wegen

HHw Hw = HwHw = (E − 2wwH)(E − 2wwH) = E − 4wwH + 4wwHwwH

folgt unter Berücksichtigung von wHw = 1 die Beziehung HHw ·Hw = E; also gilt:

H−1w = HH

w .

2. ist wegen (1) und wegen HHw = Hw klar.

3. Einen Vektor x ∈ Cm projizieren wir auf die eindeutig bestimmte Hyperebene L,welche orthogonal zu w ist, vgl. Abbildung 1.2.

Dann lässt sich x in eindeutiger Weise in der Form

x = tw + v mit t ∈ C, v ∈ L

darstellen. Spiegelung an L entspricht dem Übergang von

x 7→ x := −tw + v.

WegenwHx = twHw + wHv = t

folgtx = −wHxw + v

und daraus mitv = x− tw = x− wHxw


L

x

v

x~

w

tw

−tw

Abbildung 1.2: Spiegelung von x an der zu w orthogonalen Hyperebene L

die Darstellung

x = −wHxw + x− wHxw= x− 2wHxw

= x− 2wwHx (beachte: wHx ∈ C !)= (E − 2wwH)x

= Hwx.

Mit Hilfe von Householder-Transformationen werden wir ebenfalls die QR-Zerlegungkonstruieren. Dazu benötigen wir den algorithmischen Zusammenhang, der die Spie-gelung eines gegebenen Vektors x in ein skalares Vielfaches eines weiteren gegebenenVektors y beschreibt; y wird ein kanonischer Einheitsvektor ek, 1 ≤ k ≤ m, sein.Wir machen uns zunächst anschaulich klar, dass es zwei Spiegelungen gibt, die dasgewünschte leisten, vgl. Abbildung 1.3.

Nach diesen anschaulichen Überlegungen stellen wir nun den entsprechenden algorith-mischen Zusammenhang auf.

Gegeben sei der Vektor x 6= 0. Wir suchen elementare Matrizen

Hw = E − 2wwH , wHw = 1,

welcheHwx = αek, k ∈ 1, ...,m fest, 0 6= α ∈ C,

liefern; dabei bezeichnetek = (0, ..., 0, 1, 0, ..., 0)t


L

x

x~

w

y

(w x)wH

x−(w x)wH

x

y

w

(w x)wH

L

x~

x−(w x)wH

Abbildung 1.3: Zwei mögliche Spiegelungen

den k-ten Einheitsvektor.

Zunächst beachten wir, dass eine Spiegelung die euklidische Länge eines Vektors inva-riant lässt; also gilt

|α| = ‖x‖e :=√xHx =

√√√√ m∑ν=1

|xν |2 6= 0,

wenn x die Komponenten x1, ..., xm hat. Wir verwenden die Darstellung

xk = |xk| · eiϕk ( ϕk := 0 für xk = 0)

von xk in Polarkoordinaten.Wegen x 6= 0 können wir nun w ∈ Cm mit wHw = 1 und α ∈ C derart bestimmen,dass

αek = Hwx

gilt. Denn ausαek = (E − 2wwH)x = x− 2wwHx

folgtx− αek = 2wwHx.


Hieraus erhält man durch Multiplikation mit xH von links

xHx− αxHek = 2xHwwHx

oderxHx− αxk = 2|wHx|2.

Diese Gleichung zeigt unter Beachtung der Tatsache, dass xHx reell ist, dass auch α ·xkreell sein muss. Ist xk 6= 0, so kann α wegen

xk = |xk| · eiϕk und α 6= 0

nur die Darstellungen

α1 = |α| · eiϕk oder α2 = −|α| · eiϕk

besitzen. Beide Vorzeichen sind möglich; dies steht im Einklang mit Abbildung 1.3,wo wir die beiden möglichen Spiegelungen dargestellt haben. Ist xk = 0, so kann dasArgument von α zunächst beliebig gewählt werden; im Einklang mit der Festlegungϕk = 0 beschränken wir uns auch hier auf die Fälle α1 = |α| oder α2 = −|α|. DenVektor w erhalten wir aus der Beziehung

x− α1,2ek = 2wwHx = 2(wHx)w,

d.h. w is ein Vielfaches von x−α1,2ek. Welches ist die bessere Wahl: α1 oder α2? Wegen

‖x− α1,2ek‖2e = |x1|2 + ...+ |xk−1|2 + |xk − α1,2|2 + |xk+1|2 + ...+ |xm|2

giltx− α2ek 6= 0 und ‖x− α2ek‖e > ‖x− α1ek‖e.

Man setzt deshalbw :=

x− α2ek‖x− α2ek‖e

,

um den Rundungsfehler der Komponente wk von w möglichst klein zu halten. DieseWahl von w leistet das Gewünschte, denn α2 = −‖x‖eeiϕk und daher

Hwx = x− 2w(wHx)

= x− 2‖x‖2

e − α2xk‖x‖2

e − α2xk − α2xk + |α2|2(x− α2ek)

= x− 2‖x‖2

e − α2xk‖x‖2

e − α2xk − α2xk + |α2|2(x− α2ek)

= α2ek.

Wir stellen die Transformationsformeln für eine Householder-Spiegelung nochmals über-sichtlich zusammen.

Algorithmus 1.27 (Spiegelung durch Householder-Transformation).Es sei x = (x1, ..., xm)t 6= 0 ein gegebener Vektor und k ∈ 1, ...,m.Ist xk 6= 0, so setze man

xk =: |xk|eiϕ.


Ist xk = 0, so setze manϕ := 0.

Man berechne

|α| := ‖x‖e =

√√√√ m∑ν=1

|xν |2,

α := −|α|eiϕ,β := ‖x− αek‖e := [|x1|2 + ...+ |xk−1|2 + (|xk|+ |α|)2 + |xk+1|2 + ...+ |xm|2]1/2,

w :=1

β(x− αek).

Dann giltwHw = 1,

und die durch die elementare Hermitesche Matrix

Hw := E − 2wwH

gegebene Householder-Transformation spiegelt den Vektor x auf den Vektor αek 6= 0,

Hw := x 7→ αek.

(Für reelles xk 6= 0 berücksichtige man, dass eiϕ = sign(xk) gilt; für x ∈ Rm verläuftdie Rechnung also im Reellen).

Diesen Algorithmus verwenden wir nun dazu, die QR-Zerlegung

A = QR

einer gegebenen regulären Matrix A zu erzeugen. Wir gehen rekursiv vor und spiegelnim ersten Schritt den ersten Spaltenvektor a1 von A = (a1, ..., am) auf ein skalaresVielfaches von e1. Dies erreichen wir durch geeignete Wahl von w1 ∈ Cm entsprechenddem Algorithmus 1.27. Dann hat

A(1) := Hw1A = (E − 2w1wH1 )A, wH1 w1 = 1,

die Gestalt

A(1) =

∗ a(1)12 ∗ . . . . . . ∗

0 a(1)22 ∗ . . . . . . ∗

0...

......

......

......

......

......

0 a(1)n2 ∗ . . . . . . ∗

.

Im zweiten Schritt wird w2 ∈ Cm so konstruiert, dass Hw2 in der zweiten Spalte unter-halb der Diagonalen Nullen erzeugt und die erste Spalte nicht verändert:

w2 =

(0w2

); w2 ∈ Cm−1


so, dass die Householder-Transformation Hw2 in Cm−1 liefert:

Hw2

a(1)22...a

(1)n2

= β

10...0

∈ Cm−1.

Dann

Hw2

10...0

=

10...0

, Hw2

a

(1)12......a

(1)k2

=

a

(1)12

β0...0

,

also

Hw2A(1) =

∗ ∗ ∗ · · · ∗0 ∗ ...

...... 0

......

......

......

0 0 ∗ . . . ∗

=: A(2)

Im dritten Schritt gehen wir wie folgt vor:

w3 =

00w3

, w3 ∈ Cm−2,

wobei w3 in Cm−2 so gewählt wird, dass Hw3 den Vektor

a(2)33...a

(2)n3

∈ Cm−2 auf

γ

10...0

∈ Cm−2 abbildet, etc.. In dieser Weise fortfahrend erhält man in m − 1

Schritten die Darstellung

A(m−1) = Hwm−1 ...Hw1A =: R =

∗ . . . . . . ∗

. . . .... . . ...

0 ∗

.Dabei hat R obere Dreicksform und nichtverschwindende Diagonalelemente.

Aufgabe 1.28. Man formuliere einen Algorithmus, der mit Hilfe von Householder-Transformationen die QR-Zerlegung einer reellen regulären Matrix liefert.

Man beachte, dass die QR-Zerlegung für jede reguläre (m×m)-Matrix existiert, wäh-rend die LR-Zerlegung selbst bei regulären Maritzen i.A. nur unter Verwendung vonZeilen- (oder Spalten-) permutationen (Pivot-Suche) möglich ist.


Resultat 1.29 (QR-Zerlegung durch Householder-Transformation).Eine reguläre (m × m)-Matrix A lässt sich mit Hilfe von m − 1 Householder-Trans-formationen in der Form

A = QR mit QHQ = E, R= obere Dreiecksmatrix,

darstellen. Das Gleichungssystem Ax = b ist nun leicht auflösbar: QRx = b ⇔ Rx =QHb da Q unitär (Auflösen durch Rückwärtssubstitution).

Zusatz: Es sei bemerkt, dass man auch QR-Zerlegungen singulärer quadratischer Ma-trizen bestimmen kann, wenn Spaltenpermutationen zugelassen werden. In diesem Fallwird zu Beginn des k-ten Schrittes in der oben (für reguläre Matrizen) beschriebenenQR-Zerlegung die Matrix

A(k) =

∗ . . . . . . . . . ∗. . . ...

∗ . . . ∗

0 B(k)

von rechts mit einer (m×m)-Permutationsmatrix P (k) multipliziert,

P (k) =

1 0. . .

1

0 P(k)1

wobei die ((m − k + 1) × (m − k + 1))-Permutationsmatrix P

(k)1 so gewählt wird,

dass die Matrix B(k) · P (k)1 in der ersten Spalte eine nichtverschwindende Komponente

besitzt. Auf A(k)P (k) kann nun die im Algorithmus 1.27 beschriebene Householder-Transformation angewendet werden. Das Verfahren bricht nach genau r := Rang(A)Schritten ab (wenn A singulär ist) und liefert

A(r) = Hwr · · ·Hw1AP(1) · · ·P (r) =

∗ . . . . . . . . . . . . ∗. . . ...

∗ . . . . . . ∗

0 O

bzw.

AP (1) · · ·P (r) = Hw1 · · ·HwrA(r) =: QR.

Kapitel 2

Eigenwertprobleme

2.1 Begriffe und Definitionen

Gegeben sei eine Matrix A ∈ Km×m (K = R oder K = C).

Definition 2.1 (Eigenwert, Eigenvektor).Ein Wert λ ∈ C heißt Eigenwert von A, falls ein Vektor u ∈ Cm \ 0 existiert mit

Au = λu.

Jeder derartige Vektor u 6= 0 heißt ein zu λ gehöriger Eigenvektor.

Die Eigenwerte einer Matrix können berechnet werden als Nullstellen des charakteris-tischen Polynoms

pA(λ) := det(A− λE)

der Matrix A. Dieses Vorgehen ist numerisch instabil und daher nicht zu empfehlen. Zielder Untersuchungen dieses Kapitels ist es, numerisch praktikable Verfahren zu finden,mit denen man (unter geeigneten Voraussetzungen an die Matrix A) Näherungen andie Eigenwerte und Eigenvektoren von A berechnen kann.

Wir werden uns im Folgenden auf die Klasse der diagonalisierbaren Matrizen beschrän-ken. Dabei heißt eine m×m Matrix A diagonalisierbar, falls es m linear unabhängigeEigenvektoren u1, . . . , um der Matrix A gibt. Die Vektoren u1, . . . , um bilden eine Basisdes Cm aus Eigenvektoren. Der zu ui gehörige Eigenwert sei mit λi bezeichnet, i =1, . . . ,m. Setze nun

T :=

u1 u2 . . . um

.Die m × m-Matrix T ist regulär, da ihre Spalten u1, . . . , um linear unabhängig sind.Wir berechnen

AT =

Au1 Au2 . . . Aum

=

λ1u1 λ2u

2 . . . λmum

=

u1 u2 . . . um

λ1 0

. . .0 λm

= T

λ1 0. . .

0 λm

,29

KAPITEL 2. EIGENWERTPROBLEME 30

und erhalten somit für eine diagonalisierbare Matrix A die Darstellung

T−1AT =

λ1 0. . .

0 λm

= diag(λ1, . . . , λm)

bzw.A = T diag(λ1, . . . , λm)T−1.

Unter jeder der folgenden vier Bedingungen ist die Matrix A diagonalisierbar:

(1) A besitzt m verschiedene Eigenwerte.

(2) A ist normal, d.h. AAH = AHA. In diesem Fall kann man die Eigenvektoren sogarso wählen, daß u1 . . . , um eine Orthonormalbasis ist. Damit ist T eine unitäreMatrix, denn

THT =

u1H

u2H

...umH

u1 u2 . . . um

= E, d.h. T−1 = TH .

(3) A ist Hermitesch. Denn dann ist wegen AH = A die Matrix A insbesonderenormal. In diesem Fall sind die Eigenwerte λ1, . . . , λm alle reell.

(4) A ist unitär. Denn dann ist wegen AHA = E = AAH die Matrix A insbesonderenormal. In diesem Fall gilt für die Eigenwerte: |λ1| = . . . = |λm| = 1.

2.2 Die von-Mises Iteration

Ziel diese Abschnittes ist es, ein iteratives Verfahren zur Bestimmung eines Eigenwerteseiner diagonalisierbaren Matrix zu formulieren. Es sei also A ∈ Cm×m eine diagonali-sierbare m×m-Matrix. Wir ordnen die Eigenwerte gemäß der Größe ihres Betrages

|λ1| ≥ |λ2| ≥ . . . ≥ |λm|.

Im Folgenden betrachten wir den Spezialfall

|λ1| > |λ2| ≥ . . . ≥ |λm|

und beschreiben ein Verfahren zur Bestimmung des betragsgrößten Eigenwertes λ1. Seialso u1, . . . , um mit Aui = λiu

i, i = 1, . . . ,m eine Basis aus Eigenvektoren von A. Einbeliebiger Vektor x0 ∈ Cm lässt sich in der Basis entwickeln:

x0 = ρ1u1 + ρ2u

2 + . . .+ ρmum mit ρ1, . . . , ρm ∈ C.

Wir nehmen an, dass ρ1 6= 0 gilt.

Definierexk := Axk−1 für k = 1, 2, . . . .


Dann gilt

xk = Axk−1 = A(Axk−2) = . . . = A · A · . . . · A︸︷︷︸=:Ak

x0

= Akx0.

Es folgt

xk = Akx0 = Ak(ρ1u1 + ρ2u

2 + . . .+ ρmum)

= Ak−1(ρ1Au1 + ρ2Au

2 + . . .+ ρmAum)

= Ak−1(ρ1λ1u1 + ρ2λ2u

2 + . . .+ ρmλmum)

= . . .

= ρ1λk1u

1 + ρ2λk2u

2 + . . .+ ρmλkmu

m.

Folglich gilt:

xk

λk1= ρ1u

1 + ρ2

(λ2

λ1

)k︸︷︷︸→0

u2 + . . .+ ρm

(λmλ1

)k︸︷︷︸→0

um

→ ρ1u1 für k →∞.

Problem: λ1 ist gesucht, d.h. im Allgemeinen nicht bekannt! Abhilfe wird durch diefolgende Modifikation der obigen Iteration geschaffen.

Algorithmus 2.2 (Von-Mises Iteration).Sei A eine diagonalisierbare m×m-Matrix; wähle Startvektor x0 ∈ Cm wie zuvor.Iteration: Für k = 1, 2, ... bilde die Vektoren

zk :=Axk−1

xk :=zk

zkik, wobei der Index ik so gewählt ist, dass gilt: |zkik | =

mmaxi=1|zki |

Resultat 2.3 (Konvergenz der von-Mises Iteration).Für die von-Mises Iteration gilt:

• zk+1ik→ λ1 für k →∞

• xk nähert sich einem Vielfachen des Eigenvektors u1. Genauer:

xk − u1

u1ik

→ 0 für k →∞.

Beweis: Wir skizzieren die Beweisschritte.


1. Es gilt folgende Darstellung für den k-ten iterierten Vektoren

xk =zk

zkik=

Axk−1

(Axk−1)ik=

Azk−1 · 1

zk−1ik−1

(Azk−1)ik · 1

zk−1ik−1

=A2xk−2

(A2xk−2)ik= . . .

=Akx0

(Akx0)ik

2. Nun betrachten wir zk+1ik

und erhalten

zk+1ik

= (Axk)ik =(Ak+1x0)ik(Akx0)ik

=(ρ1λ

k+11 u1 + ρ2λ

k+12 u2 + . . .+ ρmλ

k+1m um)ik

(ρ1λk1u1 + ρ2λk2u

2 + . . .+ ρmλkmum)ik

= λ1

(ρ1u

1 + ρ2

(λ2λ1

)k+1

u2 + . . .+ ρm

(λmλ1

)k+1

um)ik(

ρ1u1 + ρ2

(λ2λ1

)ku2 + . . .+ ρm

(λmλ1

)kum)ik

→ λ1 für k →∞,

da die Terme(λ2λ1

)k, . . . ,

(λmλ1

)kfür k → ∞ gegen Null streben. Damit ist die erste

Aussage des Resultates bewiesen.

3. Die zweite Aussage folgt auf ähnliche Art und Weise:

xk − u1

u1ik

=Akx0

(Akx0)ik− u1

u1ik

=ρ1λ

k1u

1 + ρ2λk2u

2 + . . .+ ρmλkmu

m

(ρ1λk1u1 + ρ2λk2u

2 + . . .+ ρmλkmum)ik

− u1

u1ik

=ρ1u

1 + ρ2

(λ2λ1

)ku2 + . . .+ ρm

(λmλ1

)kum(

ρ1u1 + ρ2

(λ2λ1

)ku2 + . . .+ ρm

(λmλ1

)kum)ik

− u1

u1ik

→ 0 für k →∞,

da wiederum die Terme(λ2λ1

)k, . . . ,

(λmλ1

)kfür k → ∞ gegen Null streben. Damit ist

die Konvergenz der von-Mises Iteration geklärt.

Bemerkung: Die Bedingung ρ1 6= 0 bei der Wahl des Startvektors x0 bereitet keineProbleme, denn aufgrund von Rundungsfehlern ist dies spätestens ab dem zweitenIterationsschritt gewährleistet.


2.3 Die inverse Iteration von Wielandt

Die folgende Variante der von-Mises Iteration liefert Approximationen des betrags-kleinsten Eigenwertes einer diagonalisierbaren und invertierbaren Matrix A. Wiederumseien λ1, . . . λm die Eigenwerte von A mit zugehöriger Basis aus Eigenvektoren ui mit

Aui = λiui für i = 1, . . . ,m,

wobei gelten möge:|λ1| ≥ |λ2| ≥ . . . > |λm|.

Da A als invertierbar vorausgesetzt wurde, gilt

ui = λiA−1ui bzw. A−1ui =

1

λiui für i = 1, . . . ,m.

Das bedeutet, dass die Matrix A−1 die Eigenwerte 1λ1, . . . , 1

λmmit zugehörigen Eigen-

vektoren u1, . . . , um hat. Außerdem gilt1

|λm|>

1

|λm−1|≥ . . . ≥ 1

|λ1|.

Nun wenden wir die von-Mises Iteration auf die Matrix A−1 an, deren betragsgrößterEigenwert gerade 1/λm ist. Das entstehende Verfahren heißt inverse Iteration.

Algorithmus 2.4 (Inverse Iteration).Sei A eine diagonalisierbare, reguläre m×m-Matrix; wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bilde die Vektoren,

wk :=A−1yk−1

yk :=wk

wkik, wobei der Index ik so gewählt ist, dass gilt: |wkik | =

mmaxi=1|wki |

Resultat 2.5 (Konvergenz der inversen Iteration).Für die inverse Iteration gilt:

• wk+1ik→ 1

λmfür k →∞

• yk nähert sich einem Vielfachen des Eigenvektors um. Genauer:

yk − um

umik→ 0 für k →∞.

In der Praxis wird A−1 nicht berechnet. Anstelle dessen wird der Algorithmus derinversen Iteration wie folgt formuliert:

Algorithmus 2.6 (Inverse Iteration – Variante).Sei A eine diagonalisierbare, reguläre m×m-Matrix; wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem Awk = yk−1

yk :=wk


mmaxi=1|wki |


Für die Lösung des linearen Gleichungssystems kann man z.B. die LR-Zerlegung derMatrix A bestimmen, vgl. Kapitel 1.

Zusammenfassung:

Die m×m-Matrix A sei diagonalisierbar. Die von-Mises Iteration liefert Approximatio-nen an den betragsgrößten Eigenwert von A (und den zugehörigen Eigenvektor). Dieinverse Iteration liefert (sofern A invertierbar ist) Approximationen an den Kehrwertdes betragskleinsten Eigenwertes von A (und den zugehörigen Eigenvektor).

Praktischer Nutzen der inversen Iteration:

Angenommen, wir kennen bereits eine brauchbare Approximation λ an einen Eigenwertλj, d.h.

|λ− λj| < |λ− λl| für alle l 6= j.

Die bedeutet, dass λj − λ der betragskleinste Eigenwert der Matrix A − λE ist. Nunkönnen wir die inverse Iteration anwenden.

Wähle Startvektor y0 ∈ Cm.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem (A− λE)wk = yk−1

yk :=wk


mmaxi=1|wki |

Diese Iteration liefert das Ergebnis:

yk+1ik→ 1

λj − λfür k →∞

bzw.λ+

1

yk+1ik

→ λj für k →∞,

d.h. wir erhalten ein iteratives Verfahren, das verbesserte Approxmationen an λj liefert.

Bemerkung: Es liegt nahe, in jedem Iterationsschritt λ durch die gerade neu gewon-nene bessere Approximation an λj zu ersetzen. Dies führt zu folgendem Algorithmus:

Wähle Startvektor y0 ∈ Cm. Setze µ0 := λ =: µ1.Iteration: Für k = 1, 2, ... bestimme die folgenden Vektoren:

löse das lineare Gleichungssystem (A− µk−1E)wk = yk−1

yk :=wk


mmaxi=1|wki |

µk := µk−1 +1

ykik−1

für k ≥ 2.


2.4 Das LR-Verfahren und das QR-Verfahren für Ei-genwertprobleme (Ergänzung)

Wir bereits zuvor erwähnt, setzen wir voraus, daß die Matrix A diagonalisierbar ist.Von Rutishauser wurde 1958 das LR-Verfahren vorgeschlagen. Wie der Name schonandeutet, wird dabei an wesentlicher Stelle die LR-Zerlegung aus Abschnitt 1.2 benützt.

Wir beginnen mit einer Motivation für das weitere Vorgehen: Für die Matrix A =: A1

existiere die LR-Zerlegung (ohne Zeilenvertauschungen)

A1 = L1R1,

wobei

L1 =

1 0

∗ . . .... . . . . . .... . . . . . .∗ . . . . . . ∗ 1

,

R1 =

∗ . . . . . . . . . ∗

. . . .... . . ...

. . . ...0 ∗

untere bzw. obere Dreiecksmatrizen sind. Nun wollen wir überlegen, wie die LR-Zerlegung der k-ten Potenz Ak von A aussieht. Für die k-te Potenz Ak folgt zuerst

Ak = Ak1 = L1R1L1R1 · · · L1R1L1R1︸︷︷︸k−mal der Faktor L1R1

.

Wir setzenA2 := R1L1

und erhaltenAk1 = L1 A2 · · · A2︸︷︷︸

k − 1 Faktoren

R1 = L1Ak−12 R1.

Man erkennt, wie man durch Wiederholung dieses Prozesses eine Faktorisierung vonAk erhalten kann.

Resultat 2.7.Setze

A1 := A.

Wir nehmen an, daß die LR-Zerlegungen (ohne Zeilenvertauschungen)

Aν = LνRν , ν = 1, ..., k,

für A1 und für die Matrizen

Aν := Rν−1Lν−1, ν = 2, ..., k


existieren. Dann giltAk = L1L2 · · · LkRkRk−1 · · ·R1.

Setzt manLk := L1L2 · · · Lk und Rk := RkRk−1 · · ·R1,

so ist Lk eine untere Dreiecksmatrix mit normierter Diagonale und Rk eine obere Drei-ecksmatrix. Damit haben wir die LR-Zerlegung

Ak := LkRk

von Ak bestimmt.

Wir betrachten nun eine diagonalisierbare m×m-Matrix A, bei der λ1 der dominanteEigenwert ist, d.h.:

|λ1| > |λν |, ν = 2, ...,m.

Die zugehörige Basis aus Eigenvektoren sei u1, ..., um. Wir starten nun ein Iterati-onsverfahren mit

z0 := e1 = (1, 0, ..., 0)t

und setzenzk := Azk−1 = Akz0 = Ake1.

In der Basisdarstellung des Vektors e1

e1 = ρ1u1 + ρ2u2 + ...+ ρmum

gelte die Annahmeρ1 6= 0.

Dann folgt

zk = Ak(ρ1u1 + ρ2u2 + ...+ ρmum)

= ρ1λk1u1 + ρ2λ

k2u2 + ...+ ρmλ

kmum

= λk1

ρ1u1 +

m∑µ=2

ρµ

[λµλ1

]kuµ

,

und darauszkλk1−→ ρ1u1 für k →∞.

Zum Vergleich berechnen wir erneut zk; diesmal jedoch unter Verwendung der zuvorerörterten LR-Zerlegung von Ak

Ak = LkRk.


Unter Ausnützung der Dreiecksgestalt von Lk und Rk sowie der besonderen Form deskanonischen Einheitsvektors e1 berechnet man

zk = Ake1 =

1 0

l(k)21

. . .... . . . . . .... . . . . . .l(k)m1 . . . . . . l

(k)mm−1 1

︸︷︷︸

Lk

r(k)11 . . . . . . . . . r

(k)1m

. . . .... . . ...

. . . ...0 r

(k)mm

︸︷︷︸

Rk

10......0

= r(k)11

(1, lk21, ..., l

km1

)t.

Wir erhalten also

zkλk1

=r

(k)11

λk1

1

l(k)21...l(k)m1

︸︷︷︸

=:l(k)1

→ ρ1

η11

η21...ηm1

︸︷︷︸

:=u1 6=0

für k →∞

und insbesondere (bei Betrachtung der ersten Komponente):

r(k)11

λk1→ ρ1η11 für k →∞.

Setzt manRk =:

(r

(k)ij

)m×m

,

so erhält man ausRk = RkRk−1

die Beziehungr

(k)11 = r

(k)11 r

(k−1)11 .

Unter der Annahmeη11 6= 0

folgt dann aus der Konvergenz

r(k)11 λ

−k1 → ρ1η11 für k →∞,

dass das linke obere Element der oberen Dreiecksmatrizen Rk gegen den dominantenEigenwert konvergiert:

r(k)11 =

r(k)11

r(k−1)11

=r

(k)11 λ

−k1 λ1

r(k−1)11 λ

−(k−1)1

→ ρ1η11λ1

ρ1η11

= λ1 für k →∞.

Weiter konvergiert die erste Spalte der unteren Dreiecksmatrizen Lk wegen

zkλk1

=r

(k)11

λk1

(1, l

(k)21 , ..., l

(k)m1

)t→ ρ1 (η11, η21, ..., ηm1)t , k →∞,


gegen einen zu λ1 gehörenden Eigenvektor:(1, l

(k)21 , ..., l

(k)m1

)t→ 1

η11

(η11, ..., ηm1)t =u1

η11

, k →∞.

Diese Konvergenzaussagen, insbesondere die Aussage

r(k)11 → λ1 für k →∞,

erhielten wir unter einschränkenden Bedingungen an λ1 (dominanter Eigenwert) undu1 (η11 6= 0), sowie unter der Annahme, dass die LR-Zerlegung für jedes Ak existiert.

Damit wird die Vermutung nahegelegt, dass unter weiteren Bedingungen an A (vgl.Resultat 2.9) die Hauptdiagonalelemente von Rk gegen die Eigenwerte von A konver-gieren und alle Spalten von Lk - und damit die Matrix Lk selbst - konvergieren. Da dieLk normierte untere Dreiecksmatrizen sind, folgt wegen

Lk+1 = LkLk

aus der Konvergenz der Lk, dass die Lk gegen die Einheitsmatrix konvergieren unddamit in

Ak = LkRk

die Elemente unterhalb der Hauptdiagonalen für k →∞ im Grenzwert verschwinden.Wir formulieren daher:

Algorithmus 2.8 (LR-Verfahren).Sei A eine reguläre m×m-Matrix; setze A := A1.Iteration: Für k = 1, 2, ... bilde die LR-Zerlegung von Ak (falls diese existiert),

Ak = LkRk,

und berechneAk+1 := RkLk.

Man stoppe die Iteration, falls die Komponenten von Ak+1 unterhalb der Diagonalenkleiner sind als eine vorgegebene Fehlerschranke.

Es stellt sich natürlich die Frage, ob das LR-Verfahren konvergiert. Wir wenden unsdaher nun der Konvergenzbetrachtung des LR-Verfahrens zu und formulieren folgendesResultat. Der Beweis findet sich im Anschluss.

Resultat 2.9 (Konvergenz des LR-Verfahrens).Für die Matrix A =: A1 ∈ Km×m seien folgende Voraussetzungen erfüllt:

1. A sei diagonalisierbar,

A = T diag(λ1, ..., λm)T−1,

wobei für T und für T−1 die LR-Zerlegungen (ohne Zeilenvertauschungen) exis-tieren mögen.

2. Die Eigenwerte von A lassen sich betragsmäßig ordnen gemäß

|λ1| > |λ2| > ... > |λm| > 0.


3. Das LR-Verfahren (ohne Zeilenvertauschungen)

Ak =: LkRk, Ak+1 := RkLk, k = 1, 2, ...,

sei durchführbar, d.h. in jedem k-ten Schritt existiere die LR-Zerlegung der Ma-trix Ak. Dann gilt

limk→∞

Ak = limk→∞

Rk =

λ1 ∗ . . . . . . ∗

λ2. . . .... . . . . . ...

. . . ∗0 λm

und

limk→∞

Lk = E.

Beweis: Wir führen nun den Beweis der Konvergenz des LR-Verfahrens unter denobigen Annahmen. Aus der Darstellung

A = TDT−1

mitD = diag(λ1, ..., λm)

folgt für die Potenzen Ak, k = 1, 2, ...

Ak = (TDT−1)k = TDkT−1.

Wenn für T und T−1 die LR-Zerlegungen

T = LTRT ,

T−1 = LT−1RT−1

existieren, so folgtAk = LTRTD

kLT−1RT−1 .

Mit A ist auch D regulär. In diesem Fall gilt

Ak = LTRT (DkLT−1D−k)DkRT−1 , k = 1, 2, ....

In der folgenden Aufgabe zeigen wir, dass in gewissen Fällen die FolgeDkLT−1D−k

k∈N

gegen die Einheitsmatrix strebt.

Aufgabe 2.10.Es gelte

|λ1| > |λ2| > ... > |λm| > 0.

Dann konvergiert die FolgeDkLT−1D−k

k=1,2,...

, D := diag(λ1, ..., λm),

geometrisch gegen die Einheitsmatrix:

DkLT−1D−k = E + Fk, k = 1, 2, ...,

limk→∞

Fk = 0.


Dieses Resultat verwenden wir nun, um das Verhalten der Matrixpotenzen Ak, k =1, 2, ..., zu untersuchen. Es folgt

Ak = LTRT (DkLT−1D−k)DkRT−1

= LTRT (E + Fk)DkRT−1

= LT (E +RTFkR−1T )RTD

kRT−1 .

Wir beachten, dass mitlimk→∞

Fk = 0

auchlimk→∞

RTFkR−1T = 0

gilt. Für genügend große k existiert somit die LR-Zerlegung der Matrix

E +RTFkR−1T =: LkRk.

Dabei giltlimk→∞

Lk = E = limk→∞

Rk,

wie man unmittelbar auslimk→∞

RTFkR−1T = 0

folgert.

Für hinreichend großes k folgt also für die Matrixpotenzen Ak die Darstellung

Ak = LT LkRkRTDkRT−1 .

In dieser Faktorisierung ist LT Lk eine untere Dreiecksmatrix mit normierter Diagonaleund RkRTD

kRT−1 eine obere Dreiecksmatrix. Also folgt aufgrund der Eindeutigkeitder LR-Zerlegung durch Vergleich mit Resultat 2.7:

Lk = LT Lk, Rk = RkRTDkRT−1 ,

wobei - wie oben gezeigt -limk→∞

Lk = limk→∞

Rk = E,

gilt. WegenLk = L−1

k−1Lk = L−1k−1L

−1T LT Lk = L−1

k−1Lk

und

Rk = RkR−1k−1 = RkRTD

kRT−1R−1T−1D

−(k−1)R−1T R−1

k−1

= RkRTDR−1T R−1

k−1

folgt somit

limk→∞

Lk = E

limk→∞

Rk = RTDR−1T


und damitlimk→∞

Ak = limk→∞

LkRk = RTDR−1T .

Dabei hat die Matrix RTDR−1T obere Dreiecksform, und in der Diagonalen stehen die

Diagonalelemente von D:

RTDR−1T =

λ1 ∗ . . . . . . ∗

λ2. . . .... . . . . . ...

. . . ∗0 λm

.

Insgesamt ist damit gezeigt, dass das LR-Verfahren in gewissen Fällen (nämlich unterobigen Annahmen an die Matrix A) iterativ sämtliche Eigenwerte von A liefert. Diesbeendet die Konvergenzuntersuchung.

Bemerkung 2.11.Ist die Matrix A positiv definit, so kann unter Verwendung der Cholesky-Zerlegung einesymmetrische Variante des LR-Verfahrens durchgeführt werden:

A =: A1,

Ak =: LkLHk , Ak+1 := LHk Lk, k = 1, 2, ....

Es ist zu bemerken, dass die Matrizen Ak alle postiv definit sind; folglich existiert injedem Iterationsschritt die Cholesky-Zerlegung.

Die wesentliche Schwäche des LR-Verfahrens liegt darin, dass die LR-Zerlegung nichtfür jede reguläre Matrix notwendig existiert bzw. ihre Berechnung numerisch instabilist. Wie wir in Abschnitt 1.4 gesehen haben, existiert aber bei regulärer Matrix stetseine QR-Zerlegung, die z.B. nach Algorithmus 1.27 berechnet werden kann. Analogzum LR-Verfahren erhalten wir so das von Francis vorgeschlagene QR-Verfahren:

Algorithmus 2.12 (QR-Verfahren).Sei A =: A1 eine reguläre m×m-Matrix.Iteration: Für k = 1, 2, ... zerlege Ak:

Ak =: QkRk,

wobei Qk unitär und Rk obere Dreiecksmatrix ist, und berechne

Ak+1 := RkQk.

Breche die Iteration ab, wenn die Komponenten von Ak+1 unterhalb der Diagonalendem Betrag nach kleiner sind als eine gegebene Fehlerschranke.

Zur Untersuchung des QR-Verfahrens gehen wir ähnlich wie beim LR-Verfahren vor.

Aufgabe 2.13.Man zeige, dass mit den in Algorithmus 2.12 gegebenen Matrizen Qi, Ri eine QR-Zerlegung der Matrixpotenzen Ak aufgebaut werden kann: Man beweise

Ak = QkRk, k = 1, 2, ...,


wobei

Qk := Q1Q2 · · ·Qk,

Rk := RkRk−1 · · ·R1

gesetzt wurde.

Es sei A diagonalisierbar mit dominantem Eigenwert

λ1 =: |λ1|eiϕ.

Es gilt wiederum

Ake1

λk1→ ρ1u1,

‖Ake1‖|λk1|

→ ‖ρ1u1‖ für k →∞.

Daraus folgt

e−ikϕAke1

‖Ake1‖−→ ρ1u1

‖ρ1u1‖,

e−i(k−1)ϕ Ake1

‖Ak−1e1‖−→ λ1

ρ1u1

‖ρ1u1‖für k →∞,

falls der kanonische Einheitsvektor e1 in Bezug auf den zu λ1 gehörenden Eigenvektoru1 eine nichtverschwindende Komponente ρ1 hat. Mit

Rk = (r(k)ij )m×m,

Qk =

q(k)1 q

(k)2 . . . q

(k)m

, k = 1, 2, ...

folgtAke1 = r

(1)11 · r

(2)11 · · · r

(k)11 q

(k)1 , ‖Ake1‖ = |r(1)

11 · · · r(k)11 |,

und falls wir

r(1)11 · · · r

(k)11 := |r(1)

11 · · · r(k)11 | · eiψk k = 1, 2, ...,

q(k)1 =: (q

(k)11 , ..., q

(k)m1)t k = 1, 2, ...,

u1 =: (η1, ...ηm)t

setzen, ergibt sich für ν = 1, ...,m:

ei(ψk−kϕ)q(k)ν1

k→∞−→ ρ1ην‖ρ1u1‖

,

ei(ψk−1−(k−1)ϕ)r(k)11 q

(k)ν1

k→∞−→ λ1ρ1ην‖ρ1u1‖

.

Für ην 6= 0 erhalten wir schließlich unter Verwendung der Phasenfaktoren eiφk mit

φk := ϕ+ ψk−1 − ψk


die Konvergenzaussageeiφkr

(k)11 −→ λ1 für k →∞.

Die links oben stehenden Komponenten der Matrizen Rk konvergieren demnach nurbis auf einen Phasenfaktor gegen λ1. (Wählt man hierbei in jedem Schritt die QR-Zerlegung so, dass die Matrizen Rk reelle positive Diagonalelemente haben, so giltψk = 0, k = 1, 2, ..., und r(k)

11 → |λ1| für k →∞). Dieses für das QR-Verfahren typischeKonvergenzverhalten zeigt sich auch im folgenden Konvergenzsatz:

Satz 2.14 (Konvergenz des QR-Verfahrens).Für die Matrix A =: A1 ∈ Km×m seien folgende Voraussetzungen erfüllt:

1. A sei diagonalisierbarA = T diag(λ1, ..., λm)T−1,

wobei für T−1 die LR-Zerlegung vorausgesetzt wird:

T−1 = LT−1RT−1 .

2. Die Eigenwerteλj =: |λj|eiϕj , j = 1, ...,m,

lassen sich betragsmäßig ordnen gemäß

|λ1| > |λ2| > ... > |λm| > 0.

Wählt man in jedem Schritt des QR-Verfahrens

Ak =: QkRk, Ak+1 := RkQk, k = 1, 2, ...,

die obere Dreiecksmatrix Rk derart, dass in der Diagonalen reelle positive Ele-mente stehen, so gilt für k →∞

Qk −→ diag(eiϕ1 , eiϕ2 , ..., eiϕm),

(r(k)11 , r

(k)22 , ..., r

(k)mm) −→ (|λ1|, |λ2|, ..., |λm|),

und damita

(k)ij −→

0 für i > j,λi für i = j.

(Hierbei haben wir Ak = (a(k)ij )m×m, Rk = (r

(k)ij )m×m gesetzt.)

Beweis: Wir führen den Beweis der Konvergenz des QR-Verfahrens unter obigenAnnahmen. In Aufgabe 2.13 haben wir gezeigt, dass die Matrixpotenzen Ak die QR-Zerlegungen

Ak = QkRk mitQk = Q1Q2 · · ·Qk undRk = RkRk−1 · · ·R1, k = 1, 2, ...,

besitzen, und diese Zerlegungen sind eindeutig bestimmt, falls für Rk positive Diagonal-elemente vorgeschrieben werden. Im folgenden leiten wir eine alternative Darstellungder Matrizen Qk und Rk ab.


Wir setzen

D = diag(λ1, λ2, ..., λm),

∆ = diag(eiϕ1 , eiϕ2 , ..., eiϕm).

WegenA = TDT−1

gilt auchAk = TDkT−1,

und unter Verwendung der QR-Zerlegung von T

T = QTRT

(RT besitze positive Diagonalelemente!) und der LR-Zerlegung von T−1,

T−1 = LT−1RT−1 ,

ergibt sichAk = QTRTD

kLT−1RT−1 .

FürL∗k := DkLT−1D−k

gilt wegen Aufgabe 2.10L∗k → E für k →∞,

da LT−1 eine untere Dreiecksmatrix mit normierter Diagonale ist und da die Eigenwertevon A nach Voraussetzung betragsmäßig getrennt liegen. Bildet man die QR-Zerlegungvon RTL

∗k gemäß

RTL∗k = Q∗kR

∗k,

wobei R∗k in der Diagonale wiederum positive Elemente besitze, so erhalten wir schließ-lich

Ak = QTRTL∗kD

kRT−1 = QTQ∗kR∗kD

kRT−1 .

Hiermit haben wir eine weitere Zerlegung der Matrix Ak in das Produkt einer unitärenMatrix QTQ

∗k und einer oberen Dreiecksmatrix R∗kDkRT−1 gefunden. Das Argument in

der komplexen Polardarstellung der Diagonalelemente von R∗kDkRT−1 ist allein durchDk und die Diagonalelemente ρ1, ρ2, ..., ρm von RT−1 bestimmt, da R∗k nur positiveDiagonalelemente besitzt. Wir setzen

ρj =: |ρj|eiψj , j = 1, ...,m,

und∆ = diag(eiψ1 , eiψ2 , ..., eiψm).

Dann hat∆−1∆−kR∗kD

kRT−1

in der Diagonalen nur positive Elemente. Da die Ri nach Voraussetzung nur positi-ve Diagonalelemente besitzen, hat auch Rk nur positive Elemente in der Diagonalen.Aufgrund der Eindeutigkeitsaussage für die QR-Zerlegung folgt

QTQ∗k∆

k∆ = Qk = Q1Q2 · · ·Qk


und∆−1∆−kR∗kD

kRT−1 = Rk = RkRk−1 · · ·R1.

Unter Verwendung dieser Identitäten werden wir die Konvergenzaussagen ableiten kön-nen. Zunächst gilt

Qk = Q−1k−1Qk

= (QTQ∗k−1∆k−1∆)−1QTQ

∗k∆

k∆

= ∆−1∆−(k−1)(Q∗k−1)−1Q∗k∆k∆.

AusRTL

∗k = Q∗kR

∗k

undL∗k → E für k →∞

folgt wegen der Eindeutigkeit der QR-Zerlegung (da sowohl RT als auch R∗k in derDiagonale positive Elemente besitzen)

Q∗k → E, R∗k → RT für k →∞.

Wegen Q∗k → E können wir auf

∆−(k−1)(Q∗k−1)−1Q∗k∆k → ∆ für k →∞

und weiter aufQk → ∆−1∆∆ = ∆ für k →∞

schließen.Die Konvergenzaussage für die oberen Dreiecksmatrizen Rk erhält man aus der Dar-stellung

Rk = RkR−1k−1

= ∆−1∆−kR∗kDkRT−1R−1

T−1D−(k−1)(R∗k−1)−1∆k−1∆

= ∆−1∆−kR∗kD(R∗k−1)−1∆k−1∆

Wegen

R∗kD(R∗k−1)−1 → RTDR−1T =

λ1 ∗ . . . ∗

. . . . . . .... . . ∗

0 λm

, k →∞,

konvergiert die Diagonale von ∆−kR∗kD(R∗k−1)−1∆k−1 gegen die Beträge der Eigenwer-te, woraus wegen der Diagonalgestalt der Matrix ∆ die im Satz behauptete Konver-genzaussage für die Matrizen Rk folgt.Die Konvergenzaussage für die Matrizen Ak erhält man schließlich direkt aus der Dar-stellung

Ak = QkRk, k = 1, 2, ...,

unter Verwendung der schon bewiesenen Konvergenzaussagen für die Matrizen Qk undRk. Dies beendet den Beweis der Konvergenz des QR-Verfahrens.

Wir schließen diesen Abschnitt mit einigen Bemerkungen.


(1) Die für die Konvergenzaussagen 2.9 und 2.14 wesentliche Forderung an die Ma-trix A ist die Eigenschaft, dass A diagonalisierbar ist. Die anderen Forderungen,insbesondere die Forderung

|λ1| > |λ2| > ... > |λm|,

können abgeschwächt werden, ohne dass die Konvergenzaussage wesentlich ein-geschränkt wird. (Wir verweisen auf Wilkinson: The Algebraic Eigenvalue Pro-blem, Oxford, Clarendon Press, 1965). Es ist allerdings darauf hinzuweisen, dassdas LR-Verfahren selbst bei theoretisch gesicherter Konvergenz zusammenbre-chen kann, da die Berechnung der LR-Zerlegung in einem Iterationsschritt aufnumerische Instabilität führen kann.

(2) Vom Standpunkt der Praxis aus kann man sich bei Hermiteschen Matrizen Aimmer auf den Spezialfall reeller Matrizen beschränken. Denn, falls A nicht reellist, so kann man komplexe Arithmetik dadurch vermeiden, dass man A zerlegtin Real- und Imaginärteil,

A = A1 + iA2

und anstelle von A die Matrix

A =

[A1 −A2

A2 A1

]betrachtet. Es ist einfach einzusehen, dass ein Eigenwert λ von A ein zweifacherEigenwert von A ist. (Verifizieren Sie diese Aussage!)

(3) Der unverhältnismäßig hohe numerische Aufwand von O(m3) Rechenoperationenin jedem Schritt der beiden Verfahren kann dadurch vermindert werden, dass mandie vorliegende Matrix zuerst mit einer der im folgenden Abschnitt 2.5 beschrie-benen Methoden auf einfachere Gestalt (Tridiagonalform bzw. Hessenberg-Form)bringt. Wesentlich ist, dass diese spezielle Form bei LR- bzw. QR-Verfahren in-variant bleibt, so dass der Aufwand pro Iterationsschritt auf O(m) bzw. O(m2)Punktoperationen reduziert wird.

(4) Auch bei Anwendung des LR- bzw. QR-Verfahrens auf eine Matrix A(=: A1) mitspezieller Bandgestalt haben die in den Verfahren berechneten Matrizen Ak, k =1, 2, ..., dieselbe Bandgestalt, so dass auch hier der Aufwand pro Iterationsschrittvermindert wird. Dies zeigt die folgende Aufgabe:

Aufgabe 2.15.Man zeige

1. Ist A1 =: (aij)m×m eine Bandmatrix mit Bandbreite d, d.h. gilt

aij = 0 für |i− j| ≥ d,

so sind beim LR-Verfahren die Ak, k = 1, 2, ..., ebenfalls Bandmatrizender Bandbreite d. Insbesondere bleibt etwa Tridiagonalgestalt (Fall d = 2)erhalten (Tridiagonalgestalt siehe Abschnitt 2.5).

2. Ist A1 eine reguläre Hermitesche Bandmatrix mit Bandbreite d, so sind esbeim QR-Verfahren die Ak, k = 1, 2, ..., ebenfalls.


3. Ist A1 =: (aij)m×m eine reguläre Matrix mit unterem Band der Breite d,d.h., gilt

aij = 0 für i− j ≥ d,

so sind es beim LR-Verfahren die Ak, k = 1, 2, ..., ebenfalls. Insbesonderebleibt die obere Hessenberg-Form (Fall d = 2) erhalten ( obere Hessenberg-Form siehe Abschnitt 2.5).

4. Ist A1 eine reguläre Matrix mit unterem Band der Breite d, so sind es beimQR-Verfahren die Ak, k = 1, 2, ..., ebenfalls.

Im Folgenden behandeln wir abschließend shift-Methoden in Verbindung mit LR- undQR-Verfahren.

In den Konvergenzsätzen 2.9 und 2.14 hatten wir gesehen, dass in den Matrizen Akdie Elemente unterhalb der Diagonalen gegen Null und die Diagonalelemente gegendie Eigenwerte der Ausgangsmatrix streben. Man darf also erwarten, dass das Elementa

(k)mm eine von Schritt zu Schritt bessere Näherung für den Eigenwert λm wird. Shift-

Methoden für LR- und QR-Verfahren werden gemäss folgendem Schema gebildet:

Seien σk, k = 1, 2, ..., Näherungen für λm. Man bilde für k = 1, 2, ... (mit A =: A1)

Ak − σkE =: LkRk, Ak+1 := RkLk + σkE (LR-Verfahren mit shift)

bzw.

Ak − σkE =: QkRk, Ak+1 := RkQk + σkE (QR-Verfahren mit shift).

Folgende Strategien haben sich in der Praxis bewährt (wir setzen Ak = (a(k)ij )m×m):

Strategie a: σk = a(k)mm.

Strategie b: σk wird gewählt als derjenige Eigenwert der 2× 2-Matrix[a

(k)m−1,m−1 a

(k)m−1,m

a(k)m,m−1 a

(k)m,m

]

der am nächsten bei a(k)mm liegt.

Man kann zeigen, dass die Strategie b, falls sie auf eine (nicht-zerlegbare) HermitescheTridiagonalmatrix angewendet wird, mindestens quadratische Konvergenz für

a(k)m,m−1 −→ 0,

a(k)m,m −→ λm für k →∞

liefert; in vielen Fällen kann sogar kubische Konvergenz gesichert werden.

Zusammenfassung:

In diesem Abschnitt wurden Ihnen zwei vom Typ ähnliche Iterationsverfahren zur si-multanen Berechnung aller Eigenwerte einer Matrix beschrieben. Für beide Verfahrensind unter relativ allgemeinen Voraussetzungen globale Konvergenzaussagen bekannt.In der Praxis werden diese Verfahren üblicherweise nur unter Verwendung von shift-Techniken benützt, um lokal eine höhere Konvergenzordnung zu erhalten.


2.5 Die Reduktionsmethode von Householder aufHessenberg- bzw. Tridiagonalform (Ergänzung)

Im vorangehenden Abschnitt hatten wir Methoden kennengelernt, die es gestatten,unter gewissen einschränkenden Bedingungen die Eigenwerte einer Matrix A in ge-schickter Weise zu berechnen. Wir wenden uns nun dem Problem zu, wie man für einegegebene Matrix A die sogenannte Hessenberg-Form bzw. für eine Hermitesche Matrixdie Hermitesche Tridiagonalgestalt erreichen kann. Damit lässt sich der Aufwand desLR- bzw. des QR-Verfahrens erheblich reduzieren.

Eine Matrix A hat obere Hessenberg-Form, falls sie von folgender Bauart ist:

A =

∗ . . . . . . . . . ∗∗ . . . ...

. . . . . . .... . . . . . ∗

0 ∗ ∗

.

Eine Matrix A hat Tridiagonalgestalt, falls sie von folgender Bauart ist:

A =

∗ ∗ 0

∗ . . . . . .. . . . . . . . .

. . . . . . ∗0 ∗ ∗

.

Bei dem oben formulierten Problem handelt es sich also um Folgendes: Gegeben seieine Matrix A ∈ Km×m (K = R oder K = C). Da Ähnlichkeitstransformationen

A 7−→ T−1AT, wobei T regulär,

und insbesondere unitäre Transformationen

A 7−→ UHAU, wobei U unitär, d.h. UH = U−1,

die Eigenwerte von A invariant lassen, kann man versuchen, möglichst einfache Trans-formationsmatrizen zu finden, dieA auf Hermitesche Tridiagonalform oder auf Hessenberg-Form bringen. Es wird sich zeigen, dass man mit einer endlichen Kette solcher Trans-formationen dieses Problem lösen kann:

Sei

A(0) := A,

A(1) := UH1 A

(0)U1,...

A(k) := UHk A

(k−1)Uk;

dann hat bei geeigneter Wahl von U1, ..., Uk die EndmatrixA(k) die gewünschte Hessenberg-oder Hermitesche Tridiagonalform. Die Länge k der Kette hängt von der Zeilenzahl vonA und der Bauart der verwendeten Transformationsmatrizen Uν , ν = 1, . . . , k, ab.


Aufgabe 2.16.Es sei

A =

2 3 13 4 51 5 6

.1. Man konstruiere eine Householder-Matrix

Hw := E − 2wwH , wHw = 1,

welche den Vektor (3, 1)T in die Richtung des ersten Einheitsvektors im R2 spie-gelt:

Hw :

[31

]7−→ α

[10

].

2. Man bilde

U :=

1 0 000 Hw

und zeige, dass

A(1) := UHAU

Hermitesche Tridiagonalform hat.

Bei dieser Aufgabe haben wir schon das Prinzip der Reduktionsmethode von House-holder kennengelernt. Wir betrachten nun eine beliebige m-reihige Matrix A, die wirauf obere Hessenberg-Form transformieren wollen. Es soll gezeigt werden, dass dies mitm − 2 unitären Transformationen, die aus Householder-Spiegelungen aufgebaut sind,zu erreichen ist.

Wir gehen davon aus, dass durch i − 1 Schritte (i ≥ 2) von „links oben her“ schonein Stück obere Hessenberg-Form erzeugt ist, d.h. die Ausgangsmatrix A = A(0) seiunitär ähnlich einer Matrix A(i−1) des Typs:

A(i−1) = UHi−1 · · · UH

1 A(0)U1 · · · Ui−1 =

...

Bi... Dm−i...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−i

......

;

Bi : i× i-Matrix in oberer Hessenbergform;

Cm−i : (m− i)× (m− i)-Matrix;

bi ∈ Km−i (K = R oder K = C);Dm−i : i× (m− i)-Matrix.


Nach Abschnitt 1.4, in dem wir die QR-Zerlegung behandelt haben, existiert eineHouseholdertransformation

Hi := E − 2wiwHi , wHi wi = 1,

auf dem Raum Cm−i, die den Vektor bi in ein skalares Vielfaches des kanonischenEinheitsvektors e1 ∈ Cm−i spiegelt:

Hi : bi 7−→ αie1 ∈ Cm−i.

Wie man bei gegebenem Vektor bi den entsprechenden Vektor wi numerisch am güns-tigsten bestimmt, haben wir bei der Behandlung der QR-Zerlegung gezeigt. Hier gehtes darum, die Transformationsmatrix Ui zu definieren. Wir setzen (entsprechend derEinteilung der Matrix A(i−1)):

Ui :=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

.

Da Hi Hermitesch und unitär ist,

Hi = HHi = H−1

i ,

gilt dasselbe auch für UiUi = UH

i = U−1i .

Wir betrachten jetzt die unitäre Ähnlichkeitstransformation

A(i−1) 7−→ UHi A

(i−1)Ui = UiA(i−1)Ui =: A(i).


Aufgrund der Blockstruktur der Matrizen A(i−1) und Ui ergibt sich

A(i) =

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

·

...

Bi... Dm−i...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−i

......

·

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

·

...

Bi... Dm−iHi...

. . . . . . . . . . . . . . . . . ....

...

O ... bi... Cm−iHi

......

=

...

Bi... Dm−iHi...

. . . . . . . . . . . . . . . . . .... αi

...

O ... 0... HiCm−iHi

......

...... 0

...

=:

...

Bi+1... Dm−i−1...

. . . . . . . . . . . . . . . . . ....

...

O ... bi+1... Cm−i−1

......

,

wobei die (i+ 1)× (i+ 1)-Matrix Bi+1 obere Hessenberg-Form besitzt.

Wir erkennen somit, dass jedem-reihige Matrix A durchm−2 Ähnlichkeitstransforma-tionen mittels unitärer Transformationsmatrizen auf obere Hessenberg-Form gebracht


werden kann:

A 7−→ Um−2Um−1 · · · U1︸︷︷︸=UH

AU1U2 · · · Um−2︸︷︷︸=:U

= A(m−2) =: A,

UHU = E, A =

∗ . . . . . . . . . ∗∗ . . . ...

. . . . . . .... . . . . . ∗

0 ∗ ∗

.

Ist A Hermitesch, so liefert der Transformationsprozess wegen

AH = (UHAU)H = UHAHU = UHAU = A

sogar in A eine Hermitesche Tridiagonalmatrix.

Resultat 2.17 (Reduktion auf obere Hessenberg-Form).Eine beliebige m-reihige Matrix A lässt sich mit Hilfe von m−2 Householder-Transfor-mationen auf eine obere Hessenberg-Form bringen. Ist A Hermitesch, so liefert dieserTransformationsprozess sogar eine Hermitesche Tridiagonalmatrix.

Algorithmus 2.18 (Reduktionsverfahren nach Householder).Start: Es sei

A(0) := (a(0)νµ )ν,µ=1,...,m := A = (aνµ)ν,µ=1,...,m.

Iteration: Für i = 1, ...,m− 2 bilde man

A(i) = (a(i)νµ)ν,µ=1,...,m gemäß

A(i) := UiA(i−1)Ui,

wobei

Ui :=

1 0...

. . . ... O0 1

.... . . . . . . . . . . . . . . . . .

...

O ... Hi...

Die (m− i)-reihige Matrix Hi ist eine Householder-Spiegelung, die wir mit dem Algo-rithmus 1.27 durch die Forderung erhalten, dass Hi die i-te Spalte von A(i−1) unterhalbder Diagonalen auf ein skalares Vielfaches des ersten Einheitsvektors von Cm−i spiegelt.

Bemerkung 2.19.Es ist naheliegend zu fragen, ob mit einer endlichen Kette solcher Ähnlichkeitstrans-formationen

A(0) := A −→ A(1) := T−11 A(0)T1 −→ A(2) := T−1

2 A(1)T2 ...


die volle Jordansche Normalform, d.h. insbesondere bei Hermiteschen Matrizen dieDiagonalform erreichbar ist. Wir machen uns klar, dass dies, wenn die Lösung des Ei-genwertproblems noch nicht bekannt ist, wovon wir ja ausgehen wollen, nicht möglichist. Der Grund ist der folgende: Selbst wenn wir von einer Matrix A mit ganzzahligenElementen aνµ, ν, µ = 1, ...,m ausgehen, können die Eigenwerte als Nullstellen einesPolynom m-ten Grades irrational sein und auch nicht durch einen endlichen arith-metischen Ausdruck, der nur die Grundrechenarten und die Quadratwurzelrechnungverwendet, berechnet werden. (In der Sprache der Algebra ausgedrückt: Die Wurzelneines Polynoms m-ten Grades, m > 2, liegen sogar bei ganzzahligen Koeffizienten i. A.nicht in einem Erweiterungskörper von Q, der durch Adjunktion von Quadratwurzelnentsteht.)Es ist also prinzipiell nicht möglich, mit Reduktionsmethoden des betrachtetenTyps die Jordan-Normalform zu erreichen. Deswegen war es auch sinnvoll, dass wiruns mit der Hessenberg- bzw. der Hermiteschen Tridiagonalform begnügten.

Zusammenfassung:

In diesem Abschnitt wurde Ihnen eine Methode vorgestellt, wie beliebige Matrizenauf obere Hessenberg-Form und insbesondere Hermitesche Matrizen auf HermitescheTridiagonalform transformiert werden können. Damit erhalten die Verfahren, die Sieim vorangehenden Abschnitt kennengelernt haben, erst ihre wahre Bedeutung, da Sienunmehr Algorithmen für die Berechnung der Eigenwerte beliebiger Matrizen in derHand haben.

Kapitel 3

Lineare Optimierung

Definition 3.1 (lineares Optimierungsproblem).Gesucht ist ein Extremum - das kann ein Maximum oder ein Minimum sein - derZielfunktion

z(x) =n∑k=1

ckxk, (c1, . . . , cn ∈ R sind gegeben)

wobei die m Nebenbedingungen∑n

k=1 aikxk ∼ bi, (i = 1, ...,m) erfüllt sein müssen.Dabei steht ∼ für eines der Zeichen =, ≤ oder ≥.

Definition 3.2 (Standardmodell).Ein Standardmodell ist ein lineares Optimierungsproblem, bei dem das Maximum derZielfunktion

z(x) =n∑k=1

ckxk

gesucht wird, wobei die m Nebenbedingungen∑n

k=1 aikxk ≤ bi, (i = 1, ...,m) sowiexk ≥ 0, (k = 1, ..., n) erfüllt sein müssen.

Satz 3.3.Jedes lineare Optimierungsproblem lässt sich in ein Standardmodell überführen, indemman die folgenden Umforungen durchführt:

1. Eine Nebenbedingung in Gleichungsform wird durch 2 Ungleichungen mit ≤ und≥ ersetzt.

2. Eine ≥-Ungleichung wird mit (−1) multipliziert, damit sich das Ungleichheitszei-chen umdreht.

3. Ein Minimierungsproblem wird zu einem Maximierungsproblem, indem man dieZielfunktion mit (−1) multipliziert.

4. Variablen xk, die sowohl negativ also auch positiv sein können, werden als Diffe-renz zweier neuer nicht-negativer Variablen geschrieben. Soll etwa xk ≥ 0 nichtgelten, so schreibt man xk = yk − yk mit yk, yk ≥ 0.

Definition 3.4 (Normalform).Ein Standardmodell liegt in Normalform vor, falls bi ≥ 0 gilt für i = 1, ...,m.

54

KAPITEL 3. LINEARE OPTIMIERUNG 55

Definition 3.5 (Zulässiger Bereich).Die Teilmenge des Rn, in der alle Nebenbedingungen eines linearen Optimierungspro-blems erfüllt sind, heißt zulässiger Bereich.

In der Regel ist der zulässige Bereich ein n-dimensionales Vieleck (Polyeder).

Satz 3.6 (Hauptsatz der linearen Optimierung).Falls das lineare Optimierungsproblem eine optimale Lösung besitzt, dann gibt es ins-besondere eine optimale Lösung in einem Eckpunkt des zulässigen Bereiches.

Folgerung 3.7.Das bedeutet, dass es genügt, nur die zulässigen Ecken als Kandidaten für die optimaleLösung des Optimierungsproblems zu betrachten.

Definition 3.8 (Schlupfvariable).Durch die Einführung der Schlupfvariablen y1, . . . , ym werden die Ungleichungen

n∑k=1

aikxk ≤ bi (i = 1, . . . ,m)

zu Gleichungenn∑k=1

aikxk + yi = bi mit Nebenbedingung yi ≥ 0 (i = 1, . . . ,m).

Die Variablen x1, . . . , xn heißen Struktur- oder Problemvariable; die Variablen y1, . . . , ymheißen Schlupfvariable.

Durch das Einführen von Schlupfvariablen können die Nebenbedingungen eines Linea-ren Optimierungsproblems

∑nk=1 aikxk ≤ bi (i = 1, ...,m) als lineares Gleichungssystem

geschrieben werden:

a11x1 + a21x2 + . . . + a1nxn + y1 = b1

a21x1 + a22x2 + . . . + a2nxn + y2 = b2...

......

......

...am1x1 + am2x2 + . . . + amnxn + ym = bm

.

In Matrixschreibweise erhält man

a11 a21 . . . a1n 1 0 . . . 0a21 a22 . . . a2n 0 1 . . . 0...

......

...... . . . ...

am1 am2 . . . amn 0 0 . . . 1

x1...xny1...ym

=

b1

b2...bm

(3.1)

oder kürzerAx+ y = b, bzw. (A|E)

(xy

)= b.

Dieses besitzt n+m Variablen und m Gleichungen. Es ist Rg(A|E) = m, da die letztenm Spalten linear unabhängig sind, und der Lösungsraum ist n dimensional.


Der zulässige Bereich eines Standardmodells in Normalform (vgl. Definition 3.2 undDefinition 3.4) besteht aus den Lösungen des Gleichungssystems, für welche die Bedin-gungen xk ≥ 0, k = 1, ..., n und yi ≥ 0, i = 1, ...,m erfüllt sind.

Definition 3.9 (Basislösung, Basisvariable).Eine Basislösung erhält man, indem man jeweils n der Variablen x1, ..., xn, y1, ..., ym auf

Null setzt und das Gleichungssystem (A|E)

(xy

)= b löst, wobei die entsprechenden

m Spalten von (A|E) linear unabhängig sein müssen. Diejenigen Variablen, die dabeinicht Null gesetzt wurden, heißen Basisvariablen, weil sie in die jeweilige Basislösungeingehen. Die Variablen, die Null gesetzt wurden, heißen Nicht-Basisvariablen.

Basislösungen entsprechen den Ecpunkten des zulässigen Bereichs.

Algorithmus 3.10.Naiv-rechnerische Herangehensweise an die Lösung eines Standardmodells.

1. Stelle das Gleichungssytem (A|E)

(xy

)= b auf.

2. Setze jeweils n Variablen gleich Null und löse das Gleichungssystem, sofern dieentsprechenden verbleibenden m Spalten linear unabhängig sind. Jede dieser Lö-sungen ist eine Basislösung.

3. Überprüfe die Basislösungen auf Zulässigkeit. Das ist der Fall, wenn xk ≥ 0,k = 1, ..., n und yi ≥ 0, i = 1, ...,m.

4. Setze die zulässigen Basislösungen in die Zielfunktion ein.

5. Bestimme die Basislösung, an der die Zielfunktion maximal wird.

Algorithmus 3.10 bedeutet einen sehr hohen Rechenaufwand, wenn die Anzahl n der

Strukturvariablen oder die Anzahl der Nebenbedingungen groß wird, weil(n+mn

)Basislösungen berechnet und auf Zulässigkeit überprüft werden müssen. Der Simplex-Algorithmus umgeht dieses Problem, indem er von vornherein nur zulässige Basislösun-gen berechnet und hierbei zielstrebig vorgeht, indem er den folgenden Satz beachtet:

Satz 3.11.Ist eine zulässige Basislösung eines linearen Optimierungsproblems nicht optimal, sogibt es eine benachbarte Basislösung (d.h. eine Basislösung zu einem benachbarten Eck-punkt), in der die Zielfunktion einen besseren Wert annimmt.

Der Übergang zu einer benachbarten Basislösung geschieht im Simplex-Algorithmusdadurch, dass jeweils eine Basisvariable gegen eine Nicht-Basisvariable ausgetauschtwird. Dieser Austausch von Variablen geschieht durch Operationen, die schon aus demGauß-Verfahren bekannt sind.

Definition 3.12.Das Ausgangstableau für den Simplex-Algorithmus erhält man aus Gleichung (3.1),indem man als letzte Zeile die Zielfunktionszeile anfügt, wobei die Koeffizienten ck


jeweils mit (−1) multipliziert werden. Da die Zielfunktion nicht von den Schlupfvaria-blen y1, ..., ym abhängt, steht in den entsprechenden Spalten jeweils eine 0. In der erstenSpalte wird vermerkt, welche die aktuellen Basisvariablen sind.

aktuelle x1 x2 . . . xn y1 y2 . . . ym rechte SeiteBasisvar.

y1 a11 a12 . . . a1n 1 0 . . . 0 b1

y2 a21 a22 . . . a2n 0 1 . . . 0 b2...

......

......

... . . . ......

ym am1 am2 . . . amn 0 0 . . . 1 bm−c1︸︷︷︸=:z1

−c2︸︷︷︸=:z2

. . . −cn︸︷︷︸=:zn

0︸︷︷︸=:zn+1

0︸︷︷︸=:zn+2

. . . 0︸︷︷︸=:zn+m

0

Im Ausgangstableau sind die Basisvariablen durch die Schlupfvariablen y1, ..., ym ge-geben, daher sind alle Strukturvariablen Null und dies entspricht der Basislösung imKoordinatenursprung. Für diese Basislösung gilt y1 = b1, ..., ym = bm, d.h. diese Ba-sislösung ist zulässig, falls b1, ..., bm ≥ 0. Rechts unten im Ausgangstableau steht derentsprechende Wert der Zielfunktion z(x) = 0, da ja alle xk = 0 sind.

Algorithmus 3.13 (Der Simplex-Algorithmus).Voraussetzung:xk ≥ 0 und bi ≥ 0 für alle k = 1, . . . , n und i = 1, . . . ,m, d.h. das Optimierungsproblemliegt als Standardmodell in Normalform vor.

1. Stelle das Ausgangstableau gemäß Def. 3.12 auf.

2. Auswahl der Pivotspalte l: Wähle als Pivotspalte diejenige Spalte, die in der Ziel-funktionszeile den betragsmäßig größten negativen Wert zl < 0 aufweist.

3. Auswahl der Pivotzeile p:

(i) Berechne für jede Zeile j den Wert bjajl

, sofern ajl > 0.

(ii) Falls ajl ≤ 0 für alle j = 1, . . . ,m, so existiert keine optimale Lösung, daxl beliebig groß gewählt werden kann und hierdurch die Zielfunktion beliebiggroß wird.

(iii) Falls ajl > 0 für mindestens eine Zeile j, so wähle unter diesen Zeilendiejenige aus (→ Zeile p), für die der Quotient bj

ajlminimal wird.

4. Austausch der Variablen:

(i) Tausche diejenige Basisvariable, in deren Spalte der p-te Einheitsvektor ep ∈Rm+1 steht, gegen die Nichtbasisvariable in der l-ten Spalte aus.

(ii) Addiere zu jeder Zeile j 6= p das − ajlapl

-fache der p-ten Zeile.

(iii) Addiere zur Zielfunktionszeile das − zlapl︸︷︷︸>0

−fache der p-ten Zeile.

(iv) Dividiere die p-te Zeile durch apl.


Bemerkungen:

• Für die neue ”rechte Seite” bneu gilt die Formel bneuj = baltj −ajlapl· baltp . So-

mit wird durch 3.(iii) gewährleistet, dass bneuj ≥ 0 gilt, denn die Wahl desminimalen Quotienten impliziert:

baltj −ajlapl· baltp = ajl︸︷︷︸

>0

·( baltjajl−baltpapl︸︷︷︸

≥0

)≥ 0

• Durch die Aktionen 4.(ii)-4.(iv) wird in der l-ten Spalte mittels Zeilenum-formung der Einheitsvektor ep ∈ Rm+1 erzeugt. Man zeigt induktiv, dass derWert rechts unten im Tableau stets der Wert der Zielfunktion an der ak-tuellen Basislösung ist. Durch 4.(iii) wird die Zielfunktion in jedem Schrittvergrößert (es sei denn, das Optimalitätskriterium greift).

5. Überprüfung des Abbruchkriteriums:Falls alle Werte der letzten Zeile nichtnegativ sind, lies den optimalen Wert derZielfunktion rechts unten im Tableau ab. Eine optimale (Basis-)Lösung erhältman, indem man die aktuellen Nicht-Basisvariablen auf 0 und die aktuellen Ba-sisvariablen auf die aktuellen b1, . . . , bm setzt (in der durch die aktuellen Basis-spalten vorgegebenen Reihenfolge).Der Algorithmus ist beendet.Falls es in der letzten Zeile negative Werte gibt, so ist das Optimum noch nicht er-reicht. Ersetze darum das alte Tableau durch das neue und durchlaufe den obigenAlgorithmus ab 2.

Wenn das Standardmodell nicht in Normalform vorliegt, ist die Basislösung 0 nichtzulässig. In diesem Fall muss vor dem Simplex-Algorithmus eine Vorphase durchgeführtwerden, in der eine zulässige Basislösung gesucht wird.

Beispiel 3.14.Eine Fabrik kann zwei Typen A und B eines Produkts unter folgenden Bedingungenherstellen:

Produkt Typ A Typ B maximal möglichStück pro Tag x1 x2 100 StückArbeitszeit pro Stück 4 1 160 StundenKosten pro Stück 20 10 1100 EURGewinn pro Stück 120 40

Wie müssen x1 und x2 gewählt werden, damit der Gewinn maximal wird? Dabei mussoffenbar der lineare Ausdruck

z(x1, x2) := 120x1 + 40x2

zu einem Maximum gemacht werden unter den linearen Nebenbedingungen

x1 + x2 ≤ 1004x1 + x2 ≤ 160 , x1 ≥ 0, x2 ≥ 0.

20x1 + 10x2 ≤ 1100


Lösung des Beispiels:

y1 1 1 1 0 0 100y2 4 1 0 1 0 160y3 20 10 0 0 1 1100−120 −40 0 0 0 0

120 > 40 ⇒ erste Spalte wird Pivotspalte

b1

a11

= 100,b2

a21

= 40,b3

a31

= 55 : 40 minimal

⇒ a21 = 4 Pivotelement

y1 0 3/4 1 −1/4 0 60x1 1 1/4 0 1/4 0 40y3 0 5 0 −5 1 300

0 −10 0 30 0 4800

zweite Spalte wird Pivotspalte (einziger negativer Eintrag unter den aktuellen cj)

b1

a12

= 80,b2

a22

= 160,b3

a32

= 60 : 60 minimal

⇒ a32 = 5 Pivotelement

y1 0 0 1 1/2 −3/20 15x1 1 0 0 1/2 −1/20 25x2 0 1 0 −1 1/5 60

0 0 0 20 2 5400

alle aktuellen cj ≥ 0 ⇒ Optimalität erreicht

Optimum: x1 = 25, x2 = 60Gewinn: 5400 Euro

Interpretation: y2 = y3 = 0 bedeutet 4x1 + x2 = 160 und 20x1 + 10x2 = 1100, d.h.Arbeitszeit und Kosten sind voll ausgeschöpft. Hingegen besteht bei der Stückzahlx1 + x2 = 85 noch eine Reserve von y1 = 15.

Kapitel 4

Fehleranalyse

4.1 Einleitung

In diesem Paragraphen beschäftigen wir uns mit Fehleruntersuchungen. An verschiede-nen Stellen dieses Kurses hatten wir schon auf diesen Teil verwiesen und eine detaillierteAnalyse der möglichen Fehlerquellen und deren Auswirkungen auf numerische Resul-tate angekündigt. Um Motivation für unser weiteres Vorgehen zu erhalten, betrachtenwir zunächst ein bereits früher untersuchtes Beispiel.

In Kapitel 1 hatten wir das folgende elektrische Netzwerk untersucht.

A

D

B

C

I

I

I

I

I

I

U

R

R

RR

R

R

6

3

4 5

1

21

2

3

54

6

Abbildung 4.1: Schaltbild eines elektrischen Netzwerkes

Die in diesem Netzwerk fließenden Ströme Iν , ν = 1, ..., 6, lassen sich aus dem linearen

60

KAPITEL 4. FEHLERANALYSE 61

Gleichungssystem1 0 −1 1 0 00 −1 1 0 −1 0−1 1 0 0 0 1R1 0 0 −R4 0 R6

0 R2 0 0 −R5 −R6

0 0 R3 R4 R5 0

I1

I2

I3

I4

I5

I6

=

000U00

berechnen.Vom Standpunkt der Anwendungen her gesehen stellt sich folgendes Problem: Wennman eine elektromotorische Kraft U misst und dann die Ströme Iν , ν = 1, ..., 6, ausdiesem System berechnet, ist dann garantiert, dass I1, ..., I6 tatsächlich in der berech-neten Stromstärke in dem Netzwerk fließen? Muss man nicht vielmehr damit rechnen,dass die berechneten Stromstärken nur näherungsweise mit den tatsächlich fließendenübereinstimmen? Diese Fragen sind in der Tat wohlbegründet, wie wir uns klar machenwollen.

• Fehler in den physikalischen Gesetzen:Mögliche Abweichungen können daher stammen, dass das verwendete physikali-sche Gesetz den Sachverhalt nicht genau wiedergibt. Denkbar ist, dass das Ohm-sche Gesetz U = R · I für die verwendeten Widerstände R1, ..., R6 nicht exakterfüllt ist. (Infolge einer geringen Temperaturabhängigkeit besitzen die Wider-stände z.B. keine genau lineare Charakteristik.) Einflüsse dieser Art auf die ge-suchten Ströme haben mit der numerischen Lösung des Problems offensichtlichnichts zu tun. Hier hat der Anwender zu entscheiden, ob das physikalische Modell,das er benützt, den wahren Sachverhalt genau genug beschreibt.

• Messungenauigkeit:Weitere Fehlerquellen resultieren aus Messungenauigkeiten. Die WiderständeR1, ..., R6 und die elektromotorische Kraft U lassen sich nur mit einer begrenz-ten Messgenauigkeit bestimmen. Eine Abschätzung (oder gar eine Reduzierung)dieser Messtoleranzen liegt ebenfalls nicht im Arbeitsbereich des Numerikers. Inder Numerik kann man aber damit zusammenhängende Fragen klären, wieweitgegebene Toleranzen bei U oder den Widerständen Rν , ν = 1, ..., 6, die StrömeIν beeinflussen können. Zu untersuchen ist also die Abhängigkeit der Resultatevon Eingangsdaten (Fehlerfortpflanzung).

• Rundungsfehler:Ein eigentlich numerisches Problem stellt sich bei der Auflösung dieses linearenGleichungssystems, wenn man mit Dezimalzahlen einer festen Stellenlänge arbei-tet. Dann ist stets damit zu rechnen, dass Zwischenresultate gerundet werdenmüssen. Es gilt dann den Einfluss von Rundungsfehlern abzuschätzen und, fallsdiese sich unangenehm akkumulierern sollten, eventuell eine günstigere Lösungs-methode einzusetzen.

• Schließlich sollte man bei starken Abweichungen der berechneten von den gemes-senen Stromstärken immer auch an die Möglichkeit von Rechenfehlern denken.


In folgenden Abschnitt 4.2 untersuchen wir speziell die Fehlerfortpflanzung bei linearenGleichungssystemen. Neben Fehlern der Komponenten der rechten Seite lassen wir auchStörungen der Matrix zu. Ist N(·) eine geeignete Matrixnorm (vgl. Abschnitt 4.2), sozeigt sich, dass beide Fehlertypen um den Faktor

condN(A) = N(A)N(A−1)

verstärkt in das Resultat eingehen können. Dieser Faktor heisst Konditionszahl vonA zur Matrixnorm N . In diesem Zusammenhang interessieren uns diejenigen Metho-den zur Lösung linearer Gleichungssysteme, welche die Konditionszahl verkleinern oderwenigstens nicht vergrößern. Dabei erweist sich das QR-Verfahren bzgl. der Spektral-kondition als numerisch günstig.

4.2 Fehlerfortpflanzung bei linearen Gleichungssyste-men

Im Folgenden befassen wir uns speziell mit der Fehlerfortpflanzung bei linearen Glei-chungssystemen. Gegeben sei also ein lineares Gleichungssystem

Ax = b,

wobeiA ∈ Km×m (K = R oder K = C), A regulär, b ∈ Km.

Auf Rm (Cm) sei ‖ · ‖ eine Norm gegeben und N(·) sei eine mit ‖ · ‖ verträglicheMatrixnorm, d.h.

‖Cy‖ ≤ N(C)‖y‖ ∀C ∈ Km×m und ∀y ∈ Km.

Meist notiert man N(C) =: ‖C‖.

Nun sei b + 4b eine Störung der rechte Seite des linearen Gleichungssystems undx+4x die Lösung von A(x+4x) = b+4b. Also gilt

A(4x) = 4b bzw. 4x = A−1(4b).

Daraus ergibt sich die folgende Abschätzung für den absoluten Fehler

‖4x‖ ≤ N(A−1) · ‖4b‖,

da N und ‖ · ‖ ein verträgliches Paar von Vektor- und Matrixnorm bilden.

Um den relativen Fehler abschätzen zu können, beachten wir

‖b‖ = ‖Ax‖ ≤ N(A) · ‖x‖,

also, falls b 6= 0 und damit auch x 6= 0 gilt,

1

‖x‖≤ N(A)

‖b‖.


Insgesamt folgt‖4x‖‖x‖

≤ N(A)N(A−1)‖4b‖‖b‖

.

Als Verstärkungsfaktor beim relativen Fehler tritt also gerade die Größe

condN(A) := N(A)N(A)−1

auf.

Bezeichnung 4.1 (Konditionszahl einer Matrix).Für eine reguläre Matrix A und eine Matrixnorm N bzeichnet man

condN(A) := N(A)N(A−1)

als die zur Matrixnorm N gehörende Konditionszahl von A.

Das oben gewonnene Resultat über die Fortpflanzung von Datenfehlern halten wir fest.

Resultat 4.2 (Fehlerfortpflanzung bei Störung von b). Bezeichnet 4b den Vektor derabsoluten Datenfehler und 4x den Vektor der absoluten Fehler des Resultatvektors, sogelten für ein lineares Gleichungssystem

Ax = b, A ∈ Km×m regulär, b ∈ Km, b 6= 0,

die Abschätzungen

‖4x‖ ≤ N(A−1)‖4b‖,‖4x‖‖x‖

≤ condN(A) · ‖4b‖‖b‖

.

Bemerkung 4.3.Die Konditionszahl condN(A) einer regulären Matrix A spielt eine wichtige Rolle beider Fehlerfortpflanzung in der numerischen linearen Algebra. Ein gewisser Nachteil istallerdings, dass sie nur bei Kenntnis der inversen Matrix zugänglich ist.

Man kann leicht eine untere Schranke für condN(A) angeben, falls N submultiplikativist, d.h. falls gilt N(AB) ≤ N(A)N(B). In diesem Fall stellt man fest

N(E) = N(AA−1) ≤ N(A)N(A−1) = condN(A).

Aus 0 < N(E) ≤ N(E)N(E) folgt N(E) ≥ 1; also kann man die Abschätzung vergrö-bern zu

1 ≤ condN(A).

Die Konditionszahl condN(A) einer regulären Matrix A hängt nach Definition von dergewählten Matrixnorm N ab. Man kann nun die Frage stellen, ob sich bei gegebenerNorm N die Konditionszahl durch den Übergang von A zu einer geeigneten Matrix TAverkleinern lässt. Dazu löse man zunächst folgende Aufgabe.


Aufgabe 4.4.Durch die Wahl der Matrixnorm

‖C‖2 := supy 6=0

‖Cy‖2

‖y‖2

=√λmax(CHC), C ∈ Km×m

ensteht als zugehörige Kondition die sogenannte Spektralkondition

cond2(A) := ‖A‖2 · ‖A−1‖2.

Für die so definierte Spektralkondition folgt: ist A eine reguläre Matrix und U eineunitäre Matrix so gilt

cond2(A) = cond2(UA) = cond2(AU).

Die Spektralkondition bleibt also beim Übergang von A zu UA oder AU invariant,wenn U unitär ist. Dies ist für numerische Zwecke günstig. So haben z.B. beim QR-Verfahren die Matrizen Ak = QkRk und Rk dieselbe Spektralkondition und, da dieMatrizen Ak unitär ähnlich sind, haben die Matrizen Ak und Rk für alle k diesselbeKonditionszahl wie die Ausgangsmatrix A.

Wir kommen zurück zur Frage, ob man die Konditionszahl einer Matrix A durch Über-gang zur Matrix TA verkleinern kann. Dazu definieren wir die Matrixnorm

‖C‖∞ := maxy 6=0

‖Cy‖∞‖y‖∞

= maxi

m∑k=1

|cik|

und die zugehörige Kondition

cond∞(A) := ‖A‖∞ · ‖A−1‖∞.

Man beachte, dass die Matrixnorm ‖ · ‖∞ zur Zeilensummennorm gehört. Motivationfür unser weiteres Vorgehen liefert die folgende

Aufgabe 4.5.

1. Für

A :=

1 1 11 10 1001 100 10000

berechne man cond∞(A).

2. Man bestimme eine Diagonalmatrix D := diag(d11, d22, d33) so, dass die Betrags-summen aller Zeilen von DA den Wert Eins haben, und berechne cond∞(DA).

Das Resultat dieser Aufgabe zeigt, dass man die auf der Zeilensummennorm beruhendeKonditionszahl cond∞(·) eventuell dadurch erheblich verkleinern kann, dass man dieZeilen von A mit geeigneten Faktoren multipliziert. Dies entspricht einer Änderung desMaßstabs, in dem die Zeilenelemente gemessen werden. Man spricht deshalb auch voneiner Skalierung. Teil 2 der obigen Aufgabe 4.5 lässt also folgendes vermuten.


Satz 4.6 (Günstige Skalierung von Matrizen).Gilt für eine reguläre Matrix A ∈ Km×m die Beziehungen

m∑k=1

|aik| = 1, i = 1, ...,m,

so folgt für jede reguläre Diagonalmatrix D die Ungleichung

cond∞(DA) ≥ cond∞(A).

Daraus folgt für eine beliebige invertierbare Matrix A ∈ Rm×m und eine invertierbareDiagonalmatrix D ∈ Rm×m:

cond∞(DA) ≥ cond∞(D∗A)

mit

D∗ =

d∗1 0

d∗2. . .

0 d∗m

, d∗i =1∑m

j=1 |aij|.

Dies folgt, weil A := D∗A gerade die im ersten Teil des Satzes verlangte Eigenschaftbesitzt.

Beweis:Wir setzen

A−1 =: (αik)i,k=1,...,m, D := diag(d11, ..., dmm).

Dann folgt

‖A−1D−1‖∞ = maxi=1,...,m

m∑k=1

|αik| ·1

|dkk|

≥

(max

i=1,...,m

m∑k=1

|αik|

)· mink=1,...,m

1

|dkk|

= ‖A−1‖∞ · mink=1,...,m

1

|dkk|

sowie

‖DA‖∞ = maxi=1,..,m

|dii|m∑k=1

|aik| = maxi=1,...,m

|dii|.

Man erhält so

cond∞(DA) = ‖DA‖∞ · ‖A−1D−1‖∞

≥ ‖A−1‖∞ · mink=1,...,m

1

|dkk|· maxi=1,...,m

|dii|,

woraus wegen

mink=1,...,m

1

|dkk|· maxi=1,...,m

|dii| ≥ 1 = ‖A‖∞


die Behauptungcond∞(DA) ≥ cond∞(A)

folgt.

Damit haben wir gezeigt, dass sich bei einer regulären Matrix A, deren sämtliche Zei-lenvektoren in der l1-Norm die Länge Eins besitzen, die Kondition cond∞(A) durchSkalierung nicht mehr verbessern lässt. Es empfiehlt sich also anstelle des Gleichungs-systems

Ax = b das System D∗Ax = D∗b

zu lösen, wobei die Diagonalmatrix D∗ so wie im obigen Satz 4.6 gewählt ist.

Neben Fehlern in den Daten b können auch „Störungen“ bei den Matrixelementen auf-treten. Wir wollen jetzt den Fall betrachten, dass ein System

(A+4A)x = b

gegeben ist. Dabei bezeichnet 4A die Fehlermatrix. Gesucht ist eine Abschätzung fürden absoluten Fehler

4x := x− x,wenn x die Lösung des „ungestörten“ Systems Ax = b bezeichnet.

Wegenx = (A+4A)−1b (falls A+4A regulär),

liegt es nahe, zunächst die „Störempfindlichkeit“ der Inversen zu bestimmen. Dazu dientfolgende Aufgabe.

Aufgabe 4.7.Es sei E die m ×m-Einheitsmatrix und S ∈ Km×m mit N(S) < 1 für eine submulti-plikative Matrixnorm N . Man zeige:

1. Die Matrix E + S ist regulär.

2. Es gilt: N((E + S)−1) ≤ N(E)

1−N(S).

Aus diesem Resultat erhalten wir für eine reguläre Matrix A im Fall

N(A−14A) < 1,

dass die Matrix E + A−14A und damit auch

A+4A = A(E + A−14A)

regulär ist und dass die Abschätzung

N((A+4A)−1) = N((E + A−14A)−1A−1) ≤ N(E)

1−N(A−14A)N(A−1)

gilt. Falls auchN(A−1)N(4A) < 1


gilt, folgt hieraus

N((A+4A)−1) ≤ N(E)

1−N(A−1)N(4A)·N(A−1).

Auf diesem Weg erhalten wir schließlich

N((A+4A)−1)

N(A−1)≤ N(E)

1−N(A−1)N(4A)

=N(E)

1− condN(A) · N(4A)

N(A)

.

Resultat 4.8 (Störempfindlichkeit der Matrixinversion).Für die reguläre Matrix A und eine zugehörige „Störmatrix“ 4A gelte

N(A−1)N(4A) < 1.

Dann existiert (A+4A)−1 und es folgt

N((A+4A)−1)

N(A−1)≤ N(E)


N(A)

.

Jetzt können wir uns dem oben gestellten Problem zuwenden, eine Abschätzung fürden Fehler 4x zu konstruieren, wenn die reguläre Matrix A entsprechend

(A+4A)(x+4x) = b

mit Fehlern 4A behaftet ist. Wegen Ax = b folgt

(A+4A)4x = −4A · x.

FallsN(A−1)N(4A) < 1

gilt, existiert (A+4A)−1. Dann erhalten wir

4x = −(A+4A)−14A · x

und hieraus‖4x‖ ≤ N((A+4A)−1)N(4A)‖x‖, x 6= 0.

Mit Resultat 4.8 folgt für den relativen Fehler

‖4x‖‖x‖

≤ N(E) · condN(A)


N(A)

· N(4A)

N(A).


Resultat 4.9 (Abschätzung des relativen Fehlers von x).Gilt

N(A−1)N(4A) < 1,

so lässt sich der relative Fehler der Lösung des gestörten linearen Gleichungssystems

(A+4A)(x+4x) = b, A regulär, b 6= 0,

abschätzen in der Form

‖4x‖‖x‖

≤ N(E) · condN(A)


N(A)

· N(4A)

N(A).

Den allgemeinen Fall, dass sowohl die Matrix A als auch die rechte Seite eines linearenGleichungssystems mit Fehlern behaftet sind, behandeln wir in der folgenden Aufgabe.

Aufgabe 4.10.Die Matrix A sei regulär und es gelte:

N(A−1)N(4A) < 1.

Dann lässt sich der relative Fehler der Lösung des linearen Gleichungssystems

(A+4A)(x+4x) = b+4b

abschätzen in der Form

‖4x‖‖x‖

≤ N(E)condN(A)


N(A)

(‖4b‖‖b‖

+N(4A)

N(A)

), x 6= 0 6= b.

Zusammenfassung:

In diesem Abschnitt haben Sie Abschätzungen für relative und absolute Fehler kennen-gelernt. Die Abschätzung des relativen Fehlers von x in Abhängigkeit von der rechtenSeite des Gleichungssystems Ax = b führte auf die Konditionszahlen von Matrizen. Andiesen Konditionszahlen erkannte man, dass Multiplikationen mit unitären Matrizenund bestimmte Skalierungen numerisch günstig sind.

Kapitel 5

Das Newton-Verfahren beinichtlinearen Gleichungssystemen

Wir betrachten die Aufgabe, für eine gegebene Abbildung F : D ⊂ Rn → Rn einx∗ ∈ D zu finden mit

F (x∗) = 0.

Sind Fi : D → R (i = 1, ..., n) die Komponentenabbildungen von F , und ist x =(x1, ..., xn)t, so suchen wir die Lösung des i. A. nichtlinearen Gleichungssystems

F1(x1, ..., xn) = 0...

Fn(x1, ..., xn) = 0.

Wir betrachten zuerst den einfachen Fall n = 1. Falls F eine differenzierbare Funk-tion ist und F ′ 6= 0 gilt, so kann man mit dem Newton-Verfahren näherungsweiseeine Lösung x∗ von F (x∗) = 0 bestimmen: Dabei ist x0 ein Startwert (ein ungefähre

xxx

Tangente im Punkt

x

y

xx

012

Tangente im Punkt 1 0

Abbildung 5.1: Das ein-dimensionale Newton-Verfahren

Schätzung) für die gesuchte Nullstelle x∗. Bestimmt man sukzessive x1, x2 usw., (vgl.

69

KAPITEL 5. NEWTON-VERFAHREN 70

Abbildung 5.1) so erhält man das Newton-Verfahren

xk+1 = xk − F (xk)

F ′(xk), k = 0, 1, 2, . . . .

Zu Gunsten einer einheitliche Schreibweise, die auch für den n-dimensionalen Fall ge-eignet ist, schreiben wir die Iterationsindizes als obere Indizes; eine Verwechslung mitExponenten kann in diesem Abschnitt kaum vorkommen. Das Newton-Verfahren hatsehr günstige Eigenschaften, wie uns der nachfolgende Satz zeigt.

Satz 5.1. Im Fall n = 1 des eindimensionalen Newton-Verfahrens

xk+1 = xk − F (xk)

F ′(xk), k = 0, 1, 2, . . .

liegt lokale quadratische Konvergenz vor, falls F in einer Umgebung der Nullstelle x∗zweifach stetig differenzierbar ist und dort |F ′(x)| ≥ α > 0 für ein gewisses α > 0 gilt.Genauer:Sei F (x∗) = 0 und F : [x∗ − δ1, x

∗ + δ2] −→ R sei zweifach stetig differenzierbar. Sindα, β so gewählt, dass |F ′(x)| ≥ α > 0 und |F ′′(x)| ≤ β für alle x ∈ [x∗ − δ1, x

∗ + δ2] sogilt:

|x∗ − xk+1| ≤ β

2α|x∗ − xk|2.

Falls zusätzlich |x∗ − x0|2 < 2αβ

gilt (d.h falls die Anfangsnäherung “gut genug” ist), sokonvergiert xk gegen x∗ für k →∞.

Beweis:Nach dem Satz von Taylor gilt:

0 = F (x∗) = F (xk) + F ′(xk)(x∗ − xk) +1

2F ′′(ζ)(x∗ − xk)2 (5.1)

mit einem Wert ζ, der zwischen xk und x∗ liegt. Nach der Vorschrift des Newton-Verfahrens gilt

0 = F (xk) + F ′(xk)(xk+1 − xk),so dass man F (xk) in (5.1) ersetzen kann. Folglich ergibt sich

0 = F ′(xk)(x∗ − xk+1) +1

2F ′′(ζ)(x∗ − xk)2

bzw.

|x∗ − xk+1| =| 1

F ′(xk)· 1

2F ′′(ζ)(x∗ − xk)2|

≤ β

2α|x∗ − xk|2.

Nachfolgend wollen wir skizzieren, wie das Newton-Verfahren im n-dimensionalen Fallfunktioniert. Unter ‖ · ‖ wollen wir eine beliebige Vektornorm auf Rn verstehen; tritteine Matrixnorm N(·) auf, so wollen wir stets voraussetzen, dass diese Matrixnorm N(·)mit der Vektornorm ‖ · ‖ verträglich ist, d.h. dass gilt ‖Ax‖ ≤ N(A)‖x‖ für x ∈ Rn

und A ∈ Rn×n. Zunächst wollen wir noch an einige Begriffe der Analysis erinnern.

KAPITEL 5. NEWTON-VERFAHREN 71

Definition 5.2 (Differenzierbarkeit).Die Abbildung F : D ⊂ Rn → Rn heißt differenzierbar (Frechet-differenzierbar) imPunkt x ∈ int(D), wenn eine lineare Abbildung A : Rn → Rn existiert, so dass

limh→0

‖F (x+ h)− F (x)− A · h‖‖h‖

= 0

ist (dabei bedeutet h→ 0, dass alle Nullfolgen hm ⊂ Rn zugelassen sind mit x+ hm ⊂D). Wir nennen A die Ableitung von F im Punkt x

A = F ′(x).

Folgerung 5.3.Ist F differenzierbar bei x, so existieren alle partiellen Ableitungen ∂Fi/∂xj (i, j =1, ..., n) an der Stelle x. Die lineare Abbildung F ′(x) : Rn → Rn wird repräsentiertdurch die n× n-Matrix der partiellen Ableitungen (Jacobi-Matrix)

F ′(x) =

[∂Fi∂xj

(x)

]1≤i,j≤n

.

Ist F differenzierbar für alle x ∈ D, so definiert

F ′ :

D → Rn×n,

x 7→ F ′(x)

eine Abbildung von D in den Raum Rn×n der quadratischen n× n-Matrizen. Ist dieseAbbildung stetig im Punkt x ∈ D, so heißt F stetig differenzierbar in x.

Unter der Annahme, dass F : D ⊂ Rn → Rn eine differenzierbare Abbildung istund F (x) = 0 eine Lösung x∗ ∈ D besitzt, können wir das n-dimensionale Newton-Verfahren

x0 ∈ D, xk+1 = xk − F ′(xk)−1F (xk), k = 0, 1, ...,

bzw.F ′(xk)yk = −F (xk), xk+1 := xk + yk

mit einem Startwert x0 ∈ D aufstellen, falls F in jedem Punkt von D (oder zumindestin einer Umgebung von x∗) eine invertierbare Jacobi-Matrix F ′(x)−1 besitzt.

Satz 5.4 (Lokale Konvergenz des Newton-Verfahrens (ohne Beweis)).Die Abbildung F : D ⊂ Rn −→ Rn besitze eine Nullstelle x∗ mit F (x∗) = 0 und seistetig differenzierbar bei x∗. Ferner sei F ′(x∗) invertierbar. In einer Umgebung U(x∗)von x∗ gelte ausserdem

N(F ′(x)− F ′(x∗)) ≤ β‖x− x∗‖ für x ∈ U(x∗) (5.2)

was z.B. erfüllt ist, wenn F zweimal stetig differenzierbar ist. Dann konvergiert dieNewton-Iteration

xk+1 = xk − F ′(xk)−1F (xk), k = 0, 1, ... (5.3)

falls x0 hinreichend nahe bei x∗ liegt. Insbesondere existiert ein C > 0 und ein K ∈ Nmit

‖xk+1 − x∗‖ ≤ C‖xk − x∗‖2 für k ≥ K (quadratische Konvergenz). (5.4)

Bemerkung 5.5.Der Fehler im k-ten Schritt ist x∗ − xk. Aufgrund der quadratischen Konvergenz ver-doppelt sich die Anzahl korrekter Dezimalstellen mit jedem Schritt.

Kapitel 6

Quadratur

6.1 Einleitung

Der Problemkreis, der in diesem Kapitel im Mittelpunkt steht, hat eine lange Geschich-te. Das Problem, von Kurven umschlossene Flächen zu berechnen, hat die Mathema-tiker schon seit dem Altertum beschäftigt und im 17. Jahrhundert zur Entwicklungder Integralrechnung geführt. Durch die Entwicklung fundierter Integralbegriffe wur-de dann in der zweiten Hälfte des 19. Jahrhunderts das Flächenbestimmungsproblemvom theoretischen Standpunkt weitgehend abgeschlossen. Durch den Hauptsatz derDifferential- und Integralrechnung lassen sich jeder im Intervall [a, b] stetigen Funktionf Stammfunktionen F zuordnen mit

F ′ = f ;

dabei gilt

I :=

∫ b

a

f(x)dx = F (b)− F (a).

Vom Standpunkt der Praxis aus ist aber damit das Flächenbestimmungsproblem noch

x

f(x)

a b

keinesfalls befriedigend gelöst.

Dies hat mehrere Gründe:

72

KAPITEL 6. QUADRATUR 73

1. Die Konstruktion des Integrals einer Funktion, wie sie beim Riemann-Integraldurchgeführt wird, beinhaltet einen komplizierten Grenzprozess. Diesen Grenz-prozess muss man in der Praxis durch einen finiten Näherungsprozess ersetzen.Darauf werden wir im nächsten Abschnitt genauer eingehen.

2. Für gewisse „einfache“ Funktionen kennt man die Stammfunktionen in geschlosse-ner Form in dem Sinne, dass sie auf „einfache“ Weise aus „einfachen“ Funktionenaufbauen, z. B. ∫ x

tmdt =1

m+ 1xm+1 + const, m 6= −1,∫ x dt

t= log x+ const, x > 0,∫ x

etdt = ex + const .

Es wurde aber schon von Liouville um 1835 gezeigt, dass z.B. für Funktionen desTyps

x 7−→ 1√1 + x4

, x 7−→ ex

x, x 7−→ e−x

2

eine „geschlossene“ Darstellung der Stammfunktionen durch „einfache“ Funktio-nen unmöglich ist. Mit Hilfe von Stammfunktionen in geschlossener Form kommtman also in der Praxis nicht weit genug.

3. Kennt man schließlich den Integranden nur in einer endlichen Zahl von Punkten(z.B. an Messpunkten), so ist offensichtlich, dass man den Integranden f zunächstin geeigneter Weise (z.B. durch Interpolation) approximieren muss, um dannanschließend ersatzweise diese approximierende Funktion p zu integrieren.

xa b

p(x)

f(x)

Das Problem, Integrale numerisch auszuwerten, stellt sich in den Anwendungen häufig.Ein Grund dafür ist, dass sich die mechanische Arbeit als Wegintegral der Kraft ergibt:

A =

∫ x1

x0

K(x)dx;

hier wird angenommen, dass die Kraft parallel zur Bewegungsrichtung wirkt. Ein an-derer wichtiger Grund ist, dass die Gesamtenergiemenge das Zeitintegral der Leistung


ist:

E =

∫ t1

t0

L(t)dt.

Wir denken uns die in einer Wohnung währen eines Tages aufgenommene elektrischeLeistung in einem Leistungsdiagramm aufgetragen.

0h 24h

L(t)

6h 12h 18h

Dann beträgt die insgesamt zu bezahlende elektrische Energie

E =

∫ t1

t0

L(t)dt.

Tatsächlich wird aber dieses Leistungsdiagramm gar nicht aufgenommen. Vielmehr „in-tegriert“ der Stromzähler die Leistung auf. (Der Stromzähler stellt also ein Analoggerätzur numerischen Integration der elektrischen Leistung dar.)

Ein ähnliches Problem stellt sich, wenn man den Durchschnittswert einer sich kontinu-ierlich ändernden Größe bestimmen will (z.B. mittlere Tages- oder Jahrestemperatur,mittlere Niederschlagsmenge in einem Monat).

a b

f(t)

t

Dann ist der Mittelwert bekanntlich

m :=

∫ baf(t)dt

b− a.

In der Praxis ersetzt man die Integration durch n äquidistant verteilte Messungen undnimmt als genäherten Mittelwert

m :=1

n

n∑i=1

f(ti), ti = a+ ih, i = 0, ..., n,

h =b− an

,


d.h. man nähert das Integral∫ baf(t)dt an durch

h

n∑i=1

f(ti).

f(t)

tt t t t t t

t=a t=b

t1 2 3

0

n−4 n−3 n−2 n−1

n

Der Integrand f wird also durch einen Treppenzug ersetzt und das Integral dieses Trep-penzuges als Näherung für

∫ baf(t)dt verwendet. Dieses hier angewendete Prinzip zur

numerischen Integration ist der Ausgangspunkt für die meisten Quadraturformeln. Manbezeichnet deshalb eine große Klasse von Quadraturformeln auch alsMittelwertformeln.

Als Beispiel zur mechanischen Arbeit betrachten wir den Flug einer senkrecht star-tenden Rakete. Wenn wir zunächst nur die Gravitation berücksichtigen, so gilt

K(x) = −mga2

x2,

wenn wir mit

x

xx 10

K(x)

m : Raketenmasse,g : Erdbeschleunigung,a : Erdradius

bezeichnen. Also folgt mit x0 = a die Beziehung

A = −∫ x1

a

mga2dx

x2= mga2

[1

x1

− 1

a

].


x

x0

Abwurf

x1

1.Stufe

Abwurf

2.Stufe

K(x)

Tatsächlich ist das Kraftgesetz wesentlich komplizierter, da sowohl die Masse variabelist (Massenverlust durch Ausstoß der Verbrennungsgase, Mehrstufenrakete) und ande-rerseits neben der Graviatation auch andere Kräfte zu berücksichtigen sind, die vomLuftwiderstand herrühren.Am einfachsten lässt sich eine Funktion dieses komplizierten Typs mit Hilfe einer Qua-draturformel näherungsweise integrieren.

Im Abschnitt 6.2 untersuchen wir exemplarisch die Trapezregel und die Rechteckregel.Beide Quadraturformeln sind geometrisch naheliegend, wenn man an den Zusammen-hang des Integrals mit dem Flächenbegriff denkt. Für beide Formeln leiten wir Fehler-darstellungen vom Cauchyschen und vom Peanoschen Typ her. Schließlich zeigen wir,dass man durch Zusammensetzen der einfachen Trapez- und der einfachen Rechteckre-gel zu Formeln höherer Genauigkeit gelangen kann. Für diese iterierten Formeln leitenwir ebenfalls Fehlerdarstellungen her.

Im Abschnitt 6.3 behandeln wir interpolatorische Quadraturformeln, die man am ein-fachsten durch Integration aus der Lagrange-Darstellung von Interpolationspolynomenerhält.

Im Abschnitt 6.4 behandeln wir die Newton-Côtes-Formeln, die interpolatorisch zuäquidistant verteilten Stützstellen definiert werden. Insbesondere untersuchen wir ein-gehend die Simpsonsche Regel (Keplersche Fassregel), welche historisch gesehen dievielleicht wichtigste Quadraturformel überhaupt ist. Die Newton-Côtes-Formeln wer-den uns bei der numerischen Behandlung von Differentialgleichungen wieder begegnen.

6.2 Die Trapezregel und die Rechteckregel

Um ein Integral

I :=

∫ b

a

f(x)dx

näherungsweise zu berechnen, erinnern wir uns an die ursprüngliche Problemstellungaus dem 17.Jahrhundert, als man die Integralrechnung zu entwickeln begann. Damalssah man in erster Linie das Problem, Flächen zu berechnen, die vom Graphen derFunktion f , der x-Achse und zwei zur y-Achse parallelen Geraden berandet werden.


x

f(x)

a b

Die Anschauung legt es nahe, eine Näherung für I dadurch zu berechnen, dass manden Graphen von f durch die Sekante durch die Punkte (a, f(a)) und (b, f(b)) ersetzt.(Diese Idee spielt auch bei der Entwicklung des Riemannschen Integralbegriffs eineentscheidende Rolle.)

xa b

f(x)

F

Die zu berechnende Fläche wird also durch ein Trapez mit der Fläche

F = (b− a)f(a) + f(b)

2

ersetzt. Wir erhalten so die zweipunktige Trapezregel∫ b

a

f(x)dx = (b− a)f(a) + f(b)

2+R(f),

wobei R(f) den auftretenden Fehler bezeichnet, der offensichtlich von der zu integrie-renden Funktion f und der Intervalllänge (b− a) abhängt.

Satz 6.1 (Fehler der Trapezregel).Ist f zweimal stetig differenzierbar auf [a, b], so gilt die Fehlerdarstellung

R(f) = −(b− a)3

12f ′′(η)

mit einem η ∈ (a, b).


Die „einfache“ Trapezregel, wie wir sie bisher behandelt haben, wird meistens noch zuungenaue Resultate liefern. Man teilt deshalb das Integrationsintervall in Teilintervallegleicher Länge auf und wendet auf jedes die Trapezregel an.

x

f(x)

x xn−11x=a

0 x=bn

Setzt man

h :=b− an

,

xi := a+ ih, i = 0, ..., n,

so erhält man die iterierte oder zusammengesetzte Trapezregel∫ b

a

f(x)dx =h

2f(a) + 2f(a+ h) + ...+ 2f(b− h) + f(b)+Rh(f)

= h ·n∑i=0

′′

f(xi) +Rh(f),

wenn wir mit∑′′ eine Summation bezeichnen, bei der der erste und letzte Summand

den Faktor 12erhalten.

Aufgabe 6.2.Man zeige:

1. Für die iterierte Trapezregel gilt die Fehlerdarstellung vom Peano-Typ

Rh(f) =

∫ b

a

f ′′(t) ·G(t)dt, f ∈ C2[a, b],

wobei

G(t) =

(x1 − t)(x0 − t)

2, t ∈ [x0, x1],

G(t− ih), t ∈ [xi, xi+1], i = 1, ..., n− 1.

2. Es gilt außerdem die Fehlerdarstellung vom Cauchyschen Typ

Rh(f) = −(b− a)

12· h2 · f ′′(η), η ∈ [a, b].


x1 x2xn−1

x=bnx=a0

t

G(t)

Eine Variante der Trapezregel erhält man in der Rechteckregel (Mittelpunktsregel)∫ b

a

f(x)dx = (b− a) · f(a+b− a

2) + R(f).

Die zusammengesetzte Rechteck-Regel lautet dann: h =b− an

, xi = a+ ih

∫ b

a

f(x)dx = h

n−1∑i=0

f(xi +h

2).

6.3 Interpolatorische Quadraturformeln

Bei der Konstruktion der Rechteckregel bzw. der Trapezregel hatten wir mit Poly-nomen nullten bzw. ersten Grades interpoliert. Dieses Konstruktionsprinzip lässt sichunter Verwendung von Polynomen höheren Grades weiterentwickeln.

Zur Berechnung von

I :=

∫ b

a

f(x)dx

approximieren wir den Integranden f durch ein Interpolationspolynom pn, wobei wirn+ 1 Stützstellen xi, i = 0, ..., n, aus dem Intervall [a, b] wählen. Es gelte

a ≤ x0 < x1 < ... < xn−1 < xn ≤ b.

x

f(x)

p(x)

ba


Das Interpolationspolynom pn stellen wir in der Lagrange-Form

pn(x) =n∑ν=0

f(xν)lν(x),

lν(x) =n∏µ=0µ6=ν

x− xµxν − xµ

, ν = 0, ..., n,

dar. Offenbar giltlν(xν) = 1 und lν(xj) = 0 für j 6= ν,

und daher erfüllt pn(x) auch die Interpolationsbedingung pn(xj) = f(xj) für j =0, . . . , n. Daher folgt∫ b

a

f(x)dx =

∫ b

a

n∑ν=0

f(xν)lν(x)dx+Rn(f)

=n∑ν=0

f(xν)

∫ b

a

lν(x)dx+Rn(f).

Die Gewichte

aν :=

∫ b

a

lν(x)dx

hängen nur von der Lage der Stützstellen xν , ν = 0, .., n, nicht aber von f ab.

Bezeichnung 6.3 (Interpolationsquadraturformel).Zu einem festen Satz von Stützstellen

a ≤ x0 < x1 < ... < xn−1 < xn ≤ b.

bezeichnet man die Formel∫ b

a

f(x) =n∑ν=0

aνf(xν) +Rn(f),

aν :=

∫ b

a

lν(x)dx, ν = 0, ..., n,

lν(x) =n∏µ=0µ6=ν

x− xµxν − xµ

, ν = 0, ..., n,

als die zu diesen Stützstellen gehörende Interpolationsquadraturformel.

6.4 Newton-Côtes-Formel

Wählt man bei der Interpolationsformel 6.3 eine äquidistante Stützstellenverteilung,so erhält man die Newton-Côtes-Formeln.


Bezeichnung 6.4 (Newton-Côtes-Formel).Das Intervall [a, b] werde durch äquidistante Stützstellen gemäß

xi := a+ ih, i = 0, ..., n, h :=b− an

, n ∈ N,

in n Teilintervalle zerlegt; dann bezeichnet man die Formel∫ b

a

f(x)dx = (b− a)n∑i=0

a(n)i f(xi) +Rn(f)

mit den Gewichten

a(n)i :=

1

b− a

∫ b

a

l(n)i (x)dx =

1

b− a

∫ b

a

n∏µ=0µ6=i

x− xµxi − xµ

dx, i = 0, ..., n,

als Newton-Côtes-Formel.

Substituiert man mit x = a+ hs die Variable x durch s, erhält man für i = 0, ..., n

l(n)i (a+ hs) =

n∏µ=0µ6=i

a+ hs− a− µha+ ih− a− µh

=n∏µ=0µ6=i

s− µi− µ

und

a(n)i :=

1

b− a

∫ b

a

l(n)i (x)dx =

h

b− a

∫ n

0

n∏µ=0µ 6=i

s− µi− µ

ds

=(−1)n−i

n · i!(n− i)!

∫ n

0

s(s− 1) · · · (s− i+ 1)(s− i− 1) · · · (s− n)ds.

Wir betrachten die Formel für gerades n = 2m, m ∈ N, näher. Laut Konstruktion istdie Formel exakt für jedes Polynom pn ∈ Πn (Πn sei die Menge der Polynome vomGrad höchstens n), also Rn(pn) = 0. Ist pn+1 ∈ Πn+1 mit der Zerlegung

pn+1(x) = α

(x− a+ b

2

)n+1

+ pn(x),

dann gilt

Rn(pn+1) =

∫ b

a

pn+1(x)dx− (b− a)n∑i=0

a(n)i pn+1(xi)

= α

∫ b

a

(x− a+ b

2

)n+1

dx− (b− a)n∑i=0

a(n)i · α ·

(xi −

a+ b

2

)n+1

+Rn(pn).

Da a(n)i = a

(n)n−i, wie man für i = 0, ..., n − 1 aus obiger Darstellung leicht verifiziert,

und aufgrund der Punktsymmetrie von x 7−→ (x − a+ b

2)n+1 um

a+ b

2für n = 2m,

findet man

α

∫ b

a

(x− a+ b

2

)n+1

dx = 0,

α(b− a)n∑i=0

a(n)i

(xi −

a+ b

2

)n+1

= 0;

wegen Rn(pn) = 0 folgt dann Rn(pn+1) = 0.


Satz 6.5 (Exaktheit der Newton-Côtes-Formeln).Für n ∈ N, n gerade, sind die Newton-Côtes-Formeln exakt für Polynome pn+1 ∈ Πn+1

vom Grade n+ 1, also gilt Rn(pn+1) = 0.

Für gerades n ist der Grad der Exaktheit also um 1 höher, als nach der Konstruktionzu erwarten war. Dies ist in der Symmetrie der Stützstellenverteilung um die Stellea+ b

2begründet.

Für n = 1 erhält man wegen

a(1)0 = −

∫ 1

0

(s− 1)ds =1

2,

a(1)1 =

∫ 1

0

sds =1

2

gerade die Trapezregel.

Für n = 2 ergibt sich

a(2)0 =

1

4

∫ 2

0

(s− 1)(s− 2)ds =1

4

∫ 2

0

(s2 − 3s+ 2)ds =1

6,

a(2)1 = −1

2

∫ 2

0

s(s− 2)ds = −1

2

∫ 2

0

(s2 − 2s)ds =4

6,

a(2)2 =

1

4

∫ 2

0

s(s− 1)ds =1

4

∫ 2

0

(s2 − s)ds =1

6.

Die resultierende Formel∫ b

a

f(x)dx =b− a

6

(f(a) + 4f(

a+ b

2) + f(b)

)+R2(f)

bezeichnet man als Simpsonsche Regel oder Keplersche Fassregel.

Wir erwähnen (ohne Beweis), dass der Fehler R2(f) der Simpsonsche Regel die folgendeCauchy-Darstellung hat:

R2(f) = − 1

90h5 · f (4)(η) für ein η ∈ [a, b].

Für wachsendes n ergeben sich weitere Newton-Côtes-Formeln. Wir geben (mit h =b− an

) ohne weiteren Beweis an:

Satz 6.6 (Newton-Côtes-Formeln und zugehörige Fehlerdarstellungen vom Cauchy–Typ).

n a(n)0 a

(n)1 a

(n)2 a

(n)3 a

(n)4 a

(n)5 a

(n)6 Bezeichnung Rn(f)

1 12

12

Trapezregel − 112h3f (2)(η)

2 16

46

16

Simpsonregel − 190h5f (4)(η)

3 18

38

38

18

3/8-Regel − 380h5f (4)(η)

4 790

3290

1290

3290

790

Milne-Regel − 8945h7f (6)(η)

5 19288

75288

50288

50288

75288

19288

6-Punkt-Regel − 27512096

h7f (6)(η)6 41

840216840

27840

272840

27840

216840

41840

Weddle-Regel − 91400

h9f (8)(η)


Hierbei ist η jeweils ein von f und n abhängiger Zwischenwert. Die angegebene Ablei-tung von f soll jeweils existieren und stetig sein.

Für n = 8 und n ≥ 10 treten negative Gewichte auf, wodurch sich große Betrags-summen der Gewichte ergeben. Des Weiteren ist bei der numerischen Auswertung einerQuadraturformel mit Vorzeichenwechsel in den Gewichten eine starke Fehlerfortpflan-zung wegen Auslöscheffekten zu erwarten. Man wendet daher auch die oben angege-benen Newton-Côtes-Formeln vorteilhaft in iterierter (zusammengesetzter) Form an,indem man also zunächst das Ausgangsintervall teilt und die Newton-Côtes-Formel aufdie Teilintervalle ansetzt.Gut erkennt man aus Satz 6.6 auch, dass man günstigerweise Formeln mit geradem nwählt, da man schon wegen Satz 6.5 die Exaktheit der nächsthöheren Formel mit n+ 1erreicht.

Kapitel 7

Numerische Lösung vonAnfangswertproblemen -Einschrittverfahren

7.1 Einleitung

In diesem und den noch folgenden Paragraphen stehen Diskretisierungsverfahren beiDifferentialgleichungen im Vordergrund. Da sehr viele Probleme aus den Naturwissen-schaften und der Technik auf Differentialgleichungen führen, ist die Entwicklung voneffizienten Methoden zur Auflösung solcher Gleichungen eine Hauptaufgabe der Nume-rischen Mathematik. Zu diesem Problemkreis gibt es eine immense Zahl von Publika-tionen, die sowohl sehr allgemeine und für große Klassen von Differentialgleichungenanwendbare Methoden als auch sehr typabhängige Verfahren, die nur für sehr spe-zielle Differentialgleichungen angewendet werden können, behandeln. In diesem Kurskönnen wir dieses ausgedehnte Teilgebiet keinesfalls auch nur annähernd erschöpfendvorstellen.

Im folgenden gehen wir auf einige Beispiele aus den Anwendungsgebieten der Mathe-matik ein, die auf Differentialgleichungen führen. Ein Wachstums- oder Zerfallsprozesswird durch die Differentialgleichung

y′ = λy, λ ∈ R

beschrieben, welche gerade besagt, dass zu jedem Zeitpunkt t der Zuwachs (oder dieAbnahme) y′(t) proportional zur vorhandenen Substanz y(t) ist. Hier ist bei Angabeeiner Anfangssituation im Zeitpunkt t0

y(t0) = m0

der Verlauf der Lösungsfunktion y vollständig bestimmt. Man erkennt leicht, dass

y(t) = m0eλ(t−t0)

die Lösung unseres Problems ist.

In den Anwendungen wird dieses einfache Wachstumsgesetz nur unter sehr idealisiertenAnnahmen gelten. In der Biologie wird man oft annehmen müssen, dass die Größe λ

84

KAPITEL 7. NUMERISCHE LÖSUNG VON ANFANGSWERTPROBLEMEN 85

selbst zeitabhängig ist (z.B. jahreszeitlich bedingt). Man hat dann

y′(t) = λ(t) · yy(t0) = m0

Hier ist nuny(t) = m0e

Λ(t)

die Lösung, wenn Λ mit

Λ(t) =

∫ t

t0

λ(τ) dτ

eine Stammfunktion zu λ bezeichnet. In diesem Fall führen also die früher behandeltenQuadraturverfahren zu einer numerischen Lösung.

Während man das bisher behandelte Problem mit nur einer Substanz (Population) re-lativ leicht übersehen kann, wird es schon schwieriger, wenn mehrere Substanzen (ver-schiedene Arten) vorliegen, wobei gewisse Substanzen (Arten) auf Kosten der anderenentstehen können. Diese Problemstellung liegt z.B. bei chemischen Reaktionen, bei Zer-fallsprozessen in der Atomphysik oder bei gemischten Populationen in der Biologie vor.Bezeichnet man die Menge der i-ten Substanz im Zeitpunkt t mit yi(t), i = 1, . . . , l, sowird der Zerfallsprozess (die chemische Reaktion, die Zusammensetzung der Populati-on) in seinem zeitlichen Verlauf durch ein System linearer Differentialgleichungen mitkonstanten Koefffizienten

y′1 =l∑

k=1

λ1kyk

... , λik ∈ R, i, k = 1, . . . , l

y′l =l∑

k=1

λlkyk

beschrieben, wobei außerdem l Anfangsbedingungen

yk(t0) = vk, k = 1, . . . , l ,

erfüllt werden müssen. Während man den Fall zeitunabhängiger Parameter λik, i, k =1, . . . , l, völlig beherrscht, indem man das gegebene System von Differentialgleichun-gen mit Hilfe einer Hauptvektorbasis der Matrix (λik) ”entkoppelt”, bereitet der Fall,dass die Parameter zeitabhängig sind, erhebliche Schwierigkeiten. Bei der numerischenLösung ist insbesondere der Fall, dass die Matrix (λik(t)) für gewisse Werte von tEigenwerte sehr unterschiedlichen Betrags besitzt (steife Differentialgleichung), mit er-heblichen Komplikationen verbunden.

Die Kinetik führt ebenfalls bei vielen Problemen auf Differentialgleichungen. Der ein-fachste Typ ist die Bewegungsgleichung eines Schwingungsvorgangs

my′′ +Ry′ + ky = f(t) ,

y(t0) = y0 ,

y′(t0) = y(1)0 .


(Hier bedeutet m die Masse, R den Reibungskoeffizienten, k die Rückstellkraft, f dieschwingungserzeugende Kraft.) Während man diesen Typ ebenfalls völlig beherrscht,bereitet die Berechnung von Bahnkurven mehrerer Massen, die gegenseitig Gravitations-kräfte aufeinander ausüben, erhebliche theoretische und numerische Schwierigkeiten.

Eine Problemstellung ähnlichen Typs liefert die Raumfahrt. Wir betrachten ”nur” denSpezialfall einer periodischen Satellitenbahn im Erde-Mond-System: Unter idealisiertenAnnahmen (restringiertes Dreikörperproblem) wird die Bahnkurve in der Bewegungs-ebene durch ein System von zwei Differentialgleichungen zweiter Ordnung beschrieben.Bezeichnet

µ =m

M=

1

82, 45

das Verhältnis der Mondmasse m zur Erdmasse M , so gilt

y′′ = y + 2z′ − (1− µ)y + µ

((y + µ)2 + z2)3/2− µ y − (1− µ)

((y − 1 + µ)2 + z2)3/2

z′′ = z − 2y′ − (1− µ)z

((y + µ)2 + z2)3/2− µ z

((y − 1 + µ)2 + z2)3/2.

Mit den Anfangsbedingungen

y(0) = 1, 2 , y′(0) = 0

z(0) = 0 , z′(0) = −1, 049357 . . .

hat die Bahnkurve (y(t), z(t)) den in Abbildung 7.1 dargestellten Verlauf (vgl. E. Fehl-berg, zur numerischen Integration von Differentialgleichungen durch Potenzreihenan-sätze, dargestellt an Hand physikalischer Beispiele, ZAKM 44, 83-88 (1964)). Dabeiwird angenommen, dass das Koordinatensystem sich mit der Erde ”mitbewegt”; dieErde liegt also stets im Ursprung des Koordinatensystems.

Abbildung 7.1: Abbildung der Bahnkurve des Erde-Mond-Systems

Bei diesen und ähnlich gelagerten Beispielen ist die Auswahl des richtigen Verfahrensvon eminenter Bedeutung. Dieses muss sowohl in der Schrittweite als auch in der Ord-nung dem Problem angepasst werden. Besonders wichtig ist die Wahl der richtigenSchrittweite. Diese darf relativ groß in dem Bereich gewählt werden, wo die Bahn nurwenig gekrümmt ist, während sie in Erdnähe sehr viel kleiner sein muss. Eine konstan-te Schrittweite müsste sich am Verhalten der Bahn in Erdnähe orientieren und würdedadurch viel zu klein ausfallen. Der resultierende Rechenaufwand wäre ein Mehrfaches


dessen, was bei variabler Schrittweite ausreicht. Um so erstaunlicher sind aber dannangesichts dieser Problematik die Erfolge der Raumfahrtszentren, in denen derzeit wohlTausende von Satellitenbahnen rechnerisch verfolgt werden.

Im Abschnitt 7.2 stellen wir einige Resultate aus der Lösungstheorie für Anfangswert-probleme bei gewöhnlichen Differentialgleichungen zusammen. Wir definieren zunächstdie Problemstellung und erklären, was man unter einer Lösung eines Anfangswert-problems zu verstehen hat. Dann erwähnen wir den Existenz- und Eindeutigkeits-satz von Picard-Lindelöf für Differentialgleichungen, deren rechte Seite einer Lipschitz-Bedingung genügt. Schließlich weisen wir darauf hin, dass jede Lösung, deren Existenzdurch den Satz von Picard-Lindelöf zunächst nur in einer kleinen Umgebung des An-fangspunktes gesichert ist, ”von Rand zu Rand” des betrachteten Gebietes fortgesetztwerden kann.

Im Abschnitt 7.3 behandeln wir exemplarisch das Eulersche Polygonzugverfahren, dasals Grundtyp aller Einschrittverfahren angesehen werden kann. Wir motivieren diesesLösungsverfahren geometrisch mit Hilfe des Richtungsfeldes und analytisch mit Hilfenumerischer Differentiation und numerischer Integration sowie mit Hilfe von Taylorent-wicklung. Diese Ansätze liegen auch einer Reihe anderer im folgenden zu behandelndenMethoden zugrunde. Für spezielle Beispiele untersuchen wir die Konvergenz des Poly-gonzugverfahrens bei kleiner werdender Schrittweite. Schließlich weisen wir noch dar-auf hin, dass Systeme von Differentialgleichungen erster Ordnung komponentenweisebehandelt und Differentialgleichungen höherer Ordnung auf Systeme erster Ordnungzurückgeführt werden können.

Im Abschnitt 7.4 stehen Definition und grundlegende Eigenschaften von Einschrittver-fahren im Mittelpunkt. Wir definieren zunächst, was wir unter einer Zuwachsfunktionverstehen wollen und erhalten damit die Rekursion eines allgemeinen Einschrittver-fahrens. Anschließend führen wir den Begriff des lokalen Diskretisierungsfehlers ein,der es uns dann ermöglicht, den Konsistenzbegriff und die Konsistenzordnung einesEinschrittverfahrens zu definieren.

Im Abschnitt 7.5 lernen wir die Methode des Taylorabgleichs kennen. Diese Vorge-hensweise ermöglicht es im Prinzip, für genügend oft differenzierbare Funktionen fEinschrittverfahren vorgeschriebener Konsistenzordnung zu konstruieren. Da aber indie Zuwachsfunktion partielle Ableitungen von f entsprechend hoher Ordnung einge-hen, hat diese Methode nur einen beschränkten Anwendungsbereich, der entscheidenddavon abhängt, ob die erforderlichen partiellen Ableitungen in ”einfacher” Weise be-rechnet werden können.

Im Abschnitt 7.6 behandeln wir exemplarisch die Runge-Kutta-Verfahren der Konsis-tenzordnung 2. Das Prinzip der Runge-Kutta-Verfahren besteht darin, das Auftretenvon Ableitungen von f durch einen Mittelungsprozess von Funktionswerten von f angeeignet gewählten Stützstellen zu vermeiden. Wir zeigen durch Taylorentwicklung,dass eine einparametrige Schar von Runge-Kutta-Verfahren der Konsistenzordnung 2existiert.

Im Abschnitt 7.7 gehen wir auf allgemeine Runge-Kutta-Verfahren ein. Wir definierenzunächst, was wir unter einemR-stufigen Runge-Kutta-Verfahren verstehen wollen. An-schließend sondern wir einige praktisch wichtige Beispiele, insbesondere das ”klassische”Runge-Kutta-Verfahren, aus. Wie mühsam die Konstruktion von höherstufigen Runge-Kutta-Verfahren mit entsprechend hoher Konsistenzordnung ist, zeigen wir im Fall der


dreistufigen Runge-Kutta-Verfahren der Konsistenzordnung 3. Durch Taylor-Abgleicherhalten wir nach langwieriger Rechnung eine zweiparametrige Schar solcher Verfahren.Zum Schluss gehen wir auf die erreichbare Ordnung bei höherstufigen Verfahren einund zitieren in diesem Zusammenhang ein tiefliegendes Resultat von Butcher.

Im Abschnitt 7.8 befassen wir uns mit der Konvergenz von Einschrittverfahren. ZumSchluss dieses Abschnitts gehen wir auf eine Fehlerabschätzung ein und zeigen, dassdie Konsistenzordnung des Einschrittverfahrens die Ordnung des akkumulierten Fehlersbestimmt.

Im Abschnitt 7.9 befassen wir uns mit der Praxis der Einschrittverfahren. Dabei stehtdie Wahl der Schrittweite im Vordergrund.

7.2 Einführung in die Lösungstheorie von Anfangs-wertproblemen

Anfangswertproblem

Die Differentialgleichungy′ = f(x, y)

zusammen mit dem Anfangswerty(x0) = y0

nennt man ein Anfangswertproblem, falls f in einem Gebiet G ⊂ R2 stetig ist und(x0, y0) in G liegt. In vielen Fällen wird G als Streifen (α, β)× R vorausgesetzt.

Lösung eines Anfangswertproblems

Eine reellwertige Funktion y heißt Lösung des Anfangswertproblems, falls y auf einemIntervall (a, b) mit x0 ∈ (a, b) definiert und stetig differenzierbar ist und ferner gilt:

(1) (x, y(x)) ∈ G für x ∈ (a, b)

(2) y′(x) = f(x, y(x)) für x ∈ (a, b)

(3) y(x0) = y0 .

Lipschitz-stetige Funktionen

Die rechte Seite f der Differentialgleichung heißt Lipschitz-stetig auf G, falls eine Kon-stante (Lipschitz-Konstante) L existiert derart, dass für alle Punkte (x, y), (x, y) ∈ Gdie Bedingung (Lipschitz-Bedingung)

|f(x, y)− f(x, y)| ≤ L|y − y|

erfüllt ist.


Integralgleichung vom Volterra-Typ

Das Auffinden einer Lösung des Anfangswertproblems ist äquivalent zum Auffindeneiner Lösung der Integralgleichung

y(x) = y0 +

∫ x

x0

f(t, y(t)) dt.

Diese Gleichung heißt Integralgleichung vom Volterraschen Typ.

Lösbarkeit von Anfangswertproblemen

Nach dem Satz von Peano besitzt das Anfangswertproblem (bei stetiger rechter Seite)stets wenigstens eine Lösung. Ist f Lipschitz-stetig auf G, so ist die Lösung nach demSatz von Picard-Lindelöf lokal eindeutig bestimmt; es existiert in diesem Fall eineeindeutige maximale Lösung, die für wachsendes und fallendes Argument gegen denRand des Gebiets G läuft.

Picard-Iteration

Bei Lipschitz-stetiger rechter Seite kann die Lösung des Anfangswertproblems lokaldurch die sogenannte Picard-Iteration

y0(x) = y0 ,

yν(x) = y0 +

∫ x

x0

f(t, yν−1(t)) dt , ν ≥ 1 ,

bestimmt werden; die Folge (yν)ν≥0 konvergiert lokal gleichmäßig gegen die Lösung.

7.3 Das Eulersche Polygonzugverfahren

Richtungsfeld, Isoklinen

Einen Überblick über die Lösungsgesamtheit einer Differentialgleichung

y′ = f(x, y)

(mit in einem Gebiet G ⊂ R2 stetiger rechter Seite) kann man sich verschaffen, indemman das Richtungsfeld zeichnet. Hierzu markiert man in jedem Punkt (x, y) ∈ G dieSteigung

p := f(x, y) .

Die durchf(x, y) = const

definierten Kurven nennt man Kurven gleicher Neigung oder Isolklinen.


Eulersches Polygonzugverfahren

Diese Verfahren erhält man dadurch, dass man stückweise in der durch das Richtungs-feld vorgeschriebenen Richtung weiterläuft: Man gibt sich eine Schrittweite h > 0 vor,setzt

xν := x0 + ν · h , ν ≥ 0 ,

y0 := y(x0),

und iteriert gemäß

yν := yν−1 + h · f(xν−1, yν−1) , ν ≥ 1 ,

solange die rechte Seite definiert ist.

Eulersches Polygonzugverfahren für ein System erster Ordnung

Liegt ein System erster Ordnung

y′1 = f1(x, y1, . . . , ym) ,

y′2 = f2(x, y1, . . . , ym) ,

...y′m = fm(x, y1, . . . , ym)

vor, so iteriert man komponentenweise. Dies ergibt die Rekursion

y[ν]1 = y

[ν−1]1 + h · f1(xν−1, y

[ν−1]1 , . . . , y[ν−1]

m ) ,

...

y[ν]m = y[ν−1]

m + h · fm(xν−1, y[ν−1]1 , . . . , y[ν−1]

m ) .

Eulersches Polygonzugverfahren für eine Differentialgleichung m-ter Ord-nung

Eine Differentialgleichung m-ter Ordnung

y(m) = f(x, y, y′, . . . , y(m−1))

wandelt man um in ein System von m Differentialgleichungen erster Ordnung

y′0 = y1 ,

y′1 = y2 ,

...y′m−2 = ym−1 ,

y′m−1 = f(x, y0, . . . , ym−1)

und wendet darauf das Eulersche Polygonzugverfahren an.


7.4 Einschrittverfahren - Definition und grundlegen-de Eigenschaften

Allgemeines Einschrittverfahren

Einen Algorithmus

y0 = y(x0) ,

xν = xν−1 + ν · h ,yν = yν−1 + h · Φ(xν−1, yν−1, h) ,

mit einer auf G × [0, α] definierten, reellwertigen Funktion Φ heißt allgemeines Ein-schrittverfahren für das auf dem Gebiet G ⊂ R2 definierte Anfangswertproblem

y′ = f(x, y), y(x0) = y0.

Man nennt Φ die Zuwachs-, Inkrement- oder Verfahrensfunktion.

Lokaler Diskretisierungsfehler

Ist z : (a, b)→ R die Lösung des Anfangswertproblems

z′(t) = f(t, z(t)), z(x) = y

mit einer auf G (bezüglich der zweiten Variablen) Lipschitz-stetigen Funktion f , soheißt die Funktion

∆(x, y, h) :=

z(x+h)−y

h, für h 6= 0

f(x, y), für h = 0

exakter relativer Zuwachs der Lösung z. Ferner bezeichnet man mit

θ(x, y, h) = ∆(x, y, h)− Φ(x, y, h)

den lokalen Diskretisierungsfehler des durch Φ definierten Einschrittverfahrens an derStelle (x, y) ∈ G bei Schrittweite h.

Konsistenzordnung

Ein Einschrittverfahren hat die Konsistenzordnung p, falls für den lokalen Diskretisie-rungsfehler gilt

θ(x, y, h) = O(hp) für h→ 0

für alle (x, y) ∈ G und alle f , deren partielle Ableitungen bis zur p-ten Ordnung in Gexistieren und dort stetig sind.

Konsistenz

Einschrittverfahren der Konsistenzordnung p ≥ 1 nennt man konsistent. Bei stetigenZuwachsfunktionen impliziert die Konsistenz die Forderung

Φ(x, y, 0) = f(x, y) .


Konsistenz des Eulerschen Polygonzugverfahrens

Das Eulersche Polygonzugverfahren hat die Konsistenzordung 1.

7.5 Die Methode des Taylorabgleichs

Verfahren der Konsistenzordnung p durch Taylorabgleich

Wählt man, falls f p-mal stetig differenzierbar ist, als Verfahrensfunktion Φ das Taylor-Polynom (p−1)-ten Grades der exakten Zuwachsfunktion ∆, entwickelt nach Potenzenvon h, so erhält man dadurch ein Einschrittverfahren der Konsistenzordnung p. Insbe-sondere erhält man durch

Φ(x, y, h) = f(x, y)︸︷︷︸y′(x)

(1)

ein Verfahren erster Ordnung (Eulersches Polygonzugverfahren). Durch

Φ(x, y, h) = f(x, y)︸︷︷︸y′(x)

+h

2(fx(x, y) + fy(x, y)f(x, y))︸︷︷︸

y′′(x)

(2)

erhählt man ein Verfahren zweiter Ordnung. Und durch

Φ(x, y, h) = f(x, y)︸︷︷︸y′(x)

+h

2(fx(x, y) + fy(x, y)f(x, y))︸︷︷︸

y′′(x)

+h2

6(fxx(x, y) + 2fxy(x, y)f(x, y) + fyy(x, y)f(x, y)2 + fy(x, y)[fx(x, y) + fy(x, y)f(x, y)])︸︷︷︸

y′′′(x)

(3)

erhält man ein Verfahren dritter Ordnung.

Die Brauchbarkeit dieser Verfahren in der Praxis hängt wesentlich davon ab, wie kom-pliziert die auftretenden partiellen Ableitungen sind.

7.6 Runge-Kutta-Verfahren der Konsistenzordnung 2

Allgemeines Runge-Kutta-Verfahren der Konsistenzordnung 2

Bei der Aufstellung von Runge-Kutta-Verfahren geht man ähnlich vor wie bei derMethodes des Taylorabgleichs. Für β 6= 0 wird durch die Verfahrensfunktion

Φ(x, y, h) = (1− β)f(x, y) + βf(x+

h

2β, y +

h

2βf(x, y)

)ein Runge-Kutta-Verfahren definiert. Man stellt fest, dass dieses Verfahren für jedenWert von β 6= 0 die Konsistenzordnung 2 besitzt.


Spezialfälle

Für β = 12erhält man das Vefahren von Heun mit

Φ(x, y, h) =1

2

(f(x, y) + f

(x+ h, y + hf(x, y)

))und für β = 1 das Halbschrittverfahren mit

Φ(x, y, h) = f(x+

1

2h, y +

1

2hf(x, y)

)Ist f von y unabhängig, so liefern diese beiden Verfahren die Sehnentrapezregel bzw.die Mittelpunktregel.

7.7 Allgemeine Runge-Kutta-Verfahren

Mehrstufige Runge-Kutta-Verfahren (R-stufige Verfahren)

Mit

k1 = f(x, y) ,

kr = f(x+ har, y + h ·r−1∑s=1

brsks) , r = 2, . . . , R,

wobei

ar =r−1∑s=1

brs , r = 2, . . . , R,

wird durch die Verfahrensfunktion

Φ(x, y, h) =R∑r=1

crkr

ein R-stufiges Runge-Kutta-Verfahren definiert. Für konsistente Verfahren gilt notwen-dig

R∑r=1

cr = 1. (Quadratur!)

Man beschreibt solche Verfahren durch das Schema

0a2 b21

a3 b31 b32

a4 b41 b42 b43...

......

...aR bR1 bR2 bR3 . . . bRR−1

c1 c2 c3 . . . cR−1 cR


Beispiele:

(1) 1-stufiges Runge-Kutta-Verfahren

01 Eulersches Polygonzugverfahren

(2) 2-stufige Runge-Kutta-Verfahren

01

2β1

2β

1− β β

mit β 6= 0: allgemeines 2-stufigesRunge-Kutta-Verfahren

speziell:

012

12

0 1

modifiziertes Polygonzugverfahren(Halbschrittverfahren)

01 1

12

12

Verfahren von Heun


013

13

23

0 23

14

0 34

Verfahren dritter Ordnung von Heun

012

12

1 −1 216

23

16

Verfahren dritter Ordnung von Kutta



012

12

12

0 12

1 0 0 116

13

13

16

”Klassisches” Runge-Kutta-Verfahren

013

13

23−1

31

1 1 −1 118

38

38

18

38-Regel

3-stufige Runge-Kutta-Verfahren der Konsistenzordnung 3

Jede Lösung des algebraischen Gleichungssystems

c1 + c2 + c3 = 1

c2a2 + c3a3 =1

2

c2a22 + c3a

23 =

1

3

c3b32a2 =1

6

definiert ein 3-stufiges Runge-Kutta-Verfahren

0a2 a2

a3 a3 − b32 b32

c1 c2 c3

der Konsistenzordnung 3.

Dieses Gleichungssystem besitzt eine zweiparametrige Lösungsschar. Unter der Zusatz-voraussetzung a2 = a3 ergibt sich eine einparametrige Schar von Runge-Kutta-Verfahren:

023

23

23

23− 1

4γ1

4γ14

34− γ γ


4-stufige Runge-Kutta-Verfahren der Konsistenzordnung 4

4-stufige Runge-Kutta-Verfahren

0a2 b21

a3 b31 b32

a4 b41 b42 b43

c1 c2 c3 c4

der Konsistenzordnung 4 werden beschrieben durch das algebraische System

a2 = b21

a3 = b31 + b32

a4 = b41 + b42 + b43

c1 + c2 + c3 + c4 = 1

a2c2 + a3c3 + a4c4 =1

2

a22c2 + a2

3c3 + a24c4 =

1

3

a32c2 + a3

3c3 + a34c4 =

1

3

a3b43c4 + a2b42c4 + a2b32c3 =1

6

a3a4b43c4 + a2a4b42c4 + a2a3b32c3 =1

8

a23 + b43c4 + a2

2b42c4 + a22b32c3 =

1

12

a2b32b43c4 =1

24.

Erreichbare Konsistenzordnung

Bezeichnet man mit p∗(R) die erreichbare Konsistenzordnung eines R-stufigen Runge-Kutta-Verfahrens, so gilt

p∗(R)

= R für R = 1, 2, 3, 4 ,

= R− 1 für R = 5, 6, 7 ,

= R− 2 für R = 8, 9 ,

≤ R− 2 für R ≥ 10 .


7.8 Konvergenz von Einschrittverfahren und eine Feh-lerabschätzung

Konvergente Einschrittverfahren

Ein Einschrittverfahren heißt konvergent in einem Rechteck R := [x0, b] × [c, d], wennfür alle Anfangswertprobleme (f sei auf R bezüglich y Lipschitz stetig)

y′ = f(x, y), y(x0) = y0 ,

deren exakte Lösung ganz in R verläuft, stets gilt

limh→0

x0+n·h=x

yn = y(x) gleichmäßig für x ∈ [x0, b].

Konvergenz und Konsistenz

Die Zuwachsfunktion Φ mit

Φ : [x0, b]× [c, d]× [0, h0]→ R, h0 > 0

sei stetig differenzierbar und genüge einer Lipschitzbedingung bezüglich der zweitenVariablen y der Form

|Φ(x, y, h)− Φ(x, y, h)| ≤ L|y − y| .

Dann sind die folgenden beiden Aussagen äquivalent:

(1) Das durch Φ definierte Verfahren ist konsistent.

(2) Das durch Φ definierte Verfahren ist konvergent im Rechteck R := [x0, b]× [c, d].

Fehlerabschätzung für den Verfahrensfehler

Die Zuwachsfunktion Φ sei stetig in S := [x0, b] × [c, d] × [0, h0] und genüge einerLipschitzbedingung der Form

|Φ(x, y, h)− Φ(x, y, h)| ≤ L|y − y| , (x, y, h), (x, y, h) ∈ S .

Für den lokalen (relativen) Diskretisierungsfehler gelte die Abschätzung

|θ(xν , yν , h)| ≤ Dhr ,

d.h. das Verfahren habe die Konsistenzordnung r. Dann gilt für 0 < h ≤ h0 die a-priori-Fehlerabschätzung

|y(xν)− yν | ≤ eL(xν−x0)|y(x0)− y0|+eL(xν−x0) − 1

LDhr , ν = 1, . . . , n .


7.9 Abschließende Bemerkungen

Schrittweitensteuerung

Praktisch wird die Schrittweite h meistens während der Rechnung verändert, d.h.man hat Schrittweiten hν (ν = 1, 2, . . .) statt einer von vornherein fest gewähltenSchrittweite h. Zur aktuellen Wahl der Schrittweite hν werden Schrittweitensteuerungs-Algorithmen benutzt.

Mehrschrittverfahren

Bei den hier behandelten Einschrittverfahren wird zur Berechnung von yν nur der vor-hergehende Wert yν−1 verwendet (die Werte xi = x0 +ih liegen ja fest). Mehrschrittver-fahren verwenden zur Berechnung von yν die Werte yν−1, yν−2, . . . , yν−r, wobei r ≥ 2fest ist.

Implizite Verfahren

Die hier vorgestellten Verfahren sind sämtlich explizit. Bei impliziten Verfahren ist derneue Wert yν nur implizit als Lösung einer gewissen gleichung gegeben. So lautet z.B.das implizite Euler-Verfahren

yν = yν−1 + hf(xν , yν), ν = 1, 2, . . .

Zur Bestimmung von yν muss man diese (i.a. nichtlineare) Gleichung numerisch lösen.Als Beispiel betrachten wir das Differentialgleichungssystem

(~y)′ = A~y, ~y(0) = ~y0,

wobei A ∈ Rm×m (oder A ∈ Cm×m) sei. Hier ist xν = νh und für das (explizite)Euler-Verfahren aus Abschnitt 7.3 erhalten wir

~yν = ~yν−1 + hA~yν−1 = (Em + hA)~yν−1 = . . . = (Em + hA)ν~y0, ν = 1, 2, 3, . . . .

Für das implizite Euler-Verfahren erhalten wir hingegen

~yν = ~yν−1 + hA~yν , d.h.(Em − hA)~yν = ~yν−1.

Hier ist also ein lineares Gleichungssystem zu lösen. Nach Aufgabe 4.7 ist Em−hA fürkleine h > 0 invertierbar und also

~yν = (Em − hA)−1~yν−1 = . . . = ((Em − hA)−1)ν~y0, ν = 1, 2, . . . .

Man beachte, dass für diese Problem die exakte Lösung gegeben ist durch ~y(x) = exA~y0,x ≥ 0, und dass gilt

limn→∞

(E +

x

nA)n~y0 = exA~y0 = lim

n→∞

((E − x

nA)−1)n

~y0,

was zumindest im Fall m = 1 aus der HM bekannt ist. Natürlich bedeutet das Löseneines Gleichungsystems in jedem Schritt einen numerischen Mehraufwand. Das Stabi-litätsverhalten impliziter Verfahren ist aber besser, wenn A betragsmäßig große (imVerhältnis zu den anderen) Eigenwerte mit negativem Realteil hat (steife Differential-gleichungen).

Kapitel 8

Finite Differenzen Verfahren zurLösung von Randwertproblemen

8.1 Diskretisierung bei Randwertproblemen für ge-wöhnliche DGlen

In diesem Abschnitt erläutern wir exemplarisch an einer besonders einfachen Situa-tion, wie man mit Hilfe von Differenzenapproximationen der Ableitungen numerischeLösungen von Randwertaufgaben gewinnen kann.

Wir gehen aus von einem Randwertproblem für eine gewöhnliche Differentialgleichungzweiter Ordnung des folgenden, beispielhaften Typs

y′′ − y = 0 auf (0, 1)

y(0) = 1

y(1) =1

2(e+

1

e) = cosh(1).

Gesucht ist eine zweimal stetig differenzierbare Funktion

y : [0, 1]→ R,

die der Differentialgleichung und den Randbedingungen genügt. Man kann die Lösungdieses Problems leicht erraten; es gilt

y(x) = cosh(x)

Aufgabe 8.1. Bestimmen Sie konstruktiv die Lösung des betrachteten Randwertpro-blems, indem Sie zunächst die Lösungsgesamtheit der Differentialgleichung bestimmenund anschließend daraus diejenige(n) Lösung(en) aussondern, welche außerdem denRandbedingungen genügen.

Wir wollen nun ein numerisches Verfahren entwickeln, um Näherungslösungen der ge-stellten Randwertaufgabe zu gewinnen. Zu diesem Zweck diskretisieren wir das Problemund unterteilen das Einheitsintervall [0, 1] äquidistant in N + 1 Teilintervalle gemäß

xi = ih, i = 0, ..., N + 1,

h : =1

N + 1.

99

KAPITEL 8. FINITE DIFFERENZEN FÜR RANDWERTPROBLEME 100

y = cosh(x)cosh(1)

1

1

...x xx 1

1

x = 0 0

1 2 i

Gesucht sind die Wertey(xi), i = 0, ..., N + 1;

dabei sind uns allerdings wegen der gegebenen Randbedingungen die beiden Werte

y(x0) = 1,

y(xN+1) = cosh(1)

bereits bekannt. Wir approximieren nun die Ableitungswerte

y′′(xi), i = 1, ..., N,

mit Hilfe der sogenannten zweiten Differenzen gemäß

y′′(xi) =y(xi−1)− 2y(xi) + y(xi+1)

h2+ ri(h).

Dabei bezeichnet ri(h) den Fehler zur Schrittweite h. Es gilt wegen des TaylorschenSatzes

ri(h) = O(h2) für h→ 0,

denn aus

y(xi − h) = y(xi)− hy′(xi) +h2

2y′′(xi)−

h3

6y′′′(xi) +O(h4)

y(xi + h) = y(xi) + hy′(xi) +h2

2y′′(xi) +

h3

6y′′′(xi) +O(h4)


folgt

y(xi−1)− 2y(xi) + y(xi+1)

h2= y′′(xi) +O(h2).

Wir setzen die obige Entwicklung von y′′(xi) in die Differentialgleichung ein und erhal-ten an den Stellen xi, i = 1, ..., N , die folgenden Gleichungen

y(xi−1)− 2y(xi) + y(xi+1)

h2− y(xi) + ri(h) = 0, i = 1, ..., N,

wobei zusätzlich

y(x0) = 1,

y(xN+1) = cosh(1)

gilt. Wenn wir nun die Fehlergrößen ri(h) vernachlässigen, so wird dieses Gleichungs-system im Allgemeinen nicht mehr von den Werten y(xi) erfüllt. Mit Näherungswerten

yi ≈ y(xi), i = 1, ..., N,

und

y0 = y(x0)

yN+1 = y(xN+1)

erhalten wir so das lineare Gleichungssystem

yi−1 − 2yi + yi+1

h2− yi = 0, i = 1, ..., N

y0 = 1,

yN+1 = cosh(1).

Wir setzen die bekannten Randwerte in die erste und die N -te Gleichung ein undformen gleichzeitig etwas um. Dies liefert

(2 + h2)y1 − y2 = 1,

−yi−1 + (2 + h2)yi − yi+1 = 0, i = 2, ..., N − 1

−yN−1 + (2 + h2)yN = cosh(1).

Nach Multiplikation jeder Gleichung mit

τ =1

2 + h2

hat das lineare Gleichungssystem die folgende Gestalt:

1 −τ 0 0 ... 0−τ 1 −τ 0 ... 00 −τ 1 −τ 0... . . . ...0 ... −τ 1 −τ0 ... −τ 1

y1

y2

...

yN

=

τ0

...

τ cosh(1)


Resultat 8.2. Diskretisiert man das Randwertproblem

y′′ − y = 0,

y(0) = 1,

y(1) = cosh(1)

mit Hilfe von zweiten Differenzen, so erhält man das lineare Gleichungssystem1 −τ 0 0 ... 0−τ 1 −τ 0 ... 0... . . . ...0 ... −τ 1 −τ0 ... −τ 1

y1

y2...

yN

=

τ0...

τ cosh(1)

wobei

τ :=1

2 + h2,

h :=1

N + 1,

und yi, i = 1, ..., N Näherungswerte für y(ih) sind.

Dieses lineare Gleichungssystem hat einige leicht zu verifizierende Eigenschaften, diewir in folgendem Resultat festhalten.

Resultat 8.3. Die Matrix A des obigen linearen Gleichungssystems hat folgende wich-tige Eigenschaften:

1. A is reell symmetrisch.

2. A hat Tridiagonalgestalt.

3. A ist strikt diagonaldominant.

4. Die Eigenwerte von A liegen im Intervall [1 − 2τ, 1 + 2τ ] ⊂ (0, 2), wie man mitHilfe des Gerschgorinschen Kreissatzes erkennt. Insbesondere ist A positiv definit.

Da A die hier aufgelisteten Eigenschaften besitzt, sind offensichtlich einige der unsbekannten Lösungsmethoden für lineare Gleichungssysteme anwendbar wie z.B. dieLösung mit Hilfe der Cholesky-Zerlegung.

8.2 Diskretisierung bei Randwertproblemen für par-tiellen Differentialgleichungen

Exemplarisch behandeln wir in diesem Zusammenhang das sogenannte ”Modellpro-blem”, das, wie schon sein Name besagt, in der Literatur häufig herangezogen wird, umdie Wirksamkeit eines Diskretisierungsverfahrens zu demonstrieren oder um verschie-dene Näherungsmethoden zu vergleichen.


Wir betrachten das sogenannte Dirichletproblem für ein Quadrat. Darunter verstehtman die folgende Problemstellung:

Gesucht wird eine zweimal stetig differenzierbare Funktion

u = u(x, y),

die im Innern des Quadrates

Q := (x, y) : 0 ≤ x, y ≤ 1

der Laplace-Gleichung∂2u

∂x2+∂2u

∂y2= 0

genügt und auf dem Rand ∂Ω von Q vorgeschriebene Werte

u(x, y) = f(x, y), (x, y) ∈ ∂Q,

annimmt. Beispiele für Lösungen der Laplace-Gleichung sind z.B. elektrische Potentialevon Ladungsverteilungen, falls man die Potentiale außerhalb des Bereichs betrachtet,in dem die Ladungen konzentriert sind.

Ein Näherungsverfahren zur Lösung des Modellproblems entwickeln wir wiederum mitHilfe von Diskretisierungen. Dazu überdecken wirQmit einem Gitter der Maschenweite

h =1

N + 1.

x ... x = 1y = 0

1 2

y

x

N+1

2

y = 11

0

x = 00

N+1

y = 1

Gesucht sind die Funktionswerte

uij := u(xi, yj), i, j = 1, ..., N.

Näherungen dafür erhalten wir als Lösungen eines linearen Gleichungssystems, das wirmit Hilfe von Diskretisierung gewinnen. Wir ersetzen dabei die partiellen Ableitungen

∂2u

∂x2

∣∣∣(xi,yj)

,∂2u

∂y2

∣∣∣(xi,yj)

durch zweite Differenzen. Dazu betrachten wir einen ”Stern” im obigen Gitter:


j+1(x ,y ) i

i−1 i i+1(x ,y )j (x ,y )

j(x ,y )j

(x ,y )i j−1

Mit Hilfe von zweiten Differenzen folgt analog zum eindimensionalen Fall

∂2u

∂x2

∣∣(xi,yj)

=ui−1,j − 2uij + ui+1,j

h2+O(h2)

und∂2u

∂y2

∣∣(xi,yj)

=ui,j−1 − 2uij + ui,j+1

h2+O(h2)

für h → 0. Vernachlässigen wir nun die O(h2)-Terme, so erhalten wir das lineareGleichungssystem

ui−1,j + ui,j−1 − 4uij + ui,j+1 + ui+1,j = 0, i, j = 1, ..., N,

wobei zusätzlich die Randbedingungen

uij = f(xi, yj) =: fij für i oder j ∈ 0, N + 1

zu erfüllen sind. Setzt man diese bekannten Randwerte in das obige lineare Gleichungs-system ein, so erhält man ein lineares Gleichungssystem von N2 Gleichungen in denN2 Unbekannten uij mit i, j = 1, ..., N . Da in jeder Gleichung höchstens 5 Unbekann-te miteinander durch nichtverschwindende Koeffizienten verbunden sind, enthält dieKoeffizientenmatrix des betrachteten linearen Gleichungssystems sehr viele Nullen. Esliegt eine sogenannte ”sparse matrix” vor.

Resultat 8.4. Durch Diskretisieren des Modellproblems

∂2u

∂x2+∂2u

∂y2= 0 für (x, y) ∈ Q

u(x, y) = f(x, y) für (x, y) ∈ ∂Q

mit Hilfe von zweiten dividierten Differenzen erhält man das lineare Gleichungssystem

ui−1,j + ui,j−1 − 4uij + ui,j+1 + ui+1,j = 0, i, j = 1, ..., N,

uij = fij falls i ∈ 0, N + 1 oder j ∈ 0, N + 1.

Während bei dem oben betrachteten eindimensionalen Randwertproblem die Indizie-rung der Unbekannten yi, i = 1, ..., N , in natürlicher Weise vorgegeben ist, kann man


beim Modellproblem nicht in so eindeutiger Weise eine speziell Anordnung der Index-mengen (i, j) : i, j = 1, ..., N als besonders bevorzugt ansehen. Wir werden einespezielle Nummerierung der Unbekannten untersuchen, die zu in gewisser Weise ausge-zeichneter Struktur der Koeffizientenmatrix führt. Dabei denken wir uns die Gleichun-gen, die Randterme enthalten, in die übrigen eingesetzt.

Nummerierung in Richtung der Koordinatenachsen

Zunächst wird man an die Nummerierung der Unbekannten in Richtung der Koordinaten-achsen denken, d.h. man ordnet die Indizes der Unbekannten uij aus Resultat 8.4 inder Form (u11, u21, ..., uN1, u12, ..., uN2, ..., uNN):

N

N

N+2N+1

1 2

2N

2N −N+1

2

Bei dieser Nummerierung ergibt sich offensichtlich eine Bandstruktur für die Glei-chungsmatrix, da jede Unbekannte höchstens mit ihren beiden direkten Nachbarn undden beiden mit einer Nummer N höher oder niedriger durch einen nichtverschwinden-den Koeffizienten verknüpft ist:

k

k−N

k+1k−1

k+N


Man erhält folgende Gleichungsmatrix:

−4 1 0 0 1

1. . . . . . . . .. . . . . . 1

. . .1 −4 1

1 −4 1 0 0. . . 1

. . . . . .. . . . . . . . . 1

1 1 −4. . . 1

. . . . . .. . . . . .

. . . 11 −4 1 0 0

. . . 1. . . . . .

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

Die Matrix zerfällt in natürlicher Weise in N2 Blöcke, die ebenfalls eine besonderseinfache Struktur besitzen: Bezeichnen wir die auftretenden Blöcke mit Aνµ, ν, µ =1, ..., N so gilt

Aνν =

−4 1 0 0 ... 0

1. . . . . . 0 ... 0

0. . . ...

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

Aνν ist also eine Tridiagonalmatrix sehr einfacher Bauart. Weiter gilt

Aν,ν+1 = Aν+1,ν =

1 0 ... 0

0. . . 0

0 ... 0 1

, ν = 1, ..., N − 1

sowie Aνµ = (0)N×N ′ für |ν − µ| ≥ 2. Von den N2 Elementen sind also ”fast alle” Null;es treten nur

N(N + 2(N − 1)) + 2(N − 1)N = 5N2 − 4N

von Null verschiedene Elemente auf.

Kapitel 9

Finite Elemente

9.1 Schwache Formulierung von Randwertaufgaben

Betrachten wir erneut die Randwertaufgabe

− (∂2u

∂x2+∂2u

∂y2︸︷︷︸=:∆u

) = f in Ω, u = 0 auf ∂Ω (9.1)

mit gegebenem (z.B. stetigem) f : Ω→ R, wobei Ω ⊂ R2 ein polygonales Gebiet sei.

Zuerst leiten wir die sogenannten schwache Formulierung der obigen Randwertaufgabeher. Dazu nehmen wir an, dass u eine auf Ω stetige und in Ω zweimal stetig differen-zierbare Lösung von (9.1) ist.

Sei V ⊂ C(Ω) der Raum der stetigen Funktionen, die in Ω stückweise stetig differen-zierbar und auf ∂Ω gleich Null sind. Multiplizeren wir die Gleichung (9.1) mit einerFunktion ϕ ∈ V so ergibt sich∫

Ω

(−∆u)(x, y)ϕ(x, y) d(x, y) =

∫Ω

f(x, y)ϕ(x, y) d(x, y).

Mit dem Gaußschen Integralsatz und der Ausnutzung der Randbedingung u = 0 auf∂Ω folgt ∫

Ω

(−∆u)(x, y)ϕ(x, y) d(x, y)

=

∫Ω

∇u(x, y)∇ϕ(x, y) d(x, y)−∫∂Ω

∂u

∂ν(x, y) ϕ(x, y)︸︷︷︸

=0 auf ∂Ω

d(x, y)

=

∫Ω

∇u(x, y)∇ϕ(x, y) d(x, y) für jedes ϕ ∈ V.

Die resultierende Integralbeziehung∫Ω

∇u(x, y)∇ϕ(x, y) d(x, y) =

∫Ω

f(x, y)ϕ(x, y) d(x, y) für jedes ϕ ∈ V (9.2)

betrachten wir als ”Ersatz” für die Differentialgleichung (9.1). Wir nennen daher (9.2)die schwache Formulierung von (9.1). Es lässt sich mit Mitteln der Funktionalanalysis

107

KAPITEL 9. FINITE ELEMENTE 108

zeigen, dass (9.2) eine eindeutige Lösung u ∈ V hat. Dazu benutzt man die Theorieder Sobolevräume.

Nun führen wir zur Abkürzung folgende Bezeichnungen ein. Für u, v ∈ V sei

a(u, v) :=

∫Ω

∇u(x, y)∇v(x, y) d(x, y)

b(v) :=

∫Ω

f(x, y)v(x, y) d(x, y).

Damit ist eine Bilinearform a : V × V → R und eine Linearform b : V → R definiert.Die schwache Formulierung (9.2) der Randwertaufgabe (9.1) lässt sich somit wie folgtleichter schreiben: finde u ∈ V so dass gilt

a(u, ϕ) = b(ϕ) für alle ϕ ∈ V. (9.3)

Das Auffinden einer Lösung von (9.3) ist ein unendlichdimensionales Problem, da derRaum V ein unendlichdimensionaler Funktionenraum ist. Als Nächstes werden wir eineendlichdimensionale Approximation an (9.3) suchen.

9.2 Ritz-Galerkin Approximation

Im Raum V der stetigen und in Ω stückweise stetig differenzierbaren Funktionen, dieauf ∂Ω gleich Null sind, wählen wir einen k-dimensionalen Unterraum Vk ⊂ V ⊂ C(Ω).Zur näherungsweisen Lösung der schwachen Formulierung (9.3) der Randwertaufgabe(9.1) suchen wir nun nach einer Lösung u ∈ Vk, die∫

Ω

∇u(x, y)∇ϕ(x, y) d(x, y) =

∫Ω

f(x, y)ϕ(x, y) d(x, y) für jedes ϕ ∈ Vk (9.4)

erfüllt. Eine äquivalente Formulierung ist: finde u ∈ Vk mit

a(u, ϕ) = b(ϕ) für alle ϕ ∈ Vk. (9.5)

Wir heben zwei wesentliche Unterschiede von (9.4) bzw. (9.5) im zu Gegensatz zu (9.2)bzw. (9.3) hervor:

1. Gesucht wirde eine Lösung u im endlichdimensionalen Unterraum Vk.

2. Die Bedingung a(u, ϕ) = b(ϕ) wird nur für die Elemente ϕ des endlichdimensio-nalen Unterraumes Vk gefordert.

Welche Gestalt hat eine solche Lösung u? Dazu wählen wir eine Basis ϕ1, ..., ϕk vonVk und betrachten den Ansatz

u =k∑j=1

αjϕj

mit α1, ..., αk ∈ R. Eingesetzt in (9.4) erhalten wir

k∑j=1

αj

∫Ω

∇ϕj(x, y)∇ϕl(x, y) d(x, y) =

∫Ω

f(x, y)ϕl(x, y) d(x, y), l = 1, ..., k


beziehungsweisek∑j=1

αja(ϕj, ϕl) = b(ϕl) für alle l = 1, . . . , k.

Dabei handelt es sich offenbar um ein lineares Gleichungssystem in den k Unbekanntenz = (α1, . . . , αk)

T

(∗) Az = b

wobei

Ajl = Alj = a(ϕj, ϕl) =

∫Ω

∇ϕj(x, y)∇ϕl(x, y) d(x, y), j, l = 1, ..., k

bl = b(ϕl) =

∫Ω

f(x, y)ϕl(x, y) d(x, y), l = 1, ..., k

Die Matrix A = (Ajl)nj,l=1 heisst Steifigkeitsmatrix und der Vektor b = (b1, . . . , bk)

T

heisst Lastvektor. Man rechnet leicht nach, dass A positiv definit ist. Dieses Verfahren,d.h. die Wahl des k-dimensionalen Unterraums, die Wahl der Basis und die anschließen-de Bestimmung der Unbekannten (α1, . . . , αk)

T durch Lösung des linearen Gleichungs-systems (∗) nennt man Ritz-Galerkin-Verfahren.

Eine der wichtigsten Fragen beim Ritz-Galerkin-Verfahren ist die folgende: wie gutapproximiert die Lösung u von (9.4) die exakte Lösung u von (9.2)? Eine Antwortdarauf wird im folgenden Satz gegeben.

Satz 9.1 (Céas Lemma).Ist u ∈ V eine Lösung von (9.2) und u ∈ Vk eine Lösung von (9.4), so gilt mit dersogenannten Energienorm ‖ · ‖a :=

√a(·, ·) die Abschätzung:

‖u− u‖a = minϕ∈Vk‖ϕ− u‖a.

Céas Lemma besagt, dass die Ritz-Galerkin-Approximation u unter allen anderen Ele-menten der Raumes Vk gemessen in der Energienorm ‖ · ‖a die optimale Näherung andie exakte Lösung u ist. Alle weiteren, konkreten Abschätzungen des Fehlers basierenauf dieser Erkenntnis.

9.3 Umsetzung des Ritz-Galerkin-Verfahrens

Offensichtlich sollte man die Dimension k des Unterraumes Vk möglichst groß wählen,um eine gute Approximation zu erreichen. Zusätzlich hätte man gerne, dass A einedünn besetzte Matrix ist. Dies erreicht man, indem man die Basisfunktionen so wählt,dass sie einen kleinen Träger haben. Dabei ist der Träger einer stetigen Funktion ϕ

durch supp(ϕ) = x ∈ Ω : ϕ(x) 6= 0 definiert.Beachtet man, dass nur dann Ajl 6= 0 sein kann, wenn supp(ϕj)∩ supp(ϕl) 6= ∅ gilt, sosieht man, dass bei ”kleinen” Trägern ”viele” der Matrix-Einträge Ajl = 0 sind.

Im Folgenden betrachten wir eine spezielle Wahl des Unterraumes Vk und eine spezi-elle Konstruktion einer Basis. Dazu zerlegen wir das zweidimensionale Grundgebiet Ω


ξ

ξ

ξ

ξ

ξ

ξ

2

6

5

4

3

1

Ω

geschickt in Dreiecke. Diesen Prozess nennt man Triangulierung von Ω. Die Triangu-lierung eines Grundgebietes kann z.B. wie im obigen Bild aussehen.

Wir bezeichnen die inneren Knotenpunkte mit ξ1, ..., ξk. Für j = 1, ..., k sei die Funktionϕj : Ω→ R definiert durch die folgenden drei Forderungen:

1. ϕj(ξi) = δij

2. auf jedem Dreick der Triangulierung sei ϕj(x, y) = ax+by+c linear (a, b, c könnendabei von Dreieck zu Dreieck verschieden sein)

3. ϕj = 0 auf ∂Ω

Der Graph von ϕj ist also eine Pyramide mit Spitze in ξj, die in den Nachbarknotenvon ξj auf 0 hinuntergeht und auf dem Rest der Menge Ω gleich Null ist.

Die Basisfunktionen ϕj heißen dann Formfunktionen (node shape functions). Mit Vkbezeichnen wir die lineare Hülle der Formfunktionen ϕ1, . . . , ϕk. Das Ritz-Galerkin-Verfahren angewandt auf diesen speziellen Unterraum Vk ist ein Beispiel für eine Nä-herungsmethode, die in der Literatur als Finite-Elemente-Methode bekannt ist.

Es gibt durch die Wahl anderer Unterräume zahlreiche weitere Beispiele für die Finite-Elemente-Methode. So kann man neben den stückweise linearen Basisfunktionen auchandere Basisfunktionen benutzen. Ebenso werden Zerlegungen des Grundgebiets Ω inVierecke anstelle von Dreiecken betrachtet. Und im Fall von drei Raumdimensionenwerden Zerlegungen in Tetraeder bzw. Prismen verwendet.

Documents

Skript zur Vorlesung - Fakultät für Mathematik · Skript zur Vorlesung Numerische Methoden für die Fachrichtungen Elektrotechnik, Meteorologie, Geodäsie und Geoinformatik Prof