BannerHauptseite TUMHauptseite LehrstuhlMathematik SchriftzugHauptseite LehrstuhlHauptseite Fakultät

Numerik Propädeutikum SoSe 2008 (Modul MA1302): Gliederung, Planung und Folien

1. Woche (14.04.08) (Folien)

1 Gauß'sche Dreieckszerlegung

(1.1) Problemstellung: Lösung linearer Gleichungssysteme

(1.2) Dreieckssysteme = einfache Gleichungssysteme

(1.3) Matrixpartitionierung

(1.4) Rekursive Beschreibung der Vorwärtssubstitution

(1.5) Ein rekursives Matlab-Programm

(1.6) Ersetzen der Rekursion durch eine for-Schleife

(1.7) Anzahl der arithmetischen Operationen

(1.8) Bemerkung: obere Dreiecksmatrizen

2. Woche (21.04.08) (Folien)

(1.9) Gauß'sche Elimination als Matrixfaktorisierung

(1.10) Rekursiver Algorithmus zur LR-Zerlegung

(1.11) in situ Speicherschema

(1.12) Ein rekursives Matlab-Programm

(1.13) Ersetzen der Rekursion durch eine for-Schleife

(1.14) Anzahl der arithmetischen Operationen der LR-Zerlegung

(1.15) Zusammenfassung: Lösung linearer Gleichungssysteme

(1.16) Vorteile des Faktorisierungszugangs: Wiederverwertbarkeit der LR-Zerlegung

3. Woche (28.04.08) (Folien)

(1.17) Probleme mit Pivot = Null oder fast Null

(1.18) Spaltenpivotisierung

(1.19) Permutationsmatrizen

(1.20) Satz: A nichtsingulär => P A = L R

4. Woche (05.05.08) (Folien)

(1.21) Satz von der Cholesky-Zerlegung (1924)

(1.22) Ein nicht-rekursives Matlab-Programm

(1.23) Aufwand der Cholesky-Zerlegung

2 Lineare Ausgleichsprobleme

(2.1) Parameteridentifikation

(2.2) Lineare Modelle

(2.3) Geometrie des Ausgleichsproblems: Lösbarkeit

(2.4) Eindeutigkeit der Lösung: voller Spaltenrang

(2.5) Normalengleichung

(2.6) Lösung der Normalengleichung mit Cholesky

5. Woche (12.05.08)

  • Pfingsten

6. Woche (19.05.08) (Folien)

(2.7) Problem mit Normalengleichungen: Beispiel von Läuchli (1961)

(2.8) Direkte Charakterisierung des Cholesky-Faktors von ATA: QR-Zerlegung von A

(2.9) Lösung des Ausgleichproblems mit QR-Zerlegung

(2.10) Rekursive Berechung der reduzierten QR-Zerlegung (modifiziertes Gram-Schmidt-Verfahren)

(2.11) Ein rekursives Matlab-Programm

(2.12) Aufwand für modifiziertes Gram-Schmidt-Verfahren

7. Woche (26.05.08) (Folien)

3 Vektorisierung, BLAS, LAPACK

(3.1) Assembler, Compiler, Interpreter

(3.2) Vergleich dreier Implementierungen der LR-Zerlegung

(3.3) Zeilen- vs. spaltenorientierte Elementzugriffe

(3.4) Level-1-BLAS

(3.5) Pipelining und Vektoroperationen

(3.6) Level-2-BLAS

(3.7) Hierarchischer Speicher und Rechenzeitmodell

(3.8) Level-3-BLAS

(3.9) Optimiertes BLAS vom Hersteller

(3.10) Algorithmenentwicklung am Beispiel der LR-Zerlegung

(3.11) LAPACK

(3.12) Zusammenfassung

8. Woche (02.06.08)

4 Einführung in die Fehlertheorie

(4.1) Fehlerquellen: Messfehler, Modellfehler, Rundungsfehler

(4.2) Fehlemaße: absolut, relativ

(4.3) Gleitkomma-Arithmetik

(4.4) Modell der Hardwarearithmetik: Auflösung und Maschinengenauigkeit

(4.5) Kondition eines Problems

(4.6) Beispiele: Nullstellen, Subtraktion (Auslöschung führender Ziffern)

(4.7) Stabilität eines Algorithmus (Vorwärtsanalyse)

(4.8) Beispiel: Stabilisierung der Lösungsformel für quadratische Gleichungen

9. Woche (09.06.08)

(4.9) Matrixnorm

(4.10) Kondition einer Matrix

(4.11) Numerisch singuläre Matrizen

(4.12) Konzept der Rückwärtsanalyse

(4.13) Rückwärtsfehler eines lineraren Gleichungssystems

(4.14) A priori Analyse der Algorithmen zur Lösung linearer Gleichungssysteme

(4.15) Stabilität und Pivoting

10. Woche (16.06.08)

5 Polynominterpolation

(5.1) Idee: Approximation durch Interpolation

(5.2) Polynome

(5.3) Existenz und Eindeutigkeit des Interpolationspolynoms

(5.4) Langrange-Formel

(5.5) Baryzentrische Formeln

(5.6) Rekursive Berechnung der Gewichte

(5.7) Äquidistante Stützstellen

(5.8) Tschebyscheff'sche Stützstellen (2. Art)

11. Woche (23.06.08)

(5.9) Absolute Kondition (Lebesgue-Konstante)

(5.10) Abschätzungen der Lebesgue-Konstante

(5.11) Beziehung zur polynomialen Bestapproximation

(5.12) Splines vom Grad k

(5.13) Lineare Splineinterpolation (Linienzuginterpolation)

(5.14) Idee der kubischen Splineinterpolation: Nachahmung der Latteninterpolation

(5.15) Extremaleigenschaft kubischer Splines

12. Woche (30.06.08)

(5.16) Typen kubischer Splineinterpolation

(5.17) Bemerkungen zur Splineinterpolation

6 Nichtlineare Gleichungssysteme

(6.1) Problemstellung und Beispiele

(6.2) Fragen: Existenz, Eindeutigkeit, Sensitivität, effiziente Algorithmen?

(6.3) Lokale Eindeutigkeit und Kondition

(6.4) Notwendigkeit eines Iterationsverfahrens

13. Woche (07.07.08)

(6.5) Newton-Verfahren

(6.6) Lokaler Konveregenzsatz (lokal quadratische Konvergenz)

(6.7) Konvergenzkriterium

(6.8) Berechnung der Jacobi-Matrix: symbolische vs. automatische Differentiation

(6.9) Numerische Differentiation: Verlust der halben Mantissenlänge

14. Woche (14.07.08)

7 Schnelle Fouriertransformation (FFT)

(7.1) Bandbegrenzte Signale und Abtastung

(7.2) Diskrete Fouriertransformation (DFT)

(7.3) Idee der FFT: Reduktion von m auf m/2

(7.4) Cooley-Tukey Radix2-FFT (1965)