Inhalt der vorherigen Vorlesungen (SS05)

(Prof. Laszlo Erdos)

12. April

Vorstellung. Organisatorische Details (siehe Webseite). Lehrplan. Aufteilung der Übungsgruppen. Übungen und Matlab Tutorium beginnen ab 18.04. Anmeldung ist auf der Webseite (JETZT).

Wichtigkeit der Mathematik und Numerik. Effektive Fehlerabschaetzungen. Taylor Entwicklung mit Restglied.

Ein Stab unter den Lupe -- Durch Diskretisierung zu linearen Gleichungssystemen.

Der Stoff ist Kapitel 1. und 2. des Skriptes

Lesen Sie auch die Katastrophen am Ende der Homepage

14. April


Übungsblatt (zur Abgabe am 21.04) und das Blatt mit der Präzensaufgaben für die Übungen der nächste Woche wurden publiziert!

Ein Beispiel für eine schlecht konditionerte Matrix.

Gleitpunktzahlen, Maschinenarithmetik. Groß O und klein o Notation. Arithmetische Regeln, Beispiele und Warnungen. Absolute und relative Fehler, Fehlerabschätzung.

Relative Kondition der Division. Präzise Definition der relativen Kondition und ihre Relation zur Jacobi Matrix.

Der Stoff ist Kapitel 2.2 -- 3.4 des Skriptes

19. April

Erste Übungsblattabgabe am 21.04, vor der Vorlesung (bis 9:15). Keine Mehrabgabe: Jede(r) Student(in) muss ein eigenes Blatt abgeben.

Wiederholung: Euklidesche Matrixnorm. Jacobimatrix. Taylor Formel in mehreren Variablen. Jede quadratische nxn Matrix hat genau n Eigenwerte. Spektralsatz: jede symmetrische (im reellen Fall) oder hermitische (komplexer Fall) Matrix hat reelle Eigenwerte und besitzt eine vollständige orthonormale Eigenbasis.

Satz zur Berechnung der relativen Kondition eines Problems mit Hilfe der Jacobimatrix.

Stabilität eines Verfahrens. Unterschied zwischen Kondition und Stabilität. Beispiel.

Vektornormen und induzierte Matrixnormen. Formel für die Spalten- und Zeilensummennormen. Frobeniusnorm.

Spektralradius und DIE (Euklidische) Norm der Matrizen. Beweis der Formel der Euklidischen Norm der Matrix.

Die Norm von A und A* sind gleich.

Spezielle Rolle des Skalarprodukts.

Der Stoff ist Kapitel 3.4 -- 3.7 des Skriptes

21. April

Konditionszahl. Beweis der Abschätzung des relativen Fehler bei der Lösung des linearen Gleichungssystems.

Inversion einer gestörten regulären Matrix.

Abschätzung für den relativen Fehler der Lösung lineare Gleichungssyteme mit gestörter Matrix.

Interpolation: Motivation: Stützpunkte, -stellen, -werten; Beispiele von gesuchte Grössen; warum in der Theorie unmöglich, man in der Praxis doch annähernd was finden kann. Graphische Beispiele.

Der Stoff ist Kapitel 3.8 -- 4.1 des Skriptes

26. April

Der Klausurtermin wurde am 16.7 um 10.00 Uhr noch einmal festgelegt. Der Nachmittagstermin denselben Tag war für mehreren Studenten unmöglich, deshalb konnte leider die Bitte von zwei anderen Studenten, um die Klausur zu verschieben, nicht berücksichtigt werden.

Aufgrund der Abstimmung in der Vorlesung wurde das Verfahren der Auswahl der Aufgabe zur Korrektur geändert:

Jeder Student muss am Anfang der ersten Seite jedes Übungsblattes seine klare Priorität unter den 4 Aufgaben bestimmen. Zwei Aufgaben werden für die Korrektur zufällig ausgewählt. Für jeden Studenten wird diejenige von diesen zwei Aufgaben korrigiert, der der Student höhere Priorität gab. Ohne Prioritätssetzung wird die erst ausgewürfelte Aufgabe korrigiert.

Die Berechnungsformel wurde entsprechend geändert: Die neue Formel ist:

Heute hatten wir die folgendes Themen diskutiert:

Polynominterpolation: Existenz und Eindeutigkeit; Lagrangesche Interpolationsformel. Suche nach eine Rekursionsformel; Newtonschen Basispolynome, und Definition von Dividierte Differenzen Ordnung k.

Schema für dividierte Differenzen. Newton'sche Formel für die Interpolationspolynom. Beispiel.
Dividierten Differenzen als eine lineare Kombination der Stützwerten. Eigenschaften der dividierten Differenzen: Symmetrie. (Beweis)

Der Stoff ist Kapitel 4.2 -- 4.3 des Skriptes

28. April


Beweis des Satzes von Newton.

Fehlerdarstellung der Interpolation: Restglied für (n+1)-mal diff'bare Funktionen (mit Beweis)
Mittelwertsatz der dividierten Differenzen. Widerholung der Sätze von Cauchy und Rolle.

Supremum norm auf C[a,b]

Verschiedene Kontrolle des Restglieds bei Polynominterpolation.
Beste Auswahl der Stützstellen (Tschebyscheff Nullstellen)

Satz von Weierstrass (ohne Beweis). Bernsteinsche Darstellung.

Der Stoff ist Kapitel 4.3 -- 4.5 (bis Mitte der Seite 65) des Skriptes

05.05 (nächste Donnerstag) ist Feiertag, keine Vorlesung. Der Abgabetermin ist 06.05 (Freitag) um 11:15 Uhr.

3. Mai

Beweisskizze der Bernstein Darstellung des approximierenden Polynoms in dem Satz von Weierstrass. Zusammenhang mit Wahrscheinlichkeitstheorie: Gesetz der großen Zahlen. Der Beweisskizze in der Vorlesung enthielt einen kleinen Fehler: die zweite Ableitung von F(k) wurde inkorrekt abgeschätzt, die korrekte (und ergänzte) Formel ist auf Seite 68.

Extrapolation. Definition der div. Differenzen auf identischen Stützstellen. Taylor-Entwicklung als Spezielfall der Extrapolation.

Allgemeine Hermite Interpolationsaufgabe. Berechnung der allgemeine div. Differenzen.

Beispiel für Berechnung der Hermite-Interpolation. Daumenregeln.

Existenz und Eindeutigkeit der Lösung der Hermite-Interpolation. (Beweis kommt später)

Hermite-Genocchi Formel. Erweiterung der Definition der div. Differenzen.

Der Stoff ist Kapitel 4.5 -- 4.7 des Skriptes (Beweis von Lemma 4.28 und Satz 4.31 kommt später)

05.05 (Donnerstag) ist Feiertag, keine Vorlesung. Der Abgabetermin ist 06.05 (Freitag) um 11:15 Uhr. Neues Blatt wird am 04.05 (Mittwoch) publiziert.

10. Mai

Beweis der Hermite-Genocchi Formel.

Stetigkeit der div. Differenzen und ihre Folgerungen: Permutationssymmetrie, Rekusion, Newtonsche Identität im allgemeinen Fall.

Existenz und Eindeutigkeit der Lösung der Hermite-Interpolation. Ursprüngliche Fehlerabschätzung gilt.

Spline-Interpolation. Definition. Vorteilen-Nachteilen im Vergleich zur Polynomiterpolation. Beispiele.

Lineare Splines. Fehlerabschätzung.

Der Stoff ist Kapitel 4.7 -- 4.9 des Skriptes

Wir hatten etwa mehr Korrekturgeld erhalten. Deshalb wird eine Aufgabe von jedem Übungsblatt korrigiert.

Aus Blatt 3 werden Aufgaben 14 und 16 korrigiert.

12. Mai

Lineare Splines. Fehlerabschätzung und Minimaleigenschaft

Berechnung der kubischen Splines. Randbedingungen.

Strikt diagonaldominante Matrix. Invertierbarkeit.

Existenz und Eindeutigkeit der kubischen Splines.

Ein numerisches Beispiel für Berechung der kubischen Splines.

Fehlerabschätzung der kubischen Splines.

Der Stoff ist Kapitel 4.9 -- 4.10 des Skriptes

Aus Blatt 4 werden Aufgaben 19 und 17 korrigiert.

19. Mai

Wiederholung der kubischen Splines.

Fehlerabschätzung.

L^2 Raum, Norm, Skalarprodukt.

Minimaleigenschaft der kubischen Splines.

Trigonometrische Interpolation.

Der Stoff ist Kapitel 4.10 -- 4.12.2 des Skriptes

Aus Blatt 5 werden Aufgaben 21 und 24 korrigiert.

24. Mai

Diskrete Fouriertransformation.

Schnelle Fouriertransformation.

Wiederholung des Riemannsche Integrals.

Lineare Funktional.

Quadraturformel. Genauigkeitsgrad

Interpolatorische Quadraturformel. Fehlerabschätzung.

Wann hat der Fehler ein bestimmtes Vorzeichen?

Newton-Cotes Formel. Symmetrie der Gewichte.

Drei wichtigste Newton-Cotes Formel (Rechteck-, Trapez- und Keplerregel). (Bis Satz 5.13 (nicht inbegriffen))

Der Stoff ist Kapitel 4.12.3-- 5.4.3 des Skriptes

Wegen der Feiertagen und der Zwischenklausur wird das Übungsblatt kürzer sein und schon am 24.5 publiziert.

31. Mai

Wiederholung der Newton-Cotes Formel.

Verbesserte Genauigkeitsgrad und Fehlerabschäatzung der Kepler-Formel.

Höhere NC Formel

Satz von Kusmin und Polya

Summierte Quadraturformel im Allgemeinen. Konzistenz der Summierten Quadraturformel.

Summierte Newton-Cotes Formel, Fehlerabschäatzungen.

Der Stoff ist Kapitel 5.4-- 5.6 des Skriptes

Extra Sprechstunde: Am 01.06 (Mittwoch) zwischen 13:00-15:00 (Raum 329)

2. Jun

Zwischenklausur.

Beweis der Konsistenz der summierte Quadraturformel.

Schrittweitesteuerung

Halbierung des Intervals: praktische Approximation des Fehlertermes.

Wiederholung (Aufgabe): Skalarprodukt, Orthokomplement, Gram-Schmidt Verfahren.

Der Stoff ist Kapitel 5.6 -- 5.8 (bis Satz 5.33) des Skriptes

7. Jun

Gauss-Quadratur, Orthogonale Polynome.
Skalarprodukt und Norm mit Gewichtsfunktion, orthogonale Komplement
Gram-Schmidt Verfahren
Drei-Terme Rekursion

Klassische orthogonale Polynome

Die Nullstelle der Orthopolynome sind alle reell in [a,b] und einfach.

Def. der Gauss Quadratur. Satz: Die Gewichte sind positive, die Genauigkeits grad = 2n-1 und die Formel ist interpolatiorisch

Konvergenzsatz der G. Quadratur für jede stetige Funktion

Fehlerabschätzung der G. Quadratur

Bestimmung der Nullstelle der Orthopolynome durch Eigenwerte

Der Stoff ist Kapitel 5.8-- 5.11 (Satz 5.42 noch nicht bewiesen) des Skriptes

Die Klausur ist in der Übungen oder bei Herrn Zenk (Raum 334) erhältlich

9. Jun

Bestimmung der Nullstelle der Orthopolynome durch Eigenwerte

Tricks für singuläre Integrande

Zwei wichtigste Aufgabe der linearer Algebra: Ein Überblick.
Beispiel für die Instabilität des Gauss-Verfahrens. Die Erklärung durch LR-Zerlegung. Gut-konditionertes Problem mit instabilem Verfahren gelöst
Spaltenmaximumstrategie und relative Spaltenmaximumstrategie
Eigenschaften der untere/obere Dreiecksmatrizen. Frobeniusmatrix
Gauss-Elimination als die LR-Zerlegung ohne Zeilenvertausch.

Der Stoff ist Kapitel 5.11, 5.12, 6.1, 6.2, 6.3 (ohne 6.3.1) des Skriptes

Kapitel 6.1. ist Wiederholungsmaterial (Hausaufgabe!) und wurde in der Vorlesung direkt nicht diskutiert. Aber dieser Stoff ist unvermeidbar obligatorisch. Wenn jemand eine konkrete Gauss-Elimination in der Prüfung nicht durchführen kann, wird er/sie ohne weitere Fragen durchfallen.

14. Jun

WICHTIG: Es gab einen Tippfehler in der Formel für die Gewichte in Satz 5.42: Statt tau_j steht tau_j^2 (wie folgt aus dem Beweis)
Inversionmatrizen, Permutationsmatrizen
Die PLR-Zerlegung mit Beweis.
Kondition der LR-Zerlegung, warum ist Gaussverfahren instabil?
Kondition der Permutation.
Positiv definite Matrizen. Spektralsatz. Eigenschaften der positiv definite Matrizen.
Der Stoff ist Kapitel 6.3.1, 6.4, 6.5 (bis Satz 6.17) des Skriptes
Wiederholungsmaterial (Hausaufgabe!): Kapitel 7.1 und Gram-Schmidt-Verfahren. Dieser Stoff ist noch einmal unvermeidbar obligatorisch. Wenn jemand eine konkrete Menge der vorgegebenen Vektoren nicht orthonormieren kann, wird er/sie ohne weitere Fragen durchfallen.

16. Jun


Cholesky Zerlegung und ihre Stabilität
Lesematerial: Bandmatrizien (Siehe Übungsblatt dazu)
Orthogonale Basis, Koordinaten, Stabilität der Koordinaten,
Parseval und Cauchy-Schwarz.
Orthogonal Matrix, Kondition des Produkts mit orthogonalen Matrix
Orthogonale Projektionen. Minimal Distanz von Unterraum
QR und erweiterte QR Zerlegung mittels Gram Schmidt
Der Stoff ist Kapitel 6.5, 6.6, 7.1, 7.2, 7.3 des Skriptes

21. Jun


Wiederholung der QR und erweiterte QR Zerlegung mittels Gram Schmidt
Lösung der Ax=b durch QR. Stabilität
Lineare Bestapproximation für gerade Linie und Polynom
Allgemeine Bestapproximation.
Lösung mittels der QR-Zerlegung und mittels der Normalgleichung.
Wichtigkeit der linearen Bestapproximationen in Anwendungen
Kondition der Projektion
Konditionszahl einer allgemeiner Matrix
Kondition des Gleichungssystems von vollem Spaltenrang
Der Stoff ist Kapitel 7.3, 7.4, 7.5 (bis Satz 7.23) des Skriptes

23. Jun


Kondition des Ausgleichsproblem (mit Variationsprinzip)
Instabilität des Gram-Schmidt-Verfahrens.
Orthogonale Methoden für die QR-Zerlegung

Householder Spiegelung, Eigenschaften
QR-Zerlegung mittels Householder Spiegelungen. Beispiel
Givens Rotation und QR-Zerlegung damit. Beispiel.
Vergleich der zwei Verfahren (Kapitel 7.11, 7.12 zu lesen)
Der Stoff ist Kapitel 7.5 (ab Satz 7.23), 7.6, 7.7, 7.8, 7.9, 7.10, 7.11, 7.12 (Kapitel 7.12 am 23.06 hinzugefuegt) des Skriptes

28. Jun


Vergleich der Householder und Givens Verfahren
Fixpunktiterationen: Methode des 2-jähriges Kindes. Beispiele.
Lokal Konvergenz der Iteration. Konvergenzordnung. Exponentiell Konvergenz.
Zusammenhang zwischen der Konvergenzordnung und der Ableitungen.
Apriori Abschätzung für die Anzahl der Schritten.
Banachsche Fixpunktsatz.
Kondition der Bestimmung der Nullstellen
Bisektionsverfahren
Sekantenverfahren und seine Modifizierung
Newton Verfahren.
Der Stoff ist Kapitel 7.11 (7.12 zum Lesen), 8.1, 8.2, 8.3, 8.4, 8.5 und 8.6 (Bis Satz 8.22) des Skriptes

30. Jun


Newton Verfahren. Konvergenzordnung in dim=1.
Mehrdimensionale Newton Verfahren, Beispiel.
Konvergenzsatz für Newton-Verfahren. Der Beweis der Eindeutigkeit in der Vorlesung gilt nur in Dim=1. Einen allgemeinen (und einfachen) Beweis wurde im Skript hinzugefügt.
Bedingung für die Lipschitzstetigkeit der Jacobimatrix
Gedämpftes Newton Verfahren. Richtung des staerksten Abstieges.
Der Stoff ist Kapitel 8.6 (ohne Satz 8.27). des Skriptes Lesematerial: Gauss-Newton Verfahren Kapitel 8.7 (wird nachste mal kurz besprochen).

5. Jul

Nichtlineare Ausgleichsproblem (Newton-Gauss)
Gedaempfte Versionen der nichtlin. Ausgleich (Levenberg-Marquard)
Allgemeine iterative Loesung zur Ax=b, Iterationsmatrix, Konvergenz, Konvergenzgeschwindigkeit
Jacobi-Verfahren
Gauss-Seidel Verfahren
Der Stoff ist Kapitel 8.7, Kapitel 9, 9.1, 9.2 des Skriptes

7. Jul


Wiederholung der Iterationsverfahren
Relaxation, Ueberschiessen.
Gauss-Seidel mit Relaxation.
Gauss-Seidel konvergiert fuer alle positiv definit Matrizen
Ueberblick: Diagonalisierung, Normalforme
Diagonalisierung, Jordan-Form (zu wiederholen!)
Exponential einer Matrix. Zwei Definitionen.
Allgemeine Funktion einer Matrix
Instabilitaet der Jordan-Form
Schur-Zerlegung
Der Stoff ist Kapitel 9.2.1, Kapitel 10, 10.1.1--10.1.4. des Skriptes (Kapitel 10.1.1, 10.1.2 und 10.1.3 sind Wiederholungsmaterial, lesen Sie durch, wenn etwa fehlt, schauen Sie in Ihre lin.Algebra Skripten an)

12. Jul

Zusammenfassung der verschiedenen Normalforme
Singulärwertzerlegung, Zusammenhang mit dem Basiswechseln.
Bildkompression mit Singulärwertzerlegung, Beispiele.
Kondition des Eigenwertsproblems
Eigenwerte einer gestörten Matrix.
Gerschgorin Kreise
Variationsprinzip fuer symmetrische Matrizen (zur Wiederholung -- wurde schon am 23.06 diskutiert)
Der Stoff ist Kapitel 10.1.5, 10.1.6, 10.2 Skriptes
ENDKLAUSUR -- Jul 16, Samstag.
Die endgütige Version der prüfung- und klausurrelevante Stoff

14. Jul


Potenzverfahren für den maximalen Eigenwert
Verschiebungstrick für die Berechnung der anderen Eigenwerten.
Beispiele.
Beschleunigung der Konvergenz mit einer guten Wahl des Verschiebungsparameter, Benutzung der Gerschgorin Kreise
QR-Verfahren, partielle Beweis für den symmetrischen Fall.
Der Stoff ist Kapitel 10.3, 10.4 Skriptes

ENDKLAUSUR -- Jul 16, Samstag.

Die endgütige Version der prüfung- und klausurrelevante Stoff

Viel Glueck und Spass mit der Klausur!