Friedrich-Schiller-Universität Jena
Institut für Mathematik und Informatik

Einführung in die numerische Mathematik und das wissenschaftliche Rechnen (WS 19/20)

Dozent: Dietmar Gallistl
Vorlesungsdaten:VL, Übung

Übungsblätter

Die Übungsblätter werden donnerstags ausgegeben und in der Übungsstunde der darauffolgenden Woche besprochen.

Programmierübungen

Klausur

Termin für die Wiederholungsprüfung: 28. April 2020: 9-11 Uhr, HS 4 Abbeanum,

Klausurtermin: 26. Februar 2020: 9-11 Uhr, HS 1 Abbeanum. Einlass bis 9:10.

Zulassung zur Klausur: Zur Klausur wird zugelassen, wer in der Übung zweimal vorgerechnet und insgesamt mindestens die Hälfte der Übungsaufgaben vollständig bearbeitet hat. Abweichende Vereinbarungen nach Absprache.

Hilfsmittel: Ein handbeschriebenes A4-Blatt mit beliebigen Notizen darf mitgebracht werden.

Klausureinsicht: Am Tag nach der Klausur (also am 27. Feb), 9-10 Uhr, Ernst-Abbe-Platz 2, Zimmer 3533.

Behandelte Themen

16. Okt:(1) Fehleranalyse und Grundlagen. §1.1 Gleitkommazahlen. Fest-/Gleitpunktdarstellung, Maschinenzahlen, Rundung, Maschinengenauigkeit, Maschinenoperationen, §1.2 Konditionierung numerischer Aufgaben. Konditionierung, relativer und absoluter Fehler Konditionszahlen, Auslöschung
17. Okt: §1.3 Stabilität numerischer Algorithmen. Algorithmen, Stabilität von Algorithmen, Vorwärtsrundungsfehleranalyse, Horner-Schema. §1.4 Normierte Räume und Innenprodukträume. (Vektor)normen, Konvergenz
23. Okt: Matrizennormen, Operatornorm, Skalarprodukte, von der euklidischen Norm erzeugte Operatornorm, Spektralnorm, §1.5 Orthogonalpolynome und Drei-Term-Rekursion. das Gram-Schmidt-Verfahren und seine numerische Instabilität, Existenz der QR-Zerlegung
24. Okt: L2-Skalarprodukt, Orthogonalpolynome, Legendre- und Čebyšëv-Polynome (Tschebyscheff-Polynome), Nullstellen von Orthogonalpolynomen, abstrakte Drei-Term-Rekursion und Anwendung auf Orthogonalpolynome
30. Okt: (2) Rekonstruktion und Approximation von Funktionen. §2.1 Kondition der Lagrange-Interpolationsaufgabe. Lagrange-Interpolationsaufgabe, eindeutige Lösbarkeit, Lagrange-Basis, Kondition, §2.2 Darstellung in der Newton-Basis. Satz über dividierte Differenzen
6. NovNewton-Basispolynome, Newton-Darstellung, Neville-Schema, Richardson-Extrapolation, §2.3 Approximationsfehler. Fehlerdarstellung der Lagrange-Interpolation
7. Novminmax-Eigenschaften der Čebyšëv-Polynome, Wahl der Stützstellen bei der Lagrange-Interpolation, §2.4 Spline-Interpolation. Spline-Funktionen, interpolierender natürlicher kubischer Spline
13. NovExistenz und Eindeutigkeit des interpolierenden natürlichen kubischen Splines, Minimierungseigenschaft, Berechnung von Splines, §2.5 Trigonometrische Interpolation. Existenz und Eindeutigkeit der (komplexwertigen) trigonometrischen Interpolierenden
14. NovDiskrete Fourier-Transformation (DFT), Rekursionsbeziehungen in der DFT, Schnelle-Fourier-Transformation (FFT), Bit-Umkehr, Komplexität der FFT, Darstellung reellwertiger trigonometrischer Polynome durch Sinus und Cosinus, (3) Numerische Integration. §3.1 Newton-Cotes-Formeln. Herleitung von Quadraturformeln, Exaktheitsgrad bzw. Ordnung einer Quadraturformel, Newton-Cotes-Formeln
20. NovBeispiele für Newton-Cotes-Formeln, Restglieddarstellungen für Trapez-, Simpson- und Mittelpunktregel, summierte Newton-Cotes-Formeln und ihre Restglieddarstellung, §3.2 Gauß-Quadratur. Satz über die maximale Ordnung interpolatorischer Quadraturformeln, Idee der Gauß-Quadratur
21. Nov Konstruktion, Existenz, Eindeutigkeit, Konvergenz der Gauß-Quadratur, (4) Lineare Gleichungssysteme. §4.1 Störungstheorie. Neumannsche Reihe
27. Nov Störungssatz, Konditionszahl, Spektralkondition, §4.2 Gauß-Elimination und LR-Zerlegung. Permutations- und Frobeniusmatrizen, Gauß-Algorithmus, Pivotsuche, Systeme in Dreiecksgestalt
28. Nov LR-Zerlegung (Existenz und Algorithmus), §4.3 Nichtreguläre Systeme und Orthogonalisierung. Residuum, Kleinste-Quadrate-Lösung, Gaußsche Normalgleichung, Äquivalenz- und Existenzsatz, Pseudoinverse und ihre Kondition
04. Dez QR-Zerlegung durch Householder-Transformationen, Householder-Algorithmus
05. Dez §4.4 Klassische Iterationsverfahren. Fixpunktiteration, Spektralradius, Charakterisierungssatz für Konvergenz, Konvergenzgeschwindigkeit, Jacobi- und Gauß-Seidel-Verfahren, starke/schwache Zeilensummenbedingung, zerfallende vs. irreduzible Matrizen
11. Dez Konvergenzkriterien für Jacobi und Gauß-Seidel, Speicherung dünn besetzter Matrizen, SOR-Verfahren, §4.5 Das cg-Verfahren. Minimierung quadratischer Funktionale, Energienorm, Abstiegsverfahren
12. Dez Gradientenverfahren, Krylow-Räume, Galerkin-Verfahren, Lemma über konjugierte Richtungen,
18. Dez cg-Verfahren und seine Eigenschaften
19. Dez Konvergenzssatz für das cg-Verfahren, Vorkonditionierung
08. Jan (5) Nichtlineare Gleichungen. §5.1 Fixpunktiteration. Banachscher Fixpunktsatz, Schrankensatz, Kriterien für die Anwendbarkeit der Fixpunktiteration, §5.2 Das Newton-Verfahren.
09. Jan Newton Verfahren, Satz von Newton-Kantorovich, Beweis des Satzes (Teil 1/2)
15. Jan Beweis des Satzes (Teil 2/2)
16. Jan Modifikationen des Newton-Verfahrens, §5.3 Sekantenverfahren. Sekantenverfahren mit Konvergenzsatz; Illustration mit Julia-Mengen, Programm: julia.m, Beispiel 1: f(z)=z^3-1 jpg-Datei (616KB), Beispiel 2: f(z)=x^5-x^3-1 jpg-Datei (724KB) (jeweils ohne Dämpfung)
22. Jan (6) Numerik von Eigenwertaufgaben. §6.1 Grundlagen. Satz über die Gerschgorin-Kreise, Konditionierung des Eigenwertproblems, Potenzmethode
23. Jan Konvergenzsatz zur Potenzmethode, Inverse Iteration nach Wielandt, Shift-Technik, §6.2 Das QR-Verfahren. Idee des QR-Verfahrens, Hessenberg-/Tridiagonalmatrizen, Reduktion auf Hessenberg-Gestalt
29. Jan QR-Algorithmus, Komplexitätsbetrachtungen, Konvergenz des QR-Verfahrens
30. Jan §6.3 Krylowraum-Verfahren. Rayleigh-Quotient, Verfahren von Lanczos, Konvergenzsatz
05. Feb §6.4 Stochastische Eigenwertprobleme. Spektraleigenschaften positiver und nichtnegativer Matrizen, Satz von Perron
06. Feb Satz von Perron-Frobenius, Anwendungsbeispiel: page rank bei Suchmaschinen

Literatur

Die meisten Werke zum Thema sollten geeignet sein, z.B.
  • J. Stoer, R. Bulirsch: Numerische Mathematik, Teil I und II, Springer
  • P. Deuflhard, A. Hohmann: Numerische Mathematik, Teil I, W. de Gruyter
  • D. Braess: Finite Elemente. Springer. (Kapitel IV zu iterativen Lösern für LGS)
  • R. Rannacher, Skript Numerik 0, Online