. 1
( 31 .)



>>

Numerische Mathematik I



Prof. Dr. Christof Buskens
¨


AG Optimierung & Optimale Steuerung
Zentrum fur Technomathematik
¨
Universit¨t Bremen
a
28334 Bremen, Germany




Vorlesungsskript
Sommersemester 2004




(Unkorrigierte Fassung)
Vorwort
Die vorliegende Ausarbeitung entstand wahrend meiner Tatigkeit am Zentrum
¨ ¨
fur Technomathematik der Universit¨t Bremen. Sie entstand im Rahmen einer
a
¨
Vorlesung, die ich im Sommersemster 2004 gehalten habe. An dieser Stelle m¨chte
o
ich mich bei allen Teilnehmerinnen und Teilnehmern fur ihr reges Interesse und
¨
ihre aktive Mitarbeit bedanken.




¨
Bremen, Juli 2004 Christof Buskens
Inhaltsverzeichnis


Inhaltsverzeichnis 5


1 Einleitung 9
1.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
¨
1.2 Literatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Ein kurzer geschichtlicher Ruckblick . . . . . . . . . . . . . . . . . 11
¨
1.4 Was ist Numerik? . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Motivationsbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 Vorl¨u¬ges Fazit . . . . . . . . . .
a . . . . . . . . . . . . . . . . . 15


2 Fehleranalyse 17
2.1 Maschinenzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Maschinenzahlen auf der Zahlengerade . . . . . . . . . . . . . . . 19
2.3 Rundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Gleitpunkt-Arithmetik . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Fehlerfortp¬‚anzung, Kondition . . . . . . . . . . . . . . . . . . . . 24
2.6 Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26


3 Lineare Gleichungssysteme 29
3.1 Einfuhrung und Aufgabenstellung . . . . . . . . . . . . . . . . . . 29
¨
3.2 LR“Zerlegung und Gauß“Elimination . . . . . . . . . . . . . . . . 31
3.2.1 Idee der Gauß“Elimination/LR“Zerlegung . . . . . . . . . 31
3.2.2 Frobeniusmatrizen . . . . . . . . . . . . . . . . . . . . . . 32

5
6 Inhaltsverzeichnis




3.2.3 Gauß“Elimination/LR“Zerlegung ohne Pivoting . . . . . . 34
3.2.4 Permutationsmatrizen . . . . . . . . . . . . . . . . . . . . 36
3.2.5 Gauß“Elimination/LR“Zerlegung mit Pivoting . . . . . . . 37
3.2.6 Aufwandsbestimmung . . . . . . . . . . . . . . . . . . . . 41
3.2.7 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Matrizen mit speziellen Eigenschaften . . . . . . . . . . . . . . . . 43
3.3.1 Diagonaldominante Matrizen: Diagonalstrategie . . . . . . 43
3.3.2 Positiv de¬nite Matrizen: Cholesky“Verfahren . . . . . . . 45
3.3.3 Bandmatrizen: Bandausnutzende Verfahren . . . . . . . . 49
3.4 Fehleranalyse und Fehlerbehandlung . . . . . . . . . . . . . . . . 51
3.4.1 Fehlerabsch¨tzungen . . . . . . . . . . . . . . . . . . . .
a . 51
3.4.2 Skalierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.3 Iterative Nachverbesserung . . . . . . . . . . . . . . . . . . 55
3.5 Die QR-Zerlegung einer Matrix, das Verfahren von Householder . 56
3.5.1 Einleitung und Motivation . . . . . . . . . . . . . . . . . . 56
3.5.2 Householdermatrizen . . . . . . . . . . . . . . . . . . . . . 57
3.5.3 QR“Zerlegung/Verfahren von Householder . . . . . . . . . 59
3.5.4 Erweiterungen . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.6 Lineare Ausgleichsrechnung, diskrete Approximation . . . . . . . 62
3.6.1 Normalgleichung . . . . . . . . . . . . . . . . . . . . . . . 62
3.6.2 Numerische L¨sung . . . . . . . . . . . . . . . . . . . . .
o . 65
3.6.3 Diskrete Approximation . . . . . . . . . . . . . . . . . . . 66


4 Nichtlineare Gleichungen und Gleichungssysteme 69
4.1 Einfuhrung und Aufgabenstellung . . . . . . . . . . . . . . . . . . 69
¨
4.2 Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.1 Fixpunkte . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2.2 Konvergenz . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.3 Nichtlineare Gleichungen . . . . . . . . . . . . . . . . . . . . . . . 72
4.3.1 Bisektionsverfahren . . . . . . . . . . . . . . . . . . . . . . 72
4.3.2 Newton“Verfahren . . . . . . . . . . . . . . . . . . . . . . 74
4.3.3 Sekanten“Verfahren . . . . . . . . . . . . . . . . . . . . . . 75
4.4 Konvergenz von Iterationsverfahren . . . . . . . . . . . . . . . . . 77
4.4.1 Kontraktion . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.4.2 Fixpunktsatz von Banach . . . . . . . . . . . . . . . . . . 79
4.4.3 Konvergenzs¨tze . . . . . . . . . . . . . . .
a . . . . . . . . 81
4.4.4 Konvergenz des Newton“Verfahrens . . . . . . . . . . . . . 82
4.5 Das Newton“Verfahren im IRn . . . . . . . . . . . . . . . . . . . . 83
4.5.1 Herleitung des Newton“Verfahrens . . . . . . . . . . . . . 83
Inhaltsverzeichnis 7




4.5.2 Praktische Realisierung . . . . . . . . . . . . . . . . . . . . 85
4.5.3 Newton“Kantorovich . . . . . . . . . . . . . . . . . . . . . 86
4.5.4 Erweiterungen . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.5.4.1 Approximation von f (x) durch Di¬erenzen . . . 88
4.5.4.2 »-Strategie, Modi¬ziertes Newton-Verfahren . . . 89


5 Interpolation 91
5.1 Einfuhrung und Aufgabenstellung . . . . . . . . . . . . . . . . . . 91
¨
5.2 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.2.1 Existenz und Eindeutigkeit der Polynominterpolation . . . 92
5.2.2 Interpolationsformel von Lagrange . . . . . . . . . . . . . . 93
5.2.3 Der Algorithmus von Aitken und Neville . . . . . . . . . . 94
5.2.3.1 Rekursionsformel von Aitken . . . . . . . . . . . 94
5.2.3.2 Variante von Neville . . . . . . . . . . . . . . . . 94
5.2.4 Die Newton™sche Interpolationsformel, Dividierte Di¬erenzen 95
5.2.5 Interpolationsfehler . . . . . . . . . . . . . . . . . . . . . . 98
5.2.6 Konvergenz . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.3 Trigonometrische Interpolation . . . . . . . . . . . . . . . . . . . . 100
5.3.1 Diskrete Fouriertransformation . . . . . . . . . . . . . . . 100
5.3.2 Trigonometrische Interpolation . . . . . . . . . . . . . . . 102
5.3.3 Schnelle Fourier“Transformation (FFT) . . . . . . . . . . . 103
5.3.4 Anwendungen . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4 Spline“Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4.1 Polynom“Splines . . . . . . . . . . . . . . . . . . . . . . . 105
5.4.2 Kubische Splines . . . . . . . . . . . . . . . . . . . . . . . 108
5.4.2.1 Einfuhrung und Aufgabenstellung . . . . . . . . . 108
¨
5.4.2.2 Existenz und Eindeutigkeit . . . . . . . . . . . . 109
5.4.2.3 Geometrische und mechanische Interpretation . . 111
5.4.2.4 Die Berechnung von Spline-Funktionen . . . . . . 112
5.4.2.5 Konvergenzeigenschaften . . . . . . . . . . . . . . 115
5.5 Numerische Di¬erentiation . . . . . . . . . . . . . . . . . . . . . . 118


6 Integration 121
6.1 Einfuhrung und Aufgabenstellung . . . . . . . . . . . . . . . . . . 121
¨
6.2 Newton“Cotes“Formeln . . . . . . . . . . . . . . . . . . . . . . . . 121
6.3 Zusammengesetzte Newton“Cotes“Formeln . . . . . . . . . . . . . 124
6.3.1 Zusammengesetzte Trapezregel . . . . . . . . . . . . . . . 125
6.3.2 Verfeinerung der zusammengesetzten Trapezregel . . . . . 126
8 Inhaltsverzeichnis




6.4 Die Gaußsche Integrationsmethode . . . . . ....... . . . . . 127
6.4.1 Orthogonalpolynome . . . . . . . . . ....... . . . . . 127
6.4.2 Gaußintegration . . . . . . . . . . . . ....... . . . . . 129
6.5 Integration und Extrapolation . . . . . . . . ....... . . . . . 132
6.5.1 Euler-Maclaurin™sche Summenformel ....... . . . . . 132
6.5.2 Anwendung der Extrapolation auf die Integration . . . . . 133
6.5.3 Integrationsfehler . . . . . . . . . . . ....... . . . . . 135


Literaturverzeichnis 139
Kapitel 1

Einleitung

1.1 Einfuhrung
¨
Gegenstand der numerischen Mathematik (oder einfach Numerik) oder auch prak-
tischen Mathematik ist die n¨herungsweise L¨sung mathematischer Probleme
a o
durch Zahlenwerte. Die Losungsberechnung erfolgt dabei durch einen Algorith-
¨
mus, d.h. durch eine Folge von elementaren Anweisungen und Rechenoperationen,
die sich auf einem Computer ausfuhren lassen. Ein solcher Algorithmus stutzt
¨ ¨
sich oft auf Ergebnisse der reinen Mathematik und re¬‚ektiert mathematische Ei-
genschaften des Problems. Die zu behandelnden Probleme stammen oft aus den
Ingenieur“ und Naturwissenschaften.

Beispiel 1.1. Als ein erstes praktisches Beispiel sei der Landean¬‚ug eines Ver-
kehrs¬‚ugzeuges bei Scherwinden benannt, bei dem es zu 2“3 Unf¨llen pro Jahr
a
kommt (bereits > 500 Tote), vgl. Abbildung 1.1.




Abbildung 1.1: Scherwinde beim Landean¬‚ug.

9
10 Einleitung




Aufgrund der Fallwinde w¨re eine sichere Vorgehensweise, den Landean¬‚ug ab-
a
zubrechen, was aber ist hierzu die sicherste Vorgehensweise? Ein sehr sicherer
Weg ist die w¨hrend des Durch¬‚uges durch den Scherwind angenommene min-
a
male H¨he zu maximieren, vgl. Abbildung 1.2; wie aber kann das erreicht werden?
o

Höhe




h min

max !

Reichweite


Abbildung 1.2: Maximierung der minimalen H¨he.
o

Da die physikalischen Vorg¨nge sehr gut bekannt sind kann zun¨chst ein sehr rea-
a a
lit¨tsnahes mathematisches Modell erstellt werden.
a
Die Mathematik kommt dann intensiv bei der L¨sung des Problems zur An-
o
wendung. Hierzu muß zun¨chst eine theoretische Aufarbeitung der zu verwen-
a
denden L¨sungsmechanismen vorgenommen werden, bzw. neu entwickelt wer-
o
den. Fur unser Beispiel greifen wir auf die sogenannte Variationsrechnung bzw.
¨
Optimale Steuerung zuruck. Die hierzu angebotenen L¨sungsmethoden sind je-
o
¨
doch nicht mehr analytisch auf unser Flugmodell anwendbar und wir werden eine
numerische L¨sung auf einem Computer bemuhen mussen. Zur Anwendung kom-
o ¨ ¨
men numerische Verfahren fur Di¬erentialgleichungen oder lineare und nichtli-
¨
neare Gleichungssysteml¨ser.
o

. 1
( 31 .)



>>