View
10
Download
0
Category
Preview:
Citation preview
Numerische Mathematik fur das Lehramt
Skriptum zur Vorlesung im SS 2009 †
PD Dr. Markus NeherUniversitat Karlsruhe (TH)Forschungsuniversitat · gegrundet 1825
Institut fur Angewandte und Numerische Mathematik
29. Juni 2009
† c©2007-2009 by Markus Neher. Dieses Skriptum ist urheberrechtlich geschutzt. Weiterverbreitung
und Einsatz in anderen Lehrveranstaltungen (auch von Teilen des Skriptums) ist ohne vorherige schrift-
liche Genehmigung des Autors untersagt. Insbesondere ist es nicht gestattet, das Skriptum oder Teile
davon in elektronischer Form im Internet zuganglich zu machen.
2 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Inhaltsverzeichnis
1 Einfuhrung 7
1.1 Symbolisches und numerisches Rechnen . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Gleitpunktzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Gleitpunktarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Algorithmen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.1 Schleifen in Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5.2 Auswahlanweisungen in Maple . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5.3 Prozeduren in Maple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 Landau-Symbole . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.7 Ziele dieser Vorlesung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 Iterationsverfahren 25
2.1 Fixpunktiteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Lokale Fixpunktsatze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3 Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Das Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5 Verwandte Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.1 Vereinfachtes Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.2 Sekantenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.3 Das Bisektionsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.6 Vektor- und Matrixnormen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7 Iterationsverfahren im Rn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Lineare Gleichungssysteme 47
3.1 Gauß-Elimination ohne Zeilentausch: LU -Zerlegung . . . . . . . . . . . . . . . . 47
3.1.1 Eliminationsmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.2 LU -Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.3 Aufwand des Gauß-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Gauß-Elimination mit Zeilentausch: PALU -Zerlegung . . . . . . . . . . . . . . . 53
3
4 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
3.2.1 Permutationsmatrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.2.2 Pivotisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.3 Fehlerabschatzungen fur lineare Gleichungssysteme . . . . . . . . . . . . . . . . 57
3.4 Iterationsverfahren fur lineare Gleichungssysteme . . . . . . . . . . . . . . . . . 60
3.4.1 Fixpunktiteration fur lineare Gleichungssysteme . . . . . . . . . . . . . . 60
3.4.2 Gesamt- und Einzelschrittverfahren . . . . . . . . . . . . . . . . . . . . . 62
3.4.3 Die Methode des steilsten Abstiegs . . . . . . . . . . . . . . . . . . . . . 66
3.4.4 Das cg-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.4.5 Vorkonditionierung beim cg-Verfahren . . . . . . . . . . . . . . . . . . . . 74
3.5 Die QR-Zerlegung einer Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.1 Orthogonale Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.5.2 Gram-Schmidt-Orthogonalisierung . . . . . . . . . . . . . . . . . . . . . . 77
3.5.3 Reduzierte QR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.5.4 Householder-Matrizen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.5.5 QR-Zerlegung durch Householder-Transformationen . . . . . . . . . . . . 81
3.6 Uber- und unterbestimmte lineare Gleichungssysteme . . . . . . . . . . . . . . . 85
3.6.1 Uberbestimmte lineare Gleichungssysteme . . . . . . . . . . . . . . . . . 85
3.6.2 Unterbestimmte lineare Gleichungssysteme . . . . . . . . . . . . . . . . . 87
4 Das Eigenwertproblem fur Matrizen (entfallt 2009) 89
5 Approximation und Interpolation 91
5.1 Approximation mit Taylor-Polynomen . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1.1 Approximationsaufgaben zum Restglied . . . . . . . . . . . . . . . . . . . 95
5.1.2 Anwendung: Berechnung transzendenter Funktionen . . . . . . . . . . . 96
5.2 Polynom-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.1 Einfuhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.2.2 Polynom-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.2.3 Interpolationsfehler der Polynom-Interpolation . . . . . . . . . . . . . . . . 103
5.2.4 Polynom-Interpolation mit Tschebyscheff-Stutzstellen . . . . . . . . . . . 105
5.2.5 Hermite-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3 Spline-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.3.1 Stuckweise lineare Interpolation . . . . . . . . . . . . . . . . . . . . . . . 108
5.3.2 Kubische Spline-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.3.3 Minimierungseigenschaft . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.3.4 Interpolationsfehler der kubischen Spline-Interpolation . . . . . . . . . . . 114
5.3.5 Anwendung: Spline-Interpolation geschlossener Kurven . . . . . . . . . . 115
5.4 Trigonometrische Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
5.4.1 Fourier-Reihen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Numerische Mathematik fur das Lehramt · SS 2009 5
5.4.2 Reelle diskrete Fourier-Transformation . . . . . . . . . . . . . . . . . . . . 116
5.5 Approximation nach der Methode der kleinsten Quadrate . . . . . . . . . . . . . 118
5.6 Nichtlineare Ausgleichsrechnung . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.6.1 Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.6.2 Gauß-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6 Numerische Integration 125
6.1 Newton-Cotes-Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Summierte Quadraturformeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
6.3 Extrapolation mit dem Romberg-Verfahren . . . . . . . . . . . . . . . . . . . . . . 130
6.4 Gauß-Quadratur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.4.1 Orthogonale Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4.2 Stutzstellen und Gewichte bei der Gauß-Quadratur . . . . . . . . . . . . . 137
7 Numerische Behandlung gewohnlicher Differentialgleichungen (entfallt 2009) 141
8 Gleitpunktrechnung, Kondition, Stabilitat 143
Kapitel 6
Numerische Integration
Manche Anwendungsprobleme lassen sich zuruckfuhren auf die Berechnung eines bestimm-
ten Integrals∫ b
a
f(x) dx. (6.1)
Dabei konnen u.a. die folgenden Schwierigkeiten auftreten:
• Die Stammfunktion von f kann nicht in geschlossener Form angegeben werden. Wichti-
ge Anwendungsbeispiele sind die Berechnung der Gauß’schen Fehlerfunktion
erf(x) :=2√π
∫ π
0e−x2
dx
oder die Auswertung elliptischer Integrale wie z.B.
E(ϕ, k) :=
∫ ϕ
0
√1 − k2 sin2 x dx.
• Es ist keine Stammfunktion von f bekannt oder die Auswertung der Stammfunktion von
f ist aufwandig.
• Es liegt kein Funktionsausdruck von f vor. Stattdessen sind nur Naherungswerte fur
f an einigen Stutzstellen gegeben. Mit dieser Information soll das Integral (6.1) dann
approximiert werden.
In diesem Kapitel werden verschiedene Methoden diskutiert, mit denen sich Naherungswerte
fur das bestimmte Integral (6.1) berechnen lassen.
6.1 Newton-Cotes-Formeln
Den im Folgenden entwickelten Newton-Cotes-Formeln liegt die folgende Idee zugrunde: Die
Funktion f wird durch ein Polynom pn interpoliert, welches anstelle von f integriert wird:
∫ b
a
f(x) dx ≈∫ b
a
pn(x) dx.
125
126 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Ist pn das Interpolationspolynom zu den n + 1 Stutzstellen x0, x1, . . . , xn in [a, b], folgt mit der
Darstellung von Langrange
∫ b
a
pn(x) dx =
∫ b
a
n∑
j=0
f(xj)Lj(x) dx =
n∑
j=0
f(xj)
∫ b
a
Lj(x) dx.
Setzt man
wj :=1
b − a
∫ b
a
Lj(x) dx,
erhalt man einen Naherungswert des bestimmten Integrals (6.1) als gewichtete Summe von
Funktionswerten: ∫ b
a
f(x) dx ≈ (b − a)
n∑
j=0
wj f(xj). (6.2)
Der lineare Operator In : C[a, b] → R
In(f) := (b − a)
n∑
j=0
wj f(xj)
wird als Quadraturformel bezeichnet. Die Gewichte wj hangen dabei weder von f noch von der
Lage (in R) oder Lange des Intervalls [a, b] ab, sondern nur von der Verteilung der Stutzstellen
xi, i = 0, 1, . . . , n, in [a, b]. Die Gewichte mussen fur jeden Satz von Stutzstellen nur einmal
berechnet werden und konnen danach in Tabellen gespeichert werden.
Die Newton-Cotes-Formeln erhalt man, wenn man in (6.2) gleichabstandige Stutzstellen ver-
wendet. Dabei werden noch offene und abgeschlossene Formeln unterschieden. Bei den ab-
geschlossenen Newton-Cotes-Formeln sind die Randpunkte des Integrationsintervalls Stutz-
stellen, bei den offenen Formeln nicht.
Beispiel 6.1 (Konstruktion abgeschlossener Newton-Cotes-Formeln fur n = 1 und
n = 2)
Fur n = 1 sind nur die Randpunkte a und b des Integrationsintervalls Stutzstellen. Mit
L0(x) =x − b
a − b, L1(x) =
x − a
b − a,
folgt
w0 =1
b − a
∫ b
a
x − b
a − b=
1
2, w1 =
1
b − a
∫ b
a
x − a
b − a=
1
2.
Die erhaltene Naherungsformel
∫ b
a
f(x) dx ≈ b − a
2
(f(a) + f(b)
)
heißt Trapezregel, da sie die Flache des Trapezes
berechnet, das von den Randwerten von f aufge-
spannt wird.a b
Abb. 6.1: Trapezregel.
Fur n = 2 kommt zu den Randpunkten noch der Mittelpunkt des Integrationsbereichs hinzu.
Setzt man h := (b − a)/2, erhalt man aus der Integration der zu den Stutzstellen gehorenden
Numerische Mathematik fur das Lehramt · SS 2009 127
Lagrange’schen Basispolynome Lj die Gewichte
w0 =1
2h
∫ a+2h
a
(x − (a + h)
)(x − (a + 2h)
)
(−h) · (−2h)dx =
1
4h3
∫ 2h
0(x2 − 3hx + 2h2) dx =
1
6,
w1 =1
2h
∫ a+2h
a
(x − a)(x − (a + 2h)
)
h · (−h)dx = − 1
2h3
∫ 2h
0(x2 − 2hx) dx =
4
6,
w2 =1
2h
∫ a+2h
a
(x − a)(x − (a + h)
)
2h · h dx =1
4h3
∫ 2h
0(x2 − hx) dx =
1
6.
Die Naherungsformel
∫ b
a
f(x) dx ≈ b − a
6
(f(a) + 4f
(a + b
2
)+ f(b)
)
heißt Simpson-Regel. Sie entspricht der Flache
zwischen der x-Achse und der Parabel, die durch
die Stutzwerte definiert wird.a b
Abb. 6.2: Simpson-Regel.
Fur großere Werte von n werden die Gewichte analog berechnet. So erhalt man die folgende
Tabelle der abgeschlossenenen Newton-Cotes-Formeln:
n Gewichte Fehler Name
112 ,
12
112 (b − a)3 ‖f ′′‖∞ Trapezregel
216 ,
46 ,
16
12880 (b − a)5
∥∥f (4)∥∥∞
Simpson-Regel
318 ,
38 ,
38 ,
18
16480 (b − a)5
∥∥f (4)∥∥∞
3/8-Regel (Pulcherima)
4790 ,
3290 ,
1290 ,
3290 ,
790
11935360 (b − a)7
∥∥f (6)∥∥∞
Milne-Regel
Tabelle 6.1: Newton-Cotes-Formeln.
Einige Eigenschaften der Newton-Cotes-Formeln lassen sich unmittelbar aus bekannten Ei-
genschaften der Polynom-Interpolation ableiten.
Satz 6.2 Die Summe der Gewichte jeder Newton-Cotes-Formel ist 1.
Beweis: Da die Summe der Lagrange’schen Basispolynome fur beliebiges n ∈ N die konstante
Funktion y = 1 ergibt (Ubungsaufgabe), folgt
n∑
j=0
wj =1
b − a
∫ b
a
n∑
j=0
Lj(x) dx =1
b − a
∫ b
a
1 dx = 1.
2
128 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Satz 6.3 (Fehlerabschatzung fur die Newton-Cotes-Formeln) Es sei n ∈ N. Die Funktion fsei auf dem Intervall [a, b] n + 1-mal stetig differenzierbar. Dann gilt fur den Quadraturfehler
En(f) :=
∫ b
a
f(x) dx − (b − a)
n∑
j=0
wj f(xj)
die Abschatzung
|En(f)| ≤∥∥f (n+1)
∥∥∞
(n + 1)!
∫ b
a
∣∣∣∣∣
n∏
i=0
(x − xi)
∣∣∣∣∣ dx. (6.3)
Beweis: Aufgrund der Definition der Gewichte wj ist
En(f) =
∫ b
a
(f(x) − pn(x)
)dx, (6.4)
wobei pn das Interpolationspolynom von f zu den Stutzstellen der Newton-Cotes-Formel
bezeichnet. Die Behauptung folgt durch Einsetzen des Approximationsfehlers der Polynom-
Interpolation (siehe Satz 3.17) in (6.4). 2
Das Integral in (6.3) kann leicht berechnet werden. Fur die Trapezregel (n = 1) gilt beispiels-
weise ∫ b
a
|(x − a)(x − b)| dx = −(
x3
3− (a + b)
x2
2+ abx
) ∣∣∣b
x=a=
1
6(b − a)3,
woraus
|E1(f)| ≤ 1
12(b − a)3
∥∥f ′′∥∥∞
(6.5)
folgt. Fur n > 1 kann man die Fehlerabschatzung (6.3) durch elementare, aber langwierige
Rechnung verbessern. Die dadurch erzielbaren Fehlerterme sind in Tabelle (6.1) angegeben.
Satz 6.4 (Genauigkeitsgrad der Newton-Cotes-Formeln)
1. Fur n ∈ N integrieren die Newton-Cotes-Formeln alle Polynome bis zum Grad n exakt.
2. Fur gerades n ∈ N integrieren die Newton-Cotes-Formeln alle Polynome bis zum Grad
n + 1 exakt.
Beweis:
von 1. Ist f ein Polynom vom Hochstgrad n, gilt f = pn und somit En(f) = 0.
von 2. Elementar, aber langwierig. Siehe z.B. Plato: Numerische Mathematik kompakt.
Vieweg, 3. Aufl. 2006.
2
Bemerkung 6.5 Der maximale Polynomgrad, bis zu dem eine Quadraturformel exakt integriert,
heißt Genauigkeitsgrad der Quadraturformel. Man kann zeigen, dass die Aussagen in Satz
6.4 optimal sind. Polynome hoheren Grades als angegeben werden durch die Newton-Cotes-
Formeln im Allgemeinen nicht mehr exakt integriert.
Numerische Mathematik fur das Lehramt · SS 2009 129
Bei der bisherigen Diskussion der Newton-Cotes-Formeln haben wir einen Umstand vollig
ausgeklammert: Die Interpolationspolynome (insbesondere diejenigen zu gleichabstandigen
Stutzstellen) konvergieren haufig nicht gegen f (siehe Beispiele in Kapitel 3). Diese Divergenz
ubertragt sich auf die Newton-Cotes-Formeln, die dann fur große Werte von n keine brauch-
baren Naherungswerte fur die gesuchten Integrale mehr liefern.
Fur n = 8 und n ≥ 10 treten in den Newton-Cotes-Formeln negative Gewichte auf. Dann gilt
zwar nach Satz 6.2 immer nochn∑
j=0
wj = 1,
abern∑
j=0
|wj | > 1.
Der Satz von Kusmin, den wir hier ohne Beweis angeben, besagt sogar, dass
limn→∞
n∑
j=0
|wj | → ∞
gilt. Die negativen Gewichte fuhren bei der numerischen Auswertung von (6.2) zu
Ausloschung. Die Newton-Cotes-Formeln sind daher fur n ≥ 10 zusatzlich zur oben disku-
tierten Problematik auch numerisch unbrauchbar.
6.2 Summierte Quadraturformeln
Zur Umgehung der soeben angesprochenen Divergenzeigenschaft der Newton-Cotes-
Formeln hoherer Ordnung unterteilt man das Intervall [a, b] in Teilintervalle und benutzt auf
jedem Teilintervall eine Newton-Cotes-Formel festen Grades. Im einfachsten Fall ist dies die
summierte Trapezregel.
Beispiel 6.6 (Summierte Trapezregel)
Fur n = 1 liefert die Unterteilung von [a, b] mit m+1 gleichabstandigen Stutzstellen xi = a+ ih,
i = 0, 1, . . . ,m, mit Schrittweite h = (b − a)/m die summierte Trapezregel
∫ b
a
f(x) dx =
m−1∑
i=0
∫ xi+1
xi
f(x) dx ≈m−1∑
i=0
h
2
(f(xi) + f(xi+1)
)
=h
2
(f(x0) + 2f(x1) + · · · + 2f(xm−1) + f(xm)
)=: Tf (h).
Die zugehorige Fehlerabschatzung folgt aus der
Fehlerabschatzung der Trapezregel (6.5), indem
man diese auf jedem Teilintervall anwendet.
Fur eine zweimal stetig differenzierbare Funktion
erhalt man
a b
Abb. 6.3: Summierte Trapezregel.
∣∣∣∣∫ b
a
f(x) dx − Tf (h)
∣∣∣∣ ≤m−1∑
i=0
1
12h3
∥∥f ′′∥∥∞
=m
12h3
∥∥f ′′∥∥∞
=(b − a)
12h2
∥∥f ′′∥∥∞
.
Der Quadraturfehler der summierten Trapezregel strebt mit dem Quadrat der Schrittweite hgegen Null.
130 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Ist f hinreichend oft differenzierbar, lasst sich fur die summierte Trapezregel eine asymptoti-
sche Entwicklung nach Potenzen von h2 angeben.
Satz 6.7 Es sei f ∈ C2r+2[a, b], r ≥ 0, sowie h = (b − a)/m. Dann gilt fur die summierte
Trapezregel
Tf (h) =h
2
(f(x0) + 2
m−1∑
i=1
f(xi) + f(xm))
die folgende Darstellung:
Tf (h) =
∫ b
a
f(x) dx +
r∑
j=1
cjh2j + Rr(h) (6.6)
mit von h unabhangigen Konstanten cj , j = 1, 2, . . . , r, und dem Fehlerterm Rr(h), fur welchen
Zahlen h0, C > 0 existieren, so dass
|Rr(h)| ≤ Ch2r+2 fur 0 ≤ h ≤ h0
gilt.
Beweis: Siehe z.B. Plato: Numerische Mathematik kompakt. Vieweg, 3. Aufl. 2006. 2
6.3 Extrapolation mit dem Romberg-Verfahren
Die asymptotische Entwicklung (6.6) kann man benutzen, um aus verschiedenen summierten
Trapeznaherungen fur das selbe Integral bessere Naherungswerte zu berechnen, als sie die
einzelnen Trapezwerte selbst liefern. Dies geschieht durch Bildung gewichteter Mittelwerte der
Trapeznaherungen. Der Vorteil dieser Vorgehensweise liegt im erheblich reduzierten Aufwand,
der zur Erzielung einer gewunschten Genauigkeit notwendig ist. Im Verhaltnis zur aufwandigen
Berechnung eines Funktionswerts von f ist die Berechnung der gewichteten Mittelwerte in
Bezug auf die benotigte Gesamtrechenzeit in der Regel vernachlassigbar.
Bei der Berechnung summierter Trapeznaherungen ist es offenbar geschickt, die Anzahl der
verwendeten Teilintervalle iterativ zu verdoppeln, damit man bereits berechnete Funktionswer-
te bei der verfeinerten Unterteilung wieder verwenden kann. Beim Romberg-Verfahren star-
tet man mit der Trapeznaherung fur das Ausgangsintervall [a, b], also mit 20 Teilintervallen
der Lange h0 = (b − a)/20. Im n-ten Halbierungsschritt werden 2n Teilintervalle der Lange
hn = (b − a)/2n verwendet. Die zugehorigen summierten Trapeznaherungen werden im Fol-
genden mit Tn bezeichnet.
Beispiel 6.8 Berechnung von
∫ 2
1
dx
x= ln 2 = 0.6931471806 . . .
mit summierten Trapeznaherungen.
Numerische Mathematik fur das Lehramt · SS 2009 131
Mit den Schrittweiten h0 = 1, hn =h0
2n=
1
2nfolgt:
T0 = h0
(f(1)
2+
f(2)
2
)=
1
2+
1
4=
3
4= 0.75,
T1 = h1
(f(1)
2+ f
(3
2
)+
f(2)
2
)
=1
2h0
(f(1)
2+
f(2)
2
)
︸ ︷︷ ︸T0
+1
2h0f
(3
2
)
︸ ︷︷ ︸=:M1
=1
2
(3
4+
2
3
)≈ 0.708334,
T2 = h2
(f(1)
2+ f
(5
4
)+ f
(3
2
)+ f
(7
4
)+
f(2)
2
)
=1
2h1
(f(1)
2+ f
(3
2
)+
f(2)
2
)
︸ ︷︷ ︸T1
+1
2h1
(f(5
4
)+ f
(7
4
))
︸ ︷︷ ︸=:M2
=1
2
(17
24+
24
35
)≈ 0.697025,
M2 = h2
(f(9
8
)+ f
(11
8
)+ f
(13
8
)+ f
(15
8
))≈ 0.691220,
T3 =1
2(T2 + M2) ≈ 0.694123.
Die Hilfsvariablen Mn enthalten die summierten Funktionswerte der im n + 1-ten Halbierungs-
schritt neu hinzukommenden Stutzstellen.
Fur dieses Beispiel gilt wegen b − a = 1, h3 =1
8und
∥∥f ′′∥∥∞
=
∥∥∥∥2
x3
∥∥∥∥∞
= 2
die Fehlerabschatzung ∣∣∣∣∫ 2
1
dx
x− T3
∣∣∣∣ ≤1
12· 1
64· 2 =
1
384,
woraus die Inklusion
ln 2 ∈ [T3 −1
384, T3 +
1
384] = [0.691517, 0.696725]
folgt.
Will man den Wert von ln 2 mit dieser Methode auf mindestens funf Dezimalstellen genau
bestimmen, ist ein n ∈ N gesucht, so dass
∣∣∣∣∫ 2
1
dx
x− Tn
∣∣∣∣ ≤1
210−5 (6.7)
gilt. Die Fehlerabschatzung1
12· 1
4n· 2
!≤ 1
210−5
liefert
n ≥ ln(100000) − ln 3
ln 4= 7.51 . . . .
132 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Fur n = 8 ist (6.7) also erfullt, d.h. T8 ist eine auf (mindestens) funf Dezimalstellen genaue
Naherung von ln 2.
Man kann nachrechnen, dass (6.7) bereits von T7, nicht jedoch von T6 erfullt wird. Die Berech-
nung von T8 erfordert 28 + 1 = 257 Funktionswerte von f , die Berechnung von T7 immerhin
noch 27 + 1 = 129 Funktionswerte von f .
Die berechneten Trapeznaherungen T0, T1, T2 und T3 wollen wir nun zur Extrapolation nutzen.
Diese beruht auf der asymptotischen Fehlerentwicklung (6.6). Setzt man in (6.6) neben h auch
2h ein, erhalt man
Tf (h) =
∫ b
a
f(x) dx + c1h2 + c2h
4 + · · · + crh2r + Rr(h), (6.8)
Tf (2h) =
∫ b
a
f(x) dx + 4c1h2 + 16c2h
4 + · · · + 4rcrh2r + Rr(2h). (6.9)
Durch Multiplikation von (6.8) mit 4 und Subtraktion von (6.9) ergibt sich:
4Tf (h) − Tf (2h) = 3
∫ b
a
f(x) dx − 12c2h4 − 60c3h
6 − · · · − (4r − 4)crh2r + 4Rr(h) − Rr(2h).
Berechnet man also (fur beliebiges h) aus den summierten Trapezwerten Tf (h) und Tf (2h)den Wert
Tf (h) :=4 Tf (h) − Tf (2h)
3,
dann ist Tf (h) ebenfalls eine Naherung des gesuchten Integrals. Tf (h) genugt der verbesser-
ten asymptotischen Fehlerentwicklung
Tf (h) =
∫ b
a
f(x) dx + c2h4 + · · · + crh
2r + Rr(h) (6.10)
mit von h unabhangigen Konstanten cj , j = 2, 3, . . . , r.
Eine gewichtete Mittelwertbildung kann analog auf die Werte Tf (h) und Tf (2h) angewandt
werden. Fur
˜T f (h) :=
16 Tf (h) − Tf (2h)
15gilt die asymptotische Fehlerentwicklung
˜T f (h) =
∫ b
a
f(x) dx + ˜c 3h6 + · · · + ˜c rh
2r +˜R r(h), (6.11)
sofern f hinreichend oft differenzierbar ist. Man beachte, dass der Quadraturfehler in (6.10)
mit h4, in (6.11) sogar mit h6 gegen Null strebt.
Das Romberg-Verfahren zur Konvergenzbeschleunigung bei der numerischen Integration mit
der Trapezmethode setzt die beschriebene Methode fort. Man setzt fur n = 0, 1, . . .
hn :=b − a
2n, Tn,0 := Tf (hn).
Die Werte Tn,0 bilden die erste Spalte des Romberg-Schemas. Die weiteren Spalten werden
durch die Rekursionsformel
Tn,k =4k · Tn,k−1 − Tn−1,k−1
4k − 1, n = 1, 2, . . . , k = 1, 2, . . . , n
berechnet. Dabei werden keine zusatzlichen Funktionswerte von f benotigt. Ist f hinreichend
oft differenzierbar, dann konvergiert jede Spalte des Romberg-Schemas mit zwei Potenzen
von h schneller gegen das gesuchte Integral als die vorangehende Spalte.
Numerische Mathematik fur das Lehramt · SS 2009 133
0. Spalte 1. Spalte 2. Spalte 3. Spalte
T0 = T0,0
T1 = T1,0 /3: T1,1 =41 · T1,0 − T0,0
41 − 1
T2 = T2,0 /3: T2,1 =41 · T2,0 − T1,0
41 − 1/15: T2,2 =
42 · T2,1 − T1,1
42 − 1
T3 = T3,0 /3: T3,1 =41 · T3,0 − T2,0
41 − 1/15: T3,2 =
42 · T3,1 − T2,1
42 − 1/63: T3,3 =
43 · T3,2 − T2,2
43 − 1
Tabelle 6.2: Romberg-Schema.
AA-1
·4
AA-1
·4
AA-1
·4
AA-1
·16
AA-1
·16
AA-1
·64
Beispiel 6.9 Berechnung von
∫ 2
1
dx
xmit dem Romberg-Schema.
0. Spalte 1. Spalte 2. Spalte 3. Spalte
T0,0 = 0.750000
T1,0 = 0.708334 /3: T1,1 = 0.694445
T2,0 = 0.697025 /3: T2,1 = 0.693255 /15: T2,2 = 0.693176
T3,0 = 0.694123 /3: T3,1 = 0.693157 /15: T3,2 = 0.693150 /63: T3,3 = 0.693150
Tabelle 6.3: Berechnung eines Integrals mit dem Romberg-Schema.
AA-1
·4
AA-1
·4
AA-1
·4
AA-1
·16
AA-1
·16
AA-1
·64
T3,3 stimmt (ebenso wie T8,0) auf funf Dezimalstellen mit dem exakten Wert des Integrals uber-
ein. Wahrend die Berechnung von T8,0 aber 257 Funktionswerte von f erfordert, werden fur
T3,3 nur 23 + 1 = 9 Funktionswerte von f benotigt.
6.4 Gauß-Quadratur
Bereits bei der Polynom-Interpolation hatten sich aquidistante Stutzstellen haufig als nachtei-
lig erwiesen. Dieser Nachteil hatte sich auf die Newton-Cotes-Formeln zur numerischen Inte-
gration mit aquidistanten Stutzstellen ubertragen. In diesem Abschnitt wird nun ein auf Gauß
zuruckgehender Ansatz entwickelt, bei dem die Stutzstellen nicht aquidistant gewahlt, sondern
mit den Gewichten bestimmt werden.
Zu einem gegebenen Intervall [a, b] sind im Folgenden fur ein n ∈ N Stutzstellen
x1, x2, . . . , xn ∈ [a, b] und reelle Gewichte w1, w2, . . . , wn gesucht, so dass die Quadraturfor-
mel ∫ b
a
f(x) dx =n∑
i=1
wif(xi) (6.12)
einen moglichst hohen Genauigkeitsgrad besitzt. Ohne zusatzliche Uberlegungen zu benoti-
gen, konnen wir sogar eine etwas allgemeinere Aufgabenstellung betrachten, bei der das aus-
zuwertende Integral noch eine Gewichtsfunktion enthalt.
134 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Definition 6.10 Eine positive, auf (a, b) stuckweise stetige und uber [a, b] integrierbare Funktion
heißt Gewichtsfunktion.
Wichtige Beispiele fur Gewichtsfunktionen sind die triviale Gewichtsfunktion ≡ 1 oder die
unbeschrankte Gewichtsfunktion
(x) =1√
(x − a)(b − x).
Anstelle von (6.12) betrachten wir also
∫ b
a
f(x)(x) dx =n∑
i=1
wif(xi) (6.13)
mit einer vorgegebenen Gewichtsfunktion . (6.12) ensteht aus (6.13) fur ≡ 1.
Beispiel 6.11 Es sei [a, b] = [0, 1], ≡ 1, n = 2. Wir bestimmen zwei Stutzstellen x1, x2 ∈ [0, 1]sowie zwei Gewichte w1, w2, so dass
∫ 1
0p(x) dx = w1p(x1) + w2p(x2) (6.14)
Polynome bis zum Hochstgrad 3 exakt integriert.
Wegen der Linearitat von (6.14) bezuglich p genugt es, (6.14) fur die Monome 1, x, x2, x3 zu
erfullen. Dieser Ansatz fuhrt auf das folgende nichtlineare Gleichungssystem:
p(x) = 1 : w1 + w2 = 1 (6.15)
p(x) = x : w1x1 + w2x2 =1
2(6.16)
p(x) = x2 : w1x21 + w2x
22 =
1
3(6.17)
p(x) = x3 : w1x31 + w2x
32 =
1
4(6.18)
Dieses Gleichungssystem lasst sich explizit losen. Wir setzen
q(x) := (x − x1)(x − x2) = x2 − (x1 + x2)x + x1x2 =: x2 + rx + s
und bestimmen zunachst r und s. Die Linearkombination s · (6.15) + r · (6.16) + (6.17) ergibt
s +1
2r +
1
3= w1 (s + rx1 + x2
1)︸ ︷︷ ︸=q(x1)=0
+w2 (s + rx2 + x22)︸ ︷︷ ︸
=q(x2)=0
= 0. (6.19)
Ebenso folgt aus s · (6.16) + r · (6.17) + (6.18)
1
2s +
1
3r +
1
4= w1x1 (s + rx1 + x2
1)︸ ︷︷ ︸=0
+w2x2 (s + rx2 + x22)︸ ︷︷ ︸
=0
= 0. (6.20)
(6.19) und (6.20) bilden ein lineares Gleichungssystem fur r und s mit der eindeutigen Losung
r = −1, s = 16 . Aus q(x) = x2 − x + 1
6 folgen die Stutzstellen
x1, x2 =1
2±
√3
6.
Numerische Mathematik fur das Lehramt · SS 2009 135
Setzt man diese Werte in (6.15) und (6.16) ein, erhalt man ein eindeutig losbares lineares
Gleichungssystem fur die Gewichte w1 und w2. Die Losung ist
w1 = w2 =1
2.
Die reichlich experimentelle Losungsmethode dieses Beispiels soll nun durch einen systema-
tischen Algorithmus ersetzt werden. Dazu fuhren wir zunachst Systeme von Orthogonalpoly-
nomen ein.
6.4.1 Orthogonale Polynome
Definition 6.12 Es bezeichne Π den Vektorraum der reellen Polynome sowie Πn den Vektor-
raum der reellen Polynome vom Hochstgrad n. sei eine gegebene Gewichtsfunktion. Dann
wird durch
< p, q > :=
∫ b
a
p(x)q(x)(x) dx
ein Skalarprodukt auf Π bzw. Πn eingefuhrt.
‖p‖ :=√
< p, p >
ist die induzierte Norm von p. Zwei Polynome p und q heißen orthogonal, wenn
< p, q >= 0
gilt. Das orthogonale Komplement von Πn (bezuglich Π) ist gegeben durch
Π⊥n := {q ∈ Π : < p, q >= 0 fur alle p ∈ Πn}.
Π⊥n ist wie Πn ein linearer Unterraum von Π.
Fur jede Gewichtsfunktion kann man eine Folge von Orthogonalpolynomen konstruieren (die
dann eine Orthogonalbasis von Π bilden), wenn man die Gram-Schmidt-Orthogonalisierung
auf die Monome 1, x, x2, . . . anwendet:
p0 := 1,
pn := xn −n−1∑
j=0
< xn, pj >
‖pj‖2 pj , n = 1, 2, . . . .(6.21)
Nach Konstruktion ist pn ein Polynom vom Grad n mit fuhrendem Koeffizienten 1. Außerdem
gilt pn ∈ Π⊥n−1. Die beiden letztgenannten Eigenschaften charakterisieren pn eindeutig.
Zur einfacheren Berechnung der pn kann man den folgenden Satz anwenden:
Satz 6.13 Die Orthogonalpolynome aus (6.21) genugen der Drei-Term-Rekursion
p0 = 1, p1 = x − β0,
pn+1 = (x − βn)pn − γ2npn−1, n = 1, 2, . . . .
(6.22)
mit
βn =< xpn, pn >
‖pn‖2 , n = 0, 1, . . . , γn =‖pn‖‖pn−1‖
, n = 1, 2, . . . .
136 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Beweis: Wir zeigen die Behauptung mit vollstandiger Induktion. Fur p0 ist nichts zu zeigen, fur
p1 stimmt die angegebene Darstellung mit (6.21) uberein. Dies liefert den Induktionsanfang.
Als Induktionsvoraussetzung durfen wir nun annehmen, dass ein N ≥ 1 existiert, fur welches
die durch (6.22) definierten Polynome fur n = 0, 1, . . . , N mit den Polynomen aus (6.21) uber-
einstimmen. Im Induktionsschluss zeigen wir, dass das Polynom
q := (x − βN )pN − γ2NpN−1
mit dem Polynom pN+1 aus (6.21) ubereinstimmt.
Nach Konstruktion ist q ein Polynom vom Grad N + 1 mit fuhrendem Koeffizienten 1. Da es
nur ein solches Polynom in Π⊥N gibt (namlich pN+1), ist die Behauptung gezeigt, wenn wir
nachgewiesen haben, dass q zu allen Polynomen pn, n = 0, 1, . . . , N , orthogonal ist.
Sei zunachst r ∈ ΠN−2 beliebig. Dann gilt:
< q, r >=< xpN , r > −βN < pN , r >︸ ︷︷ ︸=0
−γ2N < pN−1, r >︸ ︷︷ ︸
=0
= < pN , xr >︸ ︷︷ ︸=0
= 0,
d.h. es ist q ∈ Π⊥N−2.
Fur n = N − 1 gilt:
< q, pN−1 > = < xpN , pN−1 > −βN < pN , pN−1 >︸ ︷︷ ︸=0
− < pN , pN >
< pN−1, pN−1 >< pN−1, pN−1 >
= < pN , xpN−1 > − < pN , pN >=< pN , xpN−1 − pN︸ ︷︷ ︸∈ΠN−1
>= 0,
d.h. es ist q ∈ Π⊥N−1.
Fur n = N gilt:
< q, pN > = < xpN , pN > −βN < pN , pN > −γ2N < pN−1, pN >︸ ︷︷ ︸
=0
= βN ‖pN‖2 − βN ‖pN‖2 = 0,
womit schließlich auch q ∈ Π⊥N gezeigt ist. 2
Satz 6.14 Die Nullstellen x1, x2, . . . , xn von pn sind einfach und liegen alle im offenen Intervall
(a, b).
Beweis: Es seien
a < x1 < x2 < · · · < xm < b (0 ≤ m ≤ n)
diejenigen Nullstellen von pn mit ungerader Vielfachheit. Dann ist
qm(x) :=m∏
i=1
(x − xi)
ein Polynom vom Grad m und das Polynom
pn(x) · qm(x)
besitzt auf [a, b] keine Nullstelle mit Vorzeichenwechsel. Auf ganz [a, b] gilt also entweder
pn qm ≥ 0 oder pn qm ≤ 0. Da pn qm nur an endlich vielen Stellen verschwindet, folgt
< pn, qm >=
∫ b
a
pn(x)qm(x)(x) dx 6= 0.
Da aber pn zu allen Polynomen vom Hochstgrad n − 1 orthogonal ist, muss qm (mindestens)
den Grad n besitzen. Daraus folgt die Behauptung. 2
Numerische Mathematik fur das Lehramt · SS 2009 137
6.4.2 Stutzstellen und Gewichte bei der Gauß-Quadratur
Die Berechnung der Stutzstellen und Gewichte bei der Gauß-Quadratur beruht auf den im
letzten Abschnitt eingefuhrten Orthogonalpolynomen.
Satz 6.15 Es sei [a, b] ein reelles Intervall und eine Gewichtsfunktion auf [a, b]. Fur n ∈ N
seien x1, x2, . . . , xn ∈ [a, b] paarweise verschiedene Zahlen sowie w1, w2, . . . , wn ∈ R beliebige
Gewichte. Fur j = 1, 2, . . . , n seien
Lj(x) :=n∏
i=1i6=j
(x − xi)
(xj − xi)
die zu x1, x2, . . . , xn gehorenden Lagrange’schen Basispolynome.
Dann gilt ∫ b
a
p(x)(x) dx =n∑
j=1
wjp(xj) fur alle p ∈ Π2n−1 (6.23)
genau dann, wenn die folgenden Bedingungen erfullt sind:
(i) x1, x2, . . . , xn sind die Nullstellen des n-ten Orthogonalpolynoms aus (6.21).
(ii) Die Gewichte lauten
wj =< Lj , 1 > fur j = 1, 2, . . . , n.
Beweis:
(i) ist notwendig: Es gelte (6.23) und es sei
q(x) :=n∏
i=1
(x − xi).
Da q in Πn liegt, gilt fur m = 0, 1, . . . , n − 1 wegen (6.23)
< q, xm >=< qxm, 1 >=n∑
j=1
wjxmj · q(xj)︸ ︷︷ ︸
=0
= 0,
d.h. es gilt q ∈ Π⊥n−1. Nach Konstruktion besitzt q den fuhrenden Koeffizienten 1, also muss
q = pn gelten.
(ii) ist notwendig: Es gelte (6.23). Dann folgt fur k = 1, 2, . . . , n:
< Lk, 1 >=n∑
j=1
wj Lk(xj)︸ ︷︷ ︸=δjk
= wk.
(i) und (ii) sind hinreichend: Es sei p ∈ Π2n−1 ein beliebiges Polynom. Mit Hilfe von Polynom-
division lasst sich p darstellen als
p = q · pn + r
mit Polynomen q, r ∈ Πn−1. Sind (i) und (ii) erfullt, folgt wegen pn(xi) = 0
p(xi) = r(xi) fur i = 1, 2, . . . , n.
138 Markus Neher, Universitat Karlsruhe (TH) · 29. Juni 2009
Also gilt
r(x) =
n∑
j=1
r(xj)Lj(x) =
n∑
j=1
p(xj)Lj(x)
und somit
< p, 1 >=< qpn, 1 > + < r, 1 >= < q, pn >︸ ︷︷ ︸=0
+ < r, 1 >=n∑
j=1
p(xj) < Lj , 1 > .
2
Bemerkung 6.16
1. Die in Satz 6.15 formulierte Quadraturformel heißt Gauß-Quadratur.
2. Wegen L2k ∈ Π2n−2 folgt aus (6.23):
< Lk, Lk >︸ ︷︷ ︸>0
=< L2k, 1 >=
n∑
j=1
wj L2k(xj)︸ ︷︷ ︸=δjk
= wk,
d.h. bei der Gauß-Quadratur sind alle Gewichte positiv.
3. Satz 6.15 besagt, dass der Genauigkeitsgrad der Gauß-Quadratur (6.23) mindestens
2n− 1 ist. Dass die Gauß-Quadratur keinen hoheren Genauigkeitsgrad besitzt, zeigt das
Beispiel
p(x) =
n∏
j=1
(x − xj)2.
p ist ein Polynom vom Grad 2n, es ist p(x) ≥ 0 und∫ b
ap(x)(x) dx > 0, aber p(xj) = 0 fur
alle j und somit auchn∑
j=1
wjp(xj) = 0.
4. Zur Auswertung der Summe in (6.23) werden n Funktionswerte von f benotigt. Eine aus
n Funktionswerten von f gebildete Newton-Cotes-Formel benotigt den gleichen Aufwand
zur Auswertung, besitzt aber hochstens den Genauigkeitsgrad n.
Beispiel 6.17 Es sei [a, b] = [0, 1], ≡ 1, n = 2. Wir berechnen die Nullstellen und Gewichte
der zugehorigen Gauß-Quadratur mit Satz 6.13. Aus p0 = 1 folgt zunachst
β0 =< x, 1 >
< 1, 1 >=
1
2, p1(x) = x − 1
2.
Hieraus werden β1 und γ21 berechnet:
β1 =< xp1, p1 >
< p1, p1 >=
∫ 10 (x3 − x2 + 1
4x) dx∫ 10 (x2 − x + 1
4) dx=
14 − 1
3 + 18
13 − 1
2 + 14
=1
2,
γ21 =
< p1, p1 >
< p0, p0 >=
1
12.
Numerische Mathematik fur das Lehramt · SS 2009 139
Die Nullstellen von
p2(x) = (x − 1
2)p1(x) − 1
12p0(x) = (x − 1
2)2 − 1
12= x2 − x +
1
6
sind
x1, x2 =1
2∓
√3
6,
woraus man die Gewichte
w1 =
∫ 1
0
x − x2
x1 − x2dx =
1
2, w2 =
∫ 1
0
x − x1
x2 − x1dx =
1
2
erhalt. Der Genauigkeitsgrad dieser Quadraturformel ist 2n − 1 = 3 (vgl. Beispiel 6.11).
Bemerkung 6.18
1. Eine praktische Schwierigkeit bei der Gauß-Quadratur besteht in der Berechnung
der Nullstellen der Orthogonalpolynome. Fur große Werte von n ist dies numerisch
aufwandig. Allerdings mussen die Gewichte fur jede Gewichtsfunktion nur einmal be-
rechnet werden. Anschließend konnen die Werte in Tabellen gespeichert werden.
2. Wie bei den Newton-Cotes-Formeln kann man die Gauß-Quadratur auch summiert an-
wenden. Dies ist fur große Integrationsbereiche eventuell vorteilhafter als die Berech-
nung einer Gauß-Quadraturformel fur einen sehr großen Wert von n.
Index
a posteriori-Abschatzung, 29, 41
a priori-Abschatzung, 29, 41
Abstiegsverfahren, 67
Algorithmus, 11
determinierter, 12
deterministischer, 12
Ansatzfunktion
bei der Methode der kleinsten Quadrate,
118
Approximation, 98
Argumentreduktion, 96
Ausgleichsgerade, 119
Ausgleichsproblem, 85
Ausgleichsrechnung
nichtlineare, 123
Auswahlanweisung, 16
Banach’scher Fixpunktsatz
im Rn, 41
in R, 29
Bisektionsverfahren, 37
cg-Verfahren, 70
Konvergenzverhalten, 73
diagonaldominate Matrix, 52
Einzelschrittverfahren, 63
Eliminationsmatrix, 48
Energienorm, 66
Extrapolation, 98
Fixpunkt, 27
abstoßender, 31
anziehender, 31
Fixpunktiteration, 27
im Rn, 42
Fixpunktsatz
von Banach
im Rn, 41
in R, 29
Fourier-Reihe, 115
Fourier-Transformation
diskrete, 115
Gauß-Markov
Satz von, 118
Gauß-Newton-Verfahren, 123
Gauß-Seidel-Verfahren, 63
Gesamtschrittverfahren, 62
Gleitpunktsystem, 9
Gleitpunktzahl, 9
normalisierte, 9
Gram-Schmidt-Orthogonalisierung, 77
Hermite-Interpolation, 107
Householder-Matrix, 79
Householder-Transformation, 79
Interpolation, 98
Polynom-Interpolation, 98
Spline-Interpolation, 107
stuckweise lineare, 108
trigonometrische, 115
Interpolationsfehler
bei der Polynom-Interpolation, 100, 103
bei der Spline-Interpolation, 113
Interpolationspolynom
Darstellung von Lagrange, 98
Darstellung von Newton, 99
iterationsfahige Gestalt, 26
Iterationsverfahren, 27
Jacobi-Verfahren, 62
kleinste Quadrate
Methode der, 85, 117
Kondition
einer Matrix, 57
kontrahierende Abbildung, 28
im Rn, 41
Kontraktion, 28
Kontraktionskonstante, 28
Konvergenzordnung
eines Iterationsverfahrens, 32
Krylov-Raum, 71
Landau-Symbol, 22
LGS
uberbestimmtes, 85
144
Numerische Mathematik fur das Lehramt · SS 2009 145
unterbestimmtes, 87
LU -Zerlegung, 49
Aufwand der, 52
Mantisse, 9
Maple, 15
Prozedur, 19
Matrix
orthogonale, 76
positiv definite, 66
Methode der kleinsten Quadrate, 85, 117
Methode des steilsten Abstiegs, 68
Konvergenzverhalten, 69
Modellbildung, 7
Modellfehler, 7
Newton-Verfahren
fur reellwertige Funktionen, 34
quadratische Konvergenzordnung, 35
vereinfachtes, 36
im Rn, 44
Norm, 38
Matrixnorm, 38
Frobenius-Norm, 38
induzierte, 39
Spaltensummennorm, 40
Spektralnorm, 40
submultiplikative, 39
vertragliche, 39
Zeilensummennorm, 40
Vektornorm, 38
Normalgleichungssystem, 85
PALU -Zerlegung, 55
Permutationsmatrix, 53
elementare, 53
Pivotelement, 56
Polynom-Interpolation, 98
positiv definite Matrix, 66
Prozedur, 18
globale Variable, 20
lokale Variable, 20
Parameterliste, 19
QR-Zerlegung, 76, 79
reduzierte, 79
Rechnen
numerisches, 8
symbolisches, 8
regula falsi, 38
Relaxation, 33
Residuum, 60
Restglied
eines Taylor-Polynoms, 94
Rundungsfehler, 10
Satz von
Gauß-Markov, 118
Taylor, 93
Schleife, 15
Sekantenverfahren, 36
Selbstabbildung, 27
Spline
kubischer, 108
Minimierungseigenschaft, 112
naturlicher, 109
not-a-knot Spline, 109
periodischer, 109
Randbedingungen, 109
zur Parameterdarstellung einer Kurve,
114
Spline-Interpolation, 107
Splitting-Verfahren, 62
Standardfunktion, 91
Steigung, 99
n-ter Ordnung, 99
verallgemeinerte, 110
Steigungsschema, 101
Taylor
Satz von, 93
Taylor-Polynom, 93
Taylor-Reihe, 94
Tschebyscheff-Polynom, 105
Tschebyscheff-Stutzstellen, 106
Turing-Maschine, 11
Vorkonditionierung, 74
Recommended