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, 12:15-13:45 (FH8), Mi 12:15-13:45 (FH8)

Vorbesprechung und erste Vorlesung: Mo, 5.10, 12:15-13:40 (FH8)

Übungen: in Gruppen in der ersten Semesterhaelfte (Start: 5.10.09), in Kleingruppen in der zweiten

zusaetzliche Infos zu den Uebungen: siehe auch die Seite von Prof. E. Weinmueller

Repetitorium fuer Geodaeten: Mittwochs 10:15-11 im SEM 101A

---

---

Bemerkung zur Form der schriftlichen Aufgaben

Folien aus der Vorlesung

• einleitende Bermerkungen zu Konvergenz, Effizienz, Fehlerschaetzung
• Rechenzeitvergleich volle LU-Zerlegung vs. LU-Zerlegung von Bandmatrizen
• 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
• LU-Zerlegung mit Pivotsuche
• Bsp zur numerischen Stabilitaet des Loesens von LGS mittels QR-Zerlegung anstelle von LU-Zerlegung
• Bsp zur 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
• Beispiele fuer die Vektoriteration, inverse Iteration, Rayleighquotienten iteration
• Bemerkungen zu Abbruchkriterien
• Beispiel der orthogonalen Iteration
• Beispiel fuer Konvergenzverhalten der QR-Iteration mit und ohne Shift
• CG-Verfahren

Übungsblätter (Mathematiker):

Übungsblätter (Geodäten):

Abgabeanleitung: Programmieraufgaben

Inhalte

• 5.10.09: Chap. 1.1, Dreiecksmatrizen, Vorwaerts- und Rueckwaertssubstitution, Existenz von LU-Zerlegungen
• 7.10.09: Chap 1.2: LU-Zerlegung nach Crout, Bandmatrizen
• 12.10.09: Chap 1.3: Choleskyzerlegung, Relation der LU-Zerlegung zur Gausselimination
• 14.10.09: Chap 2.1 (Gleitkommaarithmetik), Chap 2.2 (Matrixnormen), Chap 2.3 (Kondition)
• 19.10.09: Chap 2.2 Vorwaertsfehleranalyse
• 21.10.09: Chap 3 (Rueckwaertsfehleranalyse, LU-Zerlegung mit Spaltenpivotsuche, LU-Zerlegung
• 28.10.09: Chap 4 QR-Zerlegung
• 04.11.09: Chap 5.1 (Methode der Normalengleichung), Chap 5.2 (Methode der QR-Zerlegung), Chap 5.3 SVD
• 09.11.09: Chap 5.4: Minimum Norm Lsg bei Ausgleichsrechnung, Chap 6.1 (Ex. + Eind. von Polynominterpolation), Chap 6.2 (Neville-Schema), Chap 6.3 (eine einfache Fehlerabschaetzung)
• 11.11.09: Chap 6.4. (Tschebyscheffpolynome), Chap. 6.5 (Bestapproximation), Chap 6.6 (Bestapprox. vs. Interpolation)
• 16.11.09: Chap 7 (Extrapolation), Chap 8.1 (lineare Splines)
• 18.11.09: Chap 8.2 (Splines hoeherer Ordnung), Chap 9.1 (trig. Interpolation)
• 23.11.09: Chap 9.2 Anwendung der FFT: schnelle Faltung; Chap 10.1: Quadratur
• 25.11.09: Chap 10.1: Newton-Cotes-Formel, 10.2 summierte Regeln, Satz 10.11 (Euler-McLaurinsche Formel)
• 30.11.09: Chap 10.11: Beispiel fuer Extrapolation, Gaussquadratur (Chap 10.4), 3-Term-Rekurrenzen (Chap 10.5)
• 2.12.09: Chap 10.2: Konvergenzeigenschaften der Gaussquadratur (Chap 10.6), adaptive Quadratur, Banachscher Fixpunktsatz (Satz 11.1)
• 7.12.09: Chap 11.2: Aitkensche Delta^2-Verfahren (Chap 11.2), Newtonverfahren in 1D (Chap 11.3.1), Newtonverfahren in Multi-D, Konvergenz des Newtonverfahrens (Satz 11.9)
• 9.12.09: Chap 11.2: gedaempftes und globalisiertes Newtonverfahren
• 14.12.09: Chap 11.3: Implementierungsaspekte des Newtonverfahrens; Chap 13.1: Normalformen von Matrizen, Chap 13.2 Kondition von Eigenwerten (Satz von Bauer-Fike), Chap 13.3 Vektoriteration
• Rest des Semesters: orthogonale Iteration, Konvergenz des QR-Verfahrens, Shiftstrategien

Literatur

• eine Vorlesungsmitschrift von Roman Hager aus dem WS 07/08
• 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