Embed Size (px)
Citation preview
Skript Numerik 1a
Vorlesung von Prof. Dr. Karsten Urban,Sommersemester 2005, Uni Ulm
Mitschrift erstellt mit LATEX von:Michael Moers
Jochen GernhardMoritz TitzeDaniel SmithAaron Spettl
Jan-Philipp Schmidt
Revision: 18. Juni 20061
1Fehler an [email protected] oder [email protected]
Inhaltsverzeichnis
Was ist Numerik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Rechnen auf digitalen Rechenanlagen 6§1 Zahlendarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1.2 Definition: Festpunktzahlen . . . . . . . . . . . . . . . . . 71.1.3 Definition: normalisierte Gleitpunktdarstellung . . . . . . 8
§2 Rundung und Maschinengenauigkeit . . . . . . . . . . . . . . . . . 91.2.1 Standardrundung . . . . . . . . . . . . . . . . . . . . . . . 91.2.2 Banker’s Rule (IEEE Norm P754) . . . . . . . . . . . . . 101.2.3 Definition: relativer/absoluter Fehler . . . . . . . . . . . . 111.2.4 Definition: relativer/absoluter Rundungsfehler . . . . . . . 111.2.5 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.2.6 Definition: (relative) Maschinengenauigkeit . . . . . . . . 121.2.7 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 12
§3 Gleitpunktarithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . 121.3.1 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
§4 Fehlerfortpflanzung bei elementaren Rechenoperationen . . . . . . . 134.1 Multiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.2 Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144.3 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
§5 Kondition und Stabilitat . . . . . . . . . . . . . . . . . . . . . . . . 161.5.1 Beispiel: Summenbildung . . . . . . . . . . . . . . . . . . 161.5.2 Beispiel: Bestimmung des Schnittpunktes zweier Geraden 161.5.3 Beispiel: Berechnung des Kohleaushubs . . . . . . . . . . 171.5.4 Definition: relative/absolute Kondition . . . . . . . . . . . 171.5.5 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5.6 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.5.7 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191.5.8 Definition: Stabilitat . . . . . . . . . . . . . . . . . . . . . 201.5.9 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5.10 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5.11 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2 Direkte Loser linearer Gleichungssysteme 22§1 Stabilitatsanalyse linearer Gleichungssysteme . . . . . . . . . . . . 23
2.1.1 Definition: Kondition einer Matrix . . . . . . . . . . . . . 23
1
2.1.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 232.1.3 Definition: Spektrum, Spektralradius . . . . . . . . . . . . 232.1.4 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.1.5 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
§2 Dreiecksmatrizen, Ruckwartseinsetzen . . . . . . . . . . . . . . . . 252.2.1 Definition: Dreiecksmatrix . . . . . . . . . . . . . . . . . . 252.2.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2.3 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
§3 Gauß-Elimination und LR-Zerlegung . . . . . . . . . . . . . . . . . 262.3.1 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3.2 Algorithmus (Gauß-Algorithmus) . . . . . . . . . . . . . . 272.3.3 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.4 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3.5 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.3.6 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 30
§4 Cholesky-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.4.1 Definition: positiv definit . . . . . . . . . . . . . . . . . . 312.4.2 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.4.3 Satz (Kriterium von Hurwitz) . . . . . . . . . . . . . . . . 312.4.4 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.4.5 Satz (Cholesky-Zerlegung) . . . . . . . . . . . . . . . . . . 332.4.6 Korollar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.4.7 Algorithmus (Cholesky-Zerlegung) . . . . . . . . . . . . . 33
3 Lineare Ausgleichsrechnung 34§1 Methode der kleinsten Fehlerquadrate . . . . . . . . . . . . . . . . . 34
3.1.1 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 353.1.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 353.1.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
§2 Normalengleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2.1 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2.2 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
§3 QR-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 373.3.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 38
§3.1 Givens-Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.3.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.3.4 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 393.3.5 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 39
§3.2 Householder-Spiegelungen . . . . . . . . . . . . . . . . . . . . . . 403.3.6 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
§4 Singularwertzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . 433.4.1 Satz (SVD) . . . . . . . . . . . . . . . . . . . . . . . . . . 433.4.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 443.4.3 Definition: Moore-Penrose-/Pseudo-Inverse . . . . . . . . 453.4.4 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.4.5 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2
4 Iterative Verfahren zur Losung linearer Gleichungssysteme 47§1 Große Gleichungssysteme und dunnbesetzte Matrizen . . . . . . . . 47
4.1.1 Beispiel: Die schwingende Membran . . . . . . . . . . . . 474.1.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 494.1.4 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 504.1.5 Definition: Dunn-besetzte/sparse Matrizen . . . . . . . . . 514.1.6 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 51
§2 Klassische Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . 514.2.1 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.2.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 53
§2.1 Das Richardson-Verfahren . . . . . . . . . . . . . . . . . . . . . . 53§2.2 Das Jacobi-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.3 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2.4 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 544.2.5 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 54
§2.3 Das Gauß-Seidel-Verfahren . . . . . . . . . . . . . . . . . . . . . . 554.2.6 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2.7 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.2.8 Definition: A-adjungierte Matrix, A-positiv, A-s.p.d. . . . 564.2.9 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 564.2.10 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.2.11 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.2.12 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 57
§3 Gradienten-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3.1 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 594.3.3 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.3.4 Lemma (Kantorowitsch-Ungleichung) . . . . . . . . . . . 614.3.5 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.3.6 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 62
§4 Verfahren der konjugierten Gradienten . . . . . . . . . . . . . . . . 634.4.1 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 634.4.2 Algorithmus (cg-Verfahren) . . . . . . . . . . . . . . . . . 644.4.3 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.4.4 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 644.4.8 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.4.9 Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.4.10 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . 684.4.11 Satz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
§5 Vorkonditionierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.5.1 Algorithmus (vorkonditioniertes cg-Verfahren, pcg) . . . . 714.5.2 Bemerkung . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Stichwortverzeichnis 72
3
Was ist Numerik?
Numerik behandelt mathematische Verfahren, Algorithmen, Methoden zur Lo-sung von ”Problemen“ mit Hilfe des Computers.
Beispiele solcher ”Probleme“:
• Funktionsauswertung: e, sin(1) (Taschenrechner oder andere Hardware)
• Losung von Gleichungen: Ax = b, f(x) = 0, u′′(x) = f(x), ...
• Naherung (Approximation) von Großen, die man nicht exakt bestimmenkann oder will (z.B. wenn diese Berechnung zu aufwendig ist):Ableitungen, Integrale, optimale Strategien, Steuerungen
• Simulation komplexer Vorgange auf dem Computer
– Wetter: turbulente Stromungen
– Stromungsmechanik: Aerodynamik, Flugzeug-, Automobil- oder Schiffs-bau
– Bauingenieurwesen: Statik von Brucken
– Medizin: Knochenheilung, Tumortherapien
– Aktienkurse, Bewertungen
In der Numerik beschaftigen wir uns
• mit der Konstruktion ”geeigneter“ Losungsverfahren:
– schnell (effizient), teilweise in ”Echtzeit“
– zuverlassig (”beweisbare“ Fehlerabschatzung: ‖ xk − x∗‖ ≤ ? )
– robust gegenuber Storungen (z.B. Messfehler, Modellunsicherheiten)
• mit der mathematischen Analyse dieser Verfahren,
• deren effizienter Realisierung (Implementierung).
Derartige Fragestellungen werden in der Numerik untersucht, welches ein Ober-begriff ist fur z.B.
• Numerische Analysis
• Numerische Lineare Algebra
• Numerische Optimierung
• Numerical Finance
• Computational Physics
• CFD: Computational Fluid Dynamics
• Wissenschaftliches Rechnen
4
Das Vorgehen kann man (vereinfacht) so darstellen:
Reales Problem → Modellierung→ Mathematisches Modell
Konstruktion und Umsetzung von Verfahren→ Simulation
Beispiel: Bestimmung des Abraums bei der Braunkohleforderung.
1.) Messungen (Experiment): Tiefenmessungen durch Stereofotographienaus Satelliten bzw. Flugzeugen
2.) Mathematisches Modell: Bestimme das Volumen des ”Lochs“, d.h. Be-rechnung von Volumenintegralen
3.) Numerische Verfahren: Verwende sog. ”Kubaturformen“ zur naherungs-weisen Berechnung von 3D-Integralen
4.) Umsetzung: Programmierung des oben genannten Verfahrens
5
Kapitel 1
Rechnen auf digitalenRechenanlagen
Ein Computer ist eine endliche Maschine (Speicherplatz), d.h. man kann nie-mals exakt rechnen, man hat es immer mit Fehlern zu tun.
Beispiel:
Darstellung von π: Rundung!
Ziel:
Analyse und Kontrolle von Rundungsfehlern.
§1 Zahlendarstellung
Grundlage:
1.1.1 Bemerkung
Sei b ∈ N, b > 1 gegeben.Zu jedem r ∈ R existieren dann eindeutige Zahlen
• σ ∈ −1, 1 (Vorzeichen)
• n ∈ N (hochste Potenz)
• ak ∈ N0, k ∈ Z, k ≤ n, an 6= 0mit 0 ≤ ak < b ∀k ≤ n,ak < b− 1 fur unendliche viele Indizes k ≤ n
so dass r = σn∑
k=−∞akb
k (”b-adische Entwicklung“)
Beweis:
Ubung.
6
Bemerkungen:
(a) b heißt Basis.
(b) Die Bedingung ak < b− 1 fur unendlich viele k ≤ n sichert die Eindeutig-keit: z.B. fur b = 10 ist fur r = 1 also 0.99... nicht zugelassen.
Die b-adische Entwicklung wird durch eine endliche Entwicklung approximiert.
1.1.2 Definition: Festpunktzahlen
Zu gegebener Basis b ist
F (l, n) :=
±
n∑k=−l
akbk = ±(an . . . a0.a−1 . . . a−l)b
die Menge der Festpunktzahlen mit n Vor- und l Nachkommastellen.
Bemerkung:
In modernen Computern wird b = 2 verwendet und negative Zahlen werden als2-er Komplement abgespeichert.
Universitat UlmAbteilung Numerik
Prof. Dr. Karsten Urban
Numerik 1a — SS 2005
Nach der Vorlesung kam heute die Frage auf, was ein 2-er Komplement ist. Zu x ist dies diejenige Zahl y, fur
die in der jeweiligen Arithmetik x + y = 0 gilt.
Beispiel: Fur b = 2 und m = 3 ist das 2-er-Komplement von x = 011 gegeben durch y = 101, denn
011
+101
= 000
Damit ergibt sich z.B. fur b = 2 und m = 3 folgende Codierungstabelle:
Betrag |x| x −x
0 000
1 001 111
2 010 110
3 011 101
4 100
also ist der darstellbare Bereich −4, . . . , 3.
13.4.2005
Karsten Urban
http://www.mathematik.uni-ulm.de/numerik/teaching/ss05/Numerik1a/Num1aSS05-1.pdf
7
Beispiel:
Binardarstellung (b = 2) von x = (14.625)10:
14 = 7 · 2 + 07= 3 · 2 + 1
3= 1 · 2 + 11 = 0 · 2 + 1
⇒
a0 = 0,a1 = 1,a2 = 1,a3 = 1
und
a−1 = b2 · 0.625c = b1.25c = 1,a−2 = b2 · 0.25c = b0.5c = 0,a−3 = b2 · 0.5c = b1c = 1.
(Rest: 0.25)(Rest: 0.5)(Rest: 0)
⇒ (14.625)10 = (1110.101)2
Bemerkung:
Typischerweise werden ganze Zahlen (integers) als Festpunktzahlen dargestellt(b = 2, l = 0). Damit ergeben sich folgende Zahlenbereiche:
n = 7 -128,...,127 (8 Stellen/Bit)n = 15 -32768,...,32767 (16 Stellen/Bit)n = 31 ≈ ± 4.294.967.295 (32 Stellen/Bit)
Problem:
Nur ein kleiner Zahlenbereich ist damit realisierbar!
1.1.3 Definition: normalisierte Gleitpunktdarstellung
Die normalisierte Gleitpunktdarstellung von x ∈ R lautet x = f · be wobei
• die Mantisse f eine feste Zahl m von Stellen hat und b−1 ≤ |f | < 1 (dieerste Nachkommastelle ist 6= 0), d.h.
f =
±(0.d1 . . . dm)b = ±m∑
j=1djb
−j , d1 6= 0
0, d1 = 0
• der Exponent e eine ganze Zahl innerhalb fester Schranken r ≤ e ≤ R ist,d.h.
e = ±(e1 . . . el)b = ±l∑
j=1
ejbl−j
Die Menge der Maschinenzahlen mit Basis b, Mantissenlange m und Exponen-tenlange l wird als M(b, m, l) bezeichnet.
8
Bezeichnungen
xMIN := min|z|, z ∈M(b, m, l) |x| < xMIN ⇒ x := 0
xMAX := max|z|, z ∈M(b, m, l) |x| > xMAX ⇒ OVERFLOW, NaN
Beispiele/Bemerkungen
(a) M(10, 4, 2), x = −51.34 → − 0.5134 · 102 = (−5134 + 2)10
(b) M(2, 4, 2), x = 3.25 → x = (11.01)2 ⇒ 0.1101 · 210 = (+1101 + 10)2
(c) Die Werte von b, m, l hangen vom Computertyp, Hardware, Betriebssystemab, ebenso r und R:
b m r R
IEEE P754-Norm float 2 23 -128 127(HP 9000, IBM-PC) double 2 52 -1024 1023IBM 370 float 16 6 -64 63
double 16 14 -64 63IEEE-Standard IEC 559 float 2 24 -125 128
double 2 53 -1021 1024
(d) Selbst bei Umwandlung exakter Eingaben in Maschinenzahlen konnen Feh-ler auftreten, z.B. x = 0.1 = (0.0001100)2
(e) Die Gleitpunktzahlen sind entlang der reellen Achse nicht gleichverteilt,sondern werden in der Nahe der kleinsten darstellbaren Zahl dichter.
§2 Rundung und Maschinengenauigkeit
Aufgabe:
Approximiere x ∈ R durch fl(x) ∈M(b, m, l) (fl = float), d.h. konstruiere eineAbbildung
fl : R → M(b, m, l)
bzw.fl : [xMIN , xMAX ] → M(b, m, l)
Dies wird durch geeignete Rundungsstrategien gewahrleistet.Hier betrachten wir 2 Beispiele:
1.2.1 Standardrundung
(”normales“ Runden: 1.4→ 1, 1.5→ 2)
(1.2.1) fl(x; b, m, l) = fl(x) := ±m∑
j=1
djbe−j +
0, falls dm+1 < b
2
be−m, falls dm+1 ≥ b2
und
|x| < xMIN ⇒ f(x) := 0|x| > xMAX ⇒ f(x) := OVERFLOW
9
fur
x = ±∞∑
k=1
dkbe−k = ±
e−1∑j=−∞
de−jbj
Beispiel:
M(10, 4, 2), x = 215.76 = 0.21576 · 103 ⇒ fl(x) = 0.2158 · 103
1.2.2 Banker’s Rule (IEEE Norm P754)
Ziel:
Bessere statistische Verteilung von Rundungsfehlern
Voraussetzung:
• b gerade, b2 ungerade, (z.B. b = 2, b = 10)
• O.B.d.A. sei b−1 ≤ x < 1 (sonst entsprechend normalisieren)mit erster Nachkommastelle 6= 0
• Mantissenlange sei m
Rundungsvorschrift:
Falls dm+1 6= b2 stimmt die Banker’s Rule mit (1.2.1) berein.
Falls dm+1 = b2 setzt man
fl(x) := b−m
⌊bmx± 1
2
⌋wobei ”±“ so gewahlt wird, dass
⌊bmx± 1
2
⌋gerade ist.
Beispiel:
M(10, 3, 0), x = 0.2545:
• mit Standardrundung: fl(x) = 0.255
• mit Banker’s Rule:
b = 10, m = 3, bm = 1000⌊bmx + 1
2
⌋=⌊254.5 + 1
2
⌋= b255c = 255 ungerade⌊
bmx− 12
⌋=⌊254.5− 1
2
⌋= b254c = 254 gerade
⇒ fl(x) = 10−3 · 254 = 0.254
Beispiel: Wiederholtes Rechnen
Standard: 2.445 → 2.45 → 2.5 → 3 (Fehler: 0.555)Banker’s Rule: 2.445 → 2.44 → 2.4 → 2 (Fehler: 0.445)
Wir betrachten nun den Rundungsfehler.
10
1.2.3 Definition: relativer/absoluter Fehler
Es sei f : R→ R eine Funktion und f : R→ R eine Approximation.
(a) Die Große |f(x)− f(x)| heißt absoluter Fehler.
(b) Die Große |f(x)− ef(x)||f(x)| heißt relativer Fehler.
1.2.4 Definition: relativer/absoluter Rundungsfehler
Fur eine Rundungsfunktion fl : R→M(b, m, l) heißt |fl(x)− x| absoluter und|fl(x)−x|
|x| relativer Rundungsfehler (also f(x) := x, f := fl(x)).
1.2.5 Lemma
Sei b gerade und fl die Standardrundung, dann gilt
|fl(x)− x| ≤ 12· be−m und
|fl(x)− x||x|
≤ 12b1−m
Beweis:
Zunachst gilt:
(1.2.2) be−1 ≤ x < be, x = ±∞∑
j=1djb
e−j
Fall 1: dm+1 < b2 : Hier gilt
|fl(x)− x| =
∣∣∣∣∣m∑
k=1
dkbe−k −
∞∑k=1
dkbe−k
∣∣∣∣∣= be
∣∣∣∣∣dm+1 · b−(m+1) +∞∑
k=m+2
dkb−k
∣∣∣∣∣≤ be
[dm+1 · b−(m+1) +
∞∑k=m+2
dkb−k
]︸ ︷︷ ︸
(∗)
≤ be(dm+1 · b−(m+1) + b−(m+1)
)= be−(m+1) · (dm+1 + 1︸ ︷︷ ︸
(∗∗)
)
≤ be−(m+1) · 12b
=12be−m
(∗)∞∑
k=m+2
dkb−k <
∞∑k=m+2
(b− 1)b−k =∞∑
k=m+1
b−k −∞∑
k=m+2
b−k = b−(m+1)
11
(∗∗)Falls b gerade, folgt aus dm+1 < b
2 ∈ N die Ungleichung dm+1 + 1 ≤ b2 .
Wegen |x| ≥ be−1 folgt auch die 2. Abschatzung.
Fall 2: dm+1 ≥ b2 : Hier gilt analog
|fl(x)− x| ≤∣∣be−m − dm+1 be−m b−1
∣∣= be−m | 1− dm+1b
−1︸ ︷︷ ︸≥ 1
2︸ ︷︷ ︸≤ 1
2
|
≤ 12be−m
1.2.6 Definition: (relative) Maschinengenauigkeit
Die Zahl
eps :=b−m+1
2heißt (relative) Maschinengenauigkeit. Nach Lemma 1.2.5 charakterisiert sie of-fenbar das Auflosungsvermogen eines Rechners.
1.2.7 Bemerkung
(a) Es gilt eps = infδ > 0 : fl(1 + δ) > 1
(b) ∃ ε > 0 mit |ε| ≤ eps und |fl(x)−x||x| = ε, d.h. fl(x) = x(1 + ε)
Beweis:
Folgt aus Lemma 1.2.5 (Ubung).
§3 Gleitpunktarithmetik
Nun wollen wir mit Maschinenzahlen rechnen und erhalten so einen Algorith-mus, d.h. eine Folge von Verknupfungen von Maschinenzahlen.
1.3.1 Beispiel
M(10, 3, 3)x = 0.346 · 103, y = 0.785 · 103
x + y = 0.1131 · 104 /∈M(10, 3, 3)⇒ Das Ergebnis einer arithmetischen Operation auf Maschinenzahlen musskeine Maschinenzahl sein, da die Maschinenzahlen nicht abgeschlossen sind.⇒ Fur die Analyse muss also eine Operation ∇ ∈ +,−, ∗,÷ durch eineGleitpunkt-Operation ∇© ersetzt werden mit x ∇© y = fl(x∇y)
Wegen fl(x) = x(1 + ε), ε| ≤ eps folgt x ∇© y = (x∇y)(1 + ε)
12
Bemerkung:
(a) Maschinenzahlen sind nicht assoziativ, wie folgendes Beispiel zeigt:M(10, 3, l) x = 6590 = 0.659 · 104
y = 1 = 0.100 · 101
z = 4 = 0.400 · 101
1. Exakt: (x + y) + z = x + (y + z) = 6595
2. Aber:
x⊕ y = 0.659 · 104 = 6590 ⇒ (x⊕ y)⊕ z = 6590y ⊕ z = 5 ⇒ x⊕ (y ⊕ z) = 6600
⇒ Die Reihenfolge der Summation ist wesentlich!
”Faustregel“: Summation in Reihenfolge aufsteigender Betrage!
(b) Ebenso gilt das Distributivgesetz nicht mehr.
Beispiel (”Ausloschung“):
Exakt:0.73553
- 0.734410.00122
Bei dreistelliger Rechnung (M(10, 3, l)):0.736
- 0.7340.002
Der absolute Fehler ist in der Großenordnung des Rundungsfehler, fur den re-lativen Fehler gilt jedoch:
0.002− 0.01220.0122
= 0.64 = 64%
Dieser ist also sehr groß. Der Effekt heißt Ausloschung (genaueres spater).
§4 Fehlerfortpflanzung bei elementaren Rechenopera-tionen
In einem Programm/ Algorithmus werden viele Rechenoperationen durchge-fuhrt.
Frage:
Wie entwickeln sich anfangliche Fehler im Verlauf der Rechnung? Wir betrach-ten zunachst exakte Operationen von Maschinenzahlen, d.h. ohne weiteres Run-den.Seien x, y die exakten Eingaben und x, y die gestorten (realen) Eingaben mitden relativen Fehlern
δx =x− x
xund δy =
y − y
y.
13
Daraus folgt
(1.4.1) x = x(1 + δx), y = y(1 + δy)
und wir nehmen an, dass
(1.4.2) |δx| , |δy| ≤ ε < 1
4.1 Multiplikation
x · y = (x(1 + δx)) · (y(1 + δy))= (x · y)(1 + δx + δy + δxδy)!= (x · y)(1 + δ)
mit |δ| = |δx + δy + δxδy| ≤ |δx|+ |δy|+ |δxδy| ≤ ε(2 + ε) ∼= 2ε bei Vernachlassi-gung des quadratischen Terms ε2 < ε 1
⇒ Fur den relativen Fehler ergibt sich∣∣∣∣ x · y − x · yx · y
∣∣∣∣ = |δ| ≤ 2ε + ε2 ≤ 3ε
Der Fehler ist also von der gleichen Großenordnung wie der Eingabefehler.
4.2 Division
x
y=
x(1 + δx)y(1 + δy)
Wegen |δy| < 1 gilt 11+δy
=∞∑
j=0(−1)jδj
y (geom. Reihe mit q = −δy), also
1 + δx
1 + δy= (1 + δx)
∞∑j=0
(−1)jδjy
= (1 + δx)(1 +∞∑
j=1
(−1)jδjy)
= 1 + δx + (1 + δx)∞∑
j=1
(−1)jδjy
!= 1 + δ
14
mit
|δ| ≤ ε + (1 + ε)∞∑
j=1
εj
︸ ︷︷ ︸=ε+ε2+...=ε
∞Pj=0
εj
= ε + (1 + ε)ε∞∑
j=0
εj
︸ ︷︷ ︸= 1
1−ε
= ε
(1 +
1 + ε
1− ε
)= ε
(1− ε
1− ε+
1 + ε
1− ε
)= 2ε
11− ε
Also falls z.B. ε ≤ 12 folgt |δ| ≤ 4ε (denn 1+ε
1−ε ≤ 3),d.h. ahnlich wie bei der Multiplikation!
4.3 Addition
x + y = x(1 + δx) + y(1 + δy)= x + y + xδx + yδy
= (x + y)(1 +x
x + yδx +
y
y + xδy)
!= (x + y)(1 + δ)
mit
|δ| ≤∣∣∣∣ x
x + y
∣∣∣∣ |δx|+∣∣∣∣ y
x + y
∣∣∣∣ |δy|
≤ (|δx|+ |δy|) max∣∣∣∣ x
x + y
∣∣∣∣ , ∣∣∣∣ y
x + y
∣∣∣∣≤ 2ε max
∣∣∣∣ x
x + y
∣∣∣∣ , ∣∣∣∣ y
x + y
∣∣∣∣Achtung:Dieser Fehler kann nicht durch ε abgeschatzt werden,wenn x ≈ −y kann dieser Term sehr groß werden→ Effekt der Ausloschung!
x = 0.d1...dr dr+1...dm · be
y = −0.d1...dr dr+1...dm · be, der Einfachheit halber dj < dj , j ≥ r + 1
⇒ x + y = 0.0...0 dr+1...dm · be
15
und damit∣∣∣ xx+y
∣∣∣ =∣∣∣∣∣∣∣∣
d1 6=0⇒d1>1≥b−1︷ ︸︸ ︷0.d1...dm ·be
0.dr+1...dm︸ ︷︷ ︸≤1
·be−r
∣∣∣∣∣∣∣∣ ≥b−1be
be−r = br−1
Man verliert mind. r − 1 Stellen an Genauigkeit, diese werden ”ausgeloscht“.
Beispiel:
Bei e−1 :=∞∑
k=0
(−1)k
k! tritt bei der Berechnung mittels Reihe das Problem der
Ausloschung auf.
§5 Kondition und Stabilitat
Frage: Welche Beziehung hat ein Algorithmus zu einem gegebenen Problem?
Allgemeiner Rahmen:
X, Y seien normierte Raume.
Aufgabe:
Bestimme f(x) fur ein x ∈ X mit f : X −→ Y .
1.5.1 Beispiel: Summenbildung
X = R2 = R× R, Y = Rf(x1, x2) = x1 + x2
1.5.2 Beispiel: Bestimmung des Schnittpunktes zweier Geraden
g1 =(x1, x2) ∈ R2 : a11x1 + a12x2 = b1
g2 =
(x1, x2) ∈ R2 : a21x1 + a22x2 = b2
fur gegebene bi ∈ R, aij ∈ R, 1 ≤ i, j ≤ 2.
MitA := (aij)1≤i,j≤2 ∈ R2×2
b = (b1, b2)T ∈ R2
gilt also fur den Schnittpunkt x = (x1, x2)T ∈ R2
Ax = b
also (falls A regular ist) x = A−1b, d.h. X = R2×2 × R2, Y = R2
f(A, b) := A−1b = x
16
1.5.3 Beispiel: Berechnung des Kohleaushubs
X = R(R3) (Menge der R-integrierbaren Funktionen auf dem R3)Y = R
f(x) :=∫∫∫
R3
x(s)ds , x ∈ X = R(R3)
wobei x : R3 → R aus den Messungen gewonnen wird.
Zunachst betrachten wir exakte Rechnungen:
Eingabe Problem/Prozess Ausgabex ∈ X −→ f : X → Y −→ y = f(x)Fehler: ∆x = x− x ∆y = f(x)− f(x)
1.5.4 Definition: relative/absolute Kondition
(a) Zu gegebenen Normen ‖·‖X , ‖·‖Y auf X bzw. Y seien
δx :=‖∆x‖X‖x‖X
, δy :=‖∆y‖Y‖y‖Y
die relativen Ein- bzw. Ausgabefehler. Dann heißt
(1.5.1) κf :=δy
δx
die (relative) Kondition des Problems f(x), f : X → Y und
(1.5.2) κf,abs :=‖∆y‖Y‖∆x‖X
die absolute Kondition von f(x).
(b) Ein Problem heißt gut konditioniert, wenn ”kleine“ Schranken fur κf furδx → 0+ existieren (optimal ware κf ≈ 1 bzw. κf = 1).
Bemerkung:
Nach §4 sind Multiplikation und Division gut konditioniert, die Addition kann(in Abhangigkeit von den Eingabedaten) extrem schlecht konditioniert sein!
1.5.5 Beispiel
Falls A und b in Beispiel 1.5.2 so beschaffen sind, dass annahernd g1 ⊥ g2 gilt,dann gilt κf ≈ 1.
17
Eingabestorungen machen die Gerade zu ”Schlauchen“.
Beachte:
• Die Kondition ist eine Eigenschaft des Problems, nicht die eines Algorith-mus!
• Fur ”skalare“ Probleme, d.h. Y = R, f : Ω ⊆ Rn → R mit ”glattem“ fkann man die Fehlerverstarkung abschatzen.
Dazu einige Vorbereitungen:
Bemerkungen:
(a) Das Landau-Symbol ”O“ (”groß Oh“) bedeutet
f = O(g) :⇔ ∃ C, 0 ≤ C <∞ : f ≤ C · g
(Ubung)
(b) Fur x = (xi)i=1,...,n ∈ R ist
‖x‖2 :=√
xT x =
√√√√ n∑i=1
x2i
die euklidische Norm im Rn.
(c) Fur f : Ω ⊆ Rn → R bezeichne ∂∂xi
f(x) die partielle Ableitung nach xi
und f ′(x) = ∇f(x) = ( ∂∂x1
f(x), . . . , ∂∂xn
f(x))T den Gradienten.
(d) Die Matrix der zweiten Ableitungen f ′′(x) := H(x) :=(
∂2
∂xi∂xjf(x)
)i,j=1,...,n
heißt Hesse-Matrix.
18
Fur n = 1: f : Ω −→ R mit Ω = [a, b] ist die Taylor-Entwicklung
(1.5.3) f(x) = f(x) + (x− x)f ′(x) +12(x− x)2f ′′(x) +
16(x− x)3f ′′′(ξ)︸ ︷︷ ︸O(‖x−x‖3)
bekannt. Das Analogon in n Dimensionen lautet:
(1.5.4) f(x) = f(x) + (x− x)T f ′(x) +12(x− x)T f ′′(x)(x− x) +O(‖x− x‖3)
Falls x ≈ x, dann ist ‖x − x‖2 klein und ‖x − x‖k2 → 0 fur k → ∞ und daherlasst man die Terme hoherer Ordnung weg.
(1.5.5) f(x) .= f(x) + (x− x)T f ′(x)
wobei .= ” in erster Naherung“ (also bei Weglassen der quadratischen und ho-heren Terme) bedeutet.
⇒ δy =∣∣∣∣f(x)− f(x)
f(x)
∣∣∣∣ .=∣∣∣∣(x− x)T f ′(x)
f(x)
∣∣∣∣= |
n∑i=1
∂f(x)∂xi
· xi
f(x)︸ ︷︷ ︸=: ϕi
· xi − xi
xi︸ ︷︷ ︸relativer Eingabe-
fehler δxi
|
und ϕi heißt Fehlerverstarkungsfaktor. Ein Problem ist umso besser konditio-niert, je kleiner die ϕi sind.
1.5.6 Beispiel
Fur n = 1 lautet ϕ = ϕi = f ′(x) · xf(x) .
1.5.7 Beispiel
Nochmal die Multiplikation:
f(x) = x1 · x2 , x = (x1, x2)T ∈ R2 ,
⇒ ∂f(x)∂x1
= x2 ,∂f(x)∂x2
= x1
⇒ ϕ1 =∂f(x)∂x1
· x1
f(x)= x2 ·
x1
x1 · x2= 1
ϕ2 =∂f(x)∂x2
· x2
f(x)= x1 ·
x2
x1 · x2= 1
⇒ Multiplikation ist gut konditioniert.
19
1.5.8 Definition: Stabilitat
Ein Algorithmus heißt stabil, wenn die durch die Rechnung erzeugten Fehler4yin der Großenordnung des durch die Kondition des Problems unvermeidbarenFehlers bleibt.
1.5.9 Beispiel
Nullstellenbestimmung x2 − 2a1x + a2 = 0. Hier sei M(10, 5, 2):
a1 = 6.0002a2 = 0.01
(x∗ = 8.3336 · 10−4)
Algorithmus I (instabil)
1.) y1 := a1 · a1 → 36.002|400042.) y2 := y1 − a2 → 35.992|400043.) y3 :=
√y2 → 5.9993|66637
4.) u∗ := y4 := a1 − y3 → 0.0009|00000 (← Ausloschung)
Das Problem selbst ist gut konditioniert (Ubung).
Idee:
x∗ = a1 −√
a12 − a2 =
a2
a1 +√
a12 − a2
Algorithmus II (stabil)
1) y1 := a1 · a1
2) y2 := y1 − a2
3) y3 :=√
y2
4) y4 := a1 + y3
5) y5 := a2y4→ 0.0008333|3 .
1.5.10 Bemerkung
(a) Ob ein Algorithmus stabil ist oder nicht, kann auch von den Eingabewertenabhangen. Ist dies nicht der Fall, nennt man den Algorithmus robust.
(b) Einige Faustregeln:
• Vermeide Subtraktionen ahnlich großer Zahlen.
• Unvermeidbare Subtraktionen moglichst an den Anfang des Algorith-mus stellen.
• Summation in aufsteigender Reihenfolge der Betrage.
20
1.5.11 Beispiel
Fur die Auswertung von Polynomen
p(x) = a0 + a1x + ... + anxn, x ∈ R
ist das Horner-Schema
p(x) = a0 + x(a1 + x(a2 + x(a3 + ... + x(an−1 + xan)...)))
deutlich stabiler und effizienter. (Ubung)
21
Kapitel 2
Direkte Loser linearerGleichungssysteme
”Lineare Gleichungssysteme lauern an jeder Straßenecke.“
Wir schreiben diese in der Form
(2.0.1) Ax = b
mit gegebenen A ∈ Rn×n, b ∈ Rn und Unbekannten x ∈ Rn (auch C ist moglich).Wir nehmen stets an, das (2.0.1) eindeutig losbar ist, d.h.
(2.0.2) detA 6= 0 (A ist regular).
In vielen Anwendungen ist n sehr groß, z.B. n ≈ 109!
Beispiel:
Aus der Schule kennen Sie die Cramersche Regel
xi =det Ai
det A
wobei Ai aus A entsteht, indem man die i-te Spalte durch b ersetzt.Man erhalt n + 1 Determinanten fur A,A1, . . . , An.
Laplace’scher Entwicklungssatz:pro Determinante n! Operationen −→ (n + 1)! Operationen
n 10 12 14 16 18 20100 MFlop (CRAY) 0,4 s 1 min 2,6 h 41 d 38 a 16.000 a2 Tera Flop (RWTH Aachen) 2 · 10−6 s 2 · 10−4 s 0,04 s 10 s 53 min 14 d
Hinzu kommen massive Ausloschungseffekte!
22
§1 Stabilitatsanalyse linearer Gleichungssysteme
Frage:Wie sensitiv hangt die Losung x von (2.0.1) von Anderungen von A und b ab?
2.1.1 Definition: Kondition einer Matrix
Sei ‖ · ‖ eine Matrixnorm auf dem Rn×n, dann heißt
(2.1.1) κ(A) := ‖A‖ · ‖A−1‖
Kondition der Matrix A ∈ Rn×n.
2.1.2 Bemerkung
(a) Es gilt 1 = ‖Id‖ = ‖A ·A−1‖Ubung≤ ‖A‖ · ‖A−1‖ = κ(A)
(b) κ(A−1) = κ(A)
(c) κ(α ·A) = κ(A) ∀α ∈ R\0
(d) A orthogonal ⇒ κ2(A) = ‖A‖2 · ‖A−1‖2 = 1
(vgl. Ubung)
Einige Erinnerungen aus der Linearen Algebra:
2.1.3 Definition: Spektrum, Spektralradius
Die Menge
(2.1.2) σ(A) := λ ∈ C : Ax = λx fur ein x ∈ Cn\0
heißt Spektrum der Matrix A ∈ Rn×n und
(2.1.3) ρ(A) := maxλ∈σ(A)
|λ|
der Spektralradius von A.
2.1.4 Satz
Sei A ∈ Rn×n
(a) limk→∞
Ak = 0 ⇐⇒ ρ(A) < 1
(b) Die geometrische Reihe∞∑
k=0
Ak konvergiert genau dann, wenn ρ(A) < 1.
Dann gilt
(2.1.4)∞∑
k=0
Ak = (Id−A)−1 (Von-Neumann’sche Reihe)
23
(c) Ist ρ(A) < 1, dann ist Id±A invertierbar und es gilt fur ‖A‖ < 1
(2.1.5)1
1 + ‖A‖≤ ‖(Id±A)−1‖ ≤ 1
1− ‖A‖
Beweis:
Siehe Lineare Algebra.
Zu (2.0.1) betrachten wir ein gestortes System
(2.1.6) Ax = b mit A = A + ∆A, b = b + ∆b
(∆A, ∆b sind Datenstorungen) mit der gestorten Losung x = x + ∆x.
Dann sind
(2.1.7) δA :=‖A−A‖‖A‖
=‖∆A‖‖A‖
δb :=‖∆b‖‖b‖
die relativen Ein- und(2.1.8) δx :=
‖∆x‖‖x‖
der relative Ausgabefehler.
Wir fordern wieder, dass A = A + ∆A regular ist. Dies ist z.B. dann der Fall,wenn
(2.1.9) ‖A−1‖ · ‖∆A‖ < 1
ist (Ubung).
2.1.5 Satz
Sei A ∈ Rn×n regular mit (2.1.9), dann gilt
(2.1.10) δx ≤κ(A)
1− δA · κ(A)· (δb + δA), b 6= 0
Beweis:
Aus (2.1.9) folgt, dass ‖A−1 ·∆A‖ ≤ ‖A−1‖ · ‖∆A‖(2.1.9)
< 1
Nun gilt(2.1.11) ρ(A) ≤ ‖A‖ ∀A ∈ Rn×n (Ubung)
also ρ(A−1 ·∆A) < 1.
Nach Satz 2.1.4 (c) ist damit Id + A−1 ·∆A invertierbar und aus (2.1.5) folgt
(2.1.12) ‖(Id + A−1 ·∆A)−1‖ ≤ 11− ‖A−1 ·∆A‖︸ ︷︷ ︸
≤‖A−1‖·‖∆A‖
≤ 11− ‖A−1‖ · ‖∆A‖
24
Aus (2.1.6)
(A + ∆A)(x + ∆x) = (A + ∆A) · x + (A + ∆A) ·∆x = b
folgt(A + ∆A)︸ ︷︷ ︸
=A(Id+A−1·∆A)
∆x = ( b︸︷︷︸=Ax
+∆b)− (A + ∆A) · x
also(2.1.13) ∆x = (Id + A−1∆A)−1 ·A−1 · (∆b−∆Ax)
Daraus folgt mit x 6= 0 (wegen b 6= 0)
‖∆x‖ ”4-Ungl.“≤ ‖(Id + A−1 ·∆A)−1‖ · ‖A−1‖ · (‖∆b‖+ ‖∆Ax‖︸ ︷︷ ︸
≤‖∆A‖·‖x‖
)
(2.1.12)
≤ ‖A−1‖1− ‖A−1‖ · ‖∆A‖
· (‖∆b‖+ ‖∆A‖ · ‖x‖)
=κ(A)
1− κ(A) · δA· 1‖A‖
· (‖∆b‖‖b‖
· ‖b‖‖x‖︸︷︷︸
‖b‖=‖Ax‖≤‖A‖·‖x‖
+‖∆A‖‖A‖
· ‖A‖) · ‖x‖
Fazit:
Die Kondition einer Matrix ist der wesentliche Faktor der Fehlerverstarkung!
§2 Dreiecksmatrizen, Ruckwartseinsetzen
2.2.1 Definition: Dreiecksmatrix
Eine Matrix R = (rij)ni,j=1 ∈ Rn×n heißt obere Dreiecksmatrix (∆-Matrix), falls
rij = 0 fur i > j gilt. Eine Matrix L ∈ Rn×n heißt untere Dreiecksmatrix, fallsLT eine obere Dreiecksmatrix ist.
2.2.2 Bemerkung
(a) D 6= 0, D ∈ Rn×n, ist obere und untere Dreieckmatrix⇔ D = diag(d11, . . . , dnn) ist eine Diagonalmatrix.
(b) A eine ∆-Matrix ⇒ det A = a11 · a22 · · · · · ann =n∏
i=1aii
⇒ (detA 6= 0⇔ aii 6= 0 (∀i, 1 ≤ i ≤ n)).
25
(c) Ein Gleichungssystem Ax = b mit einer Dreiecksmatrix A heißt gestaffelt.Ein gestaffeltes Gleichungssystem lasst sich leicht auflosen.
Rx = b ⇔ r11x1 + r12x2 + . . . r1nxn = b1
r22x2 + . . . r2nxn = b2
...rn−1,n−1xn−1 + rn−1,nxn = bn−1
rn,nxn = bn
Da det R 6= 0⇒ rii 6= 0 , also
xn =bn
rnn, xn−1 =
bn−1 − rn−1,n · xn
rn−1,n−1
Allgemein:
xj =1
rjj
bj −n∑
k=j+1
rjk · xk
, j = n, n−1, ..., 1 (”Ruckwartseinsetzen“)
Rechenaufwand:
• fur xj : n− j Multiplikationen/Additionen, eine Division
• insgesamtn−1∑j=1
(n− j) =n−1∑j=1
j = n(n−1)2 = O(n2)
+ n− 1 Divisionen → O(n2)
Bemerkung:
(a) Ein System Lx = b lost man analog durch Vorwartseinsetzen.
(b) Zur Losung von Ax = b bestimmt man niemals A−1!
2.2.3 Satz
(a) Das Produkt zweier oberer (unterer) ∆-Matrizen ist wieder obere (untere)∆-Matrix.
(b) Die Inverse einer oberen (unteren) regularen ∆-Matrix ist eine obere (un-tere) ∆-Matrix.
Beweis:
Ubung.
§3 Gauß-Elimination und LR-Zerlegung
Idee:
Transformiere A auf ∆-Gestalt und lose mit Vorwarts-/Ruckwartseinsetzen.
26
2.3.1 Beispiel
A =
2 4 61 3 51 4 9
+(−12) · 1. Zeile
+(−12) · 1. Zeile
→
2 4 60 1 20 2 6
+(−2) · 2. Zeile
→
2 4 60 1 20 0 2
= R
⇒ Mit L :=
1 0 01/2 1 01/2 2 1
gilt A = L ·R
⇒ Ax = b⇔ LRx = b
2.3.2 Algorithmus (Gauß-Algorithmus)
Gegeben: A ∈ Rn×n, b ∈ Rn, Annahme: det(A) 6= 0
A(1) := A, b(1) := b
For j = 1, . . . , n
Falls a(j)jj = 0 → ABBRUCH
lij :=aij
a(j)jj
, i > j
a(j+1)ik :=
a
(j)ik , , i ≤ j, k = 1, . . . , n;
a(j)ik − lij a
(j)jk , , i, k > j;
0, , i > j, k = j.
b(j+1)i := b
(j)i − lijb
(j)j , i = j + 1, . . . , n
End
Bemerkungen:
(a) R := A(n) ist eine obere ∆-Matrix
(b) Es gilt A(j+1) = LjA(j), b(j+1) = Ljb
(j) mit der Frobenius-Matrix
Lj =
j ↓1
. . . 0j → 1
−lj+1,j. . .
0... 0
. . .−ln,j 1
(c) Wegen det Lj = 1 gilt
Ax = b⇔ A(1)x = b(1) ⇔ A(2)x = b(2) ⇔ . . .⇔ A(j+1)x = b(j+1)
27
alsoRx = b(n) ⇔ Ax = b
Man bestimmt dann x durch Ruckwartseinsetzen.
Hinweise zur Implementierung
(a) Man legt keinen zusatzlichen Speicher fur A(j), b(j) an, sondern uber-schreibt die Eingaben. In obigem Beispiel:
2 4 6 |1 3 5 |1 4 9 |
2 4 6 |12 1 2 |12 2 6 |
lj,1
2 4 612 1 212 2 2
lj,2
ebenso fur b(j)
(b) Aufwand:n∑
j=1
(
li,jn− j)+
ai,k
(n− j)2 +bi
(n− j)
= 2 ·
n∑j=1
j +n∑
j=1j2
= n (n + 1) + 13
(n3 + 3
2n2 + n2
)= n3
3 +O(n3)
(c) Vergleich mit Cramer’scher Regel:n 1 4 20
(n + 1)! 2 120 5.1 · 1019
n3 1 64 8000
2.3.3 Satz
Wenn der Gauß-Algorithmus durchfuhrbar ist, dann gilt A = LR mit R = A(n)
und L = L−11 · L
−12 · ... · L
−1n−2 · L
−1n−1
Beweis:
R ist obere ∆-Matrix.
R = A(n) = Ln−1 ·A(n−1) = Ln−1 · Ln−2 ·A(n−2) = . . . = Ln−1Ln−2 · · ·L1︸ ︷︷ ︸=:L
A(1)︸︷︷︸=A
Da jedes Li untere ∆-Matrix ist, ist auch L nach Satz 2.2.3 ∆-Matrix undL := L−1 auch.
Frage:
Ist der Gauß-Algorithmus immer durchfuhrbar, wenn detA 6= 0?
2.3.4 Beispiel
A =(
0 11 1
)ist regular, det A = −1, aber Algorithmus 2.3.2 bricht ab.
28
Idee:
Vertausche die beiden Zeilen
A = PA =(
0 11 0
)︸ ︷︷ ︸
Permutationsmatrix
P−1=P T
·(
1 10 1
)= P
(1 00 1
)︸ ︷︷ ︸
=L
(1 10 1
)︸ ︷︷ ︸
=R
⇒ PA=LR
(In jeder Zeile und Spalte steht genau eine 1, sonst 0.)
Strategie: Spaltenpivotsuche
Bestimme das betragsmaßig großte Element a(j)ij , i ≥ j, in der aktuellen Spalte
und vertausche die Zeilen i und j.
2.3.5 Satz
Zu jeder regularen Matrix A existiert eine Permutationsmatrix P und eine Zer-legung PA=LR.
Beweis: (konstruktiv)
Mit
Nij(α) :=
j ↓
1 0. . .
i→ α. . .
0 1
gilt: (Ubung)Nij(α)−1 = Nij(−α)
Fur die Frobenius-Matrix gilt:
Lj =∏i>j
Nij(−lij)
⇒ L−1j =
∏i>j
Nij(lij),
also ohne die Pivotsuche:
L ·R = L−11 · · ·L
−1n−1 ·R = A
Spaltenpivotsuche:
Sind alle a(j)ij , i ≥ j gleich 0, ist diese Spalte gleich 0.
⇒ 0 = det A(j) = detA (detLj = 1) → Widerspruch!⇒ ∃ ein Pivotelement mit Index kj
29
Die Matrix
Pij =
i ↓ j ↓
1...
.... . .
......
1...
...i→ · · · · · · · · · 0 · · · · · · · · · 1
... 1...
.... . .
...... 1
...j → · · · · · · · · · 1 · · · · · · · · · 0
1. . .
1
ist eine Permutationsmatrix PijPji = I. PijA vertauscht die Zeilen i und jAPij vertauscht die Spalten i und j.
Betrachte nunPjkj
A(j) =: A(j) (Pjj = I)
dessen Element a(j)jj = a
(j)jkj6= 0, also ist
A(j) = Lj−1A(j−1)
mit dem Gauß-Algorithmus durchfuhrbar.
⇒ LR = L−11 · · ·L
−1n−1A
(n) = L−11 · · ·L
−1n−1A
(n) = L−11 · · ·L
−1n−1R = P1k1 · · ·P1kn︸ ︷︷ ︸
=:P∗
·A
* (Das Produkt einer Permutationsmatrix ist eine Permutationsmatrix.)
2.3.6 Bemerkung
(a) Ax = b ⇔ PAx = LRx = Pb, d.h. die Zeilen in der rechten Seite mussenauch vertauscht werden!
(b) Die Matrizen Pjkjwerden niemals komplett aufgestellt und gespeichert,
sondern werden zum Beispiel als Permutation abgelegt.
π ∈ Sn Permutation⇔ Pπ =[eπ(1), . . . , eπ(n)
],(
ej := (δ1j , . . . , δnj)T j-ter Einheitsvektor
).
Beispiel: n = 3, π = (3, 1, 2)
Pπ =
0 1 00 0 11 0 0
(Speicheraufwand: O(n))
30
(c) Fur Permutationsmatrizen gilt: P−1 = P T
(d) Der Beweis zeigt auch, dass P so gewahlt werden kann, dass alle Elementelij von L |lij | ≤ 1 erfullen.⇒ ‖L‖ ≤ 1
§4 Cholesky-Verfahren
Oftmals hat man zusatzliche Informationen uber A. Dieses Wissen nutzt manzur Konstruktion schneller Verfahren.
2.4.1 Definition: positiv definit
Eine symmetrische Matrix A ∈ Rn×n heißt positiv definit (s.p.d), falls
xT Ax > 0 ∀x ∈ Rn\0
Erinnerungen aus der Linearen Algebra:
2.4.2 Satz
Sei A ∈ Rn×n positiv definit, dann gilt:
(a) A ist invertierbar
(b) aii > 0 fur alle i = 1, ..., n
(c) maxi,j=1,...,n
|aij | = maxi=1,...,n
aii
Beweis:
(a) Hauptachsentransformation: A = UT DU , UT U = I, D = diag(λ1, . . . , λn),λi > 0⇒ A−1 = UT D−1U mit D−1 = diag( 1
λ1, . . . , 1
λn)
(Bemerkung: AA−1 = UT DUUT D−1U = I)
(b) 0 < eTi Aei = aii
(c) x := ek − el,A = (a1, . . . , an)xT Ax = (ek − el)T A(ek − el)︸ ︷︷ ︸
ak−al
= (ek − el)T (ak − al)
= akk + all − alk − akl = akk + all − 2alk
Annahme: alk = maxi,j=1,...,n
|aij | ⇒ akk + all − 2akl ≤ 0 (Widerspruch)
2.4.3 Satz (Kriterium von Hurwitz)
Eine Matrix A ∈ Rn×n ist genau dann s.p.d, wenn alle Hauptminoren positivsind, d.h.
det Ai > 0, Ai :=
a11 . . . a1i...
...ai1 . . . aii
∈ Ri×i, A = (aij)i,j=1,...,n
31
Ohne Beweis
2.4.4 Satz
Bei einer Gauß-Elimination einer symmetrischen positiv definiten Matrix A ∈Rn×n ist jede Restmatrix symmetrisch positiv definit. D.h. der Algorithmus2.3.2 ist ohne Pivotisierung durchfuhrbar.
Beweis:
Sei
A(1) = A =
a11 | zT
− − − − − − −|
z | B(1)
|
, a11 > 0, z = (a12, ..., a1n)T
Nach einem Eliminationsschritt gilt:
A(2) = L1·A(1) =
a11 | zT
− − − − − − −0 |... | B(2)
0 |
mit L1 =
1
−l21. . . 0
.... . .
... 0. . .
−ln1 1
also A(2) · LT1 = L1 ·A(1) · LT
1 =
a11 | 0 · · · · · · 0− − − − − − −0 |... | B(2)
0 |
Da L1 regular ist gilt:
xT (L1A(1)LT
1 )x = (LT1 x)T ·A(1) · (LT
1 x)= xT ·A(1) · x > 0 ∀ x 6= 0
und x = 0 ⇐⇒ x = 0⇒ nach Hurwitz ist B(2) positiv definit.(A(2) · LT
1 positiv definit ⇒ alle Hauptminoren sind positiv definit.)
32
2.4.5 Satz (Cholesky-Zerlegung)
Fur jede s.p.d. Matrix A ∈ Rn×n existiert eine eindeutig bestimmte ZerlegungA = LDLT , wobei L eine untere ∆ -Matrix mit Diagonale 1 und D eine positiveDiagonalmatrix ist.
Beweis:
Fuhrt man die Konstruktion aus dem Beweis von Satz 2.4.4 fort furk = 2, ..., n− 1, dann erhalten wir L = L−1
1 · . . . · L−1n−1, D = diag(A).
Bemerkung: Cholesky-Zerlegung nicht mit der Hauptachsentransformation ver-wechseln! L muss keine orthogonale Matrix sein.
2.4.6 Korollar
Jede s.p.d. Matrix A ∈ Rn×n besitzt eine eindeutige Zerlegung A = L · LT miteiner unteren ∆-Matrix L.
Beweis:
D ist nach Satz 2.4.4 positiv definit, d.h. D = diag(di) di > 0⇒ ∃ D
12 := diag(
√di) also gilt (D
12 ·D
12 = D)
also L := L ·D12 ist untere ∆ -Matrix.
2.4.7 Algorithmus (Cholesky-Zerlegung)
for k = 1, ..., n do
lkk := (akk −k−1∑j=1
l2kj)12
for i = k + 1, ..., n do
lik := 1lkk
(aik −k−1∑j=1
lij · lkj)
endend
33
Kapitel 3
Lineare Ausgleichsrechnung
Beispiel:
Bestimmung des Widerstandes x aus Messungen fur die Stromstarke t undSpannung b.Es liegen Messungen (bi, ti), 1 ≤ i ≤ m, m 1 vor.Ohm’sches Gesetz: b = tx also
(3.0.1) bi = ti · xi, 1 ≤ i ≤ m
Aufgrund von (z.B.) Messfehlern, kann man (3.0.1) in der Regel nicht fur alle1 ≤ i ≤ m exakt erfullen.⇒ Bestimme also eine ”Ausgleichsgerade“.
b
t
Gerade mit Steigung x
§1 Methode der kleinsten Fehlerquadrate
Frage:
Was ist eine ”gute“ Ausgleichsgerade?
Gauß (1777-1855):
f(x) =m∑
i=1
(bi − xti)2!→ min
34
Also
f ′(x) =m∑
i=1
−2ti(bi − xti)
=m∑
i=1
(2xt2i − 2tibi)
= 2x
m∑i=1
t2i − 2m∑
i=1
tibi
= 2x‖t‖22 − 2bT t!= 0
d.h. f ′(x) = 0 ⇔ x =bT t
tT t
mit t = (t1, . . . , tm)T , b = (b1, . . . , bm)T
f ′′(x) = 2 ·m∑
i=1
t2i = 2‖t‖22 > 0
⇒ x = bT ttT t
ist Minimal-Stelle.
Allgemein:
• b ∈ Rm m = #Messungen
• A ∈ Rm×n n = #Parameter (oben: n = 1)
Bestimme x ∈ Rn mit
(3.1.1) ‖b−Ax‖ !→ min
3.1.1 Bemerkung
Fur m = n ist (3.1.1) aquivalent zu Ax = b also einem linearen Gleichungssys-tem. Also sind insbesondere alle numerischen Verfahren fur lineare Ausgleichs-probleme auch fur lineare Gleichungssysteme nutzbar.
3.1.2 Bemerkung
Die Norm in (3.1.1) kann man noch wahlen.Beispiele:
‖ · ‖2 ∼ Gauß’sche Fehlerquadrate‖ · ‖1 ∼ lineare Optimierung‖ · ‖∞ ∼ Tschebyscheff-Ausgleichsproblem
35
3.1.3 Beispiel
Approximation einer Schwingung durch Sinus- und Cosinus-Wellen.
y(ti, x1, x2, x3) =x1
2+ cos(ti)x2 + (sin ti)x3 i = 1, . . . ,m
⇒ A ∈ Rm×3, ai,1 =12, ai,2 = cos ti, ai,3 = sin ti
§2 Normalengleichungen
Wie kann man die Losung von (3.1.1) fur ‖ · ‖ = ‖ · ‖2 charakterisieren /berechnen?
‖b−Ax‖22 = (b−Ax)T (b−Ax) = xT AT Ax− 2xT AT b + bT b︸ ︷︷ ︸=:f(x)
!−→ Min.
=⇒ f′(x) = 2AT Ax− 2AT b, f
′′(x) = 2AT A
3.2.1 Lemma
Wenn A ∈ Rm×n,m ≥ n, vollen Rang hat, dann ist AT A symmetrisch positivdefinit.
Beweis:
xT AT Ax = (Ax)T (Ax) = ‖Ax‖22 ≥ 0und wegen Rang(A) = n gilt ”= 0“ ⇔ x = 0
3.2.2 Satz
Der Vektor x ∈ Rn lost (3.1.1) fur ‖ · ‖ = ‖ · ‖2 genau dann, wenn er Losung derNormalengleichung
(3.2.1) AT Ax = AT b
ist. Insbesondere ist (3.2.1) eindeutig losbar, wenn A vollen Rang n hat.
Beweis:
AT A ist genau dann regular, wenn Rang(A) = n.Lemma 3.2.1 f
′′(x) > 0
und das Minimum von f ist charakterisiert durch f′(x) = 0, was aquivalent zu
(3.2.1) ist.
Numerisch ist (3.2.1) allerdings unbrauchbar:
(a) Die Berechnung von AT A ist von der Ordnung O(m ·n2) mit eventuell sehrgroßen m!
(b) Bei
(AT A)ij =m∑
k=1
aki · akj
konnen massive Ausloschungseffekte auftreten.
36
(c) Zur Erinnerung:κ(A) = ‖A‖ · ‖A−1‖ fur regulare A ∈ Rn×n (Def. 2.1.1, Satz 2.1.5). Mankann folgendes zeigen
(3.2.2) κ(A) =max‖x‖=1 ‖Ax‖min‖x‖=1 ‖Ax‖
(Ubung)
und mit (3.2.2) definiert man κ(A) fur beliebige A ∈ Rm×n
κ2(A)2 =max‖x‖2=1〈Ax,Ax〉min‖x‖2=1〈Ax,Ax〉
=λmax(AT A)λmin(AT A)
(∗)= κ2(AT A)
(∗) 〈Ax,Ax〉 = 〈AT Ax, x〉d.h. die Kondition wird extrem verschlechtert!
§3 QR-Zerlegung
Idee:
Sei Q ∈ Rm×m eine orthogonale Matrix (d.h. Q−1 = QT ).
⇒ 1 = ‖Id‖2 = ‖QT Q‖2λmax(QT Q)=λmax(Q)2
↓= ‖Q‖22
⇒ ‖Q‖2 = 1
also ‖Qv‖2 = ‖v‖2 ∀v ∈ Rn
⇒ ‖Ax− b‖2 = ‖QT (Ax− b)‖2 = ‖QT Ax−QT b‖2
Wahle Q so geschickt, dass der letzte Ausdruck leicht zu minimieren ist.A = QR, wobei R eine ∆-Matrix ist:R =
(R 0
)mit R ∈ Rn×n mit det R 6= 0 (da Rang R = n).
Dann gilt
‖Ax− b‖22 = ‖QT
=A︷︸︸︷QR x−QT b‖22 = ‖Rx−QT b‖22
= ‖[
R0
]x−
[b1
b2
]‖22 mit QT b =
[b1
b2
]→ n→ m− n
= ‖Rx− b1‖22 + ‖b2‖22︸ ︷︷ ︸(∗)
(∗) hangt nicht von x ab, kann also nicht minimiert werden!
⇒ (3.3.1) ‖Ax− b‖2 → Min ⇔ Rx = b1
3.3.1 Algorithmus
1. Bestimme die QR-Zerlegung von A (spater) und berechne QT b.
2. Lose Rx = b1 durch Ruckwartseinsetzen.
37
3.3.2 Bemerkung
(a) Wegen κ2(Q) = 1 und ‖Ax‖2 = ‖QRx‖2 = ‖Rx‖2 = ‖Rx‖2 gilt
κ2(A) = κ2(R)
d.h. die Kondition bleibt gleich.
(b) Der Ausdruck ‖b2‖2 ist der unvermeidbare Fehler des Ausgleichsproblemsund heißt Residuum.
Nun zur Bestimmung der QR-Zerlegung:A = QR bedeutet offenbar eine Orthogonalisierung von A. Gram-Schmidt,aber:
• geht nur fur regulare A
• ist außerst instabil, wenn A fast singular
§3.1 Givens-Rotation
(Givens 1953)
Idee:
Drehe die Spaltenvektoren sukzessive in Achsenrichtung.
3.3.3 Beispiel
In 2D ist eine Drehmatrix um den Winkel ϕ gegeben durch
R(ϕ) =(
cos(ϕ) sin(ϕ)− sin(ϕ) cos(ϕ)
)det R(ϕ) = 1, R(ϕ)−1 = R(ϕ)T = R(−ϕ)
Nun sei (a, b)T ∈ R2 gegeben. Man bestimme ϕ ∈ [0, 2π) so, dass
(3.3.2) R(ϕ)(
ab
)=(
r0
)(”rechte ∆-Matrix“)
Drehungen sind langenerhaltend (R(ϕ) ist orthogonal), also
|r|2 = |a|2 + |b|2
und damit kann man (3.3.2) leicht auflosen.
(3.3.3) c := cos ϕ =a√
|a|2 + |b|2, s := sinϕ =
b√|a|2 + |b|2
Beachte: Um R(ϕ) zu bestimmen braucht man nur c und s, aber nicht ϕ!
38
Nun brauchen wir R(ϕ) nur noch in den Rn (n > 2) einzubetten:
Gi,k :=
I 0c 0 . . . . . . 0 s0 1 . . . 0 0...
. . ....
......
.... . .
...0 0 . . . 1 0−s 0 . . . . . . 0 c
0 I
∈ Rn×n
⇒ det Gik = 1, G−1ik = GT
ik Gik ist orthogonal. Offenbar dreht Gik die k-teKomponente auf die i-te und setzt die k-te zu Null, vgl. Bsp. 3.3.3.
G12 · · ·G1n ·A =
∗ −− −− −−0 | |... | ∗ |... | |0 −− −− −−
⇒ (3.3.4)
(n−1∏i=1
n∏k=i+1
Gi,k
)A = R ist eine obere ∆-Matrix.
genauer:
Gik·
x1...
xn
=[x1, . . . , xi−1, (x2
i + x2k)
1/2, xi+1, . . . , xk−1, 0, xk+1, . . . , xn
]T(k > i)
mit a := xi, b := xk und c, s nach (3.3.3).
3.3.4 Algorithmus
Input: a, b
If b = 0 Then c := 1; s := 0 (Identitat)Else If |b| ≥ |a| Then τ := a
b , s := 1√1+τ2
, c := s · τElse τ := b
a , c := 1√1+τ2
, s := c · τ
3.3.5 Bemerkung
(a) Die Fallunterscheidung dient zur Vermeidung von Multiplikationen mitgroßen Fehlern.
(b) Der Algorithmus ist außerst stabil, man braucht keine Pivotisierung.
(c) Algorithmus 3.3.4 wird gemaß (3.3.4) in zwei Schleifen eingebettet.
39
(d) Man kann die QR-Zerlegung auch zur Losung linearer Gleichungssystemebenutzen:
A ∈ Rn×n, Ax = bA=QR⇔ Rx = QT b
Aufwand: O(n3), aber stabiler als LR-Zerlegung!
1030
n
κ(R), A = LR
κ(A)
Hinweise zur Implementierung
(a) Aufwand: O(m · n2)
(b) Typischerweise wird A mit Gik ·A uberschrieben.
(c) Man kann Gik in einer Zahl speichern:
ρ = ρik :=
1 falls c = 112 · sgn(c) · s falls |s| ≤ |c|2 · sgn(s)
c falls |s| > |c|
und dann (Ubung):
ρ = 1 ⇒ c = 1, s = 0|ρ| < 1 ⇒ s = 2
ρ , c =√
1− s2
|ρ| > 1 ⇒ c = 2ρ , s =
√1− c2
(d) Offenbar wird Gik ·A nur fur xk 6= 0 ausgefuhrt⇒ man nutzt die Struktur von A aus⇒ Givens ist besonders fur dunn-besetzte Matrizen geeignet
§3.2 Householder-Spiegelungen
(Householder 1958)
Langenerhaltende Abbildungen sind Drehungen und Spiegelungen.
40
|a|e1e1
a
E
v
· α
α
2
−2〈v,a〉〈v,v〉v
Sei v ein Normalenvektor der Ebene E, die die Winkelhalbierende zu a ist.
=⇒ Q1 · a = a− 2 · 〈v, a〉〈v, v〉
· v︸ ︷︷ ︸(∗)
= |a| · e1
(∗) =
(1
vT v·
(n∑
i=1
vi · ai
)· vj
)j=1,...,n
=
(1
vT v·
n∑i=1
vi · vj · ai
)j=1,...,n
=1
vT v(vvT )a
also Q1 = I − 2vvT
vT v
3.3.6 Lemma
Q1 ist symmetrisch, orthogonal und eine Projektion (d.h. Q21 = I).
Beweis:
• (vvT )T = vvT
• Q1 ·QT1 = QT
1 ·Q1 = I − 4v·vT
vT ·v + 4 1(vT ·v)2
v(vT v)vT = I
und Q1 = QT1 ⇒ Q2
1 = I
Nun sei y ∈ Rn gegeben, wahle nun v ∈ Rn so, dass
Q1 · y = α · e1, α = ‖y‖2,
41
also
αe1 = y − 2 · vT y
vT v· v ∈ spane1 = 〈e1〉
⇒ v ∈ spany − αe1
Setze also v := y − αe1, α = ±‖y‖2 und wahle das Vorzeichen zur Vermeidungvon Ausloschung:
α := −sgn(y1) · ‖y‖2, y = (y1, . . . , yn)T
⇒ vT v = 〈y − αe1, y − αe1〉= ‖y‖22︸︷︷︸
=α2
−2α 〈y, e1〉︸ ︷︷ ︸=y1
+α2
= 2α2 − 2αy1
= (−2α)(y1 − α)
und damit fur beliebige x ∈ Rn (x 6= y):
Q1x = x− 2vT x
vT vv = x +
vT x
α(y1 − α)= x +
xT (y − αe1)α(y1 − α)
⇒ A(1) := Q1 ·A =
α1 ∗ . . . ∗0 ∗ . . . ∗...
......
0 ∗ . . . ∗
mit α1 = −sgn(a11) · ‖A1‖2 mit der i-ten Spalte Ai von A.Nach k Schritten hat man dann die Matrix:
A(k) =
∗
0. . . R(k)
.... . . ∗
... 0
...... T (k+1)
0 . . . 0
Wie oben bildet man Qk+1, um die erste Spalte der Restmatrix T (k+a) auf ek+1
zu spiegeln und setzt
Qk+1 :=
Ik×k | 0−−− + −−−
0 | Qk+1
∈ Rn×n
• Qk+1 ist orthogonal.
• R = Qp · · ·Q1 ·A mit p = minm−1, n, also A = QR mit QT = Q1 · · ·Qp
42
Hinweise zur Implementierung
(a) Neben R muss man die Householder-Vektoren v1, . . . , vp speichern. Die Dia-gonale rii = αii speichert man separat. Aufwand: O(m · n2)
(b) Man kann Pivotstrategien verwenden, um numerisch r = Rang(A) zu be-stimmen.
(c) Qk spiegelt den gesamten Vektor x, eine Ausnutzung der Struktur ist nichtmoglich!
§4 Singularwertzerlegung
(SVD = Singular Value Decomposition)
3.4.1 Satz (SVD)
Zu jedem A ∈ Rm×n existieren orthogonale Matrizen U ∈ Rm×m, V ∈ Rn×n
und eine Diagonalmatrix
Σ := diag(σ1, ..., σp) ∈ Rm×n, p := minm,n
mit σ1 ≥ σ2 ≥ ... ≥ σp ≥ 0 (den Singularwerten), so dass
(3.4.1) A = UΣV T
Beweis:
Es genugt zu zeigen, dass
UT AV =(
σ 00 B
)
43
mit σ ≥ 0, B ∈ R(m−1)×(n−1), der Rest folgt induktiv.Sei
σ := ‖A‖2 = sup‖x‖2=1
‖Ax‖2
Da B1(0) := x ∈ Rn : ‖x‖2 = 1 kompakt ist, existiert ein v ∈ B1(0) mit
‖Av‖2 = ‖A‖2‖v‖2 = σ
→ u := 1σAv erfullt
Av = σu, ‖u‖2 = 1
Erganze u, v zu Orthonormalbasen:
u = U1, U2, ..., Um des Rm
v = V 1, V 2, ..., V n des Rn
Also sind die Matrizen U := (U1, ..., Um), V := (V 1, ..., V n) orthogonal und
A1 := UT AV = (UT AV 1︸︷︷︸=σu
, ..., UT AV n)
= (σe1, UT AV 2, ..., UT AV n)
=
σ wT
0 −−−| |
... | B || |
0 −−−
mit w ∈ Rn−1
Nun gilt:∥∥∥∥A1
(σw
)∥∥∥∥2
2
=∥∥∥∥(σ2 + wT w
Bw
)∥∥∥∥2
2
≥ (σ2 + wT w)2 = (σ2 + ‖w‖22)∥∥∥∥(σ
w
)∥∥∥∥2
2
also‖A1‖2 = max
x 6=0
‖Ax‖2‖x‖2
≥√
σ2 + ‖w‖22
und damit
σ2 = ‖A‖22 = ‖UA1VT ‖22 = ‖A1‖22 ≥ σ2 + ‖w‖22 ≥ σ2 > 0
⇒ w = 0
3.4.2 Bemerkung
(a) Die SVD kann man als Verallgemeinerung der Hauptachsentransformationinterpretieren.Anwendungen: z.B. Statistik, Turbulenzforschung
(b) Die SVD ist außerst stabil.
44
(c) Mit A = UΣV T folgt AT = V ΣT UT , also AT A = V ΣT UT UΣV T =V Σ2V T mit Σ2 = diag(σ2
1, ..., σ2n).
(d) Der SVD-Algorithmus besteht
• aus einer Bidiagonalisierung von A
• symmetrische QR fur AT A
Golub, Van Loan, ”Matrix Computation“, 1989, S. 427-435
3.4.3 Definition: Moore-Penrose-/Pseudo-Inverse
Angenommen A ∈ Rm×n habe den Rang r und die SVD A = UΣV T , dann heißtdie Matrix
(3.4.2) A+ := V Σ+UT
mit Σ+ := diag( 1σ1
, ..., 1σr
, 0, ..., 0) Moore-Penrose- oder Pseudo-Inverse von A.
3.4.4 Lemma
Die Pseudo-Inverse von A ∈ Rm×n hat folgende Eigenschaften:
(a) A+ = (AT A)−1AT (falls A vollen Rang hat)
(b) (A+A)T = A+A, (AA+)T = AA+
(c) A+AA+ = A+
(d) AA+A = A
(e) Falls A vollen Rang hat, gilt A+︸︷︷︸Linksinverse
A = I
Beweis:
Ubung.
Bemerkung:
Die Eigenschaften (a) bzw. (b) bis (e) konnen auch zur Definition von A+
herangezogen werden und heißen Penrose-Axiome.
3.4.5 Satz
Sei A ∈ Rm×n, m ≥ n, b ∈ Rm. Dann ist x = A+b diejenige Losung von
‖Ax− b‖2 → Min
mit der kleinsten euklidischen Norm.
45
Beweis:
Nach Satz 3.2.2 gilt AT Ax = AT b, also x = (AT A)−1AT︸ ︷︷ ︸=A+
b.
Hat man 2 Losungen x1, x2 ∈ Rn, dann gilt:
AT Ax1 = AT b = AT Ax2 ⇔ AT A(x1 − x2) = 0
also(x1 − x2)T AT A(x1 − x2) = ‖A(x1 − x2)‖22⇔ A(x1 − x2) = 0⇔ x1 − x2 ∈ ker(A)
Wenn also x eine Losung des linearen Ausgleichsproblems ist, dann hat jedeandere Losung x die Form x = x+y mit y ∈ ker(A). Also folgt die Minimalitat,wenn wir zeigen, dass A+b⊥ ker(A) ist (orthogonale Projektion), denn dann giltfur jede Losung x = x + y:
‖x‖22 = ‖x + y‖22 = 〈x + y, x + y〉 = ‖x‖22 + 2 〈x, y〉︸ ︷︷ ︸=0
+‖y‖22 = Minimal⇔ y = 0
Sei also y ∈ ker(A).
yT A+b3.3.4(c)
= yT A+AA+b = ((A+A)T y)T A+b3.3.4(b)
= (A+Ay)T A+b = 0
46
Kapitel 4
Iterative Verfahren zur Losunglinearer Gleichungssysteme
§1 Große Gleichungssysteme und dunnbesetzte Ma-trizen
In der Praxis treten oft Systeme Ax = b mit A ∈ Rn×n und n ≈ 106 − 109 auf. Gauß/Cholesky sind dort vollig unbrauchbar!
4.1.1 Beispiel: Die schwingende Membran
1
10
Ω
Die Auslenkung u : Ω→ R einer eingespannten Membran unter der Einwirkungeiner außeren Kraft f : Ω→ R ist gegeben durch
(4.1.1)−∆u(x) + λu(x) = f(x) ∀x ∈ Ω
u(x) = 0 ∀x ∈ ∂Ω (Randwerte)
mit λ ∈ R (Dampfungs-Konstante) und dem Laplace-Operator
∆u = uxx + uyy =2∑
i=1
∂2
∂x2i
u
Zu einem numerischen Verfahren fur (4.1.1) kommt man, indem man z.B. dieAbleitungen durch Differenzenquotienten approximiert: Finite Differenzen-Verfahren.
47
Dies zunachst in 1D:
(4.1.2)−u′′(x) + λu(x) = f(x) ∀x ∈ (0, 1)
u(x) = 0 ∀x ∈ 0, 1
λ
u f
m = 1
Erde
Unterteile Ω = (0, 1) durch ein Gitter der Schrittweite h = 1N , N ∈ N, N > 1.
xi
x0 = 0 1 = xN
h
xi = ih, i = 0, ..., N (Knoten, Schnittstellen)∆xi = xi+1 − xi = h (”aquidistantes Gitter“)
Approximiere nun
(4.1.3) u′′(xi) ≈1h2
(u(xi−1)− 2u(xi) + u(xi+1)) =: Dhu(xi)
und mit Taylor zeigt man∣∣u′′(xi)−Dhu(xi)∣∣ = O(h2), u ∈ C4(Ω) (Ubung)
Nun betrachtet man (4.1.2) nur fur x = xi und bestimmt eine Naherung ui ≈u(xi) durch (fi := f(xi))
(4.1.4)
1h2 (−ui−1 + 2ui − ui+1) + λui = fi, 1 ≤ i ≤ N − 1,
u0 = uN = 0
also ein lineares Gleichungssystem Ahuh = fh mit
uh = (u1, . . . , uN−1)T , fh = (f1, . . . , fN−1)T ∈ RN−1
und (”Standard-Matrix“)
Ah =
(2 + h2λ) −1
−1. . . . . .. . . . . . . . .
. . . . . . −1−1 (2 + h2λ)
∈ R(N−1)×(N−1)
48
4.1.2 Bemerkung
(a) Fur h→ 0+ konvergiert uh gegen die exakte Losung u.
(b) Obiges Ah ist eine Tridiagonalmatrix. Fur solche Matrizen kann man dieLR-Zerlegung explizit angeben und erhalt daraus einen optimalen O(N)-Losungsalgorithmus (Ubung, FLENS-Homepage). In 2D geht dies schonnicht mehr!
4.1.3 Beispiel
Nun weiter in 2D:∆u(x, y) = uxx(x, y) + uyy(x, y)
≈ 1h2
[u(x− h, y)− 2u(x, y) + u(x + h, y) + u(x, y − h)− 2u(x, y) + u(x, y + h)]
1
−1
−1
1−4
(x, y + h)
(x − h, y)
(x, y − h)
(x + h, y)(x, y)
”5-Punkte-Stern“
︸ ︷︷ ︸
h
︸︷︷
︸
h
Gitter
Die Gitterpunkte mussen noch nummeriert werden:
xi = (jh, kh), h =1N
, j, k = 1, . . . , N − 1
und i := (j − 1)N + k
49
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
”lexikographische Anordnung“
So erhalten wirAhuh = fh
mituh = (u1, . . . , un), n = (N − 1)2, ui ≈ u(xi)
und (”Block-Tridiagonalmatrix“)
Ah =
Bh Ch 0
Ch Bh. . .
. . . . . . . . .. . . . . . Ch
0 Ch Bh
∈ R(N−1)2×(N−1)2
mit Bh =
4 + h2λ −1 0
−1. . . . . .. . . . . . . . .
. . . . . . −10 −1 4 + h2λ
∈ R(N−1)×(N−1)
und Ch = diag(−1, . . . ,−1) ∈ R(N−1)×(N−1)
4.1.4 Bemerkung
(a) In 3D erhalt man ein System der Große (N − 1)3, in dD (N − 1)d (Fluchder Dimensionen).
(b) Ah ist symmetrisch positiv definit.
(c) In 1D hat Ah:(N − 1) + 2(N − 2) = 3N − 5 = O(N) = O(n)Nicht-Null-Elemente, in 2D:(N − 1) · [N − 1 + 2(N − 2)] + 2 · (N − 2)(N − 1) = 5N2 − 14N + 9 =O(N2) = O(n)wobei n der Matrixdimension Rn×n entspricht. Ah ist dunn-besetzt!
50
4.1.5 Definition: Dunn-besetzte/sparse Matrizen
Eine Matrix A ∈ Rn×n heißt dunn-besetzt (engl. sparse), wenn es eine Kon-stante C > 0, C n gibt mit
#ai,j : ai,j 6= 0 ≤ C · n = O(n).
Bemerkung:
In 1D kann man C = 3, in 2D C = 5 wahlen.
Frage:
Welcher Aufwand zur Losung von Ax = b mit A ∈ Rn×n sparse ist ”optimal“?Antwort: O(n)!Vergleich: Gauß / Cholesky: O(n3)
4.1.6 Bemerkung
Wie kann man sparse Matrizen mit Aufwand O(n) speichern?Jedes Element: O(n2)
Beispiel: compressed sparse row (csr-Format)
Gegeben: A ∈ Rn×n mit N := #non-zeros (N n2)Man speichert 3 Vektoren:
Ae ∈ RN Eintrage Ae(i) ∈ R der MatrixAc ∈ NN Spaltenindizes Ac(i) ∈ NAr ∈ Nn Position des 1. Nicht-Null-Eintrages pro Zeile
Beispiel:
A =
1 0 1 00 1 0 40 3 2 01 0 0 3
n = 4, N = 8
Ae = (1, 1, 1, 4, 3, 2, 1, 3)Ac = (1, 3, 2, 4, 2, 3, 1, 4)Ar = (1, 3, 5, 7)
Speicheraufwand: 2N + n = O(n)Fur spezielle Matrizen (symmetrisch, Band, Block) gibt es spezielle Formate.
§2 Klassische Iterationsverfahren
• Gauß / Cholesky sind ”direkte“ Verfahren: bei exakter Rechnung hat mandie Losung von Ax = b nach endlich vielen Schritten.
• Iteratives Verfahren: x(0) Startwert Iteration: x(k) mit x(k) → x ”schnell“
51
Idee:
Sei Q ∈ Rn×n regular.
Ax = b ⇔ Q−1(b−Ax) = 0
⇔ x = x + Q−1(b−Ax)︸ ︷︷ ︸=:Φ(x)
=
=:G︷ ︸︸ ︷(I −Q−1A) x +
=:c︷ ︸︸ ︷Q−1b
d.h. x ist ein Fixpunkt von Φ.Analog zum Banach’schen Fixpunktsatz gilt:
4.2.1 Satz
Sei G ∈ Rn×n symmetrisch. Das Fixpunktverfahren
x(k+1) = Gx(k) + c
konvergiert genau dann fur jeden Startwert x(0) ∈ Rn, wenn ρ(G) < 1, wobei
(4.2.1) ρ(G) := max1≤j≤n
|λj(G)|
der Spektralradius (betragsgroßter Eigenwert) von G ist.
Beweis:
G ist symmetrisch ⇒ G ist diagonalisierbar, d.h. ∃ Q ∈ Rn×n orthogonal mit
QGQT = Λ = diag(λ1, . . . , λn)
Nun gilt:
x(k+1) = Gx(k) + c = G2x(k−1) + Gc + c
= . . . =
= Gk+1x(0) +
(k∑
i=0
Gi
)c
also konvergiert x(k)k≥0 genau dann, wenn Gk k→∞−→ 0.Es gilt aber
Gk = (QT Λ
Id︷ ︸︸ ︷Q) · · · (QT ΛQ)︸ ︷︷ ︸
k−mal
undΛk = diag(λk
1, . . . λkn)
also
limk→∞
Gk = 0 ⇔ |λi| < 1 ∀i
⇔ ρ(G) < 1
52
4.2.2 Bemerkung
(a) Fur jede vertragliche Norm ‖ · ‖ gilt fur x ∈ Rn mit Ax = λmaxx, ‖x‖ = 1:
λmax = λmax · ‖x‖ = ‖λmax · x‖ = ‖A · x‖ ≤ ‖A‖ · ‖x‖ = ‖A‖
also
ρ(G) ≤ ‖G‖
also ist(4.2.2) ‖G‖ < 1
hinreichend in Satz 4.2.1.
(b) In der Praxis verlangt man, dass Gx ”leicht“ zu berechnen ist (also vorallem Q−1).
(c) Je kleiner ρ(G) (bzw. ‖G‖) ist, desto schneller konvergiert das Verfahren.
§2.1 Das Richardson-Verfahren
Die einfachste Wahl Q := I liefert
(4.2.3) x(k+1) = x(k) −Ax(k) + b, d.h. G = I −A
Falls A ∈ Rn×n s.p.d.⇒ ρ(I−A) = max|1−λmax(A)|, |1−λmin(A)|. (Ubung)⇒ (4.2.3) konvergiert, falls λmax(A) < 2.
Variante:
Gedampftes Richardson-Verfahren:
Q := ω−1 · I, ω ∈ R \ 0
Man kann zeigen, dass fur jede s.p.d.-Matrix A ein Dampfungsparameter ω ∈(0, 2) existiert, mit ρ(I − ωA) < 1.Vorsicht: das Verfahren kann sehr sensitiv von ω abhangen!Außerdem kann die Konvergenz sehr langsam sein.
§2.2 Das Jacobi-Verfahren
Verwende die additive Zerlegung
(4.2.4) A = L + D + R (NICHT: A=LR!)
mit D = diag(A) = diag(a11, . . . , ann) und dem unteren bzw. oberen Teil L, Rvon A.Wahle Q := D
x(k+1) = (I −D−1A)x(k) + D−1b
= (I −D−1(L + D + R))x(k) + D−1b
(4.2.5) = −D−1(L + R)x(k) + D−1b
53
4.2.3 Satz
Das Jacobi-Verfahren (4.2.5) konvergiert fur jeden Startwert x(0) gegen x =A−1b, falls A symmetrisch und strikt diagonaldominant ist, d.h.
(4.2.6) |ai,i| >∑i6=j
|ai,j | ∀ i = 1, . . . , n.
Beweis:
G = I −D−1A = −D−1(L + R)
und
ρ(G)Bem. 4.2.2 (a)
≤ ‖D−1(L + R)‖∞ = max1≤i≤n
∑i6=j
∣∣∣∣ai,j
ai,i
∣∣∣∣ (4.2.6)< 1
und die Behauptung folgt aus Satz 4.2.1.
4.2.4 Bemerkung
(a) Man kann (4.2.6) abschwachen zur sogenannten schwachen Diagonaldominanz:in (4.2.6) ”≥“ statt ”>“ und nur fur einen Index hat man ”>“.
(b) Die Konvergenzgeschwindigkeit hangt von (4.2.6) ab!
(c) Pro Schritt (k)→ (k+1) benotigt man etwa eine Matrix-Vektor-Mulitplikation.
A voll besetzt: O(n2) O(#Schritte · n2)A sparse: O(n) O(#Schritte · n)
(d) Das Jacobi-Verfahren heißt auch Gesamtschritt-Verfahren (GSV).
4.2.5 Bemerkung
In der Praxis kann man Ax = b niemals exakt losen, auch nicht mit direktenVerfahren. Man mochte Ax = b bis auf vorgegebene Genauigkeit ε > 0 losen.‖x− x(approx.)‖ < ε fur eine geeignete Norm ‖ · ‖.Die Anzahl der benotigten Schritte hangt also ab
• von der Konvergenz-Geschwindigkeit
• von ε
Da man ρ(G) i.d.R. nicht kennt, kann man hier keine Vorhersage uber dieAnzahl k(ε) der notwendigen Schritte machen.
54
§2.3 Das Gauß-Seidel-Verfahren
Idee:
Verwende mehr Informationen uber A in Q: Q := D + L
x(k+1) = (I − (D + L)−1A)x(k) + (D + L)−1b
= (I − (D + L)−1(D + L + R))x(k) + (D + L)−1b
(4.2.7) = −(D + L)−1Rx(k) + (D + L)−1b
Pro Schritt mussen 2 gestaffelte Gleichungssysteme gelost werden, (D + L)−1
wird NICHT berechnet!
A sparse Aufwand pro Schritt: O(n).
Fur den Konvergenzbeweis benotigen wir einige Vorbereitungen.G = I − (D + L)−1A ist nicht symmetrisch.→ Satz 4.2.1 ist nicht anwendbar!
4.2.6 Definition
Sei A ∈ Rn×n und definiere
(4.2.8) (x, y)A := xT Ay = 〈x,Ay〉, x, y ∈ Rn
sowie(4.2.9) ‖x‖A :=
√(x, x)A.
4.2.7 Lemma
‖ · ‖A bildet eine Norm, falls A s.p.d. auf dem Rn, die sog. Energienorm, (·, ·)A
heißt Energie-Skalarprodukt.
Beweis:
1.) Positivitat: ‖x‖2A = xT Ax > 0 ∀x 6= 0, da A s.p.d. und ”= 0“⇔ x = 0
2.) Homogenitat: ‖αx‖A =√
α2xT Ax = |α| · ‖x‖A ∀α ∈ R
3.) Dreiecksungleichung: A s.p.d. ⇒ A ist diagonalisierbar:A = QDQT mit D = diag(λ1(A), . . . , λn(A)), λi(A) > 0Definiere A
12 := QD
12 QT = (
√A) mit D
12 := diag
(√λ1(A), . . . ,
√λn(A)
)⇒ A
12 ·A
12 = QD
12 QT Q︸ ︷︷ ︸
I
D12 QT = QDQT = A und A
12 ist symmetrisch.
⇒ ‖x‖2A = xT Ax = xT A12 A
12 x
= (A12 x)T A
12 x = ‖A
12 x‖22
⇒ ‖x + y‖A = ‖A12 x + A
12 y‖2
4−Ungl.≤ ‖A
12 x‖2 + ‖A
12 y‖2 = ‖x‖A + ‖y‖A
55
4.2.8 Definition: A-adjungierte Matrix, A-positiv, A-s.p.d.
Fur A ∈ Rn×n heißt
(a) B∗ := A−1BT A die zu B ∈ Rn×n A-adjungierte Matrix,
(b) eine A-selbstadjungierte Matrix B (d.h. B∗ = B) A-positiv (A-s.p.d.) falls
(Bx, x)A > 0 ∀x 6= 0
4.2.9 Bemerkung
Fur x, y ∈ Rn gilt:
(x,B∗y)A = xT A
=B∗︷ ︸︸ ︷(A−1BT A) y = (Bx)T Ay = (Bx, y)A.
4.2.10 Lemma
Ist B := I −G∗G A−s.p.d., so folgt ρ(G) < 1.
Beweis:
Fur alle x 6= 0 gilt:
0B ist A−s.p.d.
< (Bx, x)A = (x, x)A−(G∗Gx, x)A = ‖x‖2A−(Gx,Gx)A = ‖x‖2A−‖Gx‖2A.
also ‖Gx‖A < ‖x‖A und damit mit Bemerkung 4.2.2
ρ(G) ≤ ‖G‖A = max‖x‖A=1
‖Gx‖A‖x‖A
< 1
4.2.11 Satz
Das Gauß-Seidel-Verfahren konvergiert fur jede s.p.d. Matrix A ∈ Rn×n.
Beweis:
A = L + D + R ist symmetrisch ⇒ L = RT
⇒ G = I −Q−1A = −(D + RT )−1R = I − (D + RT )−1A und
G∗ = A−1GT A = I −A−1 AT︸︷︷︸A︸ ︷︷ ︸
I
(D + RT )−T A
= I − (DT + R)−1A
= I − (D + R)−1A
56
Idee: Zeige, dass B := I −G∗G A−s.p.d.Dazu:
B = I −G∗G = I − (I − (D + R)−1A)(I − (D + RT )−1A)= I − I − (D + R)−1A︸ ︷︷ ︸
=I+(D+R)−1RT
(D + RT )−1A + (D + R)−1A + (D + RT )−1A
= −(D + RT )−1A− (D + R)−1RT (D + RT )−1A + (D + R)−1A + (D + RT )−1A
= −(D + R)−1 (RT (D + RT )−1 − I)︸ ︷︷ ︸=−D(D+RT )−1
A
= (D + R)−1D(D + RT )−1A
und wegen
(D + R)−T = (D + RT )−1 folgt(Bx, x)A = 〈(D + R)−1D(D + RT )−1Ax,Ax〉
= 〈D(D + RT )−1Ax, (D + RT )−1Ax〉= 〈D
12 (D + RT )−1Ax,D
12 (D + RT )−1Ax〉
= ‖D12 (D + RT )−1A︸ ︷︷ ︸regulare Matrix
x‖22 > 0 ∀x 6= 0
⇒ B ist A−s.p.d.
4.2.12 Bemerkung
(a) Das Verfahren heißt auch Einzelschritt-Verfahren (ESV).
(b) Man kann leichte Verbesserungen mit einem Relaxationsparameter ω ∈ Rerreichen:
x(k+1) = ω(Gx(k) + c) + (1− ω)x(k)
Man kann zeigen, dass der optimale Parameter
ωopt. =2
2− λmax(G)− λmin(G)lautet.
(c) Da G = −(D+L)−1R i.A. nicht symmetrisch ist, ist das GSV unsymmetrisch.Mit
G := (D + R)−1L(D + L)−1R
= (−(D + R)−1L)(−(D + R)−1R)
erhalt man eine symmetrische Variante (SGS, SGSV), welche ebenfalls furalle A ∈ Rn×n s.p.d. konvergiert.
(d) Heutzutage werden die obigen Verfahren kaum noch zur Losung von Ax = beingesetzt, sehr wohl aber als ”Gitter“ bei Mehrskalen-Verfahren:
• vorkonditionierte cg-Verfahren (spater)• Mehrgitter (Beispiel)
57
§3 Gradienten-Verfahren
Annahme:
A ∈ Rn×n s.p.d.
Idee:
Schreibe Ax = b in ein aquivalentes Minimierungsproblem um und verwendenumerische Verfahren hierfur.
Ax = b⇔ x = arg miny∈Rn
f(y)(
d.h. f(x) = miny∈Rn
f(y))
mit f(y) := 12yT Ay − bT y, f : Rn → R
4.3.1 Lemma
Sei A ∈ Rn×n s.p.d., dann gilt
Ax = b⇔ x = arg miny∈Rn
f(y)
Beweis:
∇f(y) = Ay − b = f ′(y)f ′′(y) = H f(y) = A > 0 (s.p.d.)Also ist die Losung x von ∇f(x) = 0 (⇔ Ax = b) das Minimum.
Gradientenverfahren fur allgemeine Funktionen f : Rn → R
• Der Gradient ist die Richtung des steilsten Anstiegs von f.→ −∇f ist eine Abstiegsrichtung.
• Suche entlang dieser Richtung das Minimum.
Startwert: x0 ∈ Rn, fur k = 0, 1, 2, ...
1.) Bestimmung der Abstiegsrichtung: dk := −∇f(xk)
2.) Liniensuche: Suche auf der Geraden xk + t · dk : t ≥ 0 ein Minimum,d.h. bestimme αk ≥ 0 mit f (xk + αk dk) ≤ f (xk + t dk) ∀ t ≥ 0und setze xk+1 := xk + αk dk
⇒ f(x0) ≥ f(x1) ≥ f(x2) ≥ . . .
Fur quadratische Funktionen f(x) = 12 xT Ax−bT x kann man 1.) und 2.) explizit
angeben.
1.) ∇f(x) = Ax− b also dk = −∇f(xk) = b−Axk
58
2.) Liniensuche:
f(x + td) =12(x + td)T A(x + td)− bT (x + td)
=12(x + t(b−Ax))T A(x + t(b−Ax))
− bT (x + t(b−Ax))
=12xT Ax + tdT Ax +
12t2dT Ad− bT x− tbT d
=12t2dT Ad + tdT (Ax− b)︸ ︷︷ ︸
−d
+f(x)
(4.3.1) =12t2dT Ad− tdT d + f(x)
(4.3.2)d
dtf(x + td) = tdT Ad− dT d
d2
dt2f(x + td) = dT Ad > 0 falls 0 6= d = b−Ax
⇒ αk = dTk dk
dTk Adk
4.3.2 Bemerkung
Fur allgemeine f : Rn → R kann man
1.) z.B. mit numerischer Differentiation (Numerik II)
2.) mit der sogenannten Schrittweitenregel von Armijo naherungsweise be-stimmen.
t
f(x)
︸ ︷︷ ︸
akzeptierter Bereich
Abstiegsrichtungf(x) +∇f(x)T s(Tangente)
φ(t) = f(x + td)
f(x) + γ∇f(x)T s
Wahle zwei Parameter
– β ∈ (0, 1) (oft β = 12)
– γ ∈ (0, 1) (oft γ ∈ [10−3, 10−2])
Bestimme dann die großte Schrittweite
σk ∈ 1, β, β2, β3, ...
59
mitf(xk)− f(xk + σkdk) ≥ −γ σk ∇f(xk)T dk
d.h.f(xk + σkdk︸ ︷︷ ︸
=: xk+1
) ≤ f(xk) + γ σk ∇f(xk)T dk
Fur die Konvergenzanalyse benutzen wir wieder die Energienorm aus De-finition 4.2.6 bzw. Lemma 4.2.7. Beachte Aquivalenz der Normen auf Rn!Die Fehlerabschatzung geht in 2 Schritten.
4.3.3 Lemma
Fur A ∈ Rn×n s.p.d. gilt mit Ax∗ = b fur die Folge xkk≥0 mit x0 ∈ Rn beliebigund
(4.3.3) dk = −∇f(xk), αk =dT
k dk
dTk Adk
(4.3.4) xk+1 = xk + αkdk
die Abschatzung
(4.3.5) ‖xk+1 − x∗‖2A ≤ ‖xk − x∗‖2A
1−
(dT
k dk
)2(dT
k Adk
) (dT
k A−1dk
)
Beweis:
Zunachst gilt mit (4.3.1)
f(xk+1) = f(xk + αkdk)(4.3.1)
=12
d2k dT
k Adk − dk dTk dk + f(xk)
(4.3.3)= f(xk) +
12
(dTk dk)2
dTk Adk
−(dT
k dk)2
dTk Adk
(4.3.6) = f(xk)−12
(dTk dk)2
dTk A dk
Nun gilt fur die exakte Losung x∗ = A−1b und beliebige x ∈ Rn:
f(x∗) +12‖x− x∗‖2A =
12(x∗)T Ax∗︸︷︷︸
=b
−bT x∗ +12(x− x∗)T A(x− x∗)
= −12bT x∗ +
12xT Ax− xT Ax∗︸︷︷︸
=b
+12(x∗)T Ax∗︸︷︷︸
=b
(4.3.7) = f(x)
d.h.(4.3.8) ‖x− x∗‖2A = 2(f(x)− f(x∗))
60
Setze dies in (4.3.6) ein:
‖xk+1 − x∗‖2A(4.3.8)
x=xk+1= 2 · f(xk+1)− 2 · f(x∗)(4.3.8)x=xk= 2 · f(xk+1)− 2 · f(xk) + ‖xk − x∗‖2A(4.3.6)
= ‖xk − x∗‖2A −(dT
k dk)2
dTk A dk
Wegendk = −∇f(xk) = −A xk + b = −A(xk − x∗)
folgt
‖xk − x∗‖2A = (xk − x∗)T A (xk − x∗)= (A(xk − x∗))T︸ ︷︷ ︸
−dk
A−1(−dk)
= dTk A−1 dk
also(dT
k dk)2
dTk Adk
=(dT
k dk)2
(dTk Adk)(dT
k A−1dk)‖xk − x∗‖2A
Problem:
Der Reduktionsfaktor in Lemma 4.3.3, (4.3.5) hat so nichts mit A zu tun!?
4.3.4 Lemma (Kantorowitsch-Ungleichung)
Sei A ∈ Rn×n s.p.d. und κ = κ2(A), dann gilt
(4.3.9)(xT Ax)(xT A−1x)
(xT x)2≤ 1
4(√
κ +√
κ−1)2
Beweis:
Die Eigenwerte von A seien geordnet gemaß 0 < a = λ1 ≤ λ2 ≤ . . . ≤ λn = b
⇒ κ =b
a
A ist diagonalisierbar⇒ ∃ eine orthogonale Matrix Q : QT AQ = Λ = diag λi
⇒ xT Ax = xT QΛQT xy=QT x
= yT Λy =∑i=1
λiy2i
xT A−1x =n∑
i=1
1λi
y2i
xT x = xT QQT︸ ︷︷ ︸=I
x = yT y
61
⇒ (xT Ax)(xT A−1x)(xT x)2
=
(∑i λiy
2i
) (∑i λ
−1i y2
i
)‖y‖42
=
(n∑
i=1
λizi
)(n∑
i=1
λ−1i zi
)mit zi :=
y2i
‖y‖22
⇒ (f konvex ⇔ f(αx + (1− α)y) ≤ αf(x) + (1− α)f(y))
⇒n∑
i=1
λ−1i zi︸ ︷︷ ︸
=Pn
i=1 zif(λi)
≤ λ1 + λn − λ
λ1λn︸ ︷︷ ︸=g(λ)
mit λ :=n∑
i=1
ziλi
⇒ (xT Ax)(xT A−1x)xT x
≤ λλ1 + λn − λ
λ1λn=: h(λ)
⇒ h′(λ) =λ1 + λn − λ
λ1λn− 2λ
λ1λn=
λ1 + λn
λ1λn− λ
2λ1λn
⇒ λ∗ = λ1+λn2
h′′(λ) = − 2λ1λn
< 0⇒ λ∗ ist Max., also
maxλ∈[λ1,λn]
h(λ) = h(λ∗)
=(λ1 + λn)2
4λ1λn
=14
(√λ1
λn+√
λn
λ1
)2
=14
(√κ +√
κ−1)2
4.3.5 Satz
Fur das Gradientenverfahren mit A ∈ Rn×n s.p.d. gilt
(4.3.10) ‖xk − x∗‖A ≤(
κ− 1κ + 1
)k
‖x0 − x∗‖A
Beweis:
Setze (4.3.9) in (4.3.5) ein.
4.3.6 Bemerkung
(a) Fur κ 1 gilt:
κ− 1κ + 1
=κ
κ + 1︸ ︷︷ ︸≈1
− 1κ + 1
≈ 1− 11 + κ︸ ︷︷ ︸≈0
also sehr nahe bei 1!
62
(b) Dies tritt auch schon bei einfachen Problemen auf:
A =(
1 00 a
), a 1, b =
(00
), x0 =
(a1
)→ (Ubung)
(xk+1
yk+1
)= δ
(xk
−yk
)mit δ = a−1
a+1 und da a = κ2(A)
ist dies genau die Rate aus Satz 4.3.5.
(c) Anschaulich sieht man ein ”Zick-Zack-Verhalten“ der Iteration.
§4 Verfahren der konjugierten Gradienten
- entwickelt 1952 von Hestenes und Stiefel
- enormer Bedeutungsgewinn 1971 durch Vorkonditionierung
- gehort zu den schnellsten Verfahren
- fur 2D-Standardmatrix: A ∈ Rn×n
n ≤ 400→ Choleskyn > 400→ cg-Verfahren
Idee:
Vermeide Zick-Zack durch Verwendung von Orthogonalitat bzgl. (·, ·)A
→ ”konjugierte Gradienten“: cg-Verfahren (conjugate gradient).
Wiederum sei A ∈ Rn×n im Folgenden stets s.p.d.
4.4.1 Bemerkung
(a) 2 Vektoren x, y ∈ Rn heißen konjugiert oder A-orthogonal, falls (x, y)A = 0
(b) Sind x1, ..., xn paarweise konjugiert, d.h.
(4.4.1) (xi, xj)A = δij · ‖xi‖2A , xi 6= 0 ∀ i, j
dann sind x1, ..., xn linear unabhangig (Ubung).
(c) Jedes x ∈ Rn besitzt eine eindeutige Darstellung
(4.4.2) x =n∑
k=1
αkdk
bzgl. konjugierter Richtungen d1, ..., dn.Mit (4.4.1) folgt
(x, di)A =n∑
k=1
αk (dk, di)A︸ ︷︷ ︸=δik‖di‖2A
= αi ‖di‖2A
also
(4.4.3) αi =dT
i Ax
dTi Adi
63
4.4.2 Algorithmus (cg-Verfahren)
Seien d1, ..., dn konjugierte Richtungen und x0 ∈ Rn beliebig. Fur k ≥ 1 sei
1. rk−1 := b−Axk−1, αk :=rTk−1dk
dTk Adk
2. xk := xk−1 + αkdk
4.4.3 Lemma
Algorithmus 4.4.2 liefert nach hochstens n Schritten die exakte Losung, d.h.xn = A−1b.
Beweis:
Fur x∗ = A−1b folgt aus (4.4.2), (4.4.3)
x∗ − x0 =n∑
k=1
αkdk mit αk =dT
k A(x∗ − x0)dT
k Adk=
dTk (b−Ax0)
dTk Adk
Wegen (4.4.1) folgt
dTk A(xk−1 − x0)
Alg. 4.4.2= dT
k A(x0 +k−1∑i=1
αidi − x0)
=k−1∑i=1
αi dTk Adi︸ ︷︷ ︸
=0 (da i6=k)
= 0
also
dTk A(x∗ − x0) = dT
k A(x∗ − xk−1) + dTk A(xk−1 − x0)︸ ︷︷ ︸
=0
= dTk (b−Axk−1)
= dTk · rk−1
⇒ αk = αk ⇒ x∗ = xn
4.4.4 Bemerkung
(a) Lemma 4.4.3 besagt, dass (bei exakter Rechnung) das cg-Verfahren eindirektes Verfahren ist. Fur (sehr) große n ist diese Aussage wertlos. (−→O(n2))
(b) Fur y ∈ Rn heißt r := b − Ay das Residuum von Ax = b, also ist rk dasResiduum von xk.
64
(c) xk+1 minimiert f in Richtung dk, denn wie in (4.3.1)
d
dtf(xk + tdk) = tdT
k Adk + dTk (Axk − b)
= tdTk Adk − dT
k rk,
also t∗ = αk.
Universitat Ulm
Abteilung Numerik
Prof. Dr. Karsten Urban
Numerik Ia — SS 2005
Hier einige Erganzungen zur Vorlesung. Die folgenden Satze stammen aus der Linearen Algebra und solltenGegenstand der Grundvorlesung gewesen sein. Die Nummerieung orientiert sich an der Nummerierung der Vor-lesung.
Lemma 4.4.5: Sei U ein Unterraum eines n-dimensionalen Vektorraums V mit Skalarprodukt (·, ·). Danngibt es zu jedem v ∈ V genau ein u ∈ U mit (v − u, w) = 0, d.h. v − u ∈ U⊥.
Beweis: Sei dim U = k < n. Nach dem Basis–Erganzungssatz gibt es eine Basis ϕ1, . . . , ϕn von V , so
dass ϕ1, . . . , ϕk eine Basis von U ist. Dann ist u =k∑
i=1
αiϕi bestimmt durch
k∑
i=1
(βi − αi) (ϕi, ϕj)︸ ︷︷ ︸
=:aij
= −
k∑
i=k+1
βi(ϕi, ϕj) ∀ 1 ≤ j ≤ k ,
wobei v =n∑
i=1
βiϕi. Mit Au := (aij)i,j=1,...,k ist dies ein lineares Gleichungssystem Auα = b und die Gram–
Matrix Au ist regular.
Lemma 4.4.6: Unter den Voraussetzungen von Lemma 4.4.5 gilt fur ‖v‖ :=√
(v, v), v ∈ V
‖v − u‖ := minu′∈U
‖v − u′‖ ⇐⇒ v − u ∈ U⊥ .
Beweis: Zu v ∈ V sei u ∈ U mit v − u ∈ U⊥ gem. Lemma 4.4.5.
⇒ ∀ u′ ∈ U gilt:
‖v − u′‖2 = ‖v − u + u − u′‖2
= ‖v − u‖2 + 2 (v − u, u − u′
︸ ︷︷ ︸
∈U
)
︸ ︷︷ ︸
=0
+‖u − u′‖2
≤ ‖v − u‖2
und “=” genau dann, wenn u = v′.
Bemerkung 4.4.7: Lemma 4.4.6 gilt auch fur affine Unterraume
‖v − w‖ = minw′∈x+U
‖v − w′‖ ⇐⇒ v − w ∈ U⊥
fur v ∈ V , x + U ⊂ V , U ⊂ V wie in Lemma 4.4.6.
65
.
U
v
u
Abbildung 1: Orthogonale Projektion u = PUv von v auf U .
Offenbar besagen obige Satze: “Die orthogonale Projektion ist die beste Approximation”, wie man es auchintuitiv erwartet. Dieses Situation ist in Abbildung 1 noch einmal verdeutlicht.Die orthogonale Projektion ist wiederum gegeben durch:
u = Pv =
k∑
i=1
(v, ϕi)
(ϕi, ϕi)ϕi,
wenn ϕ1, . . . , ϕk eine Orthogonalbasis von U ist bzw. w = x0 + P (v − x0) im affinen Fall.
4. Juli 2005, Karsten Urban
http://www.mathematik.uni-ulm.de/numerik/teaching/ss05/Numerik1a/ergaenzung1.pdf
4.4.8 Satz
Seien d1, . . . , dk A−konjugierte Richtungen, dann gilt
(4.4.4) ‖xk − x∗‖A = miny∈x0+Uk
‖x∗ − y‖A
mit Uk := spand1, . . . , dk.
Beweis:
d1, . . . , dk ist Orthogonalbasis von Uk bzgl. (·, ·)A, also ist (4.4.4) aquivalentzu
(4.4.5) xk − x0 = P (x∗ − x0)
mit der A−orthogonalen Projektion P auf Uk.Nun gilt:
x0 + P (x∗ − x0) = x0 +k∑
i=0
(x∗ − x0, di)A
(di, di)A· di
und
(x∗ − x0, di)A = dTi A(x∗ − x0) = dT
i (b−Ax0)= dT
i b + dTi A(xi−1 − x0)︸ ︷︷ ︸
=0 (Bew. von Lemma 4.4.3)
−dTi Axi−1
= dTi (b−Axi−1) = dT
i ri−1,
66
also
x0 + P (x∗ − x0) = x0 +k∑
i=1
dTi ri−1
dTi Adi︸ ︷︷ ︸αi
·di = xk,
also (4.4.5).
Bemerkung:
xk heißt auch Ritz-Gralerkin-Approximation (-Projektion) von x∗ in
(4.4.6) Vk := x0 + Uk.
Die Raume Uk heißen Krylov-Raume.Aus Lemma 4.4.3 folgt:
(4.4.7) rk = b−Axk = b−Axk−1 − αAdk
= rk−1 − αkAdk
Wahl der Krylov-Raume
(4.4.8) U0 := 0 , Uk := spanr0, Ar0, . . . , Ak−1r0 , k = 1, 2, . . . , n− 1
Wir brauchen noch d1, . . . , dn.
4.4.9 Lemma
Sei d1, . . . , dk eine A-orthogonale Basis von Uk, dann gilt:
(a) rTk di = 0 ∀ 1 ≤ i ≤ k, d.h. rk ⊥A Uk
(b) Uk = spanr0, . . . , rk−1, falls rk 6= 0, insbesondere
(4.4.9) rTi rj = δijr
Ti ri ∀i, j = 0, . . . , k − 1
Beweis:
(a) Nach Lemma 4.4.5 gilt (x∗ − x0) ⊥A Uk, also fur 1 ≤ i ≤ k:
0 = (x∗ − x0)T Adi = dTi ri−1
(vgl. Beweis von Satz 4.4.8).
(b) Induktion uber k: k = 1 ist trivial.k → k + 1: d1, . . . , dk A−orthogonal und Un = Rn (Lemma 4.4.3)
⇒ Adk︸︷︷︸∈Rn
=n∑
i=1
dTi Adk
dTi di︸ ︷︷ ︸
=δi,k
·di =dT
k Adk
dTk dk
· dk ∈ Uk
⇒ rk(4.4.7)
= rk−1︸︷︷︸∈Uk(IV)
−αk Adk︸︷︷︸∈Uk
∈ Uk
und nach (a) gilt: rk ⊥ Uk, d.h. rTk ri = 0 ∀1 ≤ i < k und wegen rk 6= 0
folgt die Behauptung.
67
Nun zur Definition von d1, . . . , dn:
• falls r0 6= 0 (sonst x0 = A−1b), setze d1 := r0
• fur k > 0: nach Lemma 4.4.9 gilt:
– entweder rk = 0 (xk ist Losung)
– oder Uk+1 = spand1, . . . , dk, rk A-orthogonalisiere diese Vektoren (Gram-Schmidt):
(4.4.10) dk+1 = rk −k∑
j=1
rTk Adj
dTj Adj
· dj
Lemma 4.4.9 (a)= rk −
rTk Adk
dTk Adk︸ ︷︷ ︸
=:βk+1
·dk
Man kann leicht nachrechnen (Ubung), dass
(4.4.11) αk =rTk−1rk−1
dTk Adk
(4.4.12) βk =rTk rk
rTk−1rk−1
gilt, diese Ausdrucke sind stabiler und bzgl. Speicherkapazitat gunstiger.
4.4.10 Algorithmus
Startwert: x0 ∈ Rn
• d1 = r0 = b−Ax0
• fur k = 1 to kmax do
– αk gemaß (4.4.11), xk := xk+1 + αkdk
– falls genau genug: EXIT
– rk = rk−1 − αkAdk
– βk+1 gemaß (4.4.12), dk+1 = rk + βk+1dk.
4.4.11 Satz
Fur das cg-Verfahren gilt
(4.4.13) ‖x∗ − xk‖A ≤ 2 ·
(√κ2(A)− 1√κ2(A) + 1
)k
‖x∗ − x0‖A
68
Beweis: (aus dem Sommersemester 2004)
Sei ek := xk − x∗
1. Zeige induktiv, dass Polynome
pk ∈ Pk, k = 0, . . . , n− 1
existieren mit
(4.4.14) ek = pk(A)e0 , pk(0) = 1
k=0: trivialk-1→k: ek = xk − xk−1 + xk−1 − x∗ = αkdk + ek−1 und
dk = rk−1 + βkdk−1
= b−Axk−1 + βk1
αk−1(ek−1 − ek−2)
= (−A) (xk−1 − x∗)︸ ︷︷ ︸=ek−1
+βk
αk−1(ek−1 − ek−2)
=(
βk
αk−1I −A
)ek−1 −
βk
αk−1ek−2
IV=[(
βk
αk−1I −A
)pk−1(A)− βk
αk−1pk−2(A)
]︸ ︷︷ ︸
=: eqk(A), eqk∈Pk, eqk(0)=0
·e0
also: ek = αkdk + ek−1
= (αkqk(A) + pk−1(A))︸ ︷︷ ︸pk(A), pk(0)=1
·e0
2. Mit (*): rk = b−Axk = A(x∗ − xk) = −Aek folgt:
eTk Aek
(∗)= −eT
k rk(4.4.9)
=
ek −k−1∑j=0
σjrj
T
rk(∗)= −rT
k
ek +k−1∑j=0
σjAej
(4.4.14)
= (Aek)T
pk(A) +k−1∑j=0
σjApj(A)
e0 ∀σ0, ..., σk−1 ∈ Rn
Sei qk ∈ Pk mit qk(0) = 1, ⇒ (Polynomdivision)
∃! σ, ..., σk−1 ∈ Rn mit qk(t) = pk(t) +k−1∑j=0
σk + pj(t)
Mit σi = σi folgt also:
eTk Aek = (Aek)T (qk(A)e0)
= (ek, qk(A)e0)A
CSU≤
√(ek, ek)A ·
√(qk(A)e0, qk(A)e0)A
⇒ ‖ek‖A ≤ ‖qk(A)e0‖A fur alle qk ∈ Pk, qk(0) = 1.
69
3. Fur die EW von A
(0 < λmin = λ1 ≤, . . . ,≤ λn = λmax)
gilt:‖qk(A)e0‖A ≤ ‖e0‖A max
λ∈(λ1,...,λn)|qk(λ)|
4. Man sucht nun Polynome pk, die die rechte Seite minimieren.Man kann zeigen, dass die Tschebyscheff-Polynome
Tk(x) :=12
[(x +
√1− x2
)k+(x−
√1− x2
)k]
, k = 0, 1, . . .
auf [−1, 1] folgende Eigenschaften haben
Tk(1) = 1, |Tk(x)| ≤ 1, ∀x ∈ [−1, 1]
und minimal bzgl. ‖ · ‖∞ unter allen Polynomen p ∈ Pk mit pk(1) = 1sind. Wahle also
Pk(z) := Tk
(λmax − λmin − 2z
λmax − λmin
)/Tk
(λmax + λmin
λmax − λmin
)auf [0, λmax], Pk(0) = 1
⇒ minqk∈Pk
qk(0)=1
maxλ∈(λ1,...,λn)
|qk(λ)| ≤ 1
Tk
(λmax+λminλmax−λmin
)und
Tk
(λmax + λmin
λmax − λmin
)= Tk
(κ + 1κ− 1
)≥ 1
2
(z +
√1− z2
)k
mit z =(
κ+1κ−1
)−1und z +
√1− z2 = κ+1
κ−1 .
§5 Vorkonditionierung
(4.4.13) ⇒ Konvergenz ∼ κ2(A)
Idee:
Verwende B ∈ Rn×n regular.Ax = b ⇐⇒ Ax = b mit A := A ·B, x := B−1x, b := b; und versuche
• B ≈ A−1
• B,B−1
”leicht anwendbar“
• A,B s.p.d. ⇒ A = AB ist selbstadjungiert bzgl. (·, ·)B
(x,ABy)B = xT BABy = (ABx)T By = (ABx, y)B
ersetze in Algorithmus 4.4.10 < ·, · > durch (·, ·)B und (·, ·)A durch (·, ·)AB.
70
4.5.1 Algorithmus (vorkonditioniertes cg-Verfahren, pcg)
Startwert x0 ∈ Rn
• r0 = b−Ax0, d1 = Br0
• for k = 1 to kmax do
– αk =rTk−1Brk−1
dTk Adk
, xk = xk−1 + αkdk
– falls ”genau genug“: EXIT
– rk = rk−1 − αkAdk
– βk+1 = rTk Brk
rTk−1Brk−1
, dk+1 = Brk + βk+1dk
4.5.2 Bemerkung
(a) Satz 4.4.8 gilt jetzt mit κ2(AB) anstelle von κ2(A).
(b) Beispiele fur B:
• Diagonalskalierung: B = diag(A)−1
• Jacobi-Verfahren
• symm. Gauß-Seidel
• ILU - incomplete LU (incomplete Cholesky)
(c) Fur Gleichungssysteme, die von elliptischen partiellen Differentialgleichun-gen/Integralgleichungen Anxn = bn, An ∈ Rn×n erzeugt werden, existierenoptimale Vorkonditionierer Bn:κ2(AnBn) = O(1), n −→∞ ( Gesamt-Verfahren O(n)!)(Oswald 1988, Bramble-Pasciak-Xu 1989)
71
Stichwortverzeichnis
2-er Komplement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55-Punkte-Stern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Aadjungierte Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54Anordnung
lexikographische . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47aquidistantes Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Auflosungsvermogen
eines Rechners. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10Ausgleichsrechnung
lineare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32Methode der kleinsten Fehlerquadrate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Ausloschung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11, 13
BBasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Binardarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Ccg-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .61
Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31csr-Format (compressed sparse row) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
DDampfungsparameter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Definitheit
positiv definit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Diagonaldominanz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52(Finite) Differenzen-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Dreiecksmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
obere/untere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
EEinzelschritt-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
72
Energie-Skalarprodukt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Energienorm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .53Entwicklung
b-adische . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4endliche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
ESV. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Exponent
Gleitpunktdarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
FFehler
-fortpflanzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11-verstarkung. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11-verstarkungsfaktor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17absoluter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9relativer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Fehlerfortpflanzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12Multiplikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Festpunktzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Finite Differenzen-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Fixpunkt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Frobenius-Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
GGauß’sche Fehlerquadrate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33Gauß-Seidel-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Gaußalgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24Gesamtschritt-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52Gitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
aquidistantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46Givens-Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Gleichungssysteme
Direkte Losung linearer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20gestaffelte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24Iterative Verfahren zur Losung linearer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Gleitpunkt-arithmetik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10normalisierte -darstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Gradienten-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56GSV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
HHorner-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
73
Householder-Spiegelungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Hurwitz-Kriterium. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
Iinteger
Darstellung ganzer Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Inverse
Moore-Penrose-. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43Pseudo- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Iterationsverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Gauß-Seidel-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Gradienten-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56Jacobi-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51klassische. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .49
Fixpunktverfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50Idee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50Konvergenzbedingung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Richardson-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .51gedampftes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
Iterative Verfahren zur Losung linearer Gleichungssysteme . . . . . . . . . . . . . . . . . 45
JJacobi-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
KKantorowitsch-Ungleichung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59Kondition
einer Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21eines Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
absolute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15gute . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
konjugierte Gradientenverfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Krylov-Raume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
LLosung
linearer Gleichungssysteme mit direkten Verfahren . . . . . . . . . . . . . . . . . . . . . 20linearer Gleichungssysteme mit iterativen Verfahren. . . . . . . . . . . . . . . . . . . .45
Landau-Symbol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16lexikographische Anordnung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
MMantisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Maschinengenauigkeit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
relative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10Maschinenzahlen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Matrix
74
(strikt) diagonaldominant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52A-adjungiert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54A-positiv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54dunn-besetzt/sparse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Speicherung im csr-Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49schwach diagonaldominant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .52
Mehrskalen-Verfahren. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55Moore-Penrose-Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
NNorm
Energie- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53euklidische . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
OOptimierung
lineare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .33
Ppcg-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Penrose-Axiome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43Permutationen
bei der Spaltenpivotsuche. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27Pseudo-Inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
QQR-Zerlegung
Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Idee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35mit Givens-Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36mit Householder-Spiegelungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
RRechenaufwand
Givens-Rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38Householder-Spiegelungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Ruckwartseinsetzen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .24
Relaxationsparameter. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55Residuum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36Richardson-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
gedampftes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51Ritz-Gralerkin-Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65Robustheit
eines Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Rundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Banker’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
75
Standardrundung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Rundungsfehler
absoluter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9relativer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
SSchrittweitenregel von Armijo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57SGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55SGSV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55Singularwertzerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Skalarprodukt
Energie- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53Spaltenpivotsuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Strategie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Spektralradius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Spektrum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21Stabilitat
eines Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18Stabilitatsanalyse
linearer Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21Standard-Matrix. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46Stern
5-Punkte- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47SVD (Singular Value Decomposition) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
TTridiagonalmatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Block- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Tschebyscheff-Ausgleichsproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Tschebyscheff-Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
VVorkonditionierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
ZZahlen
Darstellung ganzer. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6Speicherung negativer ganzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Zahlendarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4Zerlegung
additive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
76
