Bergische Universität Wuppertal Fachbereich Mathematik und Naturwissenschaften Angewandte Mathematik - Numerische Analysis (AMNA)

People Research Publications Teaching

---

§ 1. Numerische Mathematik - Was ist das?

• Beispiel 1: Lineare Gleichungssysteme
• Beispiel 2: Bestimmte Integrale
• Einordnung der Numerische Mathematik
• Definition 1: VDI-Norm 3633, Simulation
• Rechnerentwicklung
• Beispiel 3: Integral-Rekursion

§ 2. Rechnerarithmetik und Fehleranalyse

2.1 Gleitpunkt- und Maschinenzahlen, Rundung

• Definition 1: Gleitpunktzahlen
• Beispiel 1: 4-stellige, normalisierte Decimalzahlen
• Beispiel 2: 7-stellige, normalisierte Dualzahlen
• Definition 2: Maschinenzahlen
• IEEE-Standard 754
• Beispiel 3: Short Real
• Rundung
• Definition 3: Rundung
• Absoluter Fehler, Relativer Fehler, Auflösung der Arithmetik
• Definition 4: Maschinengenauigkeit
• Gleitpunktoperationen
• Cleve's Corner A Tale of Two Numbers

2.2 Rundungsfehleranalyse

• Vorwärts- und Rückwärtsanalyse
• Beispiel 1: Addition
• Beispiel 2: Multiplikation
• Beispiel 3: Addition und anschliessende Multiplikation
• Algorithmus 1: Horner-Schema
• Beispiel 4: Rückwärtsanalyse für Horner-Schema

2.3 Fehlerfortpflanzung und Kondition

• Kondition eines Problems
• Absolute Störung, Relative Störung, Auflösung der Arithmetik
• Definition 5: Konditionszahl
• Beispiel 1: absolute/relative Konditionszahl für Grundrechenarten
• Beispiel 2: Auslöschung
• Beispiel 3: Wurzelberechnung
• Beispiel 4: Schnittpunkt zweier Geraden
• Beispiel 5: relative Kondition der Nullstellenbestimmung
• Kondition für zusammengesetzte Probleme
• Beispiel 6: Wurzelberechnung bei quadratischen Gleichungen
• Definition 6: Akzeptables Resultat
• Definition 7: Numerisch stabiler Algorithmus
• Diskussion der verschiedenen Fehlerquellen

§ 3. Lineare Gleichungssysteme

3.1 Motivation

3.2 Elementarmatrizen

• Skalierung
• Transposition
• Permutation
• Zeilen/Spalten-Operatoren

3.3 Gauß-Elimination und Pivotsuche

• Algorithmus 1: Vorwärtssubstitution
• Algorithmus 2: Rückwärtssubstitution
• Algorithmus 3: Gauß-Elimination (ohne Pivotsuche)

• Satz 1: LR-Zerlegung
• Algorithmus 4: LR-Zerlegung (ohne Pivotsuche)
• Pivotsuche
• Beispiel 1:
• Beispiel 2:
• partielle und totale Pivotisierung
• Satz 2: LR-Zerlegung (mit Pivotisierung)
• Komplexität

3.4 Normen für Vektoren und Matrizen

• Definition 4: (Vektor-)Norm
• Definition 5: Matrixnorm
• Definition 6: Operatornorm
• Definition 7: Spektralradius
• Definition 8: Kondition einer Matrix

3.5 Kondition und Rundungsfehler

• Lemma 1: Regularität der gestörten Matrix
• Beispiel 1: Hilbert-Matrizen
• Cleve's Corner: Hilbert Matrices
• Residuum
• Rundungsfehlereinfluss
• Nachiteration
• Algorithmus 5: Nachiteration
• Cleve's Corner: Iterative Refinement for Solutions to Linear Systems

3.6 Cholesky-Zerlegung

• Definition 1: positiv definit
• Beispiel 1: Gramsche Matrix
• Eliminationsschritt beim Gauß-Verfahren
• Satz 3: Cholesky-Zerlegung
• Algorithmus 5: Cholesky-Zerlegung
• Rechen- und Speicheraufwand der Cholesky-Zerlegung

§ 4. Lineare Ausgleichsrechnung

4.1 Problemstellung

• Beispiel 1: Radioaktiver Zerfall
• Lineares Ausgleichsproblem
• Methode der kleinsten Quadrate (linear least squares)
• Linearkombination von Ansatzfunktionen

4.2 Normalgleichungen

• Geometrischer Zugang
• Lotfußpunkt, senkrechte Projektion
• Minimierungszugang
• Satz 1: Charakterisierung, Eindeutigkeit des Minimierers
• Beispiel 1: numerisch singuläre Normalgleichungen
• Orthogonale Eliminationstechnik

4.3 Householder-Transformation und QR-Zerlegung

• Definition 1: Spiegelungsmatrix
• Geometrische Interpretation der Spiegelungsmatrix
• Eigenschaften der Spiegelungsmatrix
• Satz 2: Householder-Transformation
• Algorithmus 1: QR-Zerlegung mithilfe von Householder-Transformationen
• Implementierung
• Aufwand
• Beispiel 1: QR-Zerlegung mit Householder-Transformationen

4.4 Kondition des linearen Ausgleichsproblems

4.5 Das nichtlineare Ausgleichsproblem

• Gauß-Newton Verfahren

§ 5. Polynominterpolation

5.1 Interpolation und Approximation

• Interpolationsaufgabe
• Approximationssaufgabe

5.2 Grundlagen der Polynominterpolation

• Satz 1:

5.3 Interpolationsformel nach Lagrange

• Lagrangepolynome
• Satz 2:

5.4 Aitken-Neville-Schema und Dividierte Differenzen

• Aitken-Neville-Schema
• Lemma 3:
• Algorithmus 1: Aitken-Neville-Schema
• Beispiel 1:
• Dividierte Differenzen
• Satz 4:
• Satz 5: Rekursionsformel
• Algorithmus 1: Dividierte Differenzen
• Beispiel 2:

5.5 Erweiterter Mittelwertsatz und Restgliedformel

• Satz 6: Erweiterter Mittelwertsatz
• Satz 7: Restgliedformel

5.6 Kondition der Interpolationsaufgabe

• Beispiel 1:

§ 6. Spline-Interpolation

6.1 Motivation

• Polynom-Splines
• stückweise zusammengesetzte Interpolanten
1. Polygonzug
2. stückweise quadratische Polynome
3. stückweise kubische Polynome
• Definition 1: Splines vom Grad k
• rekursive Konstruktion der kubischen Splines

6.2 Hermite-Interpolation

• Monotone kubische Interpolation

6.3 Kubische Spline-Interpolation

• Randbedingungen
1. natürliche Randbedingungen
2. vollständige Randbedingungen
3. periodische Randbedingungen
• Berechnung der Spline-Interpolanten
• Eigenschaften der Spline-Interpolanten
• Gesamtkrümmung von interpolierende Funktionen
• Lemma 1: Integralrelation
• Satz 1: Optimalität des kubischen Splines
• Satz 2: Fehlerformel
• Korrolar: äquidistante Stützstellen

6.4 B-Splines

• abgeschnittene Potenzfunktionen
• Definition 2: B-Splines

§ 7. Numerische Quadratur

7.1 Quadraturformeln

• Anforderungen an Quadraturformeln
• Forderung minimaler Fehlerverstärkung
• Übersicht zu Quadraturformeln
1. Newton-Cotes-Formeln und Summenformeln
2. adaptive Simpson- und Extrapolationsverfahren
3. Gauß-Quadratur

7.2 Newton-Cotes-Formeln

• Idee einer interpolatorischen Quadraturformel
• abgeschlossene und offene Newton-Cotes-Formeln (NCF)
• Trapezregel
• Restgliedformel
• Verallgemeinerter Mittelwertsatz der Integralrechnung
• Fehler der Trapezregel
• Kepler'sche Fassregel (Simpson-Regel)
• Restgliedformel
• Fehler der Fassregel
• Exaktheitsgrad der Fassregel
• Nachteile der Newton-Cotes-Formeln

7.3 Summierte Newton-Cotes-Formeln

• Rechtecksumme
• Trapezsumme
• Summenmittelwertsatz
• (zusammengesetzte) Simpson-Regel
• Vergleich des Aufwands
• Adaptives Simpson-Verfahren
• Fehlerschätzer
• Algorithmus 1: Adaptives Simpson-Verfahren
• absolute und relative Toleranzen

7.4 Extrapolationsverfahren

• Idee der Extrapolation
• Asymptotische Entwicklung der Näherung
• Asymptotische Entwicklung der Trapezsumme
• Euler-MacLaurinsche Summenformel
• Elimination von führenden Fehlertermen
• Richardson-Extrapolation
• Romberg-Quadratur
• geometrische und Bulirsch-Schrittweitenfolge
• Algorithmus 2: Romberg-Quadratur
• Extrapolationstableau
• Satz 1: Fehler in der Romberg-Quadratur
• Adaptive Romberg-Quadratur

7.5 Gauß-Quadratur

• Maximale Genauigkeit von interpolatorischen Quadraturformel
• Beispiel 1: 2-Punkt Gauß-Legendre-Regel
• Herleitung der n-Punkt Gauß-Legendre-Regel
• System von orthogonalen Polynomen
• Legendre-Polynom vom Grad n
• Satz 2: Nullstellen des Orthogonalpolynoms
• Satz 3: Gauß-Legendre-Quadratur
• Satz 4: Gewichte in Gauß-Legendre-Quadratur
• Tabelle 1: Gewichte der n-Punkt Gauß-Legendre-Regel
• Knoten und Gewichte bei affin-linearer Transformation des Intervalls
• Gauß-Quadratur mit Gewichtsfunktionen
• Beispiel 2: Erwartungswert einer normalverteilten Zufallsvariablen
• Tabelle 1: Orthogonalpolynome im Fall von Standardverteilungen
• Vor- und Nachteile der Gauß-Quadratur

§ 8. Iterative Lösung großer linearer Gleichungssysteme

8.1 Stationäre Iterationsverfahren

• Spektralradius
• Satz 1: Konvergenz stationärer Verfahren
• Satz 2: Konvergenzgeschwindigkeit

8.2 Klassische Iterationsverfahren

• Jacobi-Verfahren / Gesamtschrittverfahren
• starkes Zeilen-/Spaltensummenkriterium
• Gauß-Seidel-Verfahren / Einzelschrittverfahren
• Relaxationsverfahren
• SOR-Verfahren (successive overrelaxation)
• Iterative Nachbesserung

8.3 Anwendungsbeispiel

• Dirichlet Randwertproblem für die Poisson-Gleichung
• Ausblick: CG-, GMRES- und Mehrgitterverfahren

§ 9. Nichtlineare Gleichungssysteme

9.1 Der eindimensionale Fall

• Bisektion
• Algorithmus 1: Bisektion
• Newton-Verfahren
• Algorithmus 2: Newton-Raphson-Verfahren
• Konvergenzuntersuchung
• Definition 1: lokal konvergente Iteration
• Definition 2: global konvergente Iteration
• Konvergenzordnung
• vereinfachtes Newton-Verfahren

9.2 Der mehrdimensionale Fall

• Newton-Verfahren
• Algorithmus 3: mehrdimensionales Newton-Verfahren
• vereinfachtes Newton-Verfahren
• Algorithmus 4: vereinfachtes Newton-Verfahren

9.3 Konvergenz des gewöhnlichen Newton-Verfahrens

• Satz 1: Konvergenz des gewöhnlichen Newton-Verfahrens
• Satz 2: Satz von Newton-Kantorowich
• Beispiel 1:
• Modifiziertes Newton-Verfahren
• Einbettungsverfahren (Fortsetzungsverfahren)

§ 10. Numerische Differentiation

10.1 Numerische Differentiation

• Problemstellung
• Satz 1: Satz von Taylor
• Definition 1: Diskretisierungsfehler, Fehlerordnung
• Beispiel 1:
• Beispiel 2:
• Beispiel 3:
• Differenzenformeln für höhere Ableitungen

10.2 Extrapolation

• Beispiel 4:
• Satz 2: Fehlerentwicklung der extrapolierten Formel
• Satz 3: Fehlerentwicklung der allgemeinen extrapolierten Formel
• Algorithmus 1: h-Extrapolation
• Beispiel 5:
• Algorithmus 2: h²-Extrapolation
• Beispiel 6:
• Satz 4: Aitken-Neville Schema für h-Extrapolation
• Satz 5: Aitken-Neville Schema für h²-Extrapolation

§ 11. Anfangswertprobleme gewöhnlicher Differentialgleichungen

11.1 Problemstellung

• Anwendungen von Differentialgleichungen
• Definition 1: gewöhnliche Differentialgleichung, Anfangswertproblem
• Beispiel 1:
• Geometrische Interpretation: Richtungsfeld
• Beispiel 2:
• Diskretisierung

11.2 Das Euler-Verfahren

• Herleitung des Eulerschen Polygonzugverfahren
• Algorithmus 1: Euler-Verfahren
• Beispiel 3:
• Betrachtung der Fehlerquellen
• Definition 2: lokaler Fehler, Konsistenzordnung
• Definition 3: globaler Fehler, Konvergenzordnung
• Satz 1: Konsistenz und Konvergenz des Euler-Verfahrens
• Lipschitzbedingung

11.3 Praktische Aspekte

• Diskussion des Fehlerschätzers aus Satz 11.1
• Schrittweitensteuerung
• Schätzung des lokalen Fehlers
• eingebettete Formeln

11.4 Weitere Einschrittverfahren

• Definition 4: Einschrittverfahren
• Mittelpunktsregel (modifiziertes Euler-Verfahren)
• Mittelpunktsregel aus h-Extrapolation
• Verfahren von Heun
• klassisches vierstufiges Runge-Kutta-Verfahren
• Beispiel 4:
• Definition 5: allgemeines s-stufiges Runge-Kutta-Verfahren
• Butcher-Schema
• eingebettete Runge-Kutta-Verfahren

11.5 Weitere Verfahren

• Extrapolationsverfahren
• Implizite Verfahren
• Mehrschrittverfahren

Vorstellung weiterführender Vorlesungen im WS 15/16