Numerische Mathematik A und B

Prof. J.M. Melenk

hier zu den Pruefungsterminen

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:50-13:50 (EI8), Mi 12-13:15 (EI8), Do 12:10-12:55 (EI3)

Vorbesprechung und erste Vorlesung: Mi, 1.10, 12-13:30 (EI8)

Übungen: in 4 Gruppen in der ersten Semesterhaelfte, in Kleingruppen in der zweiten

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

---

Übungsgruppen (1. Semesterhaelfte):

Bemerkung zur Form der schriftlichen Aufgaben

Herr Ferraz-Leite war so freundlich, ein Beispiel fuer die Beantwortung von Serie 2, Aufg. 1 zu erstellen.

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

Übungsblätter:

Inhalte

• 1.10.08: Konvergenz, Effizienz, Fehlerschaetzer am Beispiel der Nullstellensuche und Quadratur
• 2.10.08: Kapitel 1: Gauss-Elimination Teil 1. LU-Zerlegung, Parkettierung nach Crout (AuPr Kap. 3.1 + 3.2)
• 6.10.08: Kapitel 1: Bandmatrizen (AuPr Kap. 3.2)
• 8.10.08: Kapitel 1: Cholesky-Zerlegung (AuPr Kap. 3.5)
• 9.10.08: Kapitel 1: Beziehung zwischen LU-Zerlegung und Gauss-Elimination (AuPr Kap. 3.3)
• 13.10.08: Kapitel 2: Gleitkommaarithmetik, Matrixnormen, Spaltensummennorm (AuPr Kap. 1.4, 2.1)
• 15.10.08: Kapitel 2: Wohlgestelltheit eines Problems, Kondition einer Matrix (AuPr Kap. 1.2)
• 16.10.08: Kapitel 2: Vorwaertsanalyse von Algorithmen (AuPr Kap. 1.5)
• 20.10.08: Kapitel 2: Rueckwaertsanalyse von Algorithmen, Rueckwaertsfehler bei Gausselimination
• 22.10.08: Kapitel 3: Gauss-Elimination mit Pivtsuche (AuPr Kap. 3.4)
• 23.10.08: Kapitel 4: QR-Zerlegung: orthogonale Matrizen, Existenz+Eindeutigkeit von QR-Zerlegungen
• 27.10.08: Kapitel 4: QR-Zerlegung mit Householdertransformationen (AuPr Kap. 3.6)
• 29.10.08: Kapitel 4: QR-Zerlegung mit Pivotsuche (AuPr Kap. 3.6), Kapitel 5 Ausgleichsrechnung (Methode der Normalengleichung, Methode der QR-Zerlegung; AuPr Kap. 3.7)
• 30.10.08: Kapitel 5: SVD (AuPr Kap. 3.8), Pseudoinverse
• 03.11.08: Kapitel 5: Minimum norm Lsg bei Ausgleichsproblemen, Kondition und Stabilitaet bei Ausgleichsproblemen (AuPr Kap 3.8)
• 05.11.08: Kapitel 6: Existenz und Eindeutigkeit bei Polynominterpolation (AuPr Lemma 4.1, Satz 4.2) Auswertung von Interpolationspolynomen mittels Aitken-Neville (AuPr Satz 4.19)
• 06.11.08: Kapitel 6: dividierte Differenzen, Fehlerabschaetzungen fuer Polynominterpolation
• 10.11.08: Kapitel 6: Tschebyscheffpolynome, Tschebyscheffpunkte (AuPr Kap. 4.3)
• 11.11.08: Kapitel 6: Bestapproximation mit Polynomen (Satz von Weierstrass, Satz von Jackson), Lebesguekonstante, (AuPr Satz 4.7), Bestapproximation vs. Interpolation (AuPr Kap 4.4), das Rungebeispiel fuer das Versagen von Interpolation in aequidistanten Punkten
• 13.11.08: Kapitel 7: Extrapolation: (AuPr Kap. 5.1)
• 17.11.08: Kapitel 7: Extrapolation mit POlynomen spezieller Bauart
• 19.11.08: Kapitel 8: lineare Splines (AuPr Kap. 4.8)
• 20.11.08: Kapitel 8: Splines hoeherer Ordnung (AuPr Satz 3.35) und trigonometrische Interpolation (AuPr Kap 4.9 bis p. 138 unten)
• 24.11.08: Kapitel 9: der FFT-Algorithmus
• 26.11.08: Kapitel 9: Anwendung der FFT: Faltung und schnelle Multiplikation von Polynomen, Kapitel 10: Quadratur (Newton-Cotes Formeln)
• 27.11.08: Kapitel 10: Quadratur Summierte Newton-Cotes Formeln, Fehlerabschaetzungen (AuPr Kap 6.1-6.3)
• 1.12.08: Kapitel 10: Quadratur: Euler-McLaurinsche Summenformel, Rombergextrapolation (AuPr Kap 6.1-6.3)
• 3.12.08: Kapitel 10: Gaussquadratur: Eigenschaften, Eindeutigkeit, Maximalitaet (AuPr Lemma 6.7, Satz 6.8), 3-Term-Rekursionen (AuPr Lemma 6.9)
• 4.12.08: Kapitel 10: Quadratur: Gaussknoten als Eigenwerte einer Tridiagonalmatrix (AuPr Satz 6.10), Konvergenz der klassischen Gaussquadratur
• 10.12.08: Kapitel 10: adaptive Quadratur, Banachscher Fixpunktsatz (AuPr Satz 7.1), einfache Kriterien fuer Konvergenz von Fixpunktiterationen (AuPr Satz 7.2)
• 11.12.08: Aitken'sches Delta^2-Verfahren (AuPr Kap 5.2), Newtonverfahren in 1D (AuPr Kap 7.3)
• 15.12.08: Kapitel 11: Newtonverfahren in multi-D (AuPr Kap 7.3)
• 17.12.08: Kapitel 11: Konvergenz des Newtonverfahren in multi-D (AuPr Kap 7.3)
• 18.12.08: Kapitel 11: Daempfungsstrategien beim Newtonverfahren (AuPr Alg. 7.7)
• 12.1.09: Kapitel 13: EWPs: Schurform, Bauer-Fike
• 14.1.09: Kapitel 13: Vektoriteration, inverse Iteration, inverse Iteration mit Shift
• 15.1.09: Kapitel 13: Konvergenztheorie der Rayleighquotienteniteration
• 19.1.09: Kapitel 13: Abbruchkriterien, orthogonale Iteration
• 21.1.09: Kapitel 13: Konvergenztheorie der orthogonalen Iteration
• 26.1.09: Kapitel 13: Herleitung der QR-Iteration
• 28.1.09: Kapitel 13: Effiziente Realisierung der QR-Iteration: Givensrotationen, Hessenbergform
• 29.1.09: Kapitel 13: QR-Iteration als inverse Iteration fuer A^H; Shiftstrategien

Projekte (Ferraz-Leite, Dörsek, Karkulik, Kamleitner, Temme, Zechner)

• project1.pdf Strassenalgorithmus
• project2.pdf rationale Interpolation
• project3.pdf Multiplikation grosser Zahlen mittels FFT ueber Primzahlkoerper
• project4.pdf Multiplikation grosser Zahlen mit Gleitkommaarithmetik
• project5.pdf Asymptotische Formeln fuer Summen mit vielen Termen
• project6.pdf Einfuehrung in fast multipole
• project7.pdf Nichtlineare partielle Differentialgleichungen
• project8.pdf Gaussquadratur
• project9.pdf Trapezregel fuer periodische Funktionen, adaptive Quadratur

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