§ 0. Numerische Mathematik in der Informatik

• Computergraphik
• Computer Vision
• Neuronale Netze
• Chip Design
• Information Retrieval
• Prozessverwaltung / Warteschlangen

§ 1. Rechnerarithmetik und Gleitpunktzahlen

1.1 Grundlagen

• Definition 1: n-stellige Gleitpunktzahl zur Basis B, Mantisse
• Beispiel 1: IEC/IEEE-Gleitpunktzahlen: single, double, long double format
• Definition 2: Maschinenzahlen
• Größte und kleinste Maschinenzahl
• Unterlauf (underflow) und Überlauf (overflow)
• Definition 3: Rundung
• Definition 4: absoluter Fehler
• Beispiel 2:
• Definition 5: Rundungsfehler
  • Disasters due to rounding error
• n-stellige Gleitpunktarithmetik, Flops
  • List of fastest computers in the world
• Beispiel 3: Einfluß der Summationsreihenfolge
• Definition 6: relativer Fehler
• Maschinengenauigkeit eps
• Vergleichsoperation bei Gleitpunktzahlen
• Auslöschung bei der Subtraktion
• Beispiel 4: Vermeidung durch algebraische Umformung
• Beispiel 5: Vermeidung durch Fallunterscheidung
• weitere Fehlerquellen
• Modellierungsfehler
• Diskretisierungsfehler
• Abbruchfehler
• Darstellungsfehler

1.2 Fehlerrechnung, Kondition und Stabilität

• Fehlerfortpflanzung in arithmetischen Operationen
• Addition / Subtraktion
• Multiplikation / Division
• Fehlerfortpflanzung bei Funktionsauswertungen
• Satz 1: Mittelwertsatz
• Abschätzung des absoluten Fehlers bei Funktionsauswertung
• Beispiel 1:
• Beispiel 2:
• Beispiel 3:
• Beispiel 4:
• Abschätzung des relativen Fehlers bei Funktionsauswertung
• Konditionszahl / Fehlerverstärkungsfaktor
• Beispiel 5:
• Beispiel 6:
• Beispiel 7:
• Beispiel 8: Hilbert-Matrix

§ 2. Numerische Lösung von Nullstellenproblemen

2.1 Problemstellung

• Satz 1: Zwischenwertsatz

2.2 Einschließungsverfahren

• Bisektionsverfahren
• Beispiel 1:
• Beispiel 2: Polynom von Wilkinson
• Satz 1: Bisektionsverfahren
• Beispiel 3:
• Regula-Falsi-Verfahren
• Illinois-Verfahren
• Pegasus-Verfahren
• verbessertes Pegasus-Verfahren
• Brent Decker-Verfahren

2.3 Die Fixpunktiteration

• Definition 1: Fixpunktgleichung, Fixpunkte
• Beispiel 1:
• Definition 2: Fixpunktiteration / sukzessive Approximation
• Beispiel 2:
• Satz 1: anziehender/abstoßender Fixpunkt
• Beispiel 3:
• Satz 2: Banachscher Fixpunktsatz
• Beispiel 4:
• Steffensen-Verfahren

2.4 Das Newton-Verfahren

• Newton-Verfahren
• Beispiel 1:
• Heron-Verfahren
• Beispiel 2:
• vereinfachtes / modifiziertes Newton-Verfahren
• Sekantenverfahren

2.5 Konvergenzgeschwindigkeit

• Definition 1: Konvergenzordnung
• Konvergenzordnungen der vorgestellten Verfahren

§ 3. Numerische Lösung linearer Gleichungssysteme

3.1 Problemstellung

• direkte und iterative Verfahren

3.2 Gaußsches Eliminationsverfahren und LR-Zerlegung

• Beispiel 1:
• Lösung eines rechten-oberen Dreieckssystems (Rückwärtseinsetzen)
• Gaußsches Eliminationsverfahren
• Beispiel 2:
• Beispiel 3: neue rechte Seite
• Beispiel 4: Berechnung der Determinante
• Fehlerfortpflanzung beim Gauß-Algorithmus und Pivotisierung
  • Spaltenpivotisierung
  • Beispiel 5:
• LR-Zerlegung
  • Beispiel 6:
  • Beispiel 7:
  • Satz 1: LR-Zerlegung
  • Algorithmus

3.3 Cholesky-Zerlegung

• Definition 1: positiv definit
• Satz 1: Cholesky-Zerlegung
• Algorithmus
• Beispiel 1:

3.4 Fehlerrechnung bei linearen Gleichungssystemen

• Definition 1: Norm
• Definition 2: Vektornormen
• Äquivalenz von Normen
• Definition 3: induzierte Matrixnormen
• Beispiel 1:
• Satz 1: Fehlerabschätzungen, Konditionszahl einer Matrix
• Beispiel 2:
• Satz 2: Fehlerabschätzung bei gestörter rechter Seite und Matrix
• Beispiel 3:
• Algorithmus
• Beispiel 1:

3.5 Householder-Transformation und QR-Zerlegung

• Satz 1: Eigenschaften der Matrix H
• Definition 1: Householder-Transformation
• Satz 2: Eigenschaften des Vektors w
• Vermeidung der Stellenauslöschung
• Triangulierung mittels Householder-Transformationen
• Implementierung
• Anwendung 1: Stabile Lösung schlecht konditionierter Gleichungssysteme
• Anwendung 2: Data Mining und Information Retrieval
  • Anfragevektor, Dokumentenvektor
  • latent semantic indexing
  • Google und Pagerank, Adjazenzmatrix
  • Webseitentypen: Authorities und Hubs
  • Hub-Authority-Matrix

3.6 Iterative Verfahren

• Beispiel 1:
• Definition 1: Gesamtschrittverfahren, Jacobi-Verfahren
• Beispiel 2:
• Definition 2: Einzelschrittverfahren, Gauß-Seidel-Verfahren
• Beispiel 3:
• Definition 3: anziehender/abstoßender Fixpunkt
• Satz 1: a-posteriori und a-priori Fehlerabschätzungen
• Beispiel 4:
• Zeilen-und Spaltensummenkriterium
• Definition 4: diagonaldominant
• Satz 2: Konvergenz des Einzel- und Gesamtschrittverfahrens
• Beispiel 5:

§ 4. Numerische Lösung nichtlinearer Gleichungssysteme

4.1 Problemstellung

• Definition 1: nichtlineares Gleichungssystem
• Beispiel 1:

4.2 Das Newton-Verfahren für Systeme

• Algorithmus: Newton-Verfahren
• Definition 1: Jacobi-Matrix
• Beispiel 1:
• Satz 1: Konvergenz des Newton-Verfahrens
• Bemerkungen zur praktischen Implementierung
• gedämpftes Newton-Verfahren
• Beispiel 2:
• vereinfachtes Newton-Verfahren
• Beispiel 3:
• Satz 2: Konvergenz des vereinfachten Newton-Verfahrens

§ 5. Interpolation und Approximation

5.1 Problemstellung

• Definition 1: Stützstelle, Stützwerte, Stützpunkte
• Definition 2: Interpolierende
• Beispiel 1:

5.2 Polynom-Interpolation

• Satz 1: Existenz und Eindeutigkeit des Interpolationspolynoms
• Beispiel 1:
• Lagrange-Form des Interpolationspolynoms
• Definition 1: Dividierte Differenzen
• Beispiel 2:
• Satz 2: Newtonsche Interpolationsformel
• Beispiel 3:
• Horner-Schema
• Neville-Aitken-Schema
• Beispiel 4:
• Satz 3: Fehler bei der Polynom-Interpolation
• Satz 4: Fehler bei äquidistanten Stützstellen und stückweiser linearer/kubischer Interpolation
• Beispiel 5:
• Beispiel 6:
• Beispiel 7:
• Hermite-Interpolation
• Anwendung: Interpolationsverfahren in der Bildverarbeitung
  • Digitaler Zoom, Alias-Effekt, Antialiasing, digitale Filter

5.3 Spline-Interpolation

• Beispiel 1:
• Interpolation mit kubischen Splines
• Definition 1: kubischer, interpolierender, periodischer, natürlicher Spline
• Hermite-Randbedingungen
• Splines mit not-a-knot-Bedingungen
• Satz 1: Berechnung der Momente
• Satz 2: Berechnung des Splines aus den Momenten
• Beispiel 2:
• Beispiel 3:
• Beispiel 4:
• Anwendung 1:

5.4 Bézier-Kurven

• Bernstein-Polynome
• Beispiel 1:
• Bézier-Darstellung eines Polynoms
• de Casteljau-Algorithmus
• Bézier-Kurven
• Beispiel 2:
• Anwendung 1: Computer Aided Design, Computational Geometry
• Anwendung 2: skalierbare Schriftfonts (z.B. Postscript Typ1 und CFF-Opentype)

§ 6. Ausgleichsrechnung

6.1 Problemstellung

• Definition 1: Ausgleichsproblem
• Definition 2: Ausgleichsfunktion, Fehlerfunktional, Ansatzfunktionen
• kleinste Fehlerquadrate
• Ausgleichsgerade

6.2 Lineare Ausgleichsprobleme

• Beispiel 1:
• Definition 1: lineares Ausgleichsproblem, Fehlergleichungssystem
• Definition 2: Normalgleichungen, Normalgleichungssystem
• Residuumsvektor
• Beispiel 2:
• logarithmisch linearer Ansatz
• Beispiel 3:
• Kondition der Normalengleichungen
• Ausgleichsrechnung mittels QR-Zerlegung
• Beispiel 4:
• Anwendung 1: Computertomographie (einfaches Modell)
• Anwendung 2: Neuronale Netze
• Anwendung 3: Registrierung und Kalibrierung von Bilddaten

6.3 Nichtlineare Ausgleichsprobleme

• Definition 1: allgemeines Ausgleichsproblem
• Beispiel 1:
• Gauß-Newton-Verfahren
  • Definition 2: Quadratmittelproblem
  • Definition 3: Gauß-Newton-Verfahren
  • gedämpftes Gauß-Newton-Verfahren
  • Beispiel 2:

§ 7. Diskrete Fourier-Analyse und schnelle Fourier-Transformation (FFT)

7.1 Problemstellung

• trigonometrische Polynome
• Approximation im quadratischen Mittel

7.2 Fourier-Polynome

• Satz 1: interpolierendes Fourier-Polynom
• Satz 2: beste Approximation durch ein Fourier-Polynom

7.3 Die schnelle Fourier-Transformation (FFT)

• schnelle Fourier-Transformation (FFT)
• Definition 1: diskrete komplexe Fourier-Transformation
• n-te Einheitswurzeln
• Beispiel 1:
• Aufwand der FFT
• Satz 1: Beziehung zwischen komplexen und reellen Fourier-Koeffizienten
• Beispiel 2:
• Anwendung 1: (verlustbehaftete) Bildkompression JPEG
• FCT: Schnelle Cosinus-Transformation
• Anwendung 2: (verlustbehafteten) Audiodatenkompression MP3
• Anwendung 3: Filter in Bild- und Musikbearbeitung

§ 8. Numerische Differentiation

8.1 Problemstellung

• Differenzenformel, finite Differenz
• Satz 1: Satz von Taylor
• Definition 1: Diskretisierungsfehler, Abschneidefehler und Fehlerordnung
• Beispiel 1:
• Beispiel 2:
• Beispiel 3:
• symmetrische, zentral Differenzenform

8.2 Differenzenformen für höhere Ableitungen

• Konstruktion von Differenzenformen für höhere Ableitungen

8.3 Extrapolation

• Beispiel 1:
• Satz 1: Fehlerentwicklung der extrapolierten Formel bei Ordnung 2
• Satz 2: Fehlerentwicklung der extrapolierten Formel bei Ordnung k+1
• Algorithmus: h-Extrapolation
• Beispiel 2:
• Algorithmus: h²-Extrapolation
• Beispiel 3:
• Satz 3: Neville-Aitken-Schema bei der Extrapolation
• Satz 4: Fehlerentwicklung Neville-Aitken-Schema

§ 9. Numerische Integration (Quadratur)

9.1 Problemstellung

9.2 Newton-Cotes Formeln

• Fehlerabschätzungen

9.3 Summierte Newton-Cotes Formeln

• Anwendung 1: Gauß'scher Weichzeichner
• Anwendung 2: Fuzzy-Steuerung

9.4 Gauß-Quadraturen

9.5 Romberg-Extrapolation

§ 10. Anfangswertprobleme gewöhnlicher Differentialgleichungen

10.1 Problemstellung

• Definition 1: Anfangswert, gewöhnliche Differentialgleichung, Anfangswertproblem
• Richtungsfeld
• Beispiel 1:
• Diskretisierung, Gitterpunkte

10.2 Das Euler-Verfahren

• Algorithmus: Das Euler-Verfahren
• Beispiel 1:
• Definition 1: lokaler Fehler, Konsistenzordnung
• Definition 2: globaler Fehler, Konvergenzordnung
• Satz 1: Konsistenz und Konvergenz des Euler-Verfahrens
• Lipschitzbedingung
• praktische Aspekte

10.3 Weitere Einschrittverfahren

• Definition 1: Einschrittverfahren

§ 11. Exkurs: Wavelets

11.1 Problemstellung

• Anwendung 1: Bildkompression JPEG2000 (z.B. in neuen Reisepässen)

ehrhardt@math.tu-berlin.de