Embed Size (px)
Citation preview
Numerik I fur Ingenieure
Gunter Barwolff
10. Juni 2010
Zusammenfassung
An dieser Stelle werden Informationen zu den Vorlesungen ”Nu-
merik I fur Ingenieure von Prof. Dr. Gunter Barwolff im SS2010 an
der TU Berlin bereit gestellt. Dabei werden die Informationen jeweils
am Wochenende nach den aktuellen Vorlesungen erganzt, so dass am
Semesterende ein weitestgehend vollstandiges Material zur Verfugung
stehen wird.
i
Inhaltsverzeichnis
0 Vorwort 1
1 Rechnerarithmetik 21.1 Zahldarstellungen . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Allgemeine Gleitpunkt-Zahlensysteme . . . . . . . . . . . . . . 21.3 Struktur und Eigenschaften des normalisierten Gleitpunktzahlensystems F 41.4 Rechnen mit Gleitpunktzahlen . . . . . . . . . . . . . . . . . . 51.5 Ersatzarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . 81.6 Fehlerakkumulation . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Numerische Losung von Anfangswertaufgaben 112.1 Theorie der Einschrittverfahren . . . . . . . . . . . . . . . . . 132.2 Spezielle Einschrittverfahren . . . . . . . . . . . . . . . . . . . 15
2.2.1 Euler-Verfahren . . . . . . . . . . . . . . . . . . . . . . 152.2.2 Einschrittverfahren der Konsistenzordnung p = 2 . . . 15
2.3 Verfahren hoherer Ordnung . . . . . . . . . . . . . . . . . . . 192.4 Einige konkrete Runge-Kutta-Verfahren und deren Butcher-Tabellen 222.5 Implizite Runge-Kutta-Verfahren . . . . . . . . . . . . . . . . 272.6 Rundungsfehleranalyse von expliziten Einschrittverfahren . . . 282.7 Schrittweitensteuerung bei Einschrittverfahren . . . . . . . . . 282.8 Mehrschrittverfahren . . . . . . . . . . . . . . . . . . . . . . . 302.9 Allgemeine lineare Mehrschrittverfahren . . . . . . . . . . . . 33
3 Interpolation 393.1 Polynominterpolation . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.1 Konstruktion des Interpolationspolynoms . . . . . . . . 413.2 Lagrange-Interpolation . . . . . . . . . . . . . . . . . . . . . . 423.3 Newton-Interpolation . . . . . . . . . . . . . . . . . . . . . . . 423.4 Algorithmische Aspekte der Polynominterpolation . . . . . . . 44
3.4.1 Horner-Schema . . . . . . . . . . . . . . . . . . . . . . 443.5 Fehlerabschatzung der Polynominterpolation . . . . . . . . . . 45
ii
3.6 Spline-Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 473.6.1 Interpolierende lineare Splines s ∈ S∆,1 . . . . . . . . . 473.6.2 Kubische Splines . . . . . . . . . . . . . . . . . . . . . 483.6.3 Berechnung interpolierender kubischer Splines . . . . . 493.6.4 Gestalt der Gleichungssysteme . . . . . . . . . . . . . . 50
3.7 Existenz und Eindeutigkeit der betrachteten interpolierenden kubischen Splines 513.8 Fehlerabschatzungen fur interpolierende kubische Splines . . . 52
4 Numerische Integration 544.1 Numerischen Integration mit Newton-Cotes-Formeln . . . . . . 544.2 Summierte abgeschlossene Newton-Cotes-Quadraturformeln . 574.3 Gauß-Quadraturen . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3.1 Orthogonale Polynome . . . . . . . . . . . . . . . . . . 614.3.2 Konstruktion von Folgen orthogonaler Polynome . . . . 62
4.4 Fehlerabschatzungen fur lin. Gleichungssysteme . . . . . . . . 674.4.1 Vektor- und Matrixnormen . . . . . . . . . . . . . . . . 674.4.2 Weitere Vektor- und Matrixnormen . . . . . . . . . . . 69
5 Losung linearer Gleichungssysteme 745.1 LR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.1 Realisierung mit dem Gaußschen Eliminationsverfahren 745.1.2 LR-Zerlegung mit Spaltenpivotisierung . . . . . . . . . 79
5.2 Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . 825.2.1 Konstruktion der Choleksy-Zerlegung . . . . . . . . . . 83
5.3 Orthogonale Matrizen – QR-Zerlegung . . . . . . . . . . . . . 845.3.1 Gram-Schmidt-Verfahren zur Orthogonalisierung . . . 855.3.2 Householder-Matrizen/Transformationen . . . . . . . . 865.3.3 Algorithmus zur Konstruktion der Faktorisierung mittels Householder-Transformationen
5.4 Anwendungen der QR-Zerlegung . . . . . . . . . . . . . . . . . 895.4.1 Losung eines linearen Gleichungssystems . . . . . . . . 895.4.2 Ausgleichsprobleme . . . . . . . . . . . . . . . . . . . . 89
6 Die iterative Losung linearer Gleichungssysteme 936.1 Jacobi-Verfahren oder Gesamtschrittverfahren . . . . . . . . . 956.2 Gauß-Seidel-Iterationsverfahren oder Einzelschrittverfahren . . 976.3 Verallgemeinerung des Gauß-Seidel-Verfahrens . . . . . . . . . 99
7 Iterative Losung von nichtlinearen Gleichungssystemen 1007.1 Die Fixpunktiteration zur Losung nichtlinearer Gleichungen . 1007.2 Das Newton-Verfahren zur Losung nichtlinearer Gleichungen . 1027.3 Newton-Verfahren fur nichtlineare Gleichungssysteme F (x) = 0 104
iii
7.4 Gedampftes Newton-Verfahren . . . . . . . . . . . . . . . . . . 105
iv
Kapitel 0
Vorwort
Als Literaturempfehlungen seien die Lehrbucher von
• Gunter Barwollf: Numerik fur Ingenieure, Physiker und Informatiker
• Robert Plato: Numerische Mathematik kompakt. Grundlagenwissen furStudium und Praxis
• Hans R. Schwarz, Norbert Kockler: Numerische Mathematik
• Matthias Bollhofer, Volker Mehrmann: Numerische Mathematik
empfohlen, in denen die Themen der Vorlesung mehr oder wenig ausfuhrlichdargestellt sind.
1
Kapitel 1
Rechnerarithmetik
1. Vor-lesungam14.4.2010
Bei unterschiedlichen “Rechenaufgaben” treten unterschiedliche Fehler auf,und zwar
• Datenfehler aufgrund ungenauer Eingabedaten
• Darstellungsfehler von Zahlen
• Fehler durch ungenaue Rechnungen, z.B. wird man bei der Aufabe13
= 0.33333 . . . eigentlich nie fertig, d.h. man gibt irgendwann erschopftauf und macht einen Fehler.
1.1 Zahldarstellungen
Aus der Analysis ist bekannt, dass man jede Zahl x ∈ R, x 6= 0 bei einergegebenen Basis b ∈ N, b ≥ 2 in der Form
x = σ
∞∑
i=−l+1
ai+lb−i = σ
( ∞∑
i=1
aib−i
)
be (1.1)
mit a1, a2, . . . ∈ {0, 1, . . . , b − 1}, e ∈ Z, σ ∈ {+,−} darstellen kann, wobeia1 6= 0 ist. (Fordert man, dass eine unendliche Teilmenge N1 ⊂ N gibt mitai 6= b − 1 fur i ∈ N1, dann ist die Darstellung (1.1) eindeutig). (1.1) heißtGleitpunktdarstellung. Als Basis b wird oft b = 10 (Schule) oder b = 2benutzt. Man spricht vom Dezimal- bzw. Dualsystem.
1.2 Allgemeine Gleitpunkt-Zahlensysteme
Da man auf Rechnern nicht beliebig viele Stellen zur Darstellung von Zahlenin der Form (1.1) zur Verfugung hat, z.B. fur die Zahlen 1
3= (
∑∞i=1 3·10−i)100
2
im Dezimalsystem oder 23
= (∑∞
i=1 ci · 2−i)20 mit c2k−1 = 0, c2k = 1 imDualsystem, arbeitet man mit Gleitpunktzahlsystemen wie folgt
Definition 1.1. Zu gegebener Basis b ≥ 2 und Mantisselange t ∈ N sowiefur Exponentenschranken emin < 0 < emax ist die Menge F = F (b, t, emin, emax) ⊂R durch
F =
{
σ
(t∑
i=1
aib−i
)
be : a1, . . . , at ∈ {0, 1, . . . , b − 1}, a1 6= 0, e ∈ Z,
emin ≤ e ≤ emax, σ ∈ {+,−}}
∪ {0}(1.2)
erklart und wird System von normalisierten Gleitpunktzahlen genannt.Lasst man noch die Kombination e = emin, a1 = 0 zu, dann erhalt manmit F ⊃ F das System der denormalisierten Gleitpunktzahlen.
Statt der Angabe von Exponentenschrankten emin, emax ∈ Z wird bei einemGleitpunktzahlsystem auch mit l die Stellenzahl des Exponenten e angege-ben, sodass man statt
F = F (2, 24,−127, 127) (1.3)
auchF = F (2, 24, 7)
schreiben kann, da man mit einer 7-stelligen Dualzahl alle Exponenten von0 bis ±127 darstellen kann. Statt F wird auch M (Maschinenzahlen) alsSymbol genutzt, also z.B.
M = F (2, 24, 7) (1.4)
Die Darstellung (1.3) ist aber oft praziser, da in der Praxis tatsachlich |emin| 6=emax ist, was bei (1.4) nicht zu erkennen ist.
3
1.3 Struktur und Eigenschaften des normali-
sierten Gleitpunktzahlensystems F2. Vor-lesungam15.4.2010
Es ist offensichtlich, dass die Elemente von F symmetrisch um den Nullpunktliegen, weshalb hier nur die positiven Elemente betrachtet werden sollen.Konkret betrachten wir F = F (b, t, emin, emax) und finden mit
xmin = (1 · b−1 + 0 · b−2 + · · · + 0 · b−t) · bemin = b−1+emin (1.5)
die die kleinste positive normalisierte Gleitpunktzahl. Andererseitsergibt sich mit
xmax = ((b − 1) · b−1 + (b − 1) · b−2 + · · · + (b − 1) · b−t) · bemax
= (1 − b−1 + b−1 − b−2 + · · · − b−t) · bemax
= (1 − b−t) · bemax (1.6)
die großte positive normalisierte Gleitpunktzahl. Fur die Mantissen a
von Zahlen aus F ergibt sich aus (1.5) und (1.6)
b−1 ≤ a ≤ 1 − b−t (1.7)
In F (Menge der denomalisierten Gleitpunktzahlen) sind kleinere Zahlen alsxmin darstellbar und zwar mit
xmin = (0 · b−1 + · · · + 1 · b−t) · bemin = b−t+emin (1.8)
die kleinste positive denormalisierte Gleitpunktzahl.Mit der Festlegung einer Mantissenlange t ist die Anzahl der moglichen Man-tissen festgelegt, sodass in jedem Intervall ]be−1, be[ gleich viele Gleitpunkt-zahlen liegen, die außerdem aquidistant verteilt sind, und zwar mit dem Ab-stand
∆ = b−t · be = be−t
Der kleinste Abstand einer beliebigen reellen Zahl x ∈ [be−1, be] zum nachst-gelegenen Element z aus F ist damit durch 1
2∆ begrenzt, d.h.
|z − x| ≤ 1
2be−t (1.9)
Die Gleichheit wird erreicht, wenn x genau zwsichen zwei benachbarten Zah-len aus F liegt, wegen be−1 ≤ x folgt aus (1.9)
|z − x||x| ≤
12be−t
be−1=
1
2b−t+1 =: eps (1.10)
4
mit eps = 12b−t+1 der maximale relative Abstand der Zahlen {x ∈ R :
xmin ≤ |x| ≤ xmax} zum nachstgelegenen Element aus F .Mit der Kenntnis von eps lasst sich nun uber die Bedingung
0.5 · 10−n ≤ eps ≤ 5 · 10−n (1.11)
eine Zahl n ∈ N bestimmen, und man spricht dann beim Gleitpunktzahlen-system F von einer n-stelligen Dezimalstellenarithmetik.Als Beispiele von in der Praxis benutzten Gleipunktzahlensystemen seien hierIEEE-Standardsystem
• F (2, 24,−125, 128) (einfach, real*4)
• F (2, 53,−1021, 1024) (doppelt, real*8)
sowie die IBM-Systeme
• F (16, 6,−64, 63) einfach
• F (16, 14,−64, 63) doppelt
genannt.
1.4 Rechnen mit Gleitpunktzahlen
Einfache Rechnungen zeigen, dass Gleitpunktzahlensysteme hinsichtlich derAdiition/Subtraktion bzw. Multiplikation/Division nicht abgeschlossen sind,d.h. Addition oder Multiplikation von Zahlen x, y ∈ F ergibt i.A. keine Zahlaus F .
Beispiel 1.2. F (10, 4,−63, 64), x = 0.1502 · 102, y = 0.1 · 10−4
x + y = 15.02 + 0.00001 = 15.02001 = 0.1502001 · 102
Hier reicht die Stellenzahl t = 4 nicht aus, um x + y in F exakt darzustellen.
Um in einem Gleitpunktzahlenystem rechnen zu konnen braucht man letzt-endlich eine Abbildung aus R in F
Definition 1.3. Zu einem gegebenen Gleitpunkzahlensystem F (b, t, emin, emax)mit gerader Basis b ist die Funktion rd : {x ∈ R : xmin ≤ |x| ≤ xmax} → R
durch
rd(x) =
{σ · (∑t
k=1 akb−k) · be falls at+1 ≤ 1
2b − 1
σ · (∑t
k=1 akb−k + b−t) · be falls at+1 ≥ 1
2b
fur x = σ · (∑t
k=1 akb−k) · be erklart. rd(x) heisst auf t Stellen gerundeter
Wert von x
5
Man kann nun folgende Eigenschaften fur das Runden zeigen:
Theorem 1.4. Zu einem gegebenen Gleitpunktzahlensystem F (b, t, emin, emax)gilt fur jede reelle Zahl x mit |x| ∈ [xmin, xmax] die Eigenschaft rd(x) ∈ F unddie Minimaleigenschaft
| rd(x) − x| = minz∈F
|z − x|
Beweis. Es gilt offensichtlich
t∑
k=1
akb−k ≤
∞∑
k=1
akb−k ≤
t∑
k=1
akb−k +
∞∑
k=t+1
(b − 1) · b−k =t∑
k=1
akb−k + b−t
Nach Multiplikation mit be erhalt man(
t∑
k=1
akb−k
)
︸ ︷︷ ︸
≥b−1
·be ≤( ∞∑
k=1
akb−k
)
· be = |x| ≤(
t∑
k=1
akb−k + b−t
)
︸ ︷︷ ︸
≤1
·be
d.h. die Schranken von |x| liegen im Intervall [be−1, be] und damit sind diebeiden fur rd(x) infrage kommenden Werte
σ
(t∑
k=1
akb−k
)
· be und σ
(t∑
k=1
akb−k + b−t
)
· be
die Nachbarn von x aus F , also ist rd(x) ∈ F .
Es wird nun die Abschatzung
| rd(x) − x| ≤ 1
2b−t+e (1.12)
gezeigt.
Beweis. Fur at+1 ≤ b2− 1 (abrunden) erhalt man
| rd(x) − x| =
( ∞∑
k=t+1
akb−k
)
· be =
(
at+1b−(t+1) +
∞∑
k=t+2
akb−k
)
· be
≤[(
b
2− 1
)
· b−(t+1) +∞∑
k=t+2
(b − 1) · b−k
]
· be
=
[(b
2− 1
)
b−(t+1) + b−(t+1)
]
· be =1
2b−t+e
6
Beim Aufrunden, d.h. at+1 ≥ b2, ergibt sich
| rd(x) − x| =
(
b−t −∞∑
k=t+1
akb−k
)
· be
=
b−t − ak+1b−(t+1)
︸ ︷︷ ︸
≥ 1
2b−t
−∞∑
k=t+2
akb−k
︸ ︷︷ ︸
≥0
· be ≤ 1
2b−t+e
Da wir fruher gezeigt haben, dass 12b−t+e die Halfte des Abstandes zweier
Nachbarn in F darstellt, folgt aus (1.12)
| rd(x) − x| = minz∈F
|z − x| (1.13)
Als Folgerung aus (1.12) erhalt man wegen |x| ≥ bemin
| rd(x) − x||x| ≤ 1
2b−t+1 = eps (Maschinenepsilon) (1.14)
als Abschatzung fur den relativen Rundungsfehler
Definition 1.5. eps = 12b−t+1 als Schranke fur den relativen Rundungsfeh-
ler heißt Maschinengenauigkeit oder roundoff unit u (es werden auch dieBezeichnungen macheps oder eps∗ verwendet, es gilt eps = inf{δ > 0 :rd(1 + δ) > 1}
Neben der Moglichkeit des Rundens mit rd gibt es auch als Alternative dasAbschneiden (englisch truncate).
Definition 1.6. Zu F = F (b, t, emin, emax) ist die Funktion tc : {x ∈ R :xmin ≤ |x| ≤ xmax} → F durch
tc(x) = σ ·(
t∑
k=1
akb−k
)
· be fur x = σ ·( ∞∑
k=1
akb−k
)
· be
erklart.
Bemerkung 1.7. Abschneiden ist i.A. ungenauer als Runden und es gilt
| tc(x) − x||x| ≤ 2 · eps
fur x ∈ R mit xmin ≤ |x| ≤ xmax.
7
1.5 Ersatzarithmetik
Durch Runden oder abschneiden gelingt es, reelle Zahlen x mit xmin ≤ |x| ≤xmax in ein gegebenes Gleitpunktzahlensystem F (b, t, emin, emax) abzubilden.Deshalb werden die Grundoperationen ◦ ∈ {+,−, ·, :} oft durch
x ◦ y = rd(x ◦ y) fur x, y ∈ F, xmin ≤ |x ◦ y| ≤ xmax (1.15)
oder
x ◦ y = tc(x ◦ y) fur x, y ∈ F, xmin ≤ |x ◦ y| ≤ xmax (1.16)
auf Rechner realisiert (bei Division soll y 6= 0 sein)
Theorem 1.8. Bezuglich der durch (1.15) bzw. (1.16) definierten Ersatzope-rationen +, −, ·, : ist F abgeschlossen, d.h. im Ergebnis dieser Operationenerhalt man Elemente aus F . Außerdem gilt die Beziehung bzw. Darstellung
x ◦ y = (x ◦ y) · (1 + ǫ) mit |ǫ| ≤ k · eps (1.17)
wobei im Fall von (1.15) k gleich 1 und im Fall von (1.16) k gleich 2 ist (ǫheißt Darstellungsfehler)
Beweis. Die Abgeschlossenheit von F bezuglich ◦ folgt aus Theroem 1.8. DieDarstellung (1.16) ergibt sich im Falle von (1.15) aus
| rd(x ◦ y) − (x ◦ y)||x ◦ y| ≤ eps
also aus (1.14)
1.6 Fehlerakkumulation
Wir betrachten Zahlen x, y ∈ R. Durch eine eventuelle Rundung erhalten wirmit
rd(x) = x + ∆x ∈ F
rd(y) = y + ∆y ∈ F
mit |∆x||x| ,
|∆y||y| ≤ ǫ Zahlen aus einem Gleitpunktzahlensystem F . ◦, ◦ sei nun
Multiplikation oder Division. Mit (1.15) und (1.17) erhalt man
(x + ∆x) ◦ (y + ∆y) = (x · (1 + τx)) ◦ (y · (1 + τy)), |τx|, |τy| ≤ ǫ
= (x ◦ y)((1 + τx) ◦ (1 + τy))(1 + α), |α| ≤ ǫ
= (x ◦ y)(1 + β)
8
wobei man benutzt, dass
(1 + τx) ◦ (1 + τy)(1 + α) = 1 + β
mit einem β mit der Eigenschaft |β| ≤ 3ǫ1−3ǫ
gilt (Beweis: Plato). Damit ergibtsich fur die Multiplikation/Division das
Theorem 1.9. Zu dem Gleitpunktzahlensystem F (b, t, emin, emax) seien dieZahlen x, y ∈ R und ∆x.∆y ∈ R gegeben mit x + ∆x ∈ F, y + ∆y ∈F,
|∆x||x| ,
|∆y||y| ≤ ǫ mit ǫ < 1
4. ◦ steht fur die Grundoperation · bzw. : und
fur x ◦ y soll xmin ≤ |x ◦ y| ≤ xmax gelten. Dann gilt die Fehlerdarstellung
(x + ∆x) ◦ (y + ∆y) = x ◦ y + η (1.18)
mit |η||x◦y| ≤ 3ǫ
1−4ǫ.
Die Darstellung (1.18) zeigt, dass die Multiplikation bzw. Division verhaltnis-maßig gutartig mit einem kleinen relativen Fehler ist. Im Folgenden soll nochauf die Fehlerverstarkung bei der Hintereinanderausfuhrung von Addition ineinem gegebenen GPZS F hingewiesen werden. Es gilt das
Theorem 1.10. Zu F (b, t, emin, emax) seien x1, . . . , xn ∈ R und ∆x1, . . . , ∆xn ∈R Zahlen mit
xk + ∆xk ∈ F,|∆xk||xk|
≤ ǫ fur k = 1, .., n
und es bezeichne
Sk :=k∑
j=1
(xj + ∆xj), Sk :=k∑
j=1
xj, k = 1, . . . , n
die entsprechenden Partialsummen (Summation von links nach rechts). Danngilt
|Sk − Sk| ≤(
k∑
j=1
(1 + ǫ)k−j(2|xj| + |Sj|))
︸ ︷︷ ︸
=:Mk
ǫ fur k = 1, .., n (1.19)
Falls die Partialsummen (Notation M0 = 0) innerhalb gewisser Schrankenliegen:
xmin + (Mk−1 + |xk|)ǫ ≤ |Sk| ≤ xmax − (Mk−1 + |xk|)ǫ k = 1, . . . , n
9
Bemerkung 1.11. Der Faktor (1 + ǫ)n−j in der Abschatzung (1.19) ist um-so großer, je kleiner j ist. Daher ist es vorteilhaft beim Aufsummieren mitden betragsmaßig kleinen Zahlen zu beginnen. Dies gewahrleistet zudem,dass die Partialsummen Sk betragsmaßig nicht unnotig anwachsen. Theorem1.10 liefert mit (1.19) nur eine Abschatzung fur den absoluten Fehler. Der
relative Fehler Sn−Sn||Sn| kann jedoch groß ausfallen, falls |Sn| klein gegenuber
∑n−1j=1 (|xj| + |Sj|) + |xn| ist!
10
Kapitel 2
Numerische Losung vonAnfangswertaufgaben
3. Vor-lesung21.04.10
Anwendungen wie Flugbahnberechnungen, Schwingungsberechnungen oderdie Dynamik von Rauber-Beute-Modellen fuhren auf Anfangswertproblemefur Systeme von gewohnlichen Differentialgleichungen:
Definition 2.1. Ein Anfangswertproblem fur ein System von n gewohn-lichen Differentialgleichungen 1. Ordnung ist von der Form
y′ = f(t, y), t ∈ [a, b] (2.1)
y(a) = y0 (2.2)
mit einem gegebenen endlichen Intervall [a, b], einem Vektor y0 ∈ Rn und
einer Abbildungf : [a, b] × R
n → Rn (2.3)
wobei eine differenzierbare Abbildung y : [a, b] → Rn mit den Eigenschaften
(2.1) - (2.3) als Losung des Anfangswertproblems gesucht ist.
Aussagen zur Existenz und Eindeutigkeit der Losung liefert
Satz 2.2. Erfullt f aus (2.3) die Bedingung
‖f(t, u) − f(t, v)‖ ≤ L ‖u − v‖ , t ∈ [a, b], u, v ∈ Rn (2.4)
mit einer Konstanten L > 0 in einer beliebigen Vektornorm ‖·‖ des Rn, dann
gelten die Aussagen
(a) Das AWP (2.1),(2.2) besitzt genau eine stetig diff’bare Losung y : [a, b] →R
n (Picard-Lindelof)
11
(b) Fur differenzierbare Funktionen y, y : [a, b] → Rn mit
y′ = f(t, y), t ∈ [a, b]; y(a) = y0
y′ = f(t, y), t ∈ [a, b]; y(a) = y0
gilt die Abschatzung
‖y(t) − y‖ ≤ eL(t−a) ‖y0 − y0‖ , t ∈ [a, b] (2.5)
Beweis. Vorlesung DGL oder Analysis
Bemerkung.
(1) Mit den Aussagen des Satzes 2.2 hat man die Existenz und Eindeu-tigkeit der Losung und die stetige Abhangigkeit der Losung von denAnfangsdaten unter der Voraussetzung der Lipschitzstetigkeit von f(t, ·)vorzuliegen.
(2) Im Folgenden sollen numerische Losungsverfahren entwickelt werden, wo-bei wir ohne die Allgemeinheit einzuschranken den Fall n = 1 betrachten.Die besprochenen Verfahren gelten allerdings auch im allgemeinen Falln > 1
Definition 2.3. Unter dem Richtungsfeld der Differentialgleichung
y′ = f(t, y)
versteht man das Vektorfeld
r(t, y) =
1√1+f2(t,y)f(t,y)√1+f2(t,y)
d.h. das Vektorfeld der normierten Steigungen
Betrachtet man um einen beliebigen Punkt (t0, y0) der (t, y)- Ebene, kannman Losungskurven y(t) durch diesen Punkt annahren:
Beispiel.
y′ = y2 + t2, r(t, y) =
1√1+(y2+t2)2
y2+t2√1+(y2+t2)2
(I) y′(t0) = y20 + t20, (t0 = a entspricht Start in Anfangspunkt (a, y0))
t-Achse wird durch tk = t0 + hk aquidistant unterteilt
12
(II) mit dem Schritt von Punkt
(t0, y0) zu (t0 + h, y0 + hy′(t0)) =: (t1, y1)
bzw. allgemein vom Punkt
(tk, yk) zu (tk + h, yk + hf(tk, yk)) =: (tk+1, yk+1)
erhalt man mit h = b−aN
nach m Schritten mit
y0, y1, . . . , yN
unter “gunstigen” Umstanden eine Approximation der Losung y(t) anden Stellen
a = t0, t1, . . . , tN = b
(III) D.h. man fahrt das Richtungsfeld geeignet ab, um eine numerischeLosung yk, k = 0, 1, . . . , N zu erhalten
2.1 Theorie der Einschrittverfahren
Definition 2.4. Ein Einschrittverfahren zur naherungsweisen Bestimmungeiner Losung des AWP (2.1),(2.2) hat die Form
yk+1 = yk + hkΦ(tk, yk, yk+1, hk), k = 0, 1, . . . , N − 1 (2.6)
mit einer Verfahrensfunktion
Φ : [a, b] × R × R × R+ → R
und einem (noch nicht naher spezifizierten) Gitter bzw. Schrittweiten
∆ = {a = t0 < t1 < . . . < tN ≤ b}, hk := tk+1 − tk, k = 0, 1, . . . , N − 1(2.7)
Bemerkung. Hangt die Verfahrensfunktion nicht von yk+1 ab, ist die Be-rechnungsvorschrift (2.6) eine explizite Formel zur Berechnung von yk+1 undman spricht von einem expliziten Einschrittverfahren.
Zur Klassifizierung und Bewertung von numerischen Losungsverfahren furAWP benotigen wir im Folgenden einige Begriffe (y(t) bezeichnet hier dieexakte Losung).
13
Definition 2.5. Unter dem lokalen Diskretisierungsfehler an der Stelletk+1 des Verfahrens (2.6) versteht man den Wert
dk+1 := y(tk+1) − y(tk) − hkΦ(tk, y(tk), y(tk+1), hk) (2.8)
Definition 2.6. Unter dem globalen Diskretisierungsfehler gk an der Stelletk versteht man den Wert
gk := y(tk) − yk
Definition 2.7. Ein Einschrittverfahren (2.6) besitzt die Fehlerordnung p,falls fur seinen lokalen Diskretisierungsfehler dk die Abschatzungen
|dk| ≤ const.hp+1k , k = 1, . . . , N
max1≤k≤N
|dk| ≤ D = const.hp+1max = O(hp+1
max) (2.9)
mit hmax = maxk=0,...,N−1 tk+1 − tk gilt. (Statt Fehlerordnung verwendet manauch den Begriff Konsistenzordnung.) Ist p ≥ 1, dann heißt das Verfahrenkonsistent.
Die Bedingungen
|Φ(t, u1, u2, h) − Φ(t, v1, u2, h)| ≤ L1 |u1 − v1||Φ(t, u1, u2, h) − Φ(t, u1, v2, h)| ≤ L2 |u2 − v2| (2.10)
fur t ∈ [a, b], 0 < h ≤ b − t, uj, vj ∈ R, mit positiven konstanten L1, L2
sind fur die folgenden Konvergenzuntersuchungen von Einschrittverfahrenvon Bedeutung
Satz 2.8. Ein Einschrittverfahren (2.6) zur Losung des AWP (2.1), (2.2)besitze die Konsistenzordnung p ≥ 1 und die Verfahrensfunktion erfulle dieBedinung (2.10). Dann liegt die Konvergenzordnung p vor, d.h. es gilt
maxk=0,...,N
|yk − y(tk)| ≤ Khpmax
Mit einer Konstanten k, die vom Intervall [a, b], Konstanten C aus derAbschatzung (2.9) und L1, L1 aus (2.10) herruhrt.
Beweise des Satzes 2.8 fur Einschrittverfahren findet man z.B. den Buchernvon Barwolff oder Schwarz.
14
2.2 Spezielle Einschrittverfahren
Im Folgenden betrachten wir skalare Anfangswertprobleme, d.h. Gleichungeny′ = f(t, y) ∈ R. Damit schranken wir die Allgemeinheit nicht ein, denn dieVerfahren und deren Eigenschaften lassen sich problemlos auf den Fall vonSystemen 1. Ordnung, d.h. y′ = f(t, y) ∈ R
n ubertragen.
2.2.1 Euler-Verfahren
Mit der Verfahrensfunktion
Φ(t, y, hk) = f(t, y)
erhalt man mit
yk+1 = yk + hkf(tk, yk), k = 0, . . . , N − 1 (2.11)
das Euler-Verfahren.Fur eine stetig partiell diff’bare Funktion f : [a, b]×R → R besitzt das Euler-Verfahren die Konsistenzordnung p = 1, denn mit der Taylorentwicklung
y(t + h) = y(t) + y′(t)h +h2
2y′′(ξ), ξ ∈ [a, b]
erhalt man
dk+1 = y(tk+1) − y(tk) − hkf(tk, y(tk)) =h2
k
2y′′(ξ)
bzw.
|dk+1| ≤ Ch2k mit C =
1
2maxξ∈[a,b]
|y′′(ξ)|
2.2.2 Einschrittverfahren der Konsistenzordnung p = 2
Um ein explizites Einschrittverfahren der Konsistenzordnung p = 2 zu erhal-ten, machen wir den Ansatz
Φ(t, y, h) = a1f(t, y)+a2f(t+b1h, y+b2hf(t, y)), t ∈ [a, b], h ∈ [0, b−t], y ∈ R
(2.12)mit noch festzulegenden Konstanten aj, bj ∈ R. Es gilt nun der
Satz 2.9. Ein Einschrittverfahren (2.6) mit einer Verfahrensfunktion derForm (2.12) ist konsistent mit der Ordnung p = 2, falls f : [a, b] × R → R
zweimal stetig partiell diff’bar ist und fur die Koeffizienten
a1 + a2 = 1, a2b1 =1
2, a2b2 =
1
2(2.13)
gilt.
15
Beweis. Taylorentwicklung von Φ(t, y(t), ·) im Punkt h = 0 und von derLosung y in t ergeben
Φ(t, y(t), h) = Φ(t, y(t), 0) + hdΦ
dh(t, y(t), 0) + O(h2)
= (a1 + a2)f(t, y(t)) + h
(
a2b1∂f
∂t(t, y(t))
+a2b2f(t, y(t))∂f
∂y(t, y(t))
)
+ O(h2)
= f(t, y(t)) +h
2
∂f
∂t(t, y(t)) +
h
2f(t, y(t))
∂f
∂y(t, y(t)) + O(h2)
y(t + h) = y(t) + hy′(t) +h2
2y′′(t) + O(h3)
= y(t) + h
[
f(t, y(t)) +h
2y′′(t)
]
+ O(h3)
= y(t) + h
[
f(t, y(t)) +h
2
{∂f
∂t(t, y(t))
+f(t, y(t))∂f
∂y(t, y(t))
}]
+ O(h3)
= y(t) + hΦ(t, y(t), h) + O(h3)
und damit folgt
dk+1 = y(tk+1) − y(tk) − hkΦ(tk, y(tk), hk) = O(h3k)
also p = 2
Mit der konkreten Wahl a1 = 0, a2 = 1, b1 = b2 = 12
erhalt man mit
yk+1 = yk + hkf
(
tk +hk
2, yk +
hk
2f(tk, yk)
)
, k = 0, . . . , N − 1 (2.14)
das modifizierte Euler-Verfahren (verbesserte Polygonzugmethode) mitder Konsistenzordnung p = 2Mit der Wahl a1 = a2 = 1
2, b1 = b2 = 1 erhalt man mit
yk+1 = yk +hk
2[f(tk, yk) + f(tk + hk, yk + hkf(tk, yk))] , k = 0, . . . , N − 1
(2.15)das Verfahren von Heun mit der Konsistenzordnung p = 2
16
Im Folgenden ist ein Programm (ich habe es nur unter GNU-octave aus-probiert, es sollte aber auch unter matlab laufen) zur Erzeugung der Rich-tungsfelds der Differentialgleichung y′ = y − t sowie zur Losung des AWPsy′ = y − t, y(0) = 1
2mit dem Euler-Verfahren (p = 1) und dem Heun-
Verfahren (p = 2) angegeben.
% Hauptprogramm main.m incl. einiger Schritte der num. Verfahren
hold off
dgl = @(y, t) y-t; % Funktionsdefinition
richtungsfeld(dgl) % Aufruf des Skripts
% Euler-verfahren (explizit) zur Loesung von
% y’ = y - t, y(0) = 1/2
% mit der Schrittweite h=1/8 im Intervall [0,3.5]
%
t = linspace(0,5,40);
h = 0.125;
y(1) = 0.5;
for k=1:25
y(k+1) = y(k) + h*dgl(y(k),t(k));
end
%
% Heun-Verfahren
%
yh(1) = 0.5;
for k=1:24
k1 = dgl(yh(k),t(k));
k2 = dgl(yh(k)+h*k1,t(k)+h);
yh(k+1) = yh(k) + 0.5*h*(k1+k2);
end
%
% exakte loesung
for k=1:24
ye(k) = -0.5*exp(t(k)) + t(k) + 1;
end
hold on
% plot der num. Loesung (Euler)
plot(t(1:26),y(1:26),’+’);
% plot der num. Loesung (Heun)
plot(t(1:25),yh(1:25),’*’);
% plot der exakten Loesung
plot(t(1:24),ye(1:24));
%
17
title(’Richtungsfeld von y’’ = y - t, num. (Euler,+,Heun,*) vs. exakte Loesung’);
% Erzeugung eines Grafik-Files
print(’field.png’,’-dpng’)
% Ende des Hauptprogramms
% Unterprogramm richtungsfeld.m zur Berechnung und Zeichnung des Richtungsfeldes
function richtungsfeld(dgl)
% dgl ist die erste Ableitung von y nach t und ist i.A. eine Funktion von y und t
%
% Ausschnitt und Abstand zwischen den Vektoren
y = -5:1:5;
t = -5:.5:5;
%
for y_n = 1:length(y)
for t_n = 1:length(t)
len = sqrt( dgl(y(y_n), t(t_n))^2 + 1 ); % Laenge des Vektors fuer Normierung
dt(y_n,t_n) = 1 / len; % Laenge des Vektors entlang der Abszisse
dy(y_n,t_n) = dgl(y(y_n), t(t_n)) / len; % Laenge des Vektors entlang der Ordinate
end
end
%
quiver(t, y, dt, dy, ’r’); % Vektoren zeichnen
% Ende des Unterprogramms
18
2.3 Verfahren hoherer Ordnung4. Vor-lesung22.04.10
Die bisher besprochenen Methoden (Euler, Heun) haben wir weitestgehendintuitiv ermittelt. Um systematisch Einschrittverfahren hoherer Ordnung zukonstruieren, betrachten wir die zum AWP y′ = f(t, y), y(a) = y0 aquivalenteGleichung (nach Integration)
y(t) = y0 +
∫ t
a
f(s, y(s))ds (2.16)
bzw. fur eine Diskretisierung des Intervalls [a, b]
y(tk+1) = y(tk) +
∫ tk+1
tk
f(s, y(s))ds (2.17)
Das letzte Integral aus (2.17) approximieren wir durch eine Quadraturformel
∫ tk+1
tk
f(s, y(s))ds (2.18)
wobei die sl zu einer Zerlegung von [tk, tk+1] gehoren. (2.17) und (2.18) erge-ben
y(tk+1) ≈ y(tk) + hk
m∑
l=1
γlf(sl, y(sl)) (2.19)
wobei wir die Werte y(sl) nicht kennen. Sie mussen naherungsweise aus y(tk)bestimmt werden, damit (2.19) als Integrationsverfahren benutzt werdenkann.Wahlt man z.B. m = 2 und γ1 = γ2 = 1
2sowie s1 = tk und s2 = tk+1, dann
bedeutet (2.19)
y(tk+1) ≈ y(tk) +hk
2[f(tk, y(tk)) + f(tk+1, y(tk+1))]
und mit der Approximation
y(tk+1) ≈ y(tk) + hkf(tk, y(tk))
ergibt sich mit
y(tk+1) ≈ y(tk) +hk
2[f(tk, y(tk)) + f(tk+1, y(tk) + hkf(tk, y(tk)))]
die Grundlage fur das Verfahren von Heun.
19
Im Weiteren wollen wir mit yk die Verfahrenswerte zur Naherung der exaktenWerte y(tk) bezeichnen und als Naherungen von f(sl, y(sl))
f(sl, y(sl)) ≈ kl(tj, yj)
verwenden. Mit
sl = tk + αlhk, αl =l−1∑
r=1
βlr
werden die kl rekursiv definiert:
k1(tk, yk) = f(tk, yk)
k2(tk, yk) = f(tk + α2hk, yk + hkβ21k1(tk, yk))
k3(tk, yk) = f(tk + α3hk, yk + hk(β31k1 + β32k2)) (2.20)
...
km(tk, yk) = f(tk + αmhk, yk + hk(βm1k1 + · · · + βmm−1km−1))
Ausgehend von (2.19) und (2.20) wird durch
yk+1 = yk + hk(γ1k1(tk, yk) + · · · + γmkm(tk, yk)) (2.21)
ein explizites numerisches Verfahren zu Losung des AWP y′ = f(t, y), y(a) =y0 definiert.
Definition 2.10. Das Verfahren (2.21) heißt m-stufiges Runge-Kutta-
Verfahren mit kl aus (2.20) und die kl heißen Stufenwerte.
Bemerkung. Wir haben oben schon festgestellt, dass im Fall m = 2 mitγ1 = γ2 = 1
2, α2 = 1, β21 = 1 (2.21) gerade das Heun-Verfahren ergibt, also ein
Verfahren mit der Konsistenzordnung p = 2. Wir werden nun Bedingungenfur die freien Parameter im Verfahren (2.21) formulieren, sodass einmal einkonsistentes Verfahren (p ≥ 1) entsteht und andererseits eine moglichst großeKonsistenzordnung erhalten wird.
Aus der Verwendung der Quadraturformel
hk
m∑
l=1
γlf(sl, y(sl)) ≈∫ tk+1
tk
f(s, y(s))ds
folgt die sinnvolle Forderung
1 = γ1 + γ2 + · · · + γm (2.22)
20
also haben die γl die Funktion von Gewichten.Fordert man vom Verfahren (2.21), dass die Dgl y′ = 1 (y linear) exaktintegriert wird, ergibt sich die Bedingung
αl = βl1 + · · · + βll−1 (2.23)
Es ist namlich f(t, y) ≡ 1 und damit kl ≡ 1 fur alle l. Ausgangspunkt war
kl(tk, yk) ≈ f(sl, y(sl))
undkl ≈ f(tk + αlhk, y(tk) + hk(βl1k1 + · · · + βll−1kl−1)) .
Also steht das y-Argument fur y(sl) = y(tk + αlhk). Wir fordern, dass diesbei f ≡ 1 exakt ist, also
y(sl) = y(tk) + hk(βl1 + · · · + βll−1) (2.24)
da alle kr = 1 sind. Andererseits ist y als exakte Losung linear, d.h.
y(sl) = y(tk) + αlhk (2.25)
und aus dem Vergleich von (2.24),(2.25) folgt
αl = βl1 + · · · + βll−1
Definition 2.11. Die Tabelle mit den Koeffizienten αl, βlr, γr in der Form
0α2 β21
α3 β31 β32...
......
. . .
αm βm1 βm2 . . . βmm−1
γ1 γ2 . . . γm−1 γm
(2.26)
heißt Butcher-Tabelle und beschreibt das Verfahren (2.21). α1 ist hiergleich 0, weil explizite Verfahren betrachtet werden.
Satz 2.12. Ein explizites Runge-Kutta-Verfahren (2.21), dessen Koeffizien-ten die Bedingungen (2.22) und (2.23) erfullen, ist konsistent.
21
Beweis. Es ist zu zeigen, dass der lokale Diskretisierungsfehler die OrdnungO(hp+1
k ) mit p ≥ 1 hat. Wir setzen hk =: h, da k jetzt fixiert ist.
|dk+1| = |y(tk+1) − y(tk) − hΦ(tk, y(tk), h)|
=
∣∣∣∣∣y(tk+1) − y(tk) − h
m∑
r=1
γrkr(tk, y(tk))
∣∣∣∣∣
(2.22)=
∣∣∣∣∣y(tk+1) − y(tk) − hf(tk, y(tk)) − h
m∑
r=1
γr(kr(tk, y(tk)) − f(tk, y(tk))
∣∣∣∣∣
≤ |y(tk+1) − y(tk) − hy′(tk)|︸ ︷︷ ︸
∈O(h2)
+h
∣∣∣∣∣∣∣
m∑
r=1
γr (kr(tk, y(tk)) − f(tk, y(tk)))︸ ︷︷ ︸
∈O(h)
∣∣∣∣∣∣∣
also|dk+1| ≤ Ch2
Bemerkung. Butcher hat bewiesen, wie groß die maximale Ordnung ist,welche mit einem m-stufigen Runge-Kutta-Verfahren erreichbar ist, was inder folgenden Tabelle notiert ist:
m 1 2 3 4 5 6 7 8 9 fur m ≥ 9p 1 2 3 4 4 5 6 6 7 p < m − 2
2.4 Einige konkrete Runge-Kutta-Verfahren
und deren Butcher-Tabellen
(i) Euler-Verfahren0
1m = 1, γ1 = 1
yk+1 = yk + hkf(tk, yk), p = 1
(ii) Modifiziertes Euler-Verfahren
012
12
0 1m = 2, γ1 = 0, γ2 = 1, α2 =
1
2, β21 =
1
2
22
k1 = f(tk, yk)
k2 = f(tk +1
2hk, yk +
1
2hkk1)
yk+1 = yk + hkk2, p = 2
(iii) Verfahren von Runge von 3. Ordnung
012
12
1 0 10 0 1
m = 3, γ1 = γ2 = 0, γ3 = 1, α2 =1
2, α3 = 1, β21 =
1
2, β31 = 0, β32 = 1
k1 = f(tk, yk)
k2 = f(tk +1
2hk, yk +
1
2hkk1)
k3 = f(tk + hk, yk + hkk2)
yk+1 = yk + hkk3, p = 3
(iv) Klassisches Runge-Kutta-Verfahren 4. Ordnung
012
12
12
0 12
1 0 0 116
13
13
16
k1 = f(tk, yk)
k2 = f(tk +1
2hk, yk +
1
2hkk1)
k3 = f(tk +1
2hk, yk +
1
2hkk2)
k4 = f(tk + hk, yk + hkk3)
yk+1 = yk + hk
(1
6k1 +
1
3k2 +
1
3k3 +
1
6k4
)
, p = 4
23
Bemerkung. Die Ordnung eines konkreten Runge-Kutta-Verfahrens kannmit Hilfe von Taylor-Entwicklungen ermittelt werden, wobei man dabei voneiner geeigneten Glattheit von f(t, y) ausgeht.
Im Folgenden soll die Ordnung eines 3-stufigen expliziten Runge-Kutta- Ver-fahrens bestimmt werden.
Satz 2.13. Sei f dreimal stetig partiell diff’bar und gelte fur die Parameter
α2 = β21
α3 = β31 + β32
γ1 + γ2 + γ3 = 1
sowie
α2γ2 + α3γ3 =1
2
α2γ3β32 =1
6
α22γ2 + α2
3γ3 =1
3
Dann hat das Runge-Kutta-Verfahren (explizit, 3-stufig) die Fehlerordnungp = 3
Beweis. Grundlage fur den Beweis ist die Taylor-Approximation
f(t + ∆t, y + ∆y) = f(t, y) +
(∂f
∂t(t, y)
∂f
∂t(t, y)
) (∆t
∆y
)
+1
2(∆t, ∆y)
(∂2f
∂t2(t, y) ∂2f
∂t∂y(t, y)
∂2f
∂y∂t(t, y) ∂2f
∂y2 (t, y)
)(∆t
∆y
)
+ O(∆3)
(2.27)
der Funktion f , wobei ∂2f
∂t∂y= ∂2f
∂y∂taufgrund der Glattheit von f gilt. Mit
k1 = f(tk, y(tk))
k2 = f(tk + α2h, y(tk) + α2hk1)
k3 = f(tk + α3h, y(tk) + h(β31k1 + β32k2))
gilt es, den lokalen Diskretisierungsfehler
dk+1 = y(tk+1) − y(tk) − h(γ1k1 + γ2k2 + γ3k3)
24
abzuschatzen, wobei schon α2 = β21 verwendet wurde (h = hk). Mit ∆t =α2h und ∆y = α2hf(tk, y(tk)) ergibt (2.27) fur k2
k2 = f(tk + ∆t, y(tk) + ∆y)
= f + α2hft + α2hffy +1
2α2
2h2ftt + α2
2h2ffty +
1
2α2
2h2f 2fyy + O(h3)
=: f + α2hF +1
2α2
2h2G + O(h3) (2.28)
f, ft, . . . , fyy sind dabei die Funktions- bzw. Ableitunswerte an der Stelle(tk, y(tk)). Fur k3 erhalt man unter Nutzung von (2.28) und (2.27)
k3 = f(tk + α3h, y(tk) + h(β31k1 + β32k2)
= f + α3hft + h(β31k1 + β32k2)fy +1
2α2
3h2ftt
+ α3(β31k1 + β32k2)h2fty +
1
2(β31k1 + β32k2)
2h2fyy + O(h3)
= f + h(α3ft + [β31 + β32]ffy) + h2(
α2β32Ffy
+1
2α2
3ftt + α3[β31 + β32]ffty +1
2(β31 + β32)f
2fyy
)
+ O(h3)
= f + α3hF + h2(α2β32Ffy +1
2α2
3G) + O(h3) (2.29)
Mit (2.28) und (2.29) folgt fur den lokalen Diskretisierungsfehler
dk+1 = h(1 − γ1 − γ2 − γ3)f + h2
(1
2− α2γ2 − α3γ3
)
F
+h3
([1
6− α2γ3β32
]
Ffy +
[1
6− 1
2α2
2γ2 −1
2α2
3γ3
]
G
)
+ O(h4)
(2.30)
Aufgrund der Voraussetzungen werden dei Klammerausdrucke gleich Nullund es gilt
dk+1 = O(h4)
also hat das Verfahren die Fehlerordnung p = 3
Korollar. Mit Losungen des Gleichungssystems
γ1 + γ2 + γ3 = 1
α2γ2 + α3γ3 =1
2
α2γ3β32 =1
6(2.31)
α22γ2 + α2
3γ3 =1
3
25
hat das dazugehorrige 3-stufige Runge-Kutta-Verfahren die Fehlerordnungp = 3, wobei α2 = β21 ist. (2.31) hat z.B. mit den Einschrankungen α2 6= α3
und α2 6= 23
die Losungen
γ2 =3α3 − 2
6α2(α3 − α2), γ3 =
2 − 3α2
6α3(α3 − α2)(2.32)
γ1 =6α2α3 + 2 − 3(α2 + α3)
6α2α3
, β32 =α3(α3 − α2)
α2(2 − 3α2)
fur α2, α3 ∈ R, also die zweiparametrige Losungsmenge
M = {(γ1, γ2, γ3, α2, α3, β32)|γ1, γ2, γ3β32 gemaß (2.32),
α2, α3 ∈ R, α2 6= α3, α2 6=2
3}
Die restlichen Parameter des Verfahrens ergeben sich aus
β21 = α2, β31 = α3 − β32
26
2.5 Implizite Runge-Kutta-Verfahren5. Vor-lesung28.04.2010
Explizite Verfahren neigen zur Instabilitat und damit besteht die Gefahr derVerstarkung von Rundungsfehlern.Implizite Verfahren erweisen sich als stabil, speziell, wenn es sich um dieLosung von AWPs mit sogenannten steifen DGL handelt.Im Unterschied zum Gleichungssystem (2.20) wird beim impliziten Runge-Kutta-Verfahren das Gleichungssystem
kr(tk, yk) = f(tk +αrhk, yk +hk(βr1k1 + · · ·+βrmkm)), r = 1, . . . ,m (2.33)
zur Bestimmung der kr zugrunde gelegt.Mit (2.33) wird (2.21) zu einem impliziten Runge-Kutta- Verfahren. Aus(2.33) ergibt sich die Butcher-Tabelle
α1 β11 . . . β1m
α2 β21 . . . β2m
......
...αm βm1 . . . βmm
γ1 . . . γm
(2.34)
Die Uberlegung, die bei den expliziten Verfahren die Bedingung (2.23) fur dieKoeffizienten αr, βrl gerechtfertigt haben, ergeben analog bei den implizitenRunge-Kutta- Verfahren die Bedingung
αr = βr1 + βr2 + · · · + βrm, r = 1, . . . ,m (2.35)
Zur Losbarkeit des Gleichungssystems (2.33) gilt der
Satz 2.14. f genuge auf [a, b] × R der Lipschitz-Bedingung
|f(t, y1) − f(t, y2)| ≤ L |y1 − y2|
und die Schrittweite h = hk genuge der Bedingung
q = hL max1≤j≤m
(m∑
r=1
|βjr|)
< 1
Dann hat (2.33) zur Bestimmung von k1, . . . , km genau eine Losung
Beweis. Aussage folgt aus dem Banachschen Fixpunktsatz
27
2.6 Rundungsfehleranalyse von expliziten Ein-
schrittverfahren
Zur numerischen Losung eines AWP betrachten wir das Verfahren
yk+1 = yk + hkΦ(tk, yk, hk), k = 0, 1, 2 . . . , N − 1 (2.36)
mit der Verfahrensfunktion Φ. Durch Rundungsfehler arbeitet man statt(2.36) mit einem Verfahren der Form
yk+1 = yk + hkΦ(tk, yk, hk) + ρk, k = 0, 1, . . . , N − 1 (2.37)
y0 = y0 + e0, |ρk| ≤ δ, k = 0, 1, . . . , N − 1
mit gewissen Zahlen e0, ρk ∈ R
Fur die Rundungsfehler infolge des Verfahrens (2.37) gilt der folgende
Satz 2.15. Zur Losung des AWP y′ = f(t, y), y(a) = y0, sei durch (2.36)ein Einschrittverfahren mit der Konsistenzordnung p ≥ 1 gegeben, wobei dieVerfahrensfunktion bezuglich der 2. Variablen Lipschitz-stetig mit der Kon-stanten L > 0 ist.Dann gelten fur die durch die fehlerbehaftete Verfahrensvorschrift (2.37) ge-wonnenen Approximationen die Abschatzungen
maxk=0,...,N
|yk − y(tk)| ≤ K(hpmax +
δ
kmin
) + eL(b−a)ǫ (2.38)
mit der Konstanten K = max{C,1}L
[eL(b−a) − 1
]. C ist dabei die Konstante aus
der Abschatzung |dk| ≤ Chp+1k fur den lokalen Diskretisierungsfehler.
2.7 Schrittweitensteuerung bei Einschrittver-
fahren
Bei der Konvergenzuntersuchung von Einschrittverfahren werden die loka-len Diskretisierungsfehler in gewissem Sinn summiert und deshalb erscheinteine Beschrankung des Absolutbetrages von dk durch die Wahl geeigneterSchrittweiten hk sinnvoll. Man spricht hier von Schrittweitensteuerung.Das Prinzip soll am Beispiel des Heun-Verfahrens
k1 = f(tk, yk)
k2 = f(tk + h, yk + hk1)
yk+1 = yk +1
2h[k1 + k2]
28
erlautert werden. Als lokaler Diskretisierungsfehler ergibt sich
d(H)k+1 = y(tk+1) − y(tk) −
1
2h[k1 + k2] (2.39)
mit k1 = f(tk, y(tk)), k2 = f(tk + h, y(tk) + hk1)Nun sucht man ein Verfahren hoherer Ordnung, also mindestens dritterOrdnung, dessen Steigungen k1, k2 mit den Steigungen des Heun-Verfahrensubereinstimmen.Die Forderung der Gleichheit von k1 und k2 bedeutet α2 = β21 = 1. Dieweiteren Parameter ergeben sich aus (2.32) bei der Wahl von α3 = 1
2zu
γ3 =2
3, γ2 =
1
6, γ1 =
1
6, β32 =
1
4, β31 = α3 − β32 =
1
4
sodass sich das Runge-Kutta-Verfahren 3. Ordnung
k1 = f(tk, yk)
k2 = f(tk + h, yk + hk1)
k3 = f(tk +h
2, yk +
h
4(k1 + k2))
yk+1 = yk +h
6[k1 + k2 + 4k3] (2.40)
ergibt. Fur den lokalen Diskretisierungsfehler des Verfahrens (2.39) ergibtsich
d(RK)k+1 = y(tk+1) − y(tk) −
h
6[k1 + k2 + 4k3] (2.41)
mit k3 = f(tk + h2, y(tk) + h
4(k1 + k2)). Mit (2.39) und (2.41) ergibt sich die
Darstellung des lokalen Diskretisierungsfehlers des Heun-Verfahrens
d(H)k+1 =
h
6[k1 + k2 + 4k3] −
h
2[k1 + k2] + d
(RK)k+1
Ersetzt man nun die unbekannten Werte von kj durch die Naherungen kj
und berucksichtigt d(RK)k+1 = O(h4), so erhalt man
d(H)k+1 =
h
6[k1 + k2 + 4k3] −
h
2[k1 + k2] + O(h4) =
h
3[2k3 − k1 − k2] + O(h4)
und damit kann der lokale Diskretisierungsfehler des Heun-Verfahrens miteiner zusatzlichen Steigungsberechnung von k3 durch den Ausdruck h
3[2k3 −
k1 − k2] recht gut geschatzt werden.
29
Aufgrund der Kontrolle des Betrags dieses Ausdrucks kann man eine vorge-gebene Schranke ǫtol > 0 durch entsprechende Wahl von h = hk = tk+1 − tk
hk <3ǫtol
|2k3 − k1 − k2|⇔ hk
3[2k3 − k1 − k2] < ǫtol
unterschreiten. D.h. man kann die aktuelle Schrittweite evtl. vergroßern odermuss sie verkleinern.Die eben beschriebene Methode der Schrittweitensteuerung bezeichnet manauch als Einbettung des Heun-Verfahrens 2. Ordnung in das Runge-Kutta-Verfahren 3. Ordnung (2.40).
2.8 Mehrschrittverfahren
Die Klasse der Mehrschrittverfahren zur Losung von AWP ist dadruch ge-kennzeichnet, dass man zur Berechnung des Naherungswertes yk+1 nicht nurden Wert yk verwendet, sondern auch weiter zuruckliegende Werte, z.B.yk−1, yk−2.Als Ausgangspunkt zur Konstruktion von Mehrschrittverfahren betrachtenwir die zum AWP aquivalente Integralbeziehung
y(tk+1) = y(tk) +
∫ tk+1
tk
f(s, y(s))ds (2.42)
Kennt man die Werte fk = f(tk, yk), . . . , fk−3 = f(tk−1, yk−3), dann kann mandas Integral auf der rechten Seite von (2.42) i.d.R. besser approximieren alsbei den Einschrittverfahren unter ausschließlicher Nutzung des Wertes fk.Fur das Interpolationspolynom durch die Stutzpunkte (tj, yj)j=k−3,...,k ergibtsich
p3(t) =3∑
j=0
fk−jLk−j
mit den Lagrangschen Basispolynomen
Lj(t) =k∏
j 6=i=k−3
t − ti
tj − ti, j = k − 3, . . . , k
Die Idee der Mehrschrittverfahren besteht nun in der Nutzung von p3(t) alsApproximation von f(t, y(t)) im Integral von (2.42), sodass man auf der
30
Grundlage von (2.42) das Mehrschrittverfahren (4-Schritt-Verfahren)
yk+1 = yk +
∫ tk+1
tk
3∑
j=0
fk−jLk−j(t)dt
= yk +3∑
j=0
fk−j
∫ tk+1
tk
Lk−j(t)dt
erhalt. Im Fall aquidistanter Stutzstellen h = tk+1 − tk erh alt man fur den2. Integralsummanden (j = 1)
I1 =
∫ tk−1
tk
Lk−1(t)dt =
∫ tk+1
tk
(t − tk−3)(t − tk−2)(t − tk)
(tk−1 − tk−3)(tk−1 − tk−2)(tk−1 − tk)
und nach der Substitution ξ = t−tkh
I1 = h
∫ 1
0
(ξ + 3)(ξ + 2)ξ
2 · 1 · (−1)dξ = −h
2
∫ 1
0
(ξ3 + 5ξ2 + 6ξ)dξ = −59
24h
Fur die restlichen Integrale erhalt man
I0 =55
24h, I2 =
37
24h, I3 = − 9
24h
sodass sich mit
yk+1 = yk +h
24[55fk − 59fk−1 + 37fk−2 − 9fk−3] (2.43)
die Methode von Adams-Bashforths (kurz AB-Verfahren) ergibt.Durch Taylor-Reihenentwicklung erhalt man bei entsprechendert Glattheitvon f bzw. y(t) den lokalen Diskretisierungsfehler
dk+1 =251
720h5y(5) + O(h6) (2.44)
d.h. das Verfahren (2.43) ist von 4. Ordnung.
Definition 2.16. Bei Verwendung von m Stutzwerten
(tk, fk), . . . , (tk−m+1, fk−m+1)
zur Berechnung eines Interpolationspolynoms pm−1 zur Approximation von f
zwecks naherungsweiser Berechnung des Integrals in (2.42) spricht man voneinem linearen m-Schrittverfahren.Ein m-Schrittverfahren hat die Fehlerordngung p, falls fur seinen lokalenDiskretisierungsfehler dk die Abschatzung
maxm≤k≤N
|dk| ≤ K = O(hp+1)
gilt.
31
Allgemein kann man fur AB-Verfahren (m-Schritt)
yk+1 = yk +m−1∑
j=0
fk−j
∫ tk+1
tk
Lk−j(t)dt
bei ausreichender Glattheit der Losung y(t) zeigen, dass sie die Fehlerordnungm besitzen. Durch Auswertung der entsprechenden Integrale erhalt man furm = 2, 3, 4 die folgenden 3-,4- und 5- Schritt AB-Verfahren.
yk+1 = yk +h
12[23fk − 16fk−1 + 5fk−2] (2.45)
yk+1 = yk +h
24[55fk − 59fk−1 + 37fk−2 − 9fk−3]
yk+1 = yk +h
720[1901fk − 2774fk−1 + 2616fk−2 − 1274fk−3 + 251fk−4]
Die Formeln der Mehrschrittverfahren “funktionieren” erst ab dem Indexk = m, d.h. bei einem 3-Schrittverfahren braucht man die Werte y0, y1, y2
um y3 mit der Formel (2.45) berechnen zu konnen.Die Startwerte y1, y2 werden meist mit einem Runge-Kutta-Verfahren berech-net.Es ist offensichtlich moglich die Qualitat der Losungsverfahren fur das AWPzu erhohen, indem man das Integral
∫ tk+1
tk
f(t, y(t))dt
aus der Beziehung (2.42) genauer berechnet. Das kann man durch hinzu-nahme weiterer Stutzpunkte zur Polynominterpolation tun. Nimmt man den(noch unbekannten) Wert fk+1 = f(tk+1, yk+1) zu den Werten fk, . . . , fk−3
hinzu, dann erhalt man mit
p4(t) =3∑
j=−1
fk−jLk−j(t)
in Analogie zur Herleitung der AB-Verfahren mit
yk+1 = yk +
∫ tk+1
tk
3∑
j=−1
fk−jLk−j(t)dt = yk +3∑
j=−1
fk−j
∫ tk+1
tk
Lk−j(t)dt
bzw. nach Auswertung der Integrale
yk+1 = yk +h
720[251fk+1 + 646fk − 264fk−1 + 106fk−2 − 19fk−3] (2.46)
32
Das Verfahren (2.46) ist eine implizite 4-Schritt-Methode und heißt Methodevon Adams-Moulton (kurz AM-Verfahren). Das 3-Schritt AM-Verfahren hatdie Form
yk+1 = yk +h
24[9f(tk+1, yk+1) + 19fk − 5fk−1 + fk−2] (2.47)
Zur Bestimmung der Losung von (2.47) kann man z.B. eine Fixpunktiterationder Art
y(j+1)k+1 = yk +
h
24
[
9f(tk+1, y(j)k+1) + 19fk − 5fk−1 + fk−2
]
durchfuhren (Startwert z.B. y(0)k+1 = yk).
Bestimmt man den Startwert y(0)k+1 als Resultat eines 3-Schritt AB-Verfahrens
und fuhrt nur eine Fixpunktiteration durch, dann erhalt man das sogenanntePradiktor-Korrektor-Verfahren
y(p)k+1 = yk +
h
12[23fk − 16fk−1 + 5fk−2] (2.48)
yk+1 = yk +h
24[9f(tk+1, y
(p)k+1) + 19fk − 5fk−1 + fk−2] (2.49)
Diese Kombination von AB- und AM-Verfahren bezeichnet man als Adams-Bashforth-Moulton-Verfahren (kurz ABM-Verfahren). Das ABM-Verfahren(2.48) hat ebenso wie das AM-Verfahren (2.47) den Diskretisierungsfehlerdk+1 ∈ O(h5) und damit die Fehlerordnung 4.Generell kann man zeigen, dass m-Schritt-Verfahren von AM- oder ABM-Typ jeweils die Fehlerordnung p = m + 1 besitzen.
2.9 Allgemeine lineare Mehrschrittverfahren
Definition 2.17. Unter einem linearen m-Schrittverfahren (m > 1) verstehtman eine Vorschrift mit s = k − m + 1
m∑
j=0
ajys+j = h
m∑
j=0
bjf(ts+j, ys+j) (2.50)
wobei am 6= 0 ist und aj, bj geeignet zu wahlende reelle Zahlen sind. Die kon-krete Wahl dieser Koeffizienten entscheidet uber die Ordnung des Verfahrens.
Bemerkung. In den bisher behandelten Verfahren war jeweils am = 1 undam−1 = −1 sowie am−2 = · · · = a0 = 0. Bei expliziten Verfahren ist bm = 0und bei impliziten Verfahren ist bm 6= 0
33
OBdA setzen wir am = 1. Die anderen freien Parameter aj, bj sind so zuwahlen, dass die linke und die rechte Seite von (2.50) Approximationen von
α[y(tk+1) − y(tk)] bzw. α
∫ tk+1
tk
f(t, y(t))dt
sind (α 6= 0)Mit der Einfuhrung der Parameter a0, . . . , am hat man die Moglichkeit durchdie Nutzung der Werte yk+1−m, . . . , yk+1 nicht nur die Approximation von f ,sondern auch die Approximation von y′ mit einer hoheren Ordnung durch-zufuhren.
Beispiel. Das 3-Schritt-AB-Verfahren
yk+1 = yk +h
12[23fk − 16fk−1 + 5fk−2]
ist gleichbedeutend mit
yk+1 − yk
h=
1
12[23fk − 16fk−1 + 5fk−2]
wobei die rechte Seite eine Approximation von f(tk, y(tk)) der Ordnung O(h3)darstellt, wahrend die linke Seite y′ an der Stelle tk nur mit der Ordnung O(h)approximiert.Nutzt man neben yk+1 und yk auch noch yk−1, yk−2, dann kann man unterNutzung der Taylor-Approximationen
y(tk−2) = y(tk) − 2hy′ + 2h2y′′ − 3
2h3y′′′ + O(h4)
y(tk−1) = y(tk) − hy′ +1
2h2y′′ − 1
6h3y′′′ + O(h4)
y(tk+1) = y(tk) + hy′ +1
2h2y′′ − 1
6h3y′′′ + O(h4)
mit1
14h[5yk+1 + 6yk − 13yk−1 + 2yk−2]
die linke Seite y′ ebenfalls mit der Ordnung O(h3) approximieren.
Definition 2.18. Das lineare Mehrschrittverfahren (2.50) hat die Fehlerord-nung p, falls in der Entwicklung des lokalen Diskretisierungsfehlers dk+1 ineine Potenzreihe von h fur eine beliebige Stelle t ∈ [tk+1−m, tk+1]
dk+1 =m∑
j=0
[ajy(ts+j) − hbjf(ts+j, y(ts+j))] (2.51)
= c0y(t) + cyhy′(t) + . . . + cphpy(p)(t) + . . .
34
c0 = . . . = cp = 0 und cp+1 6= 0 gilt (s = k+1−m). Ein Mehrschrittverfahrenheißt konsistent, wenn es mindestens die Ordnung p = 1 besitzt.
Durch eine gunstige Wahl von t kann man die Entwicklungskoeffizienten cj
oft in einfacher Form als Linearkombination von aj, bj darstellen und erhaltmit der Bedingung c0 = . . . = cp = 0 Bestimmungsgleichungen fur die Koef-fizienten des Mehrschrittverfahrens.Mit der Wahl von t = ts ergeben sich fur y, y′ die Taylor-Reihen
y(ts+j) = y(t + jh) =
q∑
r=0
(jh)r
r!y(r)(t) + Rq+1
y′(ts+j) = y′(t + jh) =
q−1∑
r=0
(jh)r
r!y(r+1)(t) + Rq (2.52)
Die Substitution der Reihen (2.52) in (2.51) ergibt fur die Koeffizienten cj
durch Koeffizientenvergleich
c0 = a0 + a1 + . . . + am
c1 = a1 + 2a2 + . . . + mam − (b0 + b1 + . . . + bm)
c2 =1
2!(a1 + 22a2 + . . . + m2am) − 1
1!(b1 + 2b2 + . . . + mbm)
... (2.53)
cr =1
r!(a1 + 2ra2 + . . . + mram) − 1
(r − 1)!(2b1 + 2r−1b2 + . . . + mr−1bm)
fur r = 2, 3, . . . , q
Beispiel. Es soll ein explizites 2-Schritt-Verfahren (also b2 = 0)
a0yk−1 + a1yk + a2yk+1 = h[b0fk−1 + b1fk] (2.54)
der Ordnung 2 bestimmt werden. Mit der Fixierung von a2 = 1 ergibt sichmit
c0 = a0 + a1 + 1 = 0
c1 = a1 + 2 − (b0 + b1) = 0
c2 =1
2(a1 + 4) − b1 = 0
ein Gleichungssystem mit 3 Gleichungen fur 4 Unbekannte zur Verfufgung,d.h. es gibt noch einen Freiheitsgrad.
35
Wahlt man a1 = 0, dann folgt fur die restlichen Parameter a0 = −1, b0 = 0und b1 = 2, sodass das Verfahren die Form
yk+1 = yk−1 + 2hfk (2.55)
hat.
Definition 2.19. Mit den Koeffizienten aj, bj werden durch
ρ(z) =m∑
j=0
ajzj, σ(z) =
m∑
j=0
bjzj (2.56)
das erste und zweite charakteristische Polynom eines m-Schritt-Verfahrenserklart.
Aus dem Gleichungssystem (2.53) kann man mit Hilfe der charakteristischenPolynome die folgende notwendige und hinreichende Bedingung fur die Kon-sistenz eines Mehrschrittverfahrens formulieren.
Satz 2.20. Notwendig und hinreichend fur die Konsistenz des Mehrschritt-verfahrens (2.50) ist die Erfullung der Bedingungen
c0 = ρ(1) = 0, c1 = ρ′(1) − σ(1) = 0 (2.57)
Macht man außer der Wahl von a2 = 1 keine weiteren Einschrankungenan die Koeffizienten des expliziten 2-Schritt-Verfahrens (2.54), dann erreichtman die maximale Ordnung p = 3 durch die Losung des Gleichungssystem(2.53) fur q = 3, also c0 = c1 = c2 = c3 = 0.Man findet die eindeutige Losung
a0 = −5, a1 = 4, b0 = 2, b1 = 4
woraus das Verfahren
yk+1 = 5yk−1 − 4yk + h[4fk + 2fk−1] (2.58)
folgt.Obwohl das Verfahren (2.58) die maximale Fehlerordnung p = 3 hat, ist esim Vergleich zum Verfahren (2.55) unbrauchbar, weil es nicht stabil ist. Wasdas konkret bedeutet, soll im Folgenden erklart und untersucht werden.Dazu wird die Testdifferentialgleichung (AWP)
y′ = λy, y(0) = 1, λ ∈ R, λ < 0 (2.59)
36
mit der eindeutig bestimmten Losung y(t) = eλt betrachtet.Von einem brauchbaren numerischen Verfahren erwartet man mindestens dieWiderspiegelung des qualitativen Losungsverhaltens.Mit f = λy folgt aus (2.58)
yk+1 = 5yk−1 − 4yk + h[4λyk + 2λyk−1]
⇔ (−5 − 2λh)yk−1 + (4 − 4λh)yk + yk+1 = 0 (2.60)
Mit dem Losungsansatz yk = zk, z 6= 0 ergibt (2.60) nach Division mit zk−1
(−5 − 2λh) + (4 − 4λh)z + z2 = 0
bzw. mit dem charakteristischen Polynomen
ρ(z) = −5 + 4z + z2, σ = 2 + 4z, φ(z) = ρ(z) − λhσ(z) = 0
Als Nullstellen von φ findet man
z1,2 = −2 + 2λh ±√
(2 − 2λh)2 + 5 + 2λh
und damit fur die Losung yk von (2.60)
yk = c1zk1 + c2z
k2 (2.61)
wobei die Konstanten c1, c2 aus Anfangsbedingungen der Form c1 + c2 =y0, z1c1 + z2c2 = y1 zu ermitteln sind.Notwendig fur das Abklingen der Losung yk in der Formel (2.61) fur wach-sendes k ist die Bedingung |z1,2| ≤ 1. Da fur h → 0 die Nullstellen vonφ(z) in die Nullstellen von ρ(z) ubergehen, durfen diese dem Betrage nachnicht großer als 1 sein. Im Fall einer doppelten Nullstelle z von φ(z) eines2-Schritt-Verfahrens hat die Losung der entsprechenden DGL statt (2.61) dieForm
yk = c1zk + c2kzk
sodass fur das Abklingen von yk fur wachsendes k die Bedingung |z| < 1erfullt sein muss. Die durchgefuhren Uberlegungen rechtfertigen die folgendeDefinition.
Definition 2.21. Das Mehrschrittverfahren (2.50) heißt nullstabil, falls dieNullstellen zj des ersten charakteristischen Polynoms ρ(t)
(a) betragsmaßig nicht großer als 1 sind
(b) mehrfache Nulstellen betragsmaßig echt kleiner als 1 sind
37
Fur das oben konstruierte 2-Schritt-Verfahren mit der maximalen Fehlerord-nung p = 3 hat das charakteristische Polyno ρ(t) die Nullstellen z1,2 = −2±3und damit ist das Verfahren nicht nullstabil.Im Unterschied dazu ist das Verfahren (2.55) mit der Ordnung 2 und demcharakteristischen Polynom ρ(z) = −1 + z2 und den Nullstellen z12 = ±1nullstabil.
Bemerkung. Einschrittverfahren sind mit dem charakteristischen Polynomρ(z) = −1 + z generell nullstabil.Aufgrund der ersten charakteristischen Polynome der Adams-Bashforth- undAdams-Moulton-Verfahren erkennt man, dass diese auch generell nullstabilsind.
Bemerkung. Konsistente und nullstabile Mehrschrittverfahren sind konver-gent, falls die Funktion f(t, y) bezuglich y lipschitzstetig ist.Der Beweis verlauft im Fall expliziter Mehrschrittverfahren analog zum Kon-vergenzbeweis fur konsistente Einschrittverfahren und sollte als Ubung er-bracht werden.
38
Kapitel 3
Interpolation
6. Vor-lesung29.04.2010
Oft gibt es die Aufgabe, durch gegebene Punktepaare eine glatte Kurve zulegen, die analytisch leicht zu handhaben ist (Differenzieren, Integrieren),also:Gegeben: (xk, yk), k = 0, . . . , N gegeben.Gesucht: Glatte Funktion P = P (x) mit
P (xk) = yk, k = 0, . . . , N
Mogliche Ansatze fur P
(i) Polynome
P = P (x, a0, a1, . . . , an) = a0 + a1x + · · · + anxn, n = N
(ii) Rationale Funktionen
P (x) =a0 + a1x + · · · + anxn
an+1 + an+2x + · · · + an+m+1xm, n = N
(iii) Trigonometrische Polynome, yi ∈ C
P (x) = a0 + a1eix + a2e
2ix + · · · + anenix
= a0 + a1eix + a2(e
ix)2 + · · · + an(eix)n
(iv) Splines (stuckweise Polynome)
39
Ziel/Aufgabe der Interpolation
Bestimmung der Parameter a0, . . . , an, so dass fur P = P (x, a0, . . . , an) auseiner vorzugebenden Funktionenklasse die Beziehungen
P (xk, a0, . . . , an) = yk, k = 0, . . . , n (3.1)
zu den vorgegebenen Stutzstellen (xk, yk) erfullt sind. (3.1) heißt auch Inter-polationseigenschaft und die Stutzstellen werden auch Knoten genannt.(3.1) sind n + 1 Gleichungen fur die n + 1 Parameter a0, . . . , an.Sehr einfach: Lineare Splines
3.1 Polynominterpolation
Definition 3.1. Unter Πn versteht man die Menge aller reellen PolynomeP : R → R von Grad ≤ n
Wir wissen:
• im Fall n = 1 braucht man 2 Stutzpunkte um eine Gerade (Polynomersten Grades) durchzulegen
• im Fall n = 2 braucht man 3 Stutzpunkte um eine Parabel (Polynomzweiten Grades) durchzulegen, ...
Satz 3.2. Zu n + 1 gegebenen Stutzstellen (xk, yk), k = 0, . . . , n mit derEigenschaft xi 6= xj, i 6= j, gibt es genau ein Polynom p ∈ Πn mit P (xk) =yk, k = 0, 1, . . . , n
Beweis. Ansatz:
P (x) = a0 + a1x + · · · + anxn
P (xk) = yk, k = 0, 1, . . . , n (3.2)
bedeutet
a0 + a1x0 + · · · + anxn0 = y0
...a0 + a1xn + · · · + anx
nn = yn
⇔
1 x0 x20 · · · xn
0
1 x1 x21 · · · xn
1...
1 x2 x22 · · · xn
n
︸ ︷︷ ︸
Vandermondesche Matrix V
a0
a1...
an
=
y0
y1...
yn
(3.3)
40
V ist fur paarweise verschiedene xk regular, d.h. a0, . . . , an und damit P sindeindeutig bestimmt.
Definition 3.3. Das nach Satz 3.2 eindeutig bestimmte Polynom P mit derEigenschaft
P (xk) = yk, k = 0, 1, . . . , n
fur die vorgegebenen Stutzstellen (xk, yk) heißt Interpolationspolynom.
3.1.1 Konstruktion des Interpolationspolynoms
Wir erinnern uns an die Generalvoraussetzung
xi 6= xj ∀i, j = 0, 1, . . . , n, i 6= j
Definition 3.4. Die Polynome
Lk(x) =n∏
k 6=i=0
x − xi
xk − xi
(3.4)
heißen Lagrange-Basispolynome.
Definition 3.5. Die Polynome
Nk(x) =k−1∏
i=0
(x − xi), k = 1, . . . , n
mit N0(x) = 1 heißen Newton-Basispolynome.
Satz 3.6. Die Monombasis1, x, . . . , xn
sowie die Lagrange-Basispolynome
Lk(x), k = 0, . . . , n
und die Newton-Basispolynome
Nk(x), k = 0, . . . , n
sind Basen (linear unabhangige erzeugende Funktionensysteme) des Vektor-raums der reellen Polynome Πn vom Grad ≤ n
Beweis. Als Ubung empfohlen.
41
3.2 Lagrange-Interpolation
Zuerst ist anzumerken, dass man das Interpolationspolynom nicht in derForm (3.2) auf der Grundlage der Losung des Gleichungssystems (3.3) mitder Vandermondeschen Matrix bestimmt, weil das viel zu aufwandig ist.Besser geht es mit der Lagrange-Interpolation.Fur n = 3 haben wir zum Beispiel die Basispolynome
L0(x) =(x − x1)(x − x2)(x − x3)
(x0 − x1)(x0 − x2)(x0 − x3)
L1(x) =(x − x0)(x − x2)(x − x3)
(x1 − x0)(x1 − x2)(x1 − x3)
L0(x) =(x − x0)(x − x1)(x − x3)
(x2 − x0)(x2 − x1)(x2 − x3)
L0(x) =(x − x0)(x − x1)(x − x2)
(x3 − x0)(x3 − x1)(x3 − x2)
und erkennen:
L0(x0) = 1, L0(x1) = L0(x2) = L0(x3) = 0
allgemein gilt:Lk(xj) = δkj, k = 0, . . . , n (3.5)
Damit ergibt sich fur das Interpolationspolynom:
p(x) =n∑
k=0
ykLk(x) (3.6)
dap(xk) = 0 + 0 + · · · + ykLk(xk) + · · · + 0 = yk
gilt. (3.6) heißt Lagrangsches Interpolationspolynom.
3.3 Newton-Interpolation
Bei der Lagrange-Interpolation haben wir das Interpolationspolynom in derLagrange-Basis entwickelt. Bei der Newton-Interpolation wird das eindeutigexistierende Interpolationspolynom in der Newton-Basis entwickelt.Ansatz:
p(x) =n∑
k=0
ckNk(x)
42
Durch sukzessives Vorgehen erhalten wir durch Berucksichtigung der Stutzstellen(xk, yk), k = 0, . . . , n die Koeffizienten der Nk(x)
pn(x0) = c0 = y0 Ã c0
pn(x1) = c0 + c1(x1 − x0) = y1 Ã c1
pn(x2) = c0 + c1(x1 − x0) + c2(x2 − x0)(x2 − x1) = y2 Ã c2
...
pn(xn) =n∑
k=0
ckNk(xn) = yn à cn
Definition 3.7.
pn(x) :=n∑
k=0
ckNk(x) ∈ Πn
heißt Newtonsches Interpolationspolynom.
Bemerkung. cn ist der Koeffizient von xn im Interpolationspolynom undck ist eindeutig festgelegt durch x0, . . . , xk, y0, . . . yk d.h. durch die ersten k
Stutzstellen.
Definition 3.8. Wir schreiben cj := [x0x1 . . . xk] fur die Abbildung
{(x0, y0), . . . , (xk, yk)} 7→ ck
Mit anderen Worten:Durch die Stutzwerte {(x0, y0), . . . , (xk, yk)} ist der Koeffizient ck eindeutigfestgelegt und man findet durch die Losung des obigen Gleichungssystemsfur die Koeffizienten
ck = [x0x1 . . . xk]
die rekursive Berechnungsformeln
[xj] = yj , j = 0, . . . , n,
[xi0xi1 . . . xk] =[xi0xi1 . . . xk−1] − [xi1 . . . xk]
xi0 − xk
,
wobei i0, . . . , ik paarweise verschiedene Zahlen aus {0, . . . , k} sind.
Hier sei darauf hingewiesen, dass man statt der Bezeichnung
[xi0xi1 . . . xk] auch die Notation f [xi0xi1 . . . xk]
verwendet, was speziell dann instruktiv ist, wenn es sich bei den y-Wertenum Funktionswerte handelt, also durch yj = f(xj) mittels einer gegebenenFunktion berechnet werden.
43
Als Folgerung der bisherigen Uberlegungen findet man das folgende Schema
k = 0 k = 1 k = 2x0 y0 = f [x0]
x1 y1 = f [x1] f [x0x1] = f [x1]−f [x0]x1−x0
x2 y2 = f [x2] f [x1x2] = f [x2]−f [x1]x2−x1
f [x0x1x2] = f [x1x2]−f [x1x0]x2−x0
...
Es wird “Schema der dividierten Differenzen” genannt. Daraus liest man dasNewtonsche Interpolationspolynom ab:
p2(x) = f [x0] + f [x0x1](x − x0) + f [x0x1x2](x − x0)(x − x1)
3.4 Algorithmische Aspekte der Polynomin-
terpolation
3.4.1 Horner-Schema
Fur die Berechnung eines Polynoms in der Form
p(x) = a0 + a1x + a2x2 + · · · + anx
n
Werden 1+2+ · · ·+n = n(n+1)2
Multiplikationen und n Additionen benotigt.Also O(n2) flops
p(x) = a0 +x(a1 +x(a2 + · · · )) = (· · · (anx+an−1)x+an−2)x+ · · ·+a1)x+a0
à n Multiplikationen und Additionen, also 2n ∈ O(n) flops.
Fur die Newton Basis ergibt sich
p(x) =n∑
k=0
ckNk(x), ck gegeben
Nk rekursiv aufgebaut:
Nk(x) = (x − x0) · · · (x − xk)
à Nk(x) = (x − xk−1)Nk−1(x)
p kann in der Form
p(x) = c0 + (x − x0)(c1 + (x − x1)(c2 + · · · + cn(x − xn−1)) · · · )
geschrieben werden. Daraus resultiert der Algorithmus:
44
Algorithmus 1 Wertet Newton Polynom mittels Horner-Schema ausun+1 = 0for k = n downto 0 do
uk = (x − xk)uk+1 + ck
end forp(x) = u0
Mit Laufzeit 3n flops.
3.5 Fehlerabschatzung der Polynominterpo-
lation
Handelt es sich bei den Stutzpunkten (xk, yk) nicht um diskrete Messwerte,sondern um die Wertetabelle einer gegebenen Funktion f(x), dann ist derFehler f(x) − pn(x), den man bei der Interpolation macht, von Interesse.Nimmt man zu den Stutzwerten x0, . . . , xn den Wert x = xn+1 hinzu, ergibtdie Interpolationsbedingung y = f(x) = pn+1(x)
pn+1(x) = f(x)︸ ︷︷ ︸
pn+1(xn+1)=yn+1
= pn(x) + f [x0, x1, . . . , xn, x]n∏
k=0
(x − xk)
bzw.
f(x) − pn(x) = f [x0, x1, . . . , xn, x](x − x0)(x − x1) · · · (x − xn) (3.7)
Der folgende Satz liefert die Grundlage fur die Abschatzung des Interpolati-onsfehlers (3.7).
Satz 3.9. Sei ]a, b[ = ] min0≤j≤n xj, max0≤j≤n xj[ und sei pn(x) das Interpola-tionspolynom zur Wertetabelle (xk, f(xk)) der (n+1)-mal stetig differenzier-baren Funktion f auf [a, b], wobei die Stutstellen xk paarweise verschiedensind.Dann gibt es fur jedes x ∈]a, b[ einen Zwischenwert ξ = ξ(x0, . . . , xn) ∈]a, b[mit
f(x) − pn(x) =f (n+1)(ξ)
(n + 1)!(x − x0) · · · (x − xn)
Beweis. Siehe Barwolff
45
Aus dem Satz 3.9 folgt direkt fur eine (n + 1)-mal stetig differenzierbareFunktion die Fehlerabschatzung
|f(x) − pn(x)| ≤ maxξ∈[a,b]
∣∣f (n+1)(ξ)
∣∣
(n + 1)!
∣∣∣∣∣
n∏
k=0
(x − xk)
∣∣∣∣∣
︸ ︷︷ ︸
=:w(x)
(3.8)
Hat man bei den Stutzstellen die freie Wahl und soll auf dem Intervall [a, b]interpoliert werden, dann ist die Wahl der Nullstellen des Tschebyscheff-Polynoms Tn+1(x) auf [a, b] transformiert, d.h
x∗k =
a + b
2+
b − a
2cos
(2(n + 1 − k) − 1
2(n + 1)π
)
, k = 0, . . . , n (3.9)
von Vorteil, denn fur w∗(x) =∏n
k=0(x − x∗k) gilt:
Satz 3.10. Seien xk aquidistante und x∗k gemaß (3.9) verteilte Stutzstellen
des Intervalls [a, b]. Dann gilt:
maxx∈[a,b]
|w∗(x)| ≤ maxx∈[a,b]
|w(x)|
und falls f beliebig oft differenzierbar ist, gilt
limk→∞
p∗k(x) = f(x) auf [a, b]
46
3.6 Spline-Interpolation7. Vor-lesungam5.5.10
Problem bei der Polynom-Interpolation:Eventuell große Oszillationen durch Polynome hoheren Grades bei Stutz-punktzahlen ≥ 10Deshalb:Statt eines Interpolationspolynoms konstruiert man fur (xk, yk), k = 0, 1, . . . , nin jeden Teilintervall einzelne Polynome, die an den Randstellen glatt inein-ander ubergehen. Betrachten mit
∆ = {a = x0 < x1 < . . . < xN = b}
eine fest gewahlte Zerlegung von [a, b], wobei die Stutzstellen x0, . . . , xN auchals Knoten bezeichnet werden.
Definition 3.11. Eine Splinefunktion der Ordnung l ∈ N zur Zerlegung ∆ist eine Funktion s ∈ C l−1[a, b], die auf jedem Intervall [xk−1, xk] mit einemPolynom l-ten Grades ubereinstimmt. Der Raum der Splinefunktionen wirdmit S∆,l bezeichnet, es gilt also:
S∆,l = {s ∈ C l−1[a, b] : s|[xk−1,xk] = pk|[xk−1,xk] fur ein pk ∈ Πl}
Anstelle Splinefunktionen verwendet man auch einfach Spline.
Splines erster Ordnung nennt man auch lineare, die zweiter Ordnung auchquadratische Splines. Besonders hervorzuheben sind kubische Splines, die inder Praxis besonders haufig verwendet werden.
Da wir vorgegebene Wertetabellen interpolieren wollen, geht es im Folgendenum die Berechnung interpolierender Splinefunktionen, also Splines mit derEigenschaft
s(xk) = fk fur k = 0, 1, . . . , N (3.10)
fur (xk, fk), k = 0, 1, . . . , N
3.6.1 Interpolierende lineare Splines s ∈ S∆,1
Offensichtlich gilt:
s(x) = ak + bk(x − xk), x ∈ [xk, xk+1]
aus sk(xk) = fk sowie sk(xk+1) = fk+1 folgt
ak = fk, bk =fk+1 − fk
xk+1 − xk
, k = 0, . . . , N − 1
47
Satz 3.12.
(a) Zur Zerlegung ∆ = a = x0 < . . . < xN = b und f0, . . . , fN gibt es genaueinen Spline s ∈ S∆,1 mit der Eigenschaft (3.10)
(b) Zu einer Funktion f ∈ C2[a, b] sei s ∈ S∆,1 der zugehorige interpolierendelineare Spline. Dann gilt
‖s − f‖∞ ≤ 1
8‖f ′′‖∞ h2
max
mit hmax := maxk=0,...,N−1(xk+1 − xk)
Beweis. (a) nach Konstruktion
(b) Fur jedes k ∈ 1, . . . , N stimmt s auf [xk−1, xk] mit demjenigen p ∈ Π1
uberein, fur das p(xk−1) = f(xk−1) und p(xk) = f(xk) gilt. Der Fehlerbei der Polynominterpolation (Satz 3.9) liefert
|s(x) − f(x)| ≤ (x − xk−1)(xk − x)
2max
ξ∈[xk−1,xk]|f ′′(ξ)|
≤ 1
8h2
max ‖f ′′‖∞ , x ∈ [xk−1, xk]
3.6.2 Kubische Splines
Betrachte nun S∆,3, und verwenden
‖u‖2 :=
(∫ b
a
|u(x)|2 dx
) 1
2
Satz 3.13. Gegeben sei f ∈ C2[a, b] und ein kubischer Spline s ∈ S∆,3 mits(xk) = f(xk), k = 0, . . . , N . Dann gilt die Identitat
‖f ′′‖22 − ‖s′′‖2
2 = ‖f ′′ − s′′‖22 (3.11)
sofern eine der 3 folgenden Bedingungen erfullt ist
(a) s′′(a) = s′′(b) = 0
(b) s′(a) = f ′(a), s′(b) = f ′(a)
(c) f ′(a) = f ′(b), s′(a) = s′(b), s′′(a) = s′′(b)
48
Korollar 3.1. Zu gegebenen Werten f0, . . . , fN ∈ R hat ein interpolierenderkubischer Spline s ∈ S∆,3 mit s′′(a) = s′′(b) = 0 unter allen hinreichendglatten interpolierenden Funktionen die geringste Krummung, es gilt also
‖s′′‖2 ≤ ‖f ′′‖2
fur jede Funktion f ∈ C2[a, b] mit f(xk) = fk fur k = 0, . . . , N
Beweis. Folgt direkt aus (3.11)
3.6.3 Berechnung interpolierender kubischer Splines
Lokaler Ansatz
s(x) = ak + bk(x − xk) + ck(x − xk)2 + dk(x − xk)
3,
x ∈ [xk, xk+1], k = 0, . . . , N − 1(3.12)
fur s : [a, b] → R
Aufgabe: Bestimmung von ak, . . . , dk, k = 0, . . . , N − 1 so, dass s auf [a, b]zweimal stetig differenzierbar ist und daruberhinaus in den Knoten vorgege-bene Werte f0, . . . , fN ∈ R interpoliert
s(xk) = fk, k = 0, . . . , N
Setzen hk := xk+1 − xk, k = 0, . . . , N
Lemma 3.14. Falls N +1 reelle Zahlen s′′0, . . . , s′′N ∈ R den folgenden N − 1
gekoppelten Gleichungen (k = 1, . . . , N − 1)
hk−1 s′′k−1︸︷︷︸
mk−1
+2(hk−1 + hk) s′′k︸︷︷︸
mk
+hk s′′k+1︸︷︷︸
mk+1
= 6fk+1 − fk
hk
− 6fk − fk−1
hk−1︸ ︷︷ ︸
gk
(3.13)
genugen, so liefert der lokale Ansatz (3.12) mit den Setzungen
ck =mk
2, ak = fk, dk =
mk+1 − mk
6hk
, bk =fk+1 − fk
hk
− hk
6(mk+1 +2mk)
fur k = 0, . . . , N − 1 eine kubische Splinefunktion s ∈ S∆,3, die die Interpo-lationsbedingung s(xk) = fk erfullt.
Beweis. Vorlesung oder Plato, Barwolff
49
Bemerkung. Die Momente m0, . . . ,mN stimmen mit den 2. Ableitungender Splinefunktion s in den Knoten xk uberein
s′′k = mk = s′′(xk), k = 0, . . . , N
(3.13) bedeutet: Es liegen N − 1 Bedingungen fur N + 1 Momente vor, d.h.es gibt 2 Freiheitsgrade. Diese werden durch die folgenden Randbedingungenfestgelegt:
• Naturliche RB s′′0 = s′′N = 0
• Vollstandige RB s′0 = f ′0, s′N = f ′
N fur geg. f ′0, f
′N ∈ R
• Periodische RB s′0 = s′N , s′′0 = s′′N
(diese Festlegungen korrellieren mit den Bedinungen (a), (b), (c) des Satzes3.13)
3.6.4 Gestalt der Gleichungssysteme
Naturliche Randbedingunden
2(h0 + h1) h1 0
h1 2(h1 + h2). . .
. . . hN−2
0 hN−2 2(hN−2 + hN−1)
m1
mN−1
=
g1
...
gN−1
(3.14)
vollstandige Randbedingungen
2h0 h0 0
h0 2(h0 + h1). . .
. . . 2(hN−2 + hN−1) hN−1
0 hN−1 2hN−1
m0
mN
=
g0
...
gN
(3.15)
50
periodische Randbedingungen
2(hN−1 + h0) h0 hN−1
h0 2(h0 + h1). . .
. . . hN−2
hN−1 hN−2 2(hN−2 + hN−1)
m0
mN−1
=
g0
...
gN−1
(3.16)
3.7 Existenz und Eindeutigkeit der betrach-
teten interpolierenden kubischen Splines
Alle Koeffizientenmatrizen der Gleichungssysteme zur Berechnung der Mo-mente Mk = s′′k haben die Eigenschaft, strikt diagonal dominant zu sein, eineEigenschaft, die wie folgt definiert ist
Definition 3.15. Eine Matrix A = (aij) ∈ RN×N heißt strikt diagonal
dominant, falls
N∑
k 6=j=1
|akj| < |akk| , k = 1, . . . , N (3.17)
Lemma 3.16. Jede strikt diagonal dominante Matrix A = (akj) ∈ RN×N ist
reguar und es gilt
‖x‖∞ ≤ maxk=1,...,N
{
(|akk| −n∑
k 6=j=1
|akj|)−1
}
‖Ax‖∞ , x ∈ Rn (3.18)
Beweis. Fur x ∈ RN sei der Index x ∈ {1, . . . , N} so gewahlt, dass |xk| =
‖x‖∞ gilt. Dann findet man
‖Ax‖∞ ≥ |(Ax)k| =
∣∣∣∣∣
N∑
j=1
akjxj
∣∣∣∣∣≥ |akk| |xk| −
N∑
k 6=j=1
|akj| |xj|
≥ |akk| |xk| −N∑
k 6=j=1
|akj| ‖x‖∞ =
(
|akk| −N∑
k 6=j=1
|akj|)
‖x‖∞
⇔ ‖x‖∞ ≤(
|akk| −N∑
k 6=j=1
|akj|)−1
‖Ax‖∞
Die liefert die Gultigkeit von (3.18) woraus die Regularitat von A direkt folgt.(Aus Ax = 0 folgt x = 0 als einzige Losung)
51
Korollar 3.2. Zur Zerlegung ∆ und den Werten f0, . . . , fN ∈ R gibt es je-weils genau einen interpolierenden kubischen Spline mit den oben diskutiertenRandbedingunen.
Beweis. Die jeweiligen Koeffizientenmatrizen sind strikt diagonal dominantà s′′k eindeutig à Existenz und Eindeutigkeit der kubischen Splines.
3.8 Fehlerabschatzungen fur interpolierende
kubische Splines
Zuerst schreiben wir die Gleichungen (3.13) fur die Momente durch die je-weilige Division durch 3(hk−1 + hk) in der Form
hk−1
3(hk−1 + hk)s′′k−1 +
2
3s′′k +
hk
3(hk−1 + hk)s′′k+1
= 2fk+1 − fk
hk(hk−1 + hk)− 2
fk − fk−1
hk−1(hk−1 + hk)=: gk
auf, was fur naturliche Randbedingungen auf das Gleichungssystem
B :=
23
h1
3(h0+h1)0
h1
3(h1+h2)23
h2
3(h1+h2)
. . . . . . . . .hN−3
3(hN−3+hN−2)23
hN−2
3(hN−3+hN−2)
0 hN−2
3(hN−2+hN−1)23
B
s′′1
...
s′′N−1
=
g1
...
gN−1
(3.19)
fuhrt (hk = xk+1 − xk)Der folgende Satz liefert eine Fehlerabschatzung der Spline-Interpolation:
Satz 3.17. Sei f ∈ C4[a, b] und sei s ∈ S∆,3 ein interpolierender kubischerSpline. Weiter bezeichne hk = xk+1 − xk fur k = 0, . . . , N − 1 und
hmax = maxk=0,...,N−1
hk, hmin = mink=0,...,N−1
hk ,
52
so gelten mit der Zahl c := hmax
hminund M4 =
∥∥f (4)
∥∥∞ die folgenden Abschatzungen
fur jedes x ∈ [a, b]
|s(x) − f(x)| ≤ cM4h4max (3.20)
|s′(x) − f ′(x)| ≤ cM4h3max (3.21)
|s′′(x) − f ′′(x)| ≤ cM4h2max (3.22)
∣∣s(3)(x) − f (3)(x)
∣∣ ≤ cM4hmax (3.23)
Beweis. Plato
53
Kapitel 4
Numerische Integration
8. Vor-lesungam06.05.2010
Ziel ist die Berechnung des bestimmten Integrals
∫ b
a
f(x)dx
wobei man aus unterschiedlichen Grunden nicht die Berechnung mittels einerStammfunktion F (x) durch
∫ b
a
f(x)dx = F (b) − F (a)
nutzen kann oder will. Entweder findet man kein auswertbares F (x) wie imFall von f(x) = ex
xoder f(x) = e−x2
oder die Berechnung von F (b), F (a) istzu muhselig.
4.1 Numerischen Integration mit Newton-Cotes-
Formeln
• Aquidistante Unterteilung von [a, b]
xk = a + kh, k = 0, ..., n, h =b − a
n
• Verwendung des Interpolationspolynoms pn ∈ Πn fur die Stutzpunkte(xk, f(xk)), d.h. es ist
pn(xk) = f(xk), k = 0, ..., n
54
• Naherung des Integrals∫ b
af(x)dx durch
∫ b
a
pn(x)dx ≈∫ b
a
f(x)dx
Mit dem Lagrangschen Interpolationspolynom
pn(x) =n∑
k=0
fkLk(x), fk = f(xk)
erhalt man
∫ b
a
pn(x)dx =n∑
k=0
fk
∫ b
a
Lkdx
=n∑
k=0
fk
∫ b
a
n∏
k 6=j=0
x − xj
xk − xj
dx = (∗)
und mit der Substitution s = x−ah
, hds = dx folgt
(∗) = (b − a)n∑
k=0
fk
1
n
∫ n
0
n∏
k 6=j=0
s − j
k − jds
︸ ︷︷ ︸
σk
also∫ b
a
pn(x)dx = (b − a)n∑
k=0
fkσk (4.1)
mit den Gewichten
σk =1
n
∫ n
0
n∏
k 6=j=0
s − j
k − jds, k = 0, . . . , n (4.2)
Fur n = 1 erhalt man
σ0 =
∫ 1
0
s − 1
0 − 1ds = −1
2(s − 1)2
∣∣∣∣
1
0
=1
2, σ1 =
1
2
woraus mit
∫ b
a
f(x)dx ≈∫ b
a
p1(x)dx =b − a
2(f(a) + f(b)) (4.3)
55
die Trapezregel folgt.Fur n = 2 ergibt sich
σ0 =1
2
∫ 2
0
s − 1
0 − 1· s − 2
0 − 2=
1
4
∫ 2
0
(s2 − 3s + 2)ds
=1
4
[s3
3− 3s2
2+ 2s
]
=1
4
[8
3− 6 + 4
]
=1
4
[8 − 6
3
]
=1
6
σ2 =1
6, σ1 =
4
6
woraus mit∫ b
a
f(x)dx ≈∫ b
a
p2(x)dx =b − a
6
(
f(a) + 4f
(a + b
2
)
+ f(b)
)
(4.4)
Die Simpson-Regel, auch Keplersche Fassregel genannt, folgt.Fur n = 3 findet man auf analoge Weise mit
∫ b
a
f(x)dx ≈∫ b
a
p3(x)dx
=b − a
8
(
f(a) + 3f
(2a + b
3
)
+ 3f
(a + 2b
3
)
+ f(b)
)
(4.5)
die Newtonsche 38-Regel.
Definition 4.1. Die Naherungsformel
Qn(x) =
∫ b
a
pn(x)dx = (b − a)n∑
k=0
f(xk)σk (4.6)
zu den Stutzstellen x0, . . . , xn fur das Integral∫ b
af(x)dx nennt man inter-
polatorische Quadraturformel.Gilt fur die Stutzstellen xk = a+kh, h = b−a
n, k = 0, . . . , n spricht man bei der
Quadraturformel von einer abgeschlossenen Newton-Cotes-Quadraturformel.
Definition 4.2. Mit
En[f ] =
∫ b
a
f(x)dx − Qn = I − Qn (4.7)
bezeichnet man den Fehler der Quadraturformel Qn. Eine Quadraturformelhat den Genauigkeitsgrad m ∈ N, wenn sie alle Polynome p(x) bis zum Gradm exakt integriert, d.h. En[p] = 0 ist, und m die großtmogliche Zahl mitdieser Eigenschaft ist.
Es gilt offensichtlich der folgende
56
Satz 4.3. Zu den n+1 beliebig vorgegebenen paarweise verschiedenen Stutzstellena ≤ x0 < · · · < xn ≤ b existiert eine eindeutig bestimmte interpolatorischeQuadraturformel deren Genauigkeitsgrad mindestens gleich n ist.
Fur die Simpsonregel findet man
E2[x3] =
∫ b
a
x3dx − b − a
6
[
a3 + 4
(a + b
2
)3
+ b3
]
=1
4(b4 − a4) − b − a
6
[
a3 +1
2(a3 + 3a2b + 3ab2 + b3) + b3
]
= 0
undE2[x
4] 6= 0
Aufgrund der Additivitat und Homogenitat des Quadraturfehlers, d.h.
En[αf + βg] = αEn[f ] + βEn[g],
ist die Simpsonregel fur alle Polynome 3. Grades exakt, allerdings nicht mehrfur Polynome 4. Grades. Damit hat sie den Genauigkeitsgrad 3 obwohl ihrnur ein Interpolationspolynom vom Grad 2 zugrunde liegt.Generell findet man, dass die abgeschlossenen Newton-Cotes Quadraturfor-meln Qn fur gerades n den Genauigkeitsgrad n + 1 haben.Setzt man bei der zu integrierenden Funktion f die (n+1)- bzw. (n+2)-maligestetige Differenzierbarkeit voraus, dann gilt fur Fehler der ersten Newton-Cotes-Quadraturformeln
E1[f ] = − 1
12h3f ′′(η), h = b − a
E2[f ] = − 1
90h5f (4)(η), h =
b − a
2
E3[f ] = − 3
80h5f (4)(η), h =
b − a
3
E4[f ] = − 8
945h7f (6)(η), h =
b − a
4
wobei η ∈ [a, b] jeweils ein geeigneter Zwischenwert ist.
4.2 Summierte abgeschlossene Newton-Cotes-
Quadraturformeln
Trapezregel (Q1) und Simpsonregel (Q2) bedeutet also die Integration von
p1 bzw. p2 zur naherungsweisen Berechnung on I =∫ b
af(x)dx. Bei der Inter-
57
polation haben wir die Erfahrung gemacht, dass Polynome hoheren Gradeszu Oszillationen an den Intervallrandern neigen. Man stellt auch fest, dassab n = 8 negative Gewichte σk auftreten.Um die Genauigkeit zu erhohen, verzichtet man auf die Vergroßerung von n
und wendet stattdessen z.B. die Trapez- oder Simpson-regel auf N Teilinter-vallen an.Zur naherungsweisen Berechnung von
∫ β
αf(x)dx unterteilt man das Intervall
[α, β] durch
α = x10 < . . . < x1n = x20 < . . . < xN−1n = xN0 < . . . < xNn = β
in N gleichgroße Teilintervalle [xj0, xjn], j = 1, . . . , N mit jeweils n + 1Stutzstellen. Auf den Teilintervallen [a, b] = [xj0, xjn] nahert man das Integral
∫ xjn
xj0
f(x)dx mit Qn,j
zu den Stutzstellen xj0, . . . , xjn an. Die Summation uber j ergibt mit
Sn,N =N∑
j=1
Qn,j
die sogenannten summierten abgeschlossenen Newton-Cotes- Formeln.Mit yjk = f(xjk) erhalt man fur n = 1 die summierte Trapez- Regel (h =β−α
n)
S1,N = h
[1
2y10 + y20 + · · · + yN0 +
1
2yN1
]
= h
[
1
2(y10 + yN1) +
N∑
k=2
yk0
]
(4.8)
und fur n = 2 die aufsummierte Simpson-Regel (h = β−α
2N)
S2,N =h
3
[
(y10 + yN2) + 2N−1∑
j=1
yj2 + 4N∑
j=1
yj1
]
(4.9)
Fur die Quadraturfehler summierter abgeschlossener Newton-Cotes- Formelngilt der
Satz 4.4. Wenn f(x) in [α, β] fur gerades n eine stetige (n+2)-te Ableitungund fur ungerades n eine stetige (n + 1)-te Ableitung besitzt, dann existiertein Zwischenwert ξ ∈]a, b[, sodass die Beziehungen
ESn,N[f ] = Khn+2f (n+2)(ξ)
58
fur gerades n undESn,N
[f ] = Lhn+1f (n+1)(ξ)
fur ungerades n gelten, wobei K und L von α, β abhangige Konstanten sind,und h = b−a
nNgilt.
Beweis. Plato, Barwolff
59
4.3 Gauß-Quadraturen9. Vor-lesung12.05.10
Bei den Newton-Cotes-Quadraturformeln ist man von einer vorgegebenenZahl von aquidistanten Stutzstellen x0, . . . , xn ausgegangen und hat eineNaherung des Integrals
∫ xn
x0f(x)dx durch das Integral des Interpolations-
polynoms pn(x) fur (xk, f(xk)), k = 0, . . . , n angenahert. Dabei waren alsFreiheitsgrade die Integrationsgewichte σk zu bestimmen.Bei den Gauß-Quadraturformeln verzichtet man auf die Vorgabe der Stutzstellenund versucht diese so zu bestimmen, dass die Naherung des Integrals besserals bei den Newton-Cotes-Formeln wird.Bei den Gauß-Quadraturen verwendet man als Bezeichnung fur die St utzstellenoft λ1, . . . , λn, da sie sich letztendlich als Nullstellen eines Polynoms n-tenGrades ergeben werden. Wir wollen sie im Folgenden aber weiter mit x1, . . . , xn
bezeichnen und beginnen aber im Unterschied zu den Newton-Cotes-Formelnbei k = 1 zu zahlen.
Ziel ist die Berechnung des Integrals∫ b
ag(x)dx wobei man die zu integrierende
Funktion in der Form g(x) = f(x)ρ(x) mit einer Funktion ρ(x), die mit derevtl. Ausnahme von endlich vielen Punkten auf [a, b] positiv sein soll, vorgibt.ρ(x) heißt Gewichtsfunktion. Es ist also das Integral
I =
∫ b
a
f(x)ρ(x)dx =
∫ b
a
g(x)dx
numerisch zu berechnen. Im Folgenden geht es darum, Stutzstellen xk ∈ [a, b]und Integrationsgewichte σk so zu bestimmen, dass
In =n∑
j=1
σjf(xj) (4.10)
eine moglichst gute Naherung des Integrals I ergibt. Fordert man, dassdie Formel (4.10) fur alle Polynome f(x) bis zum Grad 2n − 1, d.h. furx0, x1, . . . , x2n−1 exakt ist und somit In = I gilt, dann mussen die Stutzstellenx1, . . . , xn und die Gewichte σ1, . . . , σn Losungen des Gleichungssystems
n∑
j=1
σjxkj =
∫ b
a
xkρ(x)dx (k = 0, 1, . . . , 2n − 1) (4.11)
sein.Wir werden im Folgenden zeigen, dass das Gleichungssystem (4.11) eindeutiglosbar ist, dass fur die Stutzstellen xk ∈]a, b[ gilt und dass die Gewichte σk
60
positiv sind.
Zuerst ein
Beispiel. fur die Berechnung von∫ 1
−1f(x)ρ(x)dx mit der Gewichtsfunktion
ρ(x) ≡ 1 und der Vorgabe von n = 2 bedeutet (4.11) mit∫ 1
−1
dx = 2,
∫ 1
−1
xdx = 0,
∫ 1
−1
x2dx =2
3,
∫ 1
−1
x3 = 0
das Gleichungssystem
σ1 + σ2 = 2
σ1x1 + σ2x2 = 0 (4.12)
σ1x21 + σ2x
22 =
2
3σ1x
31 + σ2x
32 = 0
Fur (4.12) findet man mit
x1 = − 1√3, x2 = − 1√
3, σ1 = σ2 = 1
eine Losung und damit ist die Quadraturformel
I2 = f
(
− 1√3
)
+ f
(1√3
)
fur alle Polynome f(x) bis zum Grad 3 exakt, d.h. es gilt∫ 1
−1
f(x)dx = f
(
− 1√3
)
+ f
(1√3
)
Wir sind also besser als mit der Trapezregel.
4.3.1 Orthogonale Polynome
Die beiden Stutzstellen aus dem eben diskutierten Beispiel sind mit − 1√3
und 1√3
gerade die Nullstellen des Legendre-Polynoms p2(x) = x2− 13
zweitenGrades. Das ist kein Zufall, sondern darin steckt eine Systematik. Deshalbsollen im Foglenden orthogonale Polynome besprochen werden.Mit einer Gewichtsfunktion ρ(x) statten wir den Vektorraum P aller Poly-nome uber dem Korpert der reellen Zahlen mit dem Skalarprodukt
〈p, q〉ρ :=
∫ b
a
p(x)q(x)ρ(x)dx (4.13)
61
fur p, q ∈ P aus. Folglich ist durch
‖p‖2ρ = 〈p, p〉ρ =
∫ b
a
p2(x)ρ(x)dx (4.14)
eine Norm definiert. Der Nachweis, dass (4.13), (4.14) Skalarprodukt bzw.Norm sind, sollte als Ubung betrachtet werden.
Definition 4.5. Die Polynome p, q ∈ P heißen orthogonal bezuglich 〈·, ·〉ρ,wenn
〈p, q〉ρ = 0
gilt.Ist V ein Unterraum von P , dann wird durch
V ⊥ = {f ∈ P | 〈f, p〉ρ = 0 ∀p ∈ V }
das orthogonale Komplement von V bezeichnet.Die lineare Hulle der Funktionen p1, . . . , pn ∈ P wird durch
span{p1, . . . , pn} = {c1p1 + · · · + cnpn|c1, . . . , cn ∈ K}
definiert, wobei K der Zahlkorper ist, uber dem der Vektorraum der PolynomeP betrachtet wird (und wenn nichts anderes gesagt wird, betrachten wir K =R)
4.3.2 Konstruktion von Folgen orthogonaler Polynome
Wir wissen, dass die Monome 1, x, . . . , xn, . . . eine Basis zur Konstruktionvon Polynomen bilden. Mit p0(x) = 1 wird durch
pn(x) = xn −n−1∑
j=0
〈xn, pj〉ρ〈pj, pj〉ρ
pj(x) (4.15)
also mit dem Orthogonalisierungsverfahren von Gram-Schmidt eine Folgepaarweise orthogonaler Polynome definiert (bezuglich des Skalarproduktes〈·, ·〉ρ)
Beispiel. Mit [a, b] = [−1, 1] und ρ(x) = 1 erhalt man ausgehend vonp0(x) = 1 mit
p1(x) = x, p2(x) = x2 − 1
3, p3(x) = x3 − 3
5x, p4(x) = x4 − 5
2x2 +
4
105(4.16)
62
paarweise orthogonaler Polynome bezuglich des Skalarproduktes
〈p, q〉ρ =
∫ 1
−1
p(x)q(x)dx
Die eben konstruierten orthogonalen Polynome heißen Legendre-Polynome.
Bemerkung 4.6. Bezeichnet man durch Pk = span{p0, . . . , pk} en Vek-torraum der Polynome bis zum Grad k, dann gilt allgemein fur die Folgepaarweise orthogonaler Polynome p0, . . . , pn mit aufsteigendem Grad
pn ∈ P⊥n−1
Beispiel. Mit [a, b] = [−1, 1] und der Gewichtsfunktion ρ(x) = (1−x2)−1
2 =1√
1−x2erhalt man mit dem Gram-Schmidt-Verfahren (4.15) ausgehend von
p0 = 1 mit
p0(x) = 1, p1(x) = x, p2(x) = x2 − 1
2, p3(x) = x3 − 3
4x (4.17)
die orthogonalen Tschebyscheff-Polynome.
Sowohl bei den Legendre- als auch bei den Tschebyschef-Polynomen findetman jeweils einfach reelle Nullstellen, die im Intervall ]a, b[ liegen. Generellgilt der
Satz 4.7. Die Nullstellen des n-ten Orthogonalpolynoms bezuglich eines In-tervalls [a, b] und einer Gewichtsfunktion ρ sind einfach, reell und liegen imIntervall ]a, b[
Beweis. Plato
Nun kommen wir zur Definition der Gauß-Quadratur
Definition 4.8. Mit x1, . . . , xn seien die Nullstellen des n-ten Orthogonal-polynoms pn(x) gegeben. Die numerische Integrationsformel
In =n∑
j=1
σjf(xj) mit σj = 〈Lj, 1〉ρ =
∫ b
a
Lj(x)ρ(x)dx (4.18)
heißt Gaußsche Quadraturformel der n-ten Ordnung oder kurz Gauß-Quadraturzur Gewichtsfunktion ρ
Im Folgenden wird gezeigt, dass die Stutzstellen xk und Gewichte σk alsLosung des Gleichungssystems (4.11) gerade die Nullstellen des n-ten Ortho-gonalpolynoms pn(x) bzw. die Gewichte gemaß (4.18) sind und damit dieGleichwertigkeit der Formeln (4.10) und (4.18) nachgewiesen.
63
Satz 4.9. Mit x1, . . . , xn seien die Nullstellen des n-ten Orthogonalpolynomspn(x) gegeben.Es existiert eine eindeutig bestimmte Gauß-Quadratur (4.18). Bei der Gauß-Quadratur sind alle Gewichte gemaß (4.18) positiv und die Quadratur ist furjedes Polynom vom Grad m ≤ 2n − 1 exakt, d.h. es gilt
∫ b
a
p(x)ρ(x)dx = 〈p, 1〉ρ =n∑
j=1
σjp(xj), ∀p ∈ Π2n−1 (4.19)
Außerdem ist die Quadratur interpolatorisch, d.h. es gilt fur das Interpolati-onspolynom qn−1 zu den Stutzpunkten (xj, f(xj)), j = 1, . . . , n
∫ b
a
qn−1(x)ρ(x)dx =n∑
j=1
σjqn−1(xj) =n∑
j=1
σjf(xj)
Beweis. (keine Angst, wird nur zur Information angegeben, und wird nichtin Prufungen abgefragt)Wir betrachten ein Polynom p ∈ Π2n−1 mit Grad m ≤ 2n − 1. Durch Po-lynomdivision findet man fur das n-te Orthogonalpolynom Polynome q, r ∈Pn−1 mit
p
pn
= q +r
pn
⇔ p = qpn + r
Mit den Nullstellen x1, . . . , xn von pn gilt p(xj) = r(xj) fur j = 1, . . . , n. DasLagrangsche Interpolationspolynom fur r(x) ergibt
r(x) =n∑
j=1
r(xj)Lj(x) =n∑
j=1
p(xj)Lj(x)
wegen 〈q, pn〉ρ = 0 gilt
∫ b
a
p(x)ρ(x)dx = 〈p, 1〉ρ = 〈r, 1〉ρ
=n∑
j=1
p(xj) 〈Lj, 1〉ρ =n∑
j=1
σjp(xj)
Fur p(x) = L2j(x) ∈ Π2n−2 ergibt die eben nachgewiesene Formel (4.19)
0 < ‖Lj‖2ρ
=⟨L2
j , 1⟩
ρ=
n∑
k=1
σkL2j(xk) = σj
Wegen L2j(xk) = δ2
jk folgt die Positivitat der Gewichte.
64
Zum Nachweis der Eindeutigkeit der Gauß-Quadratur nimmt man an, dasseine weitere Formel
I∗n =
n∑
j=1
σ∗j f(x∗
j) (4.20)
existiert mit x∗k 6= x∗
j fur k 6= j, deren Genauigkeitsgrad gleich 2n− 1 ist. DiePositivitat der σ∗
j wird analog der Positivitat der σj gezeigt.Fur das Hilfspolynom vom Grad 2n − 1
h(x) = L∗k(x)pn(x), L∗
k(x) =n∏
k 6=j=1
x − x∗j
x∗k − x∗
j
ergibt (4.20) den exakten Wert des Integrals fur h(x), also
∫ b
a
h(x)ρ(x)dx =
∫ b
a
L∗k(x)pn(x)ρ(x)dx
=n∑
j=1
σ∗j Lk(x
∗j)pn(x∗
j) = σ∗kpn(x∗
k)
fur alle k = 1, . . . , n. Da das 2. Integral∫ b
aL∗
k(x)pn(x)ρ(x)dx = 〈L∗k, pn〉ρ
wegen der Orthogonalitat von pn zu allen Polynomen bis zum Grad n − 1gleich Null ist, folgt σ∗
kpn(x∗k) = 0 fur alle k = 1, . . . , n. Wegen der Positivitat
der Gewichte mussen die x∗k Nullstellen des n-ten Orthogonalpolynoms pn(x)
sein, die eindeutig bestimmt sind. Damit ist die Eindeutigkeit der Gauß-Quadratur bewiesen.
Auf der Grundlage des Fehlers der Polynominterpolation von f(x) durch einPolynom n-ten Grades kann man den Fehler der Gauß-Quadratur bestimmen,es gilt der
Satz 4.10. Mit den Stutzstellen und Gewichten aus Satz 4.9 gilt fur auf demIntervall [a, b] 2n-mal stetig diffbare Funktionen f(x)
∫ b
a
f(x)ρ(x)dx −n∑
j=1
σjf(xj) =‖pn‖2
ρ
(2n)!f (2n)(ξ) (4.21)
mit einem Zwischenwert ξ ∈]a, b[.
Die folgende Tabelle zeigt Intervalle, Gewichtsfunktionen, die zugehorigenOrthogonalpolynome und deren Name (α, β > −1)
65
Intervall ρ(x) p0, p1, . . . Bezeichnung
[−1, 1] 1 1, x, x2 − 13, . . . Legendre
[−1, 1] 1√1−x2
1, x, x2 − 12, . . . Tschebyscheff
[−1, 1] (1 − x)α(1 + x)β 1, 12[α − β + (α + β + 2)x] Jacobi
] −∞,∞[ e−x2
1, x, x2 − 12, x3 − 3
2x, . . . Hermite
[0,∞[ e−xxα 1, x − α − 1, . . . Laguerre
Mit den in der Tabelle angegebenen Polynomen und deren Nullstellen las-sen sich Quadraturformeln fur endliche Intervalle und unendliche Intervallkonstruieren.Die Tschebyscheffpolynome sind trotz der Gewichtsfunktion gegenuber denLegendrepolynomen attraktiv, weil man die Nullstellen des n-ten Tschebys-cheffschen Orthogonalpolynoms explizit angeben kann (durch eine Berech-nungsformel, s.dazu (3.9) ) ohne die Polynome auszurechnen. Das ist bei denanderen Polynomen aus der Tabelle nicht direkt moglich.
66
4.4 Fehlerabschatzungen fur lin. Gleichungs-
systeme10.Vorle-sungam19.5.2010
Sei A eine regulare reelle Matrix vom Typ (n × n) und ~b ∈ Rn ein (Spalten-
)Vektor. Zu losen ist
A~x = ~b (4.22)
Beispiel 4.11.
A =
[3 1.0016 1.997
]
,~b =
[1.9994.003
]
(4.22) liefert dann
3x1 + 1.001x2 = 1.999
6x1 + 1.997x2 = 4.003
Losung ist Schnittpunkt von 2 Geraden, und zwar (x1, x2) = (1,−1). Andert
man ~b geringfugig zu
~b = ~b + ∆~b =
[2.0024.000
]
, d.h. ∆~b =
[0.003−0.003
]
dann hat A~x = ~b die Losung
(x1, x2) = (0.4004, 0.8)
d.h. eine geringfugige Veranderung der Gerade hat eine recht große Auswir-kung auf den Schnittpunkt! Die Geraden sind hier fast parallel.
Benotigen nun Werkzeuge zur mathematischen Beschreibung dieses Phano-mens:
4.4.1 Vektor- und Matrixnormen
• ‖x‖1 =∑n
k=1 |xk| Summennorm
• ‖x‖2 =√∑n
k=1 |xk|2 Euklidische Norm
• ‖x‖∞ = max1≤k≤n{|xk|} Maximumsnorm
Durch Vektornormen induzierte Matrixnormen
‖A‖σ = maxx∈Rn,~x 6=0
‖Ax‖σ
‖x‖σ
= maxy∈Rn,‖y‖=1
‖Ay‖σ
mit σ ∈ {1, 2,∞}. Es gilt
67
1. ‖Ax‖σ ≤ ‖A‖σ‖x‖σ Vertraglichkeit
2. ‖AB‖σ ≤ ‖A‖σ‖B‖σ Submultiplikativitat
Zuruck zum Beispiel 4.11. Es ist
‖∆~b‖∞ = 0.003, ‖~b‖∞ = 4.003 ⇒
∥∥∥∆~b
∥∥∥∞∥
∥∥~b
∥∥∥∞
= 7.5 · 10−4
‖∆x‖∞ = ‖x − x‖∞ = 1.8, ‖x‖∞ = 1 ⇒ ‖∆x‖∞‖x‖∞
= 1.8
⇒‖∆x‖
∞
‖x‖∞
‖∆b‖∞
‖b‖∞
= 2400
Wie hangt die Fehlerverstarkung von A ab?
‖x − x‖ =∥∥∥A−1b − A−1b
∥∥∥ =
∥∥∥A−1(b − b)
∥∥∥
⇒ ‖∆x‖ =∥∥A−1∆b
∥∥
⇒ ‖∆x‖‖x‖ =
‖A−1∆b‖ · ‖b‖‖x‖ · ‖b‖ =
‖Ax‖ · ‖A−1∆b‖‖x‖ · ‖b‖
≤ ‖A‖ ‖x‖ · ‖A−1‖ ‖∆b‖‖x‖ ‖b‖ = ‖A‖
∥∥A−1
∥∥‖∆b‖‖b‖
Also‖∆x‖‖x‖ ≤ ‖A‖
∥∥A−1
∥∥‖∆b‖‖b‖ (4.23)
Definition 4.12. Die Zahl
cond(A) = κ(A) = ‖A‖∥∥A−1
∥∥
heißt Konditionszahl der Matrix A und ist eine Schranke fur die Fehler-verstarkung bei der Losung von (4.22) bei gestorter rechter Seite.
Zuruck zu Beispiel 4.11
‖A‖∞∥∥A−1
∥∥∞ = 4798.2 = cond(A)
68
4.4.2 Weitere Vektor- und Matrixnormen
p-Norm, p ∈ N+, x ∈ R
n
‖x‖p = (|x1|p + |x2|p + · · · + |xn|p)1
p
induziert ‖A‖p
Frobenius-Norm einer (m × n) Matrix
‖A‖F =
(m∑
i=1
n∑
j=1
|aij|2) 1
2
also die euklidsche bzw. 2-Norm von A als Vektor geschrieben.
Theorem 4.13. Fur die Berechnung von speziellen induzierten Matrixnor-men gilt (A reelle (m × n) Matrix)
‖A‖1 = max1≤j≤n
m∑
i=1
|aij| Spaltensummennorm (4.24)
‖A‖∞ = max1≤i≤n
n∑
j=1
|aij| Zeilensummennorm (4.25)
‖A‖2 =√
λmax mit λmax großter EW von AT A (4.26)
Beweis. (4.24) und (4.25) als Ubung.Fur den Nachweis von (4.26) uberlegt man, dass AT A ahnlich einer Diago-nalmatrix mit den EW von AT A als Diagonalelementen ist. Die EW sindpositiv und aus der Definition von ‖A‖2 folgt dann schließlich (4.26)
Wir kehren zuruck zur Fehlerfortpflanzung bei der Losung linearer Glei-chungssysteme. Seien A und b durch ∆A = ǫF bzw. ∆b = ǫf gestort, alsostatt Ax = b wird
(A + ǫF )x(ǫ) = b + ǫf (4.27)
betrachtet. F, f, ǫ sind Storungen und fur ǫ = 0 ergibt sich das eigentlicheProblem. A sei regular. Dann kann man die Existenz und Differenzierbarkeitder Abbildung ǫ 7→ x(ǫ) und x = x(0)
x(0) = A−1(f − Fx)
zeigen. Fur die Taylorreihe folgt
x(ǫ) = x + ǫx(0) + O(ǫ2)
69
alsox(ǫ) − x = ǫx(0) + O(ǫ2) = ǫA−1(f − Fx) + O(ǫ2)
Fur den relativen Fehler gilt dann
‖x(ǫ) − x‖‖x‖ ≤ ǫ
‖A−1(f − Fx)‖‖x‖
Und im Fall einer submultiplikativen (konsistenten) Matrixnorm von A
‖x(ǫ) − x‖‖x‖ ≤ ǫ
∥∥A−1
∥∥
{‖f‖‖x‖ + ‖F‖
}
+ O(ǫ2) (4.28)
(4.28) sagt noch nichts uber die Auswirkungen der relativen Fehler
‖∆A‖‖A‖ bzw.
‖∆b‖‖b‖
aus, was aber von Interesse ist. Mit b = Ax folgt ‖b‖ ≤ ‖A‖ ‖x‖, also
1
‖x‖ ≤ ‖A‖‖b‖
und mit ‖F‖ = ‖F‖‖A‖ ‖A‖ folgt aus (4.28)
‖x(ǫ) − x‖‖x‖ ≤ ‖A‖
∥∥A−1
∥∥
{
ǫ‖F‖‖A‖ + ǫ
‖f‖‖b‖
}
+ O(ǫ2)
= κ(A)
{‖∆A‖‖A‖ +
‖∆b‖‖b‖
}
+ O(ǫ2)
≤κ(A)
{‖∆A‖‖A‖ +
‖∆b‖‖b‖
}
(4.29)
(4.29) gilt fur kleine ǫ. Im Folgenden soll eine genauere Analyse vorgenommenwerden
Lemma 4.14. F ∈ Rn×n und ‖·‖ submultiplikativ (konsistent). Fur ‖F‖ ≤ 1
ist E − F nicht singular, und es gilt
(E − F )−1 =∞∑
k=0
F k
sowie∥∥(E − F )−1
∥∥ ≤ 1
1 − ‖F‖
70
Beweis. In Analogie zur geometrischen Reihe, bzw. Verallgemeinerung der-selben.
Lemma 4.15. Es gelte Ax = b mit regularem A ∈ Rn×n und b ∈ R
n, b 6= 0.F = ∆A und f = ∆b seien Storungen mit relativem Fehler ≤ δ, d.h.
‖∆A‖‖A‖ ≤ δ,
‖∆b‖‖b‖ ≤ δ
Falls δκ(A) = r < 1, so ist A + ∆A regular und fur die Losung x von(A + ∆A)x = b + ∆b gilt
‖x‖‖x‖ ≤ 1 + r
1 − r
Beweis. Es gilt
∥∥A−1F
∥∥ ≤
∥∥A−1
∥∥ ‖F‖ ≤ δ
∥∥A−1
∥∥ ‖A‖
︸ ︷︷ ︸
κ(A)
= r < 1
⇒ A + F = A(E + A−1F ) =: A(E − F ) mit∥∥∥F
∥∥∥ < 1
(E−F )−1 ex. nach Lemma 4.14 also existiert auch (A+F )−1 = (E−F )−1A−1.Nach Definition von x folgt
(A + F )x = b + f = Ax + f
⇒ (E + A−1F )x = x + A−1f
⇒ ‖x‖ ≤∥∥(E + A−1F )−1
∥∥
∥∥x + A−1f
∥∥
mit∥∥∥(E − F )−1
∥∥∥ ≤ 1
1 −∥∥∥F
∥∥∥
≤ 1
1 − r
⇒ ‖x‖ ≤ 1
1 − r(‖x‖ +
∥∥A−1
∥∥ ‖f‖)
≤ 1
1 − r(‖x‖ + δ ‖A‖
∥∥A−1
∥∥ ‖x‖) =
1 + r
1 − r‖x‖
Zur Abschatzung des relativen Fehler betrachten wir
Ax + Fx = b + f
Ax = b
}
⇒ A(x − x) = f − Fx
⇒ x − x = A−1f − A−1Fx (4.30)
71
Theorem 4.16. Unter den Voraussetzungen des Lemmas 4.15 gilt
‖x − x‖‖x‖ ≤ 2r
1 − r, r = δκ(A) (4.31)
Beweis. Es ergibt sich aus (4.30)
‖x − x‖ ≤∥∥A−1f
∥∥ +
∥∥A−1Fx
∥∥
≤∥∥A−1
∥∥ ‖f‖ +
∥∥A−1F
∥∥ ‖x‖
≤ δκA ‖x‖ + r1 + r
1 − r‖x‖
= r
(
1 +1 + r
1 − r
)
‖x‖ =r · 21 − r
‖x‖
In den bisherigen Abschatzungen wurde der Fehler F der Matrix A in derNorm ‖F‖ betrachtet und der Fehler von b ebenso in der Vektornorm ‖f‖,d.h.
‖F‖ ≤ δ ‖A‖ und ‖f‖ ≤ δ ‖b‖wurden vorausgesetzt. Betrachtet man nur die Komponenten, d.h. fordertman
|fij| ≤ δ|aij|, i, j = 1, . . . , n
dann lassen sich die Abschatzunden des Lemmas 4.15 und des Theorems 4.16verbessern. Es gelten:
Lemma 4.17. Sei A ∈ Rn×n regular und 0 6= b ∈ R
n Es gelte Ax = b und(A + ∆A)x = b + ∆b und die Abschatzungen
|∆A| ≤ δ|A|, |∆b| ≤ δ|b|
Ist die Bedingungδ∥∥|A−1||A|
∥∥
M= r < 1
erfullt, so ist A + ∆A regular und es gilt
‖x‖‖x‖ ≤ 1 + r
1 − r
(‖·‖M ist eine der Matrixnormen ‖·‖∞ , ‖·‖1 , ‖·‖F und ‖·‖ die damit ver-tragliche Vektornorm).
72
Theorem 4.18. Unter den obigen Vorraussetzungen gilt
‖x − x‖‖x‖ ≤ 2r
1 − r(4.32)
fur die obigen Normen.
Bemerkung 4.19. Die Aussagen der Theoreme 4.16 und 4.18 findet manauch oft in der Form
‖x − x‖‖x‖ ≤ κ(A)
1 − ‖A−1‖ ‖∆A‖
(‖∆A‖‖A‖ +
‖∆b‖‖b‖
)
73
Kapitel 5
Losung linearerGleichungssysteme
11.Vorle-sungam20.5.2010
5.1 LR-Zerlegung
Zu losen ist Ax = b. Dazu soll A als Produkt einer unteren DreiecksmatrixU und einer oberen Dreiecksmatrix R geschrieben werden, d.h. man hat
Ax = b ⇔ L Rx︸︷︷︸
y
= b
Und lost zuerstLy = b
und danachRx = y
5.1.1 Realisierung mit dem Gaußschen Eliminations-verfahren
Grundprinzip:Rangerhaltende Manipulationen der Matrix [A|b] durch Linearkombinationenvon Zeilen
Lij(λ) =
1 0. . .
1
λ. . .
0 1
74
Multiplikation Lij(λ)A bewirkt die Addition des λ-fachen der j-ten Zeile vonA zur i-ten Zeile d.h. durch geeignete Wahl von λ erzeugt man in
A = Lij(λ)A
an der Position (i, j) z.B. auch eine Null (A ∈ Rn×m)
Lij(λ) hat den Rang n und die Determinante 1 ⇒ rg(A) = rg(A). Durchmehrfache Multiplikation mit
Ljk, j = k + 1, ..., n
erhalt man bei geeigneter Wahl der λ unterhalb von akk Null-Eintrage
Nun etwas praziser
A =
a11 · · · · · · a1n
. . .
akk · · ·...
ank · · ·
→
a11 · · ·. . .
akk · · ·0 ak+1k+1...0
Vorraussetzung: akk 6= 0Setzen
t = t(k)(ak) =
0...0
tk+1 k
...tnk
mit
tik =
{0 i = 1, .., k
aik
akki = k + 1, ..., n
ek sei der k-te Standardeinheitsvektor
Definition 5.1.
Mk :=
1. . .
1
−tk+1k. . .
.... . .
−tnk 1
Frobenius-Matrix, Gaußtrafomatrix
75
Man uberlegt sich, dass Mk das Produkt der oben diskutierten Matrizen Ljk(−tj), j =k + 1, ..., n ist.
Eigenschaften von Mk
Mk = E − t(k)eTk
Mkak =
ak1...
akk
0...0
d.h. ak1, ..., akk bleiben bei der Multiplikation mit Mk unverandert
rg(Mk) = n
det(Mk) = 1
M−1k = E + t(k)eT
k , da
M−1k Mk = E − t(k) eT
k t(k)
︸ ︷︷ ︸
=0
ek = E
Wenn alles gut geht, d.h. wenn jeweils akk 6= 0 ist, dann erhalt man nach derMutiplikation von A mit den Frobenius-Matrizen M1, ...,Mn−1, also
Mn−1 · ... · M1A =
r11 r12 · · · r1n
r22 · · · r2n
. . ....
0 rnn
=: R
eine obere Dreiecksmatrix R. Außerdem hat die Matrix
Mn−1 · ... · M1
die inverse Matrix
L = M−11 · ... · M−1
n−1 =
1 0t21 1t31 t32 1...
.... . .
tn1 tn2 tnn−1 1
76
sodass schließlich mitA = LR
eine LR-Zerlegung vorliegt.
Definition 5.2. Eine obere oder untere Dreiecksmatrix, deren Diagonalele-mente alle gleich eins sind, heißt unipotent. Die Zerlegung A = LR heißtLR-Zerlegung, wenn L eine unipotente untere Dreiecksmatrix ist.
Satz 5.3. Eine Matrix A ∈ Rn×n besitzt genau dann eine LR-Zerlegung,
wenndet(A(1 : k, 1 : k)) 6= 0, k = 1, 2, ..., n − 1
Falls die LR-Zerlegung existiert und A regular ist, dann sind L und R ein-deutig bestimmt, und es gilt:
det A = r11 · r22 · ... · rnn
Bemerkung. (1) Man braucht nur den Speicherplatz der Matrix:
Die obere Dreiecksmatrix entsteht durch die sukzessive Multiplikationvon A mit Frobenius-Matrizen (Gauß-Transformationen)
r11 · · · · · · r1n
r22 · · · r2n
0. . .
...rnn
An den Positionen (k + 1, k), (k + 2, k), ..., (n, k) wo durch die Gauß-Transformationen (Multiplikation mit Mk) Nullen erzeugt werden, konnendie Elemente tk+1k, tk+2k, ..., tnk sukzessiv fur k = 1, ..., n− 2 eingetragenwerden und man erhalt
t21t31 t32...
. . .
tn1 tnn−1
also die nicht redundanten Elemente von L
(2) Berechnung von L = M−11 · ... · M−1
n−1 kostet nichts, sondern besteht nurin der Ablage der jeweils bei den Gauß-Transformationen erzeugten tkj-Werten (k > j, k = 2, ..., n, j = 1, ..., n − 1)
(3) Rechenaufwand ca. n3
3∈ O(n3) Multiplikationen (flops, floating point
operations).
77
Fehleranalyse bei der Konstruktion einer LR-Zerlegung
Definition 5.4. Unter dem Absolutbetrag einer Matrix A ∈ Cm×n versteht
man die Matrix|A| = B mit bij = |aij|
also die Matrix mit den Absolutbetragen ihrer Elemente. Gilt fur A,B ∈R
m×n dass aij ≤ bij so schreibt man A < B
Bemerkung 5.5. Fur die ”Betrage”von Matrizen gelten die Beziehungen
(i) |A + B| ≤ |A| + |B|
(ii) |A · B| ≤ |A||B|
(iii) A ≤ B,C ≥ 0, D ≥ 0 ⇒ CAD ≤ CBD
(iv) ‖A‖F ≤ ‖|A|‖p , p ∈ N+
(v) ‖A‖p = ‖|A|‖p fur p ∈ {1,∞, F}
(vi) |A| ≤ |B| ⇒ ‖A‖ ≤ ‖B‖ fur diese Nomen
Es gelten nun die folgenden Satze zur Fehlerabschatzung bzw. -analyse.
Satz 5.6. Sei A ∈ Rn×n Matrix von Maschinenzahlen. Falls bei der Kon-
struktion der LR-Zerlegung kein akk = 0 zum Abbruch fuhrt, dann erfullendie berechneten Faktoren L, R die Gleichung
LR = A + H
mit|H| ≤ 3(n − 1)eps(|A| + |L||R|) + O(eps2)
Satz 5.7. Sind L, R die Matrizen aus Satz 5.6, so erhalt man bei den Algo-rithmen zum Vorwarts- und Ruckwartseinsetzen
Ly = b, Rx = y
eine Losung x von (A + ∆)x = b mit
|∆| ≤ n · eps(3|A| + 5|L||R|) + O(eps2)
78
Beweis. Ruckwartseinsetzen ergibt
(L + F )y = b, |F | ≤ n · eps|L| + O(eps2)
(R + G)x = y, |G| ≤ n · eps|R| + O(eps2)
⇒ (L + F )(R + G)x = b
⇔ ( LR︸︷︷︸
A+H
+FR + LG + FG)x = b
⇔ (A + ∆)x = b
mit ∆ = H +FR+ LG+FG. Mit der Abschatzung aus Satz 5.6 fur H ergibtsich
|∆| ≤ |H| + |F |︸︷︷︸
≤neps|L|
|R| + |L| |G|︸︷︷︸
≤neps|R|
+ |F ||G|︸ ︷︷ ︸
O(eps2
≤ 3(n − 1)eps(|A| + |L||R|) + 2neps|L||R| + O(eps2)
≤ neps(3|A| + 5|L||R|) + O(eps2)
Bemerkung. Problematisch, d.h. recht groß konnen die Elemente von |L|und |R| werden, wenn bei der Berechnung aller tkj im Rahmen der Gauß-Transformationen große Zahlen entstehen!Abhilfe: Pivotisierung
5.1.2 LR-Zerlegung mit Spaltenpivotisierung
Um zu vermeiden, dass der Algorithmus zur Konstruktion einer LR-Zerlegungaufgrund von akk = 0 abbricht, oder durch betragsmaßig sehr kleine akk (klei-ne Pivots) bei der Berechnung der tkj betragsmaßig sehr große Zahlen ent-stehen, kann man durch Zeilenvertauschungen das betragsmaßig maximaleElement in die Diagonalposition bringen.Zeilenvertauschungen bewirkt man durch Multiplikation mit Permutations-matrizen Pk (von links).
Definition 5.8. Matrizen P ∈ Rn×n die aus der Einheitsmatrix durch Ver-
tauschen von (genau) zwei Zeilen hervorgehen heißen elementare Permu-tationsmatrizen
Bei den durchgefuhrten Betrachtungen haben wir benutzt, dass fur elemen-tare Permutationsmatrizen
P · P = E
79
gilt, d.h. die Matrix gleich ihrer Inversen ist. Die Erfahrungen des Beispielskann man zusammenfassen.
Definition 5.9. Wir bezeichnen den im Beispiel beschriebenen Algorithmusals Konstruktion einer LR-Zerlegung mit Spaltenpivotisierung (auch Gaußeli-mination mit partieller Pivotisierung).
Satz 5.10. Fur die Gaußelimination mit partieller Pivotisierung mit demResultat
Mn−1Pn−1 · . . . · M1P1A = R
gilt PA = LR mit P = Pn−1 · . . . · P1. Fur L gilt
L = M−11 · . . . · M−1
n−1
mit
Mn−1 = Mn−1
Mk = Pn−1 · . . . · Pk+1MkPk+1 · . . . · Pn−1, k ≤ n − 2
wobei Mk Frobeniusmatrizen sind (deren Inverse trivial zu berechnen ist).
Beweis. Durch die Eigenschaft PP = E von elementaren Permutationsma-trizen uberlegt man sich, dass
Mn−1Pn−1Mn−2Pn−2 · · ·M1P1A
= Mn−1︸ ︷︷ ︸
Mn−1
Pn−1Mn−2Pn−1︸ ︷︷ ︸
Mn−2
Pn−1Pn−2 · · ·M1P2 · · ·Pn−1︸ ︷︷ ︸
M1
Pn−1 · · ·P2P1︸ ︷︷ ︸
P
A
gilt. Außerdem hat Mk = PµMkPµ die gleiche Struktur wie Mk, da durchdie Multiplikation von Pµ von links und rechts nur die Reihenfolge der tkl
vertauscht wird. Die Multiplikation von
Mn−1Mn−2 · · · M1PA mit L = M−11 · · · M−1
n−1
ergibtPA = LR
Dabei ist L ebenso wie im Fall der LR-Zerlegung ohne Pivotisierung alsProdukt von Frobeniusmatrizen eine untere Dreiecksmatrix mit Diagonalele-menten gleich eins.
80
Bemerkung. Konsequenz dieser LR-Zerlegung mit Spaltenpivotisierung ist,
dass∣∣∣L
∣∣∣ in der Regel wesentlich kleinere Elemente (≤ 1) hat, was zu einer
Verbesserung der Abschatzung aus Satz 5.7 fuhrt.
Beispiel 5.11. Von der Matrix
A =
2 6 14 3 23 2 4
soll eine LR-Zerlegung mit Spaltenpivotisierung konstruiert werden. Es ergibtsich
Z I ⇐⇒ Z II →
4 3 2 22 6 1 13 2 4 3
Z II := Z II − 12Z I
Z III := Z III − 34Z I
}
→
4 3 2 20 9
20 1
0 −14
104
3
Z III := Z III − (− 1
18)Z II →
4 3 2 20 9
20 1
0 0 104
3
,
wobei in der letzten Spalte mit einem Buchhaltungsvektor die Zeilenvertau-schungen registriert werden. Man erhalt also in den einzelnen Schritten dieFrobeniusmatrizen
M1 =
1 0 0−1
21 0
−34
0 1
M2 =
1 0 00 1 00 1
181
und es ergibt sich unter Berucksichtigung der Zeilenvertauschungen mit
L = M−11 M−1
2 =
1 0 012
1 034
− 118
1
und P =
0 1 01 0 00 0 1
aus
L−1 := M2M1PA =
4 3 20 9
20
0 0 104
=: R
schließlich die ZerlegungPA = LR .
81
5.2 Cholesky-Zerlegung12.Vorle-sungam26.5.2010
Bei vielen Aufgabenstellungen der angewandten Mathematik sind Gleichungs-systeme Ax = b mit symmetrischen und positiv definiten Matrizen A zulosen, z.B.
• numerische Losung elliptischer und parabolischer Differentialgleichun-gen
• Spline-Approximation
Voraussetzung: A ∈ Rn×n ist positiv definit und symmetrisch, d.h.
∀x 6= 0 : xT Ax > 0 und A = AT
Unter diesen Voraussetzungen kann man die Gauß-Elimination (LR-Zerlegung)durch die sogenannte Cholesky-Zerlegung ersetzen und verbessern!
Satz (von Sylvester). Notwendig und hinreichend fur positive Definitheit ei-ner symmetrischen Matrix A ∈ R
n×n ist die Positivitat aller Hauptabschnitts-determinanten, d.h.
∀k = 1, . . . , n : det A(1 : k, 1 : k) > 0
(auch Kriterium von Hurwitz)
Satz 5.12. Sei A symmetrisch und positiv definit. Dann existiert eine untereDreiecksmatrix G ∈ R
n×n mit positiven Diagonalelementen, sodass
A = GGT
Beweis. Nach dem Satz von Sylvester gilt A(1 : k, 1 : k), k = 1, . . . , n sindpositiv definit und det A(1 : k, 1 : k) 6= 0 sowie A invertierbar (regular) ⇒nach Satz 5.3 (Existenz eine LR-Zerlegung)
A = LR
mit L untere Dreiecksmatrix mit 1-Diagonale und R obere Dreiecksmatrix,in diesem Fall gilt
A(1 : k, 1 : k) = L(1 : k, 1 : k)R(1 : k, 1 : k)
⇒ 0 < det A(1 : k, 1 : k) = det L(1 : k, 1 : k)︸ ︷︷ ︸
=1
det R(1 : k, 1 : k)︸ ︷︷ ︸
=r11r22···rkk
⇒ 0 < det R(1 : k, 1 : k) = r11r22 · · · rkk fur alle k = 1, . . . , n
⇒ ∀j = 1, . . . , n : rjj > 0
82
Nun betrachten wir die Diagonalmatrix
D = diag(r11, . . . , rnn) =: diag(d1, . . . , dn), dk > 0
und es giltR = DR
mit rjj = 1, j = 1, . . . , n. Definiere D1
2 = diag(d1
2
1 , . . . , d1
2n )
⇒ A = LR = LDR = LD1
2 D1
2 R (5.1)
⇒ D− 1
2 L−1A = D1
2 R, D− 1
2 = diag(d− 1
2
1 , . . . , d− 1
2n )
Weiterhin gilt
D− 1
2 L−1A(L−1)T (D− 1
2 )T
︸ ︷︷ ︸
symmetrisch
= D1
2 R(L−1)T (D− 1
2 )T
︸ ︷︷ ︸
obere Dreiecksmatrix mit 1-Diagonale
⇒ D− 1
2 R(L−1)T D− 1
2 = E
⇒ R(L−1)T = D− 1
2 D1
2 = E
⇒ R = LT
Einsetzen in (5.1) ergibt
A = LD1
2 D1
2 R = LD1
2 D1
2 LT
= (LD1
2 )(LD1
2 )T
⇒ G = LD1
2
5.2.1 Konstruktion der Choleksy-Zerlegung
GGT = A ⇔
g11 0...
. . .
gn1 · · · gnn
g11 · · · gn1
. . ....
gnn
=
a11 · · · a1n
......
an1 · · · ann
⇒ akk = g2k1 + g2
k2 + · · · + g2kk−1 + g2
kk, k = 1, . . . , n
⇒ k = 1 : g211 = a11 ⇒ g11 =
√a11
gkk =
√√√√akk −
k−1∑
j=1
g2kj
83
Außerdem fur j > k
akj = gj1gk1 + gj2gk2 + · · · + gjk−1gkk−1 + gjkgkk
⇒ gkj =1
gkk
(
ajk −k−1∑
i=1
gjigki
)
Pseudocode:
Algorithmus 2 Berechne Cholesky-Zerlegung von A ∈ Rn×n symmetrisch
und positiv definit
for i = 1 to n do
gkk =
(
akk −k−1∑
j=1
g2kj
) 1
2
for j = k + 1 to n do
gjk = 1gkk
(
ajk −k−1∑
i=1
gjigki
)
end forend for
5.3 Orthogonale Matrizen – QR-Zerlegung13.Vorle-sungam27.5.2010
Im Folgenden soll fur eine gegebene Matrix A ∈ Rn×m, 1 ≤ m ≤ n, eine
Faktorisierung der FormA = QS (5.2)
bestimmt werden mit einer orthogonalen Matrix Q, d.h.
Q ∈ Rn×n, Q−1 = QT
und einer verallgemeinerten oberen Dreiecksmatrix
S =
R
−0
∈ Rn×m, R =
∗ ∗. . .
0 ∗
∈ R
m×m (5.3)
Solche Zerlegungen ermoglichen z.B. die stabile Losung von schlecht kondi-tionierten losbaren linearen Gleichungssystemen Ax = b, (m = n) oder diestabile Losung von Ausgleichsproblemen
minx∈Rm
‖Ax − b‖2
Wir erinnern uns an die Eigenschaften orthogonaler Matrizen:
84
(i)‖Qx‖2 = ‖x‖2 =
∥∥QT x
∥∥
2, x ∈ R
n (5.4)
(ii)cond(QA) = cond(A) (5.5)
(iii) fur Q1, Q2 ∈ Rn×n orthogonal, gilt Q1Q2 ist orthogonal
Faktorisierung A = QR mittels Gram-Schmidt-Orthogonalisierung. Fur qua-dratische regulare Matrizen A (m = n) hat (5.2), (5.3) die Form
A = QR (5.6)
mit Q orthogonal und R oberer Dreiecksmatrix vom Typ (n× n). SchreibenA,Q,R in der Form
A = [a1|a2| . . . |an], Q = [q1| . . . |qn], R =
r11 · · · r1n
. . ....
0 rnn
Mit den Spaltenvektoren ak, qk ∈ Rn, k = 1, . . . , n. (5.6) bedeutet dann
aj =
j∑
i=1
rijqi, j = 1, ..., n, q1, . . . , qn ∈ Rn (5.7)
5.3.1 Gram-Schmidt-Verfahren zur Orthogonalisierung
(a) Ausgangspunkt: man hat j − 1 orthonormale Vektoren q1, . . . , qj−1 ∈ Rn
mit span(a1, . . . , aj−1) = span(q1, . . . , qj−1) =: Mj−1
(b) man bestimmt im Schritt j ≥ 1 das Lot von aj auf den linearen Unter-raum Mj−1 ⊂ R
n
qj := aj −j−1∑
i=1
〈aj, qi〉 qi (5.8)
Und nach der Normierung
qj =qj
‖qj‖Sind die Vektoren q1, . . . , qj ∈ R
n paarweise orhonormal und es gilt
span(a1, . . . , aj) = span(q1, . . . , aj)
85
Aus der Gleichung (5.8) folgt
aj = ‖qj‖2︸ ︷︷ ︸
rjj
qj +
j−1∑
i=1
(aTj qi)
︸ ︷︷ ︸
rij
qi =
j∑
i=1
rijqi, j = 1, . . . , n (5.9)
Nach Abschluss der Gram-Schmidt-Orthogonalisierung hat man damit mit(5.9)
[a1|a2| . . . |an] = [q1| . . . |qn]
r11 r12 · · · r1n
r22 · · · r2n
. . ....
rnn
als QR-Zerlegung
Bemerkung 5.13. Der beschriebene Algorithmus kann im ungunstigstenFall Probleme bereiten (nicht gutartig sein), wenn z.B. ‖qj‖ recht klein wird(Losung folgt).
5.3.2 Householder-Matrizen/Transformationen
Definition 5.14. Eine Abbildung H : Rn → R
n, x 7→ Hx mit einer Matrix
H = E − 2wwT , w ∈ Rn, ‖w‖2 = wT w = 1 (5.10)
bezeichnet man als Householder-Transformation und H als Householder-Matrix
Eigenschaften von H:
• HT = H Symmetrie
• H2 = E H ist involutorisch
• HT H = E Orthogonalitat
Nachweis als Ubung
Wirkung der Householder-Transformation:Spiegelung von x ∈ R
n an der Hyperebene {z ∈ Rn : zT w = 0}, da die
IdentitatHx = x − 2(wT x)w = x − (wT x)w − (wT x)w
gilt.
86
Lemma 5.15. Gegeben sei 0 6= x ∈ Rn mit x 6∈ span{e1}. Fur
w =x + σe1
‖x + σe1‖2
mit σ = ±‖x‖2 (5.11)
gilt‖w‖ = 1, Hx = (E − 2wwT )x = −σe1 (5.12)
Beweis. ‖w‖ = 1 weil x + σe1 6= 0 und damit (5.11) wohldefiniert ist. Furden Nachweis von (5.12) erhalt man
‖x + σe1‖22 = ‖x‖2
2 + 2σeT1 x + σ2 = ‖x‖2 + 2σeT
1 x + ‖x‖2 = 2(x + σe1)T x
Und mit (5.11), d.h. (x+σe1)T
‖x+σe1‖2
= wT folgt:
2wT x =2(x + σe1)
T x
‖x + σe1‖2
= ‖x + σe1‖2
die nochmalige Nutzung von (5.11) ergibt
2wwT x = x + σe1
⇔ x − 2wwT x = −σe1
was zu zeigen war.
Bemerkung. Um Stellenausloschungen zu vermeiden, wird in (5.11) σ =sgn(x1) ‖x‖2 gewahlt, d.h. z.B. fur x = (−3, 1, 5)T ist σ = −
√35
5.3.3 Algorithmus zur Konstruktion der Faktorisierungmittels Householder-Transformationen
Ausgehend von A = A(1) ∈ Rn×m sollen sukzessive Matrizen der Form
A(j) =
a(j)11 a
(j)12 · · · a
(j)1m
. . .
a(j)j−1j−1 a
(j)j−1m
a(j)jj · · · a
(j)jm
......
a(j)nj · · · a
(j)nn
, j = 1, . . . ,m + 1 (5.13)
berechnet werden, sodass am Ende mit A(m+1) = S die verallgemeinerte obereDreiecksmatrix vorliegt.
87
Die Matrizen der Form (5.13) erhalt man fur j = 1, . . . ,m durch Transfor-mationen der Form
A(j+1) = HjA(j), Hj =
[Ej−1 0
0 Hj
]
mit Hj = En−(j−1) − 2wjwTj , ‖wj‖ = 1, El ist Einheitsmatrix aus R
l×l, und
wj ∈ Rn−(j−1) ist so zu wahlen, dass gilt
Hj
a(j)jj...
a(j)nj
︸ ︷︷ ︸
a
= σ
10...0
, wj =a + sgn(a1) ‖a‖2 e1
‖a + sgn(a1) ‖a‖2 e1‖2
, a, e ∈ Rn−(j−1)
Die Matrizen H1, . . . , Hm sind aufgrund der Eigenschaften der Matrizen H1, . . . , Hm
orthogonal und symmetrisch, sodass man mit
S = HmHm−1 · · · · · H1A, Q = H1H2 · · · · · Hm
die Faktorisierung A = QS konstruiert hat, da Q als Produkt von orthogo-nalen Matrizen auch eine orthogonale Matrix ist.
88
5.4 Anwendungen der QR-Zerlegung14.Vorle-sungam2.6.2010
5.4.1 Losung eines linearen Gleichungssystems
Ax = b, A ∈ Rn×nregular
⇒ mit A = QR,Q,R ∈ Rn×n Q orthogonal, R obere Dreiecksmatrix
Ax = b ⇔ Qy = b, y = QT b, Rx = y durch Ruckwartseinsetzen
5.4.2 Ausgleichsprobleme
Gegeben: Wertepaare (yk, xk), k = 1, . . . , n (z.B. Ergebnisse von Messungen)Gesucht: funktionaler Zusammenhang
yk = f(xk), k = 1, . . . , n (5.14)
Wobei man f nicht kennt. Man kann mit einem Mehrparameteransatz
f = f(x, r1, r2, . . . , rm), n ≫ m
und versucht (5.14) im quadratischen Mittel zu losen
minr∈Rm
n∑
k=1
(yk − f(xk, r1, . . . , rm))2
Methode der kleinsten Quadrate (Gauß)
Lineares Ausgleichsproblem als Spezialfall
f lineare Funktion von ~r. Wir setzen
fk(~r) := f(xk, ~r), ~r ∈ Rm, ~y = (y1, . . . , yn)T
und damit ergibt sich als Ansatz
f1(~r)...
fn(~r)
= M~r, M ∈ R
n×m
Beispiel. (yk, xk), k = 1, . . . , 4 quadratischer Ansatz
y = r1 + r2x + r3x2
M =
1 x1 x21
1 x2 x22
1 x3 x23
1 x4 x24
89
Lineares Ausgleichsproblem
min~r∈Rm
‖M~r − ~y‖22 (5.15)
F (~r) = ‖M~r − ~y‖22 = 〈M~r − ~y,M~r − ~y〉 ist differenzierbar und konvex, dar-
aus ergibt sich als notwendige und hinreichende Bedingung fur das gesuchteMinimum
∇F (~r) = 0 ,
nach einer einfachen Rechnung ergibt sich daraus
MT M~r = MT~y (5.16)
Im Folgenden werden die Vektorpfeile wieder weggelassen, da dort aus demKontext klar werden sollte, ob es sich um einen Vektor oder einen Skalarhandelt.
Satz 5.16. Das lineare Ausgleichsproblem (5.15) hat mindestens eine Losungr0. Fur jede andere Losung r gilt Mr = Mr0. Das Residuum d = y−Mr0 isteindeutig bestimmt und erfullt MT d = 0. Die Gleichung (5.16) ist notwendigund hinreichend dafur, dass r Losung von (5.15) ist
Beweis. Sei Im(M) Bild von M es gilt
Rn = Im(M) ⊕ Im(M)⊥
also kann y eindeutig zerlegt werden als
y = s + d, s ∈ Im(M), d ∈ Im(M)T
Nach Definition des Bildes von M gibt es zu s mindestens ein r0 mit
Mr0 = s
außerdem gilt〈 Mr
︸︷︷︸
∈Im(M)
, d︸︷︷︸
∈Im(M)⊥
〉 = 0 ∀r ∈ Rm
und somit⟨r,MT d
⟩= 0 und MT d = 0
Es folgtMT y = MT s + MT d
︸ ︷︷ ︸
=0
= MT Mr0
⇒ r0 ist eine Losung von (5.16).
90
Sei nun r eine weitere Losung, d.h.
MT Mr = MT y
Dann ist d = y − Mr orthogonal zu Im(M), denn
〈Mz, d〉 =⟨z,MT d
⟩=
⟨z,MT y − MT Mr
⟩= 0 ∀z
s = Mr gehort zu Im(M) und
y = Mr + (y − Mr) = s + d
ist damit wieder eine Zerlegung von y in s ∈ Im(M), d ∈ Im(M)⊥ und ausder Eindeutigkeit der Zerlegung folgt:
Mr = Mr0
Bestimmung der Losung des Minimumproblems
(i) Losung des SystemsMT Mr = MT y
MT M ist symmetrisch und positiv semidefinit, da⟨r,MT Mr
⟩= 〈Mr,Mr〉 ≥ 0
Die Gleichheit mit Null kann nur eintreten, wenn Mr = 0. Hat M denvollen Rang, d.h. bei n ≥ m also den Rang m, dann kann r = 0 nurgelten bei
⟨r,MT Mr
⟩= 0. Also ist MT M dann positiv definit. D.h.
Cholesky-Zerlegung ist moglich.
• dazu notwendig: Berechnung von MT M (12m2n Multiplikationen),
bei n ≫ m ist der Aufbau von MT M teurer als das CholeskyVerfahren (1
6m3 Multiplikationen)
• MT M oft schlecht konditioniert, Fehler in y werden durch die Kon-dition κ(MT M) verstarkt
• besser ist Methode, die nur M verwendet
(ii) Bestimmung von r mittels QR-Zerlegung
Gute Eigenschaft von orthogonalen Transformationen
κ2(Q) = ‖Q‖2
∥∥Q−1
∥∥
2= ‖Q‖2
∥∥QT
∥∥
2= 1
D.h. sie verstarken nicht den Fehler der Großen, auf die sie angewendetwerden.
91
Satz 5.17. Sei M ∈ Rn×m, n ≥ m, von vollem Rang und Q ∈ R
n×n ortho-gonal, sodass
QT M =
(R
0
)
QT y =
(y1
y2
)
mit y1 ∈ Rm, y2 ∈ R
n−m und einer invertierbaren oberen Dreiecksmatrix R ∈R
m×m gilt. Dann ist r = R−1y1 die Losung des linearen Ausgleichsproblemsminr∈Rm ‖Mr − y‖2
2
Beweis. Q ist isometrisch ⇒ ‖y − Mr‖2 =∥∥QT (y − Mr)
∥∥
2, daraus folgt:
‖y − Mr‖22 =
∥∥QT (y − Mr)
∥∥
2=
∥∥∥∥
(y1 − Rr
y2
)∥∥∥∥
2
= ‖y1 − Rr‖2 + ‖y2‖2 ≥ ‖y2‖2 ∀r ∈ Rm
Wahlt man r = R−1y1, so hat man die Losung.
Bemerkung. Residuum d erfullt ‖d‖2 = ‖y2‖2.
92
Kapitel 6
Die iterative Losung linearerGleichungssysteme
15.Vorle-sung3.06.10
Neben der schon beschriebenen direkten Losung linearer Gleichungssystemedurch den Gaußschen Algorithmus oder durch bestimmte Matrix-Faktorisie-rungen ist es oft sinnvoll, lineare Gleichungssysteme
Ax = b (6.1)
mit der regularen Matrix a vom Typ n × n und b ∈ Rn iterativ zu losen
(oBdA sei akk 6= 0, k = 1, . . . , n).Zerlegt man A mit der regularen Matrix B in der Form A = B + (A − B)dann gilt fur (6.1).
Ax = b ⇔ Bx = (B − A)x + b ⇔ x = (E − B−1A)x + B−1b
wahlt man B als leicht invertierbare Matrix, dann ergibt sich im Fall derKonvergenz der Fixpunktiteration
xk = (E − B−1A)xk−1 + B−1b, k = 1, 2, . . . (6.2)
bei Wahl irgendeiner Startnaherung x0 ∈ Rn mit dem Grenzwert x = limk→∞ xk
die Losung des linearen Gleichungssystems (6.1). Die Losung ist ein Fixpunktder Abbildung
F : Rn → R
n : x 7→ (E − B−1A)x + B−1b (6.3)
Die Matrix S = (E − B−1A) heißt Iterationsmatrix. Konvergenz liegt dannvor, wenn limk→∞ ‖x − xk‖ = 0 ist.Mit x und δxk = x − xk folgt
δxk = (E − B−1A)δxk−1 = (E − B−1A)kδx0
93
also gilt fur irgendeine Vektornorm und eine dadurch induzierte Matrixnorm
‖δxk‖ ≤∥∥Sk
∥∥ ‖δx0‖ (6.4)
Damit konvergiert das Losungsverfahren, wenn limk→∞ Sk = 0 bzw. limk→∞∥∥Sk
∥∥ =
0 gilt.Hilfreich zur Konvergenzuntersuchung ist der
Satz 6.1. Sei S eine (n×n)-Matrix. Dann sind folgende Aussagen aquivalent:
(a) Der Spektralradius r(S) von S ist kleiner als 1
(b) Sk → 0 fur k → ∞
(c) Es gibt eine Vektornorm, sodass sich fur die induzierte Matrixnorm ‖S‖ <
1 ergibt.
(d) S − λE ist fur alle λ mit |λ| ≥ 1 regular
Beweis. (Auszugsweise) a ⇒ b Betrachten die verallgemeinerte JordanscheNormalform S = T−1JT mit einer regularen Matrix T und J mit den Jordan-Blocken Ji
J =
J1
. . .
Jr
, Ji =
λi ǫ
λi ǫ. . . . . .
λi ǫ
fur die Eigenwerte λ1, . . . , λr von S, wobei 0 < ǫ < 1 − |λi| fur i = 1, . . . , rgewahlt wurde. Es gilt
∥∥Sk
∥∥ =
∥∥TJkT−1
∥∥. Die Potenzen von J enthalten fur
wachsendes k immer großere Potenzen von λi, sodass wegen |λi| < 1 fur alleEigenwerte
∥∥Sk
∥∥ gegen null geht.
a ⇒ c Mit der Zeilensummennorm gilt wegen der Voraussetzung zum Spek-tralradius von S, der gleich dem von J ist, und der Wahl von ǫ
‖J‖∞ = maxi=1,...,n
‖Ji‖∞ < 1
Durch‖x‖T := ‖Tx‖∞ , (x ∈ R
n)
ist eine Norm auf dem Rn erklart. Fur die durch ‖·‖T induzierte Matrixnorm
gilt ‖S‖T < 1, denn es gilt
‖Sx‖T = ‖TSx‖∞ = ‖JTx‖∞ ≤ ‖J‖∞ ‖Tx‖∞ = ‖J‖∞ ‖x‖T
94
und damit‖Sx‖t
‖x‖T≤ ‖J‖∞ < 1 fur alle x 6= 0.
c ⇒ d Annahme: S −λE singular, d.h. ∃x 6= 0 : (S −λE)x = 0, daraus folgt
Sx = λx ⇔ ‖Sx‖T = |λ| ‖x‖T ⇔ ‖Sx‖T
‖x‖T
= |λ| ≥ 1
andererseits ist 1 > ‖S‖T ≥ ‖Sx‖T
‖x‖T, d.h. es ergibt sich ein Widerspruch und
die Annahme war falsch. Damit ist S − λE regular fur |λ| ≥ 1.
Als Folgerung des Satzes 6.1 erhalt man das folgende Konvergenzkriterium
Satz 6.2. Seien A,B regulare (n × n)-Matrizen. Die Iteration (6.2) kon-vergiert fur alle Startwerte x0 genau dann gegen die eindeutig bestimmteLosung x von Ax = b, wenn der Spektralradius r = r(S) der Iterationsma-trix S = (E − B−1A) kleiner als 1 ist. Ist S diagonalisierbar, dann gilt
‖xk − x‖ ≤ Crk, C = const ∈ R (6.5)
Fur die weitere Betrachtung konkreter Verfahren stellen wir die quadratischeMatrix A = (aij) als Summe der unteren Dreiecksmatrix L = (lij), derDiagonalmatrix D = (dij) und der oberen Dreiecksmatrix U = (uij)
A = L + D + U (6.6)
mit
lij =
{aij i > j
0 i ≤ j, uij =
{0 i ≥ j
aij i < jdij =
{aij i = j
0 i 6= j
dar. Bei Iterationsverfahren der Form (6.2) ist fur den Aufwand naturlichdie einfache Invertierbarkeit von B entscheidend. Das wird bei den nun zudiskutierenden Verfahren auch berucksichtigt.
6.1 Jacobi-Verfahren oder Gesamtschrittver-
fahren
Die Wahl von B = D ergibt die Iterationsmatrix
S = E − B−1A = −D−1(L + U) =
0 a12
a11. . . a1n
a11a21
a220
.... . .
an1
ann0
(6.7)
95
Das Verfahren (6.2) mit der durch die Wahl von B = D definierten Iterati-onsmatrix (6.7) heißt Jacobi-Verfahren oder Gesamtschrittverfahren.Zur besseren Darstellung von Details der Iterationsverfahren setzen wir denIterationsindex k nach oben in Klammern, also
x(k) = xk ∈ Rn,
und die Komponenten von x(k) bezeichnen wir durch x(k)j , j = 1, . . . , n. Damit
ergibt sich fur die Jacobi-Verfahren koordinatenweise
x(k)j =
1
ajj
(
bj −n∑
j 6=i=1
ajix(k−1)i
)
, j = 1, . . . , n, k = 1, 2, . . .
Zur Konvergenz des Jacobi-Verfahrens gilt der
Satz 6.3. Sei A eine strikt diagonal dominante (n×n)-Matrix. Dann ist derSpektralradius kleiner als 1 und das Verfahren konvergiert.
Beweis.S = −D−1(L + U)
Zeilensummen von Sn∑
j=1
sij =1
aii
n∑
j 6=i
aij,
aufgrund der strikten Diagonaldominanz ist
n∑
i6=j=1
∣∣∣∣
aij
aii
∣∣∣∣< 1 ⇒ ‖S‖∞ < 1 ⇒ r(S) < 1
Bei der numerischen Losung von elliptischen Randwertproblemen treten oftMatrizen auf, die nicht strikt diagonal dominant sind, aber die folgendenetwas schwacheren Eigenschaften besitzen.
Definition 6.4. (a) Eine Matrix vom Typ (n × n) heißt schwach diagonaldominant, wenn gilt
|aii| ≥n∑
j 6=i=1
|aij| .
(b) Eine (n × n)-Matrix A = (aij) heißt irreduzibel, wenn fur alle i, j ∈{1, 2, . . . , n} entweder aij 6= 0 oder eine Indexfolge i1, . . . , is ∈ {1, . . . , n}existiert, sodass aii1ai1i2 · · · aisj 6= 0 ist. Andernfalls heißt A reduzibel.
96
(c) Eine (n×n)-Matrix A = (aij) heißt irreduzibel diagonal dominant, wennsie irreduzibel ist und wenn es einen Index l ∈ {1, . . . , n} mit
|all| >
n∑
l 6=j=1
|alj|
gibt.
Bemerkung. 1. Man kann entscheiden, ob eine Matrix reduzibel oderirreduzibel ist, indem man fur A = (aij)i,j=1,...,n einen Graphen mitn Knoten konstruiert, indem eine gerichtete Kante von Knoten i zumKnoten j existiert, wenn aij 6= 0 ist.
Kann man in diesem Graphen ausgehend von einem Knoten alle an-deren auf einem gerichteten Weg (Folge von gerichteten Kanten) errei-chen, ist A irreduzibel, andernfalls reduzibel.
2. Ein weiteres Kriterium zur Entscheidung ob A vom Typ n × n irredu-zibel oder reduzibel ist, ist Folgendes:
Lemma 6.5. Die (n × n)-Matrix A ist irreduzibel, falls es keine Per-mutationsmatrix P vom Typ n×n gibt, so dass bei gleichzeitiger Zeilen-und Spaltenpermutation
P T AP =
(F 0G H
)
gilt, wobei F und H quadratische Matrizen sind und 0 eine Nullmatrixist, andernfalls ist A reduzibel.
Satz 6.6. Fur eine irreduzibel diagonal dominante Matrix A ist das Jacobi-Verfahren konvergent.
Beweis. aufwandig (siehe z.B. Schwarz)
6.2 Gauß-Seidel-Iterationsverfahren oder Ein-
zelschrittverfahren
Wahlt man ausgehend von der Matrixzerlegung (6.6) B = L+D, dann heißtdas Iterationsverfahren (6.2) Gauß-Seidel- Verfahren oder Einzelschrittver-fahren, d.h. es ergibt sich
x(k) = (E − B−1A)︸ ︷︷ ︸
S
x(k−1) + B−1b = (L + D)−1(−Ux(k−1) + b), k = 1, 2, . . .
(6.8)
97
Die Matrix B = L + D ist eine regulare untere Dreiecksmatrix und damitleich zu invertieren, was aber keine Arbeit bedeuten wird, wie wir etwasspater sehen werden.
Satz 6.7. Das Gauß-Seidel-Verfahren konvergiert fur strikt diagonal domi-nante Matrizen A fur beliebige Startiterationen x(0) ∈ R
n
Beweis. Es ist
S = E − B−1A, λv = Sv = (E − B−1A)v = −(L + D)−1Uv, v 6= 0
fur einen EW λ mit dem EV v bzw.
λ(L + D)v = −Uv; |vk| = max1≤i≤n
|vi| > 0
Wir betrachten die k-te Zeile:
λ(akkvk +n∑
j=1
akjvj) = −n∑
j=1
akjvj
à λ
(
1 +n∑
k>j=1
akjvj
akkvk
)
= −n∑
k<j=1
akjvj
akkvk
,
∣∣∣∣
vj
vk
∣∣∣∣≤ 1
⇔ λ(1 + α) = β, |α| , |β| < 1 da A strikt diagonal dominant
⇔ λ =β
1 + αà |λ| =
|β||1 + α| ≤
|β|1 − |α|
Aus der strengen Diagonaldominanz folgt schließlich
|α| + |β| =
∣∣∣∣∣
n∑
k>j=1
akjvj
akkvk
∣∣∣∣∣+
∣∣∣∣∣
n∑
k<j=1
akjvj
akkvk
∣∣∣∣∣≤
n∑
k 6=j=1
∣∣∣∣
akj
akk
∣∣∣∣< 1,
woraus
1 >|β|
1 − |α| ≤ |λ|
fur alle EW λ folgt (r(S) < 1)
Bemerkung 6.8. Ebenso wie beim Jacobi-Verfahren kann man die Voraus-setzung der strikten Diagonaldominanz von A abschwachen.Das Gauß-Seidel-Verfahren ist fur irreduzibel diagonal dominante MatrizenA konvergent.
98
Wenn man das Gauß-Seidel Verfahren (6.8) in der aquivalenten Form
x(k) = D−1(−Lx(k) − Ux(k−1) + b), k = 1, 2, . . . (6.9)
aufschreibt, erkennt man bei der koordinatenweisen Berechnung der neuenIteration
x(k)j =
1
ajj
(
bj −j−1∑
i=1
ajix(k)i −
n∑
i=j+1
ajix(k−1)i
)
, j = 1, 2, . . . , n, k = 1, 2, . . .
(6.10)zwar, dass auf beiden Seiten der Formeln x(k) vorkommen. Allerdings benotigtman zur Berechnung der j-ten Komponenten von x(k) nur die Komponen-ten x
(k)1 , . . . , x
(k)j−1 der vorigen Iteration. Diese kennt man aber bereits. Damit
kann man die Formel (6.10) fur j = 1, . . . , n sukzessiv zum Update derKoordinaten von x anwenden. Man hat also mit (6.10) eine explizite Berech-nungsvorschrift und braucht damit B = L + D nicht wirklich zu invertieren.
6.3 Verallgemeinerung des Gauß-Seidel-Verfahrens
Wahlt man S = Sω = (D + ωL)−1[(1 − ω)D − ωU ] = E − ω(D + ωL)−1A,bzw. B = ω(D + ωL)−1, dann hat man mit
x(k) = Sωx(k−1) + B−1b, k = 1, 2, . . . , ω ∈]0, 2[
das Gauß-Seidel-Verfahren mit Relaxation erklart. Fur ω > 1 spricht manvon vom sukzessiven Uberrelaxtionsverfahren auch SOR-Verfahren genannt.Das SOR-Verfahren konvergiert in allen Fallen, in denen das Gauß-Seidel-Verfahren (ω = 1) konvergiert.Allerdings kann man in vielen Fallen mit einer Wahl von ω > 1 eine schnellereKonvergenz als mit dem Gauß-Seidel-Verfahren erreichen.
99
Kapitel 7
Iterative Losung vonnichtlinearenGleichungssystemen
16.Vorle-sung9.06.10
Im Folgenden geht es darum, in der Regel nichtlineare Gleichungen oderGleichungssysteme zu losen. Ist G eine Abbildung aus dem R
n in den Rn,
bedeutetG(x) = 0 (7.1)
gerade ein Gleichungssystem zur Bestimmung einer Nullstelle x = (x1, . . . , xn)T ∈R
n der Abbildung G. Definiert man ausgehend von G die Abbildung
F (x) := G(x) + x
Dann ist die Losung von (7.1) gleichbedeutend mit der Bestimmung einesFixpunktes x von F , also
F (x) = x ⇔ G(x) = 0 (7.2)
7.1 Die Fixpunktiteration zur Losung nicht-
linearer Gleichungen
Wenn man keinerlei Vorstellung von der Losung der Gleichung (7.2) hat,findet man mit der Folge
(xk), x0 ∈ D ⊂ Rn, xk+1 = F (xk), k = 0, 1, . . .
eine Folge, die, wenn sie konvergiert, im Falle der Stetigkeit der Abbildunggegen einen Fixpunkt von F kovergiert.
100
Die Grundlagen der iterativen Losung von Gleichungen (Gleichungssystemesollen nur nur fur den Fall n = 1 dargestellt werden.
Definition 7.1. Sei f : I → I eine Funktion, die das reelle Intervall I insich abbildet. Jede Losung der Gleichung
x = f(x) (7.3)
heißt Fixpunkt von f . Die Gleichung (7.3) wird Fixpunktgleichung genannt.
Definition 7.2. Eine auf einer Teilmenge D ⊂ R definierte Funktion f :D → R heißt Kontraktion, wenn eine Konstante L ∈ [0, 1[ existiert, sodassfur alle x1, x2 ∈ D
|f(x1) − f(x2)| ≤ L |x1 − x2|mit einer von x1, x2 unabhangigen Konstanten L < 1, d.h. f ist Kontraktion.
Satz 7.3. Sei f : I → I eine reellwertige Funktion, die ein abgeschlossenesIntervall I in sich abbildet und es gelte fur alle x1, x2 ∈ I die Ungleichung
|f(x1) − f(x2)| ≤ L |x1 − x2| (7.4)
mit einer von x1, x2 unabhangigen Konstanten L < 1, d.h. f ist Kontraktion.Dann hat f genau einen Fixpunkt x ∈ I und die durch die Fixpunktiterationxk+1 = f(xk) definierte Iterationsfolge konvergiert fur jeden Anfangspunktx0 ∈ I gegen diesen Fixpunkt
Beweis. Analysis
Bemerkung 7.4 (Banachscher Fixpunktsatz). Ist F : A → A,A ⊂ Rn
abgeschlossen, und gilt
‖F (x1) − F (x2)‖ ≤ L ‖x1 − x2‖mit L < 1 fur alle x1, x2 ∈ A, dann hat F genau einen Fixpunkt x ∈ A mit
F (x) = x
und die durch xk+1 = F (xk) definierte Iterationsfolge konvergiert fur jedenAnfangspunkt x0 ∈ A gegen diesen Fixpunkt. (Rn ist mit der Metrik ρ(x, y) =‖x − y‖ ein Banach-Raum.)
Bemerkung 7.5. Aus dem Banachschen Fixpunktsatz ergeben sich die Feh-lerabschatzungen
‖xk − x‖ ≤ Lk
1 − L‖x1 − x0‖ A-priori-Abschatzung (7.5)
‖xk − x‖ ≤ 1
1 − L‖xk+1 − xk‖ A-posteriori-Abschatzung (7.6)
101
Die Kontraktivitat ist essentiell fur die Berechnung von Fixpunkten. Unterbestimmten Voraussetzungen kann man die Existenz einer Kontraktion zei-gen.
Satz 7.6. Es sei G ⊂ R offen und f : G → R stetig diff’bar mit einemFixpunkt x ∈ G. Wenn |f ′(x)| < 1 gilt, dann existiert ein abgeschlossenesIntervall D ⊂ G mit x ∈ D und f(D) ⊂ D, auf dem f eine Kontraktion ist.
Beweis. Da f ′ stetig auf der offenen Menge G ist, existiert eine offene Um-gebung Kx,ǫ = {x| |x − x| < ǫ} in G, auf der die Betrage der Ableitung vonf immer noch kleiner als 1 sind. Setzt man D = [x− ǫ
2, x+ ǫ
2], so gilt fur alle
x1, x2 ∈ D aufgrund des Mittelwertsatzes der Differentialrechnung
|f(x1) − f(x2)| ≤ k |x1 − x2|
mit k = maxξ∈D |f ′(ξ)| < 1
Bemerkung 7.7. Ist die Voraussetzung |f ′(x)| < 1 des Satzes 7.6 nichterfullt, findet man keine Kontraktion. Ist |f ′(x)| > 1 dann gilt in der Nahevon x
|f(x) − f(x)| > |x − x|
das rechtfertigt die
Definition 7.8. Ein Fixpunkt x heißt anziehender Fixpunkt, wenn |f ′(x)| <
1 gilt, und x heißt abstoßender Fixpunkt, wenn |f ′(x)| > 1 ist.
7.2 Das Newton-Verfahren zur Losung nicht-
linearer Gleichungen
Die Grundidee der Losung der nichtlinearen Gleichung besteht in der Naherungeiner existierenden Nullstelle durch die sukzessive Losung linearer Aufga-ben. Man approximiert die diff’bare Funktion f in der Nahe eines geeignetenStartwertes x0 durch die Tangentenfunktion
g(x) = f(x0) + f ′(x0)(x − x0) ≈ f(x)
und bestimmt die Nullstelle von g, also x1 mit g(x1) = 0, d.h.
x1 = x0 −f(x0)
f ′(x0)
102
und allgemein erhalt man mit
xk+1 = xk −f(xk)
f ′(xk), k = 0, 1, 2, . . . (7.7)
eine Newton-Folge, die im Falle der Konvergenz gegen eine Nullstelle vonf geht. Die Folge (7.7) kann man auch anders erhalten. Man definiert dieHilfsfunktion
g(x) = x − f(x)
f ′(x)(7.8)
wobei man f ′(x) 6= 0 voraussetzt. Ist g eine Kontraktion mit g(I) ⊂ I, dannfolgt aus dem Banachschen Fixpunktsatz, dass die Folge xk+1 = g(xk) fureinen beliebigen Startwert x0 ∈ I (abgeschlossenes Intervall) gegen den in I
existierenden Fixpunkt x von g konvergiert. Und die Fixpunkt-Folge
xk+1 = g(xk) = xk −f(xk)
f ′(xk)
ist eine Newton-Folge zur Berechnung einer Nullstelle von f . Es gilt derfolgende
Satz 7.9. Sei f : I → R eine auf einem Intervall I ⊃ [x0 − r, x0 + r], r > 0,definierte, zweimal stetig diff’bare Funktion mit f ′(x) 6= 0 fur alle x ∈ I.Weiterhin existiere eine reelle Zahl k, 0 < k < 1, mit
∣∣∣∣
f(x)f ′′(x)
f ′(x)2
∣∣∣∣≤ k ∀x ∈ I
und ∣∣∣∣
f(x0)
f ′(x0)
∣∣∣∣≤ (1 − k)r
Dann hat f genau eine Nullstelle x ∈ I und die Newton-Folge (7.7) konver-giert quadratisch gegen x, d.h. es gilt
|xk+1 − x| ≤ C(xk − x)2 ∀k = 0, 1, . . .
mit einer Konstanten C. Außerdem gilt die Fehlerabschatzung
|xk − x| ≤ |f(xk)|M
, mit 0 < M < minx∈I
|f ′(x)|
Beweis. Folgt aus dem Banachschen Fixpunktsatz 7.3 und dem Satz 7.6 uberdie Existenz einer Kontraktion.
103
Die quadratische Konvergenz folgt aus
xk+1 − x = xk −f(xk)
f ′(xk)− x
= xk − x − f(xk) −=0
︷︸︸︷
f(x)
f ′(xk)
=1
f ′(xk)[f ′(xk)(xk − x) − f(xk) + f(x)]︸ ︷︷ ︸
Fehler der Ordnung O(|xk−x|2)
⇒ |xk+1 − x| ≤ C(xk − x)2
Bemerkung 7.10. Die Voraussetzungen des Satzes 7.9 garantieren die Kon-traktivitat der Hilfsfunktion g(x) = x− f(x)
f ′(x)in einer Umgebung von x. D.h.
man ist mit dem Newton-Verfahren immer dann erfolgreich, wenn man nurnah genug an der Nullstelle die Iteration beginnt (x0 nah bei x)In diesem Fall ist das Newton-Verfahren auch noch sehr schnell aufgrund derquadratischen Konvergenz.
7.3 Newton-Verfahren fur nichtlineare Glei-
chungssysteme F (x) = 017.Vorle-sung10.06.10
Satz 7.11. F : D → Rn, D ⊂ R
n sei zweimal stetig partiell diff’bar undbesitze eine Nullstelle x ∈ D. Weiterhin sei F ′(x) fur jedes x ∈ D regular.Dann folgt:Es gibt eine Umgebung U von x, sodass die Newton-Folge
xk+1 = xk − [F ′(xk)]−1F (xk), k = 0, 1, 2, . . . (7.9)
von einem beliebigen Startpunkt x0 ∈ U ausgehend gegen die Nullstelle x
konvergiert.Die Konvergenz ist quadratisch, d.h. es gibt eine Konstante C > 0 mit
‖xk − x‖ ≤ C ‖xk−1 − x‖2, k = 1, 2, . . .
und es gilt die Fehlerabschatzung
‖xk − x‖ ≤ ‖F (xk)‖ supx∈D
∥∥[F ′(x)]−1
∥∥
wobei auf der rechten Seite die Matrixnorm ‖A‖ =√∑n
i,j=1 a2ij fur eine
(n × n)-Matrix A = (aij) verwendet wurde.
104
Beweis. Analog zum Beweis von Satz 7.9 im eindimensionalen Fall.
Beispiel. Zur Bestimmung der Stutzstellen (Nullstellen des n-ten Tschebyscheff-Polynoms) x1, . . . , xn und der Integrationsgewichte σ1, . . . , σn ist das Glei-chungssystem
n∑
k=1
σkxjk =
∫ 1
−1
xjdx, j = 0, 1, . . . , 2n − 1 (7.10)
zu losen. Mit bj =∫ 1
−1xjdx = 1
j+1(1 − (−1)j+1) bedeutet, dass die Nullstelle
der Abbildung F : R2n → R
2n
F (σ1, . . . , σn, x1, . . . , xn) =
σ1x01 + · · · + σnx0
n − b0...
σ1x2n−11 + · · · + σnx
2n−1n − b2n−1
zu bestimmen. Mit der Ableitungsmatrix F ′ = (Jik)
Jik =
xi−1k , 1 ≤ k ≤ n, i = 1, . . . , 2n0, i = 1, n + 1 ≤ k ≤ 2n
σk−n(i − 2)xi−2k−n, i = 2, . . . , 2n, n + 1 ≤ k ≤ 2n
kann man mit dem Newton-Verfahren (7.9) versuchen, das Gleichungssystem(7.10) zu losen.
7.4 Gedampftes Newton-Verfahren
Betrachtet man
xk+1 = xk − α[F ′(xk)]−1F (xk), k = 0, 1, . . .
mit α ∈]0, 1[, spricht man von einem gedampften Newton- Verfahren.Mit gedampften Newton-Verfahren erreicht man mitunter Konvergenz derNewton-Folge, wenn das Standard-Newton-Verfahren (α = 1) versagt.Es gilt dann mit zk+1 = xk+1 − xk das Gleichungssystem
F ′(xk)zk+1 = −αF (xk)
zu losen, und wie ublich erhalt man mit
xk+1 = zk+1 + xk
die neue Iterierte.
105
