Numerische Mathematik A und B

Prof. J.M. Melenk

Ein paar Beispiele bei denen schlechte Numerik katastrophale Folgen hatte. Einige Maximen von N. Trefethen zu Numerik und Scientific Computing

Ein paar Software bugs mit Folgen

Vorlesungen: Mo, 13-14 (EI8), Mi 12-13:30 (EI8), Do 12:10-12:55 (EI3)

Vorbesprechung und erste Vorlesung: Mo, 1.10, 13-14 (EI8)

Übungen: in Kleingruppen

Folien aus der Vorlesung

• einleitende Bemerkungen zu Konvergenz, Effizienz, Fehlerschaetzung
• Rechenzeitvergleich Band-LU und volle LU-Zerlegung
• 3x3 Beispiel fuer Gauss-Elimination
• Beispiel fuer schlecht konditioniertes Problem (eine 3-Term-Rekurrenz)
• Gleitkommazahlen
• allgemeines Zu Kondition und Stabilitaet
• Normen, Matrixnormen
• Beispiel der 3-Term-Rekurrenz ``revisited''
• Ausloeschung bei Addition
• Beispiele von Ausloeschung
• Beispiel zur Spaltenpivotsuche
• Beispiel zur numerischen Stabilitaet von QR-Zerlegung im Gegensatz zu LU-Zerlegung
• Beispiel Ausgleichsrechnung
• Anwendungsbeispiel der SVD: Datenkompression
• Tschebyscheffpunkte und Tschebyscheffinterpolation
• Interpolation in aequidistanten Punkten und Tschebyscheffpunkten---das Runge-Phaenomen
• Motivation der Extrapolation
• numerische Beispiele: Extrapolation von einseitigen und symmetrischen Differenzenquotienten
• Motivation fuer Splineinterpolation
• Bestimmung kubischer interpolierender Splines
• FFT und Faltungssatz
• Newton Cotes Formel und Rombergextrapolation
• klassische Orthogonalpolynome und ihre Drei-Term-Rekurrenzrelationen
• Beispiele fuer das Konvergenzverhalten der Gaussregeln und der summierten Trapez- und Simpsonregeln
• Grundideen der adaptiven Quadratur
• Nullstellensuche mit verschiedenen Fixpunktiterationen
• Beispiel fuer Aitken'sches Delta^2-Verfahren
• Beispiele fuer das Newtonverfahren
• Beispiel fuer gedaempftes Newtonverfahren und gedaempftes Newtonverfahren mit adaptiver Steuerung des Daempfungsparameters
• Wesentliche Ideen beim CG-Algorithmus
• Beispiele fuer die Vektoriteration, inverse Iteration, Rayleighquotienteniteration
• Bemerkungen zu Abbruchkriterien
• Beispiel der orthogonalen Iteration
• Beispiel fuer Konvergenzverhalten der QR-Iteration mit und ohne Shift
• Beweis von Satz 14.26 der Vorlesung

Inhalte

• 1.10.07: Konvergenz, Effizienz, Fehlerschaetzer am Beispiel der Nullstellensuche
• 3.10.07: Kapitel 1.1: Dreieckmatrizen (AuPr: Kap 3.1)
• 4.10.07: Kapitel 1.2: LU-Zerlegung (AuPr: Kap 3.2)
• 8.10.07: Kapitel 1.2: LU-Zerlegung (AuPr: Kap 3.2)
• 10.10.07: Kapitel 1.3: Cholesky-Zerlegung (AuPr: Kap 3.5), Gauss-Elimination (AuPr: Kap 3.3)
• 11.10.07: Kapitel 2.1: Gleitkommaarithmetik
• 15.10.07: Kapitel 2.2, 2.3: Matrixnormen, Kondition (AuPr: Kap 2.1, Kap 1.2)
• 17.10.07: Kapitel 2.4, 2.5, 2.6: Kondition einer Matrix (AuPr Kap 2.2), Vorwaertsstabilitaet und Rueckwaertsstabilitaet (AuPr Kap 1.5)
• 18.10.07: Kapitel 2.7: Rueckwaertsstabilitaet der LU-Zerlegung. Kapitel 3: Gauss-Elimination
• 22.10.07: Kapitel 3: LU-Zerlegung mit Pivotsuche (AuPr: Kap 3.4)
• 22.10.07: Kapitel 4.1: elementare Eigenschaften orthogonaler Matrizen
• 24.10.07: Kapitel 4.2: QR-Zerlegung, QR-Zerlegung mit Pivotsuche (AuPr Kap 3.6)
• 25.10.07: Kapitel 5.1: Ausgleichsprobleme (Methode der Normalengleichung, QR-Zerlegungsmethode), AuPr Kap 3.7
• 29.10.07: Kapitel 5.3: Singulaerwertzerlegung (SVD), AuPr Kap. 3.8
• 31.10.07: Kapitel 5.4: Pseudoinverse Minimum Norm Lsg bei Ausgleichsrechnung, Kondition und Stabilitaet von Ausgleichsproblemen (AuPr Kap 3.8),
  Kapitel 6.1: Existenz und Eindeutigkeit bei Polynominterpolation (AuPr Lemma 4.1, Satz 4.2)
• 5.11.07: Kapitel 6.2.1: Auswertung von Interpolationspolynomen mittels Aitken-Neville (AuPr Satz 4.19)
• 7.11.07: Kapitel 6.3: Fehlerabschaetzungen fuer Polynominterpolation (AuPr Satz 4.3), Kapitel 6.4: Tschebyscheffpunkte und Tschebyscheffpolynome (AuPr Kap 4.3),
• 8.11.07: Kapitel 6.5: Bestapproximation mit Polynomen: der Satz von Weierstrass (AuPr Satz 4.7), der SAtz von Jackson
• 12.11.07: Kapitel 6.6: Bestapproximation vs. Interpolation (AuPr Kap 4.4), das Rungebeispiel fuer das Versagen von Interpolation in aequidistanten Punkten
• 14.11.07: Kapitel 7: Extrapolation (AuPr Kap. 5.1)
• 19.11.07: Kapitel 8.1: lineare Splines (AuPr Kap. 4.8)
• 21.11.07: Kapitel 8.2: Splines hoeherer Ordnung (AuPr Satz 3.35)
• 21.11.07: Kapitel 8.2: Splines hoeherer Ordnung (AuPr Satz 3.35), Kapitel 9.1: trigonometrische Interpolation (AuPr Kap. 4.9 bis p. 138 unten)
• 22.11.07: Kapitel 9.3: FFT
• 26.11.07: Kapitel 9.4: Anwendung der FFT: schnelle Berechnung von Faltungsprodukten wie z.B. Produkte von Polynomen
• 28.11.07: Kapitel 10.1: Newton-Cotes Formeln, Kapitel 10.2: summierte Trapez- und Simpsonregel, Kapitel 10.3: Euler-McLaurinsche Summenformel (AuPr Kap. 6.1-6.3)
• 29.11.07: Kapitel 10.3: Rombergextrapolation der summierten Trapezregel (AuPr Kap 6.3) Kapitel 10.4: Einfuehrung in Gaussquadratur (AuPr Lemma 6.6)
• 3.12.07: Kapitel 10.4: Eigenschaften der Gaussquadratur (Existenz, Exaktheitsgrad, Eindeutigkeit): AuPr: Lemma 6.7, Satz 6.8. 3-Term-Rekursionen: AuPr Lemma 6.9
• 5.12.07: Kapitel 10.4: Gaussknoten als Eigenwerte einer Tridiagonalmatrix (AuPr Satz 6.10), Kapitel 11.1: Fixpunktiterationen (AuPr Satz 7.1)
• 6.12.07: Kapitel 11.1: einfache Kriterien fuer Konvergenz von Fixpunktiteration (AuPr Satz 7.2), Kapitel 11.2: Aitken'sches Delta^2 Verfahren (AuPr Kap 5.2)
• 10.12.07: Kapitel 11.3: Newtonverfahren in 1D und in multi-D (AuPr Kap 7.3)
• 12.12.07: Kapitel 11.3: Konvergenz des Newtonverfahren in multi-D (AuPr Kap 7.3)
• 13.12.07: Kapitel 11.3: Daempfungsstrategien beim Newtonverfahren (AuPr Alg. 7.7)
• 7.1.08: Kapitel 12.1/12.2 einfache iterative Verfahren (Jacobi- und Gauss-Seidel): AuPr Kap 7.6)
• 9.1.08: Kapitel 12.3 Herleitung des CG-Algorithmus (AuPr p. 211-212, p. 217-221)
• 10.1.08: Kapitel 12.4 Konvergenzverhalten des CG-Verfahrens
• 14.1.08: Kapitel 14.1 EWP: Einfluss von Stoerungen auf das Spektrum (Satz von Bauer-Fike), Schur'sche Normalform einer Matrix (AuPr Kap 8.2)
• 16.1.08: Vektoriteration, inverse Vektoriteration (mit und ohne Shift), Rayleighquotienteniteration (AuPr p. 233-238)
• 17.1.08: Abbruchkriterien fuer Vektoriteration
• 21.1.08: orthogonale Iteration
• 23.1.08: Konvergenz der orthogonalen Iteration
• 24.1.08: Herleitung der QR-Iteration aus der (simultanen) orthogonalen Iteration; Konvergenz gegen obere Dreiecksgestalt
• 26.1.08: Hessenbergform, Givensrotationen, Beobachtung, dass QR-Iteration fuer Matrizen in Hessenbergform lediglich O(n^2) Kosten pro Schritt;
• 28.1.08: Herleitung der QR-Iteration mit geeigneten (einfachen) Shifts
• 29.1.08: abschliessende Bemerkungen zur QR-Iteration, Berechnung der SVD

Literatur

• Quarteroni, Sacco, Saleri Numerical Mathematics (Springer). Dieses ueber die Vorlesung hinausgehende Buch deckt sehr viele wichtige Themen der Numerik ab. Die Algortihmen werden in Matlab vorgestellt. Es gibt auch eine deutsche Uebersetzung des Buches
• P. Deuflhard und A. Hohmann: Numerische Mathematik
• R. Schaback und H. Wendland: Numerische Mathematik (Springer)
• R. Plato: Numerische Mathematik kompakt (Vieweg)
• Numerical Recipes (Sammlung von C-Routinen fuer Numerik) gibt es jetzt auch als on-line Buch! Neben den C-Routinen werden die Algorithmen auch kurz "hergeleitet" und beschrieben