Department Mathematik
print


Navigationspfad


Inhaltsbereich

Numerik: Themenübersicht der Vorlesungen

14. Oktober, 1. Vorlesung

Begriff des Algorithmus, terminierende und vollständige Verfahren. Gut gestellte und schlecht gestellte Probleme.

16. Oktober, 2. Vorlesung

Abschneidefehler, Rundungsfehler. Definition der Landau-Symbole groß O und klein o. Differzierbarkeit mit Landau-Symbolen.

21. Oktober, 3. Vorlesung

Eigenschaften der Landau-Symbole groß O und klein o. Satz von Taylor mit Landau-Symbolen. Beschränkte lineare Abbildungen. Operatornorm linearer Abbildungen zwischen normierten Vektorräumen (speziell: natürliche Matrixnorm). Äquivalenzsatz für beschränkte lineare Abbildungen (A beschränkt genau dann, wenn Operatornorm von A endlich, genau dannm wenn A lipschitzstetig genau dann, wenn A stetig genau dann, wenn A stetig in einem Punkt). Lineare Abbildungen zwischen endlichdimensionalen Räumen sind immer stetig. Die Operatornorm ist wirklich eine Norm, und es ist die kleinste Lipschitzkonstante. Die Operatornorm der Identität ist 1; die Operatornorm von BA ist kleiner oder gleich dem Produkt der Operatornormen von B und A. Zeilen- und Spaltensummennorm. Spektralnorm. Frobenius oder Hilbert-Schmidt-Norm (diese wird für m,n>1 nicht von Normen auf K^m und K^n induziert).

23. Oktober, 4. Vorlesung

Adjungierte und transponierte Matrizen. Symmetrische, hermitesche, positiv semidefinite und positiv definite Matrizen. Spektralradius. Formel zur Berechnung der Spektralnorm aus dem Spektralradius (für hermitesche Matrizen stimmt beides überein). Die Spektralnorm einer komplexen Matrix stimmt mit der Spektralnorm ihrer adjungierten Matrix überein. Definition der Gutkonditioniertheit einer Abbildung in einem Punkt und in einer (Kugel)-Umgebung eines Punktes. Definition der relativen Kondition einer gutkonditionierten Abbildung. Vergleich der Gutkonditioniertheit mit anderen Regularitätsbegriffen.

28. Oktober, 5. Vorlesung

Relative Kondition des Lösens linearer Gleichungssysteme. Konditionszahl einer Matrix, speziell: spektrale Konditionszahl. Formeln für die spektrale Konditionszahl. Abschätzungen für den Fehler der Lösung eines linearen Gleichungssystems mit gestörter rechter Seite. Die Menge der invertierbaren reellen Matrizen ist offen. Abschätzungen für den Fehler der Lösung eines linearen Gleichungssystems mit gestörter Matrix UND mit gestörter rechter Seite.

30. Oktober, 6. Vorlesung

Formel für die relative Kondition einer stetig differenzierbaren Abbildung von R^n nach R^m. Relative Kondition von (reeller) Multiplikation und Division (während die Multiplikation in jeder Umgebung eines Punktes gutkonditioniert ist, ist dies bei der Division nur der Fall, wenn die Umgebung klein genug gewählt ist).

4. November, 7. Vorlesung

Kondition der komplexen Multiplikation. Definition der Menge K[X] der Polynome über einem Körper K, sowie von Addition, Skalarmultiplikation und Multiplikation auf dieser Menge. Definition von Monomen sowie von Koeffizienten von Polynomen sowie vom Grad eines Polynoms. Definition der Normiertheit eines Polynoms. Die Polynome bilden einen K-Vektorraum sowie einen Ring mit Eins. Definition von Einsetzungs-/Auswertungshomomorphismus (dieser ist unitaler und linearer Ringhomomorphismus). Definition von Nustelle/Wurzel eines Polynoms. Definition von Polynomfunktionen (der Raum der Polynomfunktionen ist genau dann isomorph zum Raum der Polynome, wenn der Körper unendlich viele Elemente hat - in diesem Fall wird der Grad einer Polynomfunktion als der Grad des zugehörigen Polynoms definiert). Polynominterpolation: Stützpunkte und Interpolierende. Existenz und Eindeutigkeit des interpolierenden Polynoms, Lagrangesches Polynom, Lagrangesche Basispolynome.

6. November, 8. Vorlesung

Beispiel zu Lagrangeschen Basispolynomen. Definition der Ableitungen von Polynomen aus K[X], dazu Ableitungsregeln. Satz: Annuliert x aus K ein Polynom f und seine Ableitungen bis zur Ordnung m, so ist x eine Nullstelle der Vielfachheit mindestens m+1 von f (sofern die Charakteristik von K Null oder groß genug ist). Satz zur Hermite-Interpolation (Existenz und Eindeutigkeit des Interpolationspolynoms). Definition der Notationen P[x0,...,xn] und P[g|x0,...,xn] für das Interpolationspolynom. Satz, der eine Rekursion für das Hermite-Interpolationspolynom liefert, die die Auswertung mit Neville-Schema ermöglicht.

11. November, 9. Vorlesung

Hermite-Interpolationspolynom ist unabhängig von der Reihenfolge der Stützpunkte. Newtonsche Interpolationsformel, Newtonsche Basispolynome. Dividierte Differenzen. Rekursive Formel zur Berechnung der dividierten Differenzen. Auch die dividierten Differenzen sind unabhängig von der Reihenfolge der Stützpunkte.

13. November, 10. Vorlesung

Berechnung der dividierten Differenzen mit Neville-Schema. Formel für die Differenz zwischen einer differenzierbaren Funktion und dem zugeh&oum;rigen Interpolationspolynom. Hermite-Genocchi-Formel. Mittelwertsatz für dividierte Differenzen. Satz zur stetigen Abhängigkeit der dividierten Differenzen von den Daten.

18. November, 11. Vorlesung

Konvergenz der Interpolationspolynome im Fall der Approximation einer unendlich oft differenzierbaren Funktion, deren Ableitungen einer Abschätzung genügen. Formel und Fehlerabschätzung zur numerischen Differenziation. Rekursive Definition der Tschebyscheffpolynome. Eigenschaften der Tschebyscheffpolynome, insbesondere Darstellung durch cos bzw. cosh sowie Lage der Nullstellen und Extrema. Affine Bijektionen zwischen einem Intervall [a,b] und dem Intervall [-1,1]. Satz: Die Tschebyscheffpolynome minimieren die Unendlichnorm auf [-1,1] unter den Polynomen mit Grad n und Höchstkoeffizient 2^(n-1). Folgerung: Die Nullstellen der Tschebyscheffpolynome sind bei der Approximation auf [-1,1] mittels Polynominterpolation die optimalen Stützstellen (auf anderen Intervallen erhält man die optimalen Stützstellen durch Verschiebung der Nullstellen mittels der affinen Bijektion).

20. November, 12. Vorlesung

Satz: Skalierte Tschebyscheffpolynome sind bezüglich der Unendlichnorm auf [-1,1] minimal unter den Polynomen mit Grad n, die an einer gegebenen Stelle s, die nicht in [-1,1] liegt, den Wert 1 haben. Splinefunktionen der Ordnung L zu einem gegebenen Knotenvektor (also zu einer Zerlegung eines Intervalls). Speziell: lineare und kubische Splines. Satz: Polynome sind Splines, Ableitungen von Splines sind Splines, Stammfunktionen von Splines sind Splines; die Menge der Splines der Ordnung L zu einem Knotenvektor mit N+1 Knoten ist ein reeller Vektorraum der Dimension N+L (Angabe einer Basis, die Monome und L-te Stammfunktionen von charakteristischen Funktionen enthält. Existenz, Eindeutigkeit und Fehlerabschätzung für lineare Splines. Berechnung kubischer Splines.

25. November, 13. Vorlesung

Natürliche Randbedingungen, periodische Randbedingungen, Dirichlet-Randbedingungen für die erste Ableitung. Strikt diagonaldominante Matrizen. Existenz und Eindeutigkeit kubischer Splines mit natürlichen Randbedingungen. Fehlerabschätzung für kubische Splines mit natürlichen Randbedingungen.

27. November, 14. Vorlesung

Zerlegung eines Intervalls mit Stützstellen. Feinheit einer Zerlegung. Riemannsumme und Riemannintegral. Approximation des Integrals mit Riemannsummen. Gewichtsfunktionen und gewichtete Integrale. Definition der Quadraturformel. Definition der interpolatorischen Quadraturformel. Genauigkeitsgrad einer Quadraturformel. Genauigkeitsgrad, Konvergenz und Fehlerabschätzung für interpolatorische Quadraturformeln.

2. Dezember, 15. Vorlesung

Vorzeichen des Quadraturfehlers. Newton-Cotes-Formeln, speziell abgeschlossene Newton-Cotes-Formeln. Berechnung und Symmetrie der Gewichte.

4. Dezember, 16. Vorlesung

Für gerades n ist der Genauigkeitsgrad der abgeschlossenen Newton-Cotes-Formeln n+1. Rechteck-, Trapez- und Simpson-Regel (bzw. kepplersche Fassregel) jeweils mit Genauigkeitsgrad und Fehlerabschätzung. Operatornorm von Quadraturformeln. Formulierung des Satzes von Polya: Eine Folge von Quadraturformeln konvergiert genau dann für alle stetigen Funktionen, wenn sie für alle Polynome konvergiert und die Summen der Beträge der Gewichte gleichmäßig beschränkt sind. Daraus folgt, dass die abgeschlossenen Newton-Cotes-Formeln nicht für alle stetigen Funktionen konvergieren, da dort die Summen der Beträge der Gewichte gegen Unendlich konvergieren.

9. Dezember, 17. Vorlesung

Beweis des Satzes von Polya. Summierte Quadraturformeln: Definition, Konvergenz, Definition der Konvergenzordnung. Summierte Rechteck- Trapez- und Simpsonregeln mit Fehlerabschätzung und Konvergenzordnung.

11. Dezember, 18. Vorlesung

Durch eine Gewichtsfunktion gegebenens Skalarprodukt und die induzierte Norm. Gram-Schmidt-Orthogonalisierungsverfahren. Drei-Term-Rekursion für orthogonale Polynome bezüglich eines durch eine Gewichtsfunktion gegebenes Skalarprodukt. Definition der orthogonalen Polynome, speziell des n. orthogonalen Polynoms. Die Nullstellen der orthogonalen Polynome sind einfach und liegen in ]a,b[. Definition der gaußschen Quadraturformeln n. Ordnung. Eigenschaften der gaußschen Quadraturformeln: Die Formel n. Ordnung ist für Polynome höchstens (2n-1). Grades exakt, alle Gewichte sind positiv und für triviale Gewichtsfunktion ist die Formel interpolatorisch.

16. Dezember, 19. Vorlesung

Satz: Eine Quadraturformel mit n Stützstellen, die alle Polynome höchstens (2n-1). Grades exakt integriert ist notwendiger Weise die gaußsche Quadraturformel n. Ordnung. Die Gaußschen Quadraturformeln konvergieren für jede stetige Funktion gegen das exakte Integral. Man sich durch Transformation auf das Standardintervall [-1,1] und auf Standardgewichtsfunktionen beschränken. Fehlerabschätzung der Gaußschen Quadraturformeln. Definition des linearen Gleichungssystems und der erweiterten Matrix. Wiederholung: LR-Zerlegung und Lösung eines LGS bei gegebener LR-Zerlegung. Pivotstrategien: Spaltenmaximumsstrategie, relative Spaltenmaximumsstrategie.

18. Dezember, 20. Vorlesung

Cholesky-Zerlegung von hermiteschen positiv definiten Matrizen: Definition, Existenz, Eindeutigkeit, Algorithmus zur Bestimmung. Satz: Hermitesch positiv semidefinit ist notwendig für Existenz einer Cholesky-Zerlegung. Definition unitärer und orthogonaler Matrizen. Definition der QR-Zerlegung und der erweiterten QR-Zerlegung. Satz: Die QR-Zerlegung ist eindeutig bis auf Multiplikation mit einer Diagonalmatrix, deren Diagonaleinträge alle Betrag 1 haben. Satz: Multiplikation mit einer unitären Matrix ändert weder die Spektralnorm der Matrix noch ihre spektrale Konditionszahl; die spektrale Konditionszahl einer unitären Matrix ist 1. Lösung eines LGS bei gegebener QR-Zerlegung.

19. Dezember (Ersatz für 23. Dez.), 21. Vorlesung

Satz zu Existenz und Eindeutigkeit der QR-Zerlegung und der erweiterten QR-Zerlegung, Algorithmus zur Bestimmung einer QR-Zerlegung mit dem Gram-Schmidt-Orthogonalisierungsverfahren. Definition der Householdermatrix/Householderspiegelung. Householdermatrizen sind symmetrisch, involutorisch und orthogonal.

Keine Lehrveranstaltungen vom 24. Dezember bis 6. Januar

8. Januar, 22. Vorlesung

Householderspiegelungen sind wirklich Spiegelungen. Definition des Householderverfahrens. Satz: Das Householderverfahren liefert eine erweiterte QR-Zerlegung einer gegebenen Matrix.

13. Januar, 23. Vorlesung

Fixpunkte und Nullstellen. Newtonverfahren (eindimensional und mehrdimensional). Konvergenzsatz (von globalem Typ) zum eindimensionalen Newtonverfahren. Beispiele zum eindimensionalen Newtonverfahren. Formulierung: Konvergenzsatz (von lokalem Typ) zum mehrdimensionalen Newtonverfahren mit Fehlerabschätzung.

15. Januar, 24. Vorlesung

Beweis des obigen Satzes zum Newtonverfahren. Beispiel zum Satz. Wiederholung der Begriffe Eigenwert, Eigenvektor, charakterischtisches Polynom, Spektrum einer Matrix. Eigenwerte als Nullstellen des charakterischtischen Polynoms. Algebraische und geometrische Vielfachheit. Zusammenhang des Nullstellenproblems mit dem Eigenwertproblem. Definition der Gerschgorinkreise (zeilenweise und spaltenweise). Satz von Gerschgorin: Das Spektrum einer Matrix liegt immer im Schnitt der Vereinigung der zeilenweisen Gerschgorinkreise mit der Vereinigung der spaltenweisen Gerschgorinkreise.

20. Januar, 25. Vorlesung

Satz: Ist die Vereinigung von genau q Gerschgorinkreisen disjunkt zur Vereinigung der restlichen n-q Gerschgorinkreise, so liegen genau q Eigenwerte in der Vereinigung der q Kreise und n-q Eigenwerte in der Vereinigung der n-q Kreise. Folgerung: Ist bei einer reellen Matrix ein Gerschgorinkreis disjunkt zu allen anderen, so kann er nur einen reellen Eigenwert enthalten. Beispiel zur Lokalisierung der Eigenwerte mit Gerschgorinkreisen. Definition der Potenzmethode (auch Vektoriteration oder von Mises-Iteration). Satz: Die Potenzen einer Matrix konvergieren genau dann gegen Null, wenn der Spektralradius echt kleiner als 1 ist. Definition, wann ein Vektor einen nichttrivialen Anteil in einem verallgemeinerten Eigenraum einer Matrix hat. Formulierung eines Konvergenzsatzes zur Potenzmethode: Hat die Matrix A einen dominanten halbeinfachen Eigenwert lambda und hat der Startvektor des Potenzverfahrens einen nichttrivialen Anteil im zu lambda gehörenden Eigenraum, so lässt sich aus den Iterierten der Potenzmethode eine Folge von Zahlen bilden, die gegen lambda konvergiert, sowie eine Folge von Vektoren, die für große Folgenindizes beliebig nahe an einem Eigenvektor von lambda liegt (aber im Allgemeinen nicht konvergiert).

22. Januar, 26. Vorlesung

Satz zur Konvergenz des inversen Potenzmethode, mit dem andere als nur der dominante Eigenwert approximiert werden können. Im Prinzip lassen sich mit dem inversen Potenzverfahren, zumindest für gutartige Matrizen, alle Eigenwerte finden, indem man die Eigenwerte in einer kompakten Teilmenge der komplexen Zahlen lokalisiert, die kompakte Teilmenge mit einem Quadratgitter, das fein genug ist, überdeckt, und das inverse Potenzverfahren für die Mittelpunkte der Quadrate anwendet. Definition des Algorithmus des QR-Verfahrens. Formulierung eines Konvergenzsatzes zum QR-Verfahren: Für invertierbare und diagonalisierbare Matrizen A mit betragsmäßig einfachen Eigenwerten liefert das QR-Verfahren asymptotisch obere Dreiecksmatrizen, auf deren Diagonale die Eigenwerte von A stehen. Die Konvergenzrate ist linear und bestimmt von den Größenverhältnissen der Eigenwerte zueinander.

27. Januar, 27. Vorlesung

Beweis des obigen Konvergenzsatzes zum QR-Verfahren Bemerkung: Sind die Eigenwerte im Konvergenzsatz zum QR-Verfahren nicht betragsmäßig einfach, so liefert das QR-Verfahren asymptotisch nur eine obere Block-Dreiecksmatrix. Bemerkung zu QR-Verfahren mit Spektralverschiebung, QR-Verfahren mit Deflation. Formulierung von Minimierungsproblemen. Gleichungen als spezielle Minimierungsprobleme. Formulierung linearer und nichtlinearer Ausgleichsprobleme. Definition konvexer, streng konvexer und gleichmäßig konvexer Funktionen auf einem normierten Vektorraum. Beispiel: x^p ist für p>1 streng konvex.

29. Januar, 28. Vorlesung

Beispiele: Normen sind konvex, aber nicht streng konvex, das Quadrat einer von einem Skalarprodukt induzierten Norm ist gleichmäßig (speziell: streng) konvex, die Zielfunktion eines linearen Ausgleichsproblems ist konvex und im injektiven Fall sogar streng konvex. Kriterien für Konvexität (bzw. strenge bzw. gleichmäßig Konvexität) für (stetig) differenzierbare Funktionen. Satz: Ist f gleichmäßig konvex und x ein lokales Minimum, so lässt sich das Quadrat des Abstandes zwischen x und y abschätzen durch den Abstand von f(y) und f(x). Satz: Lokale Minima konvexer Funktionen sind auch globale Minima, die Menge der Minima einer konvexen Funktion ist konvex. Satz: Ist f streng konvex und hat f ein lokales Minimum, so ist dieses eindeutig und streng. Definition der Schrittweiten-Richtungssuche zu einer Folge von Richtungen und einer Folge von Schrittweiten. Definition von Abstiegsverfahren und Gradientenverfahren (Verfahren des steilsten Abstiegs).

3. Februar, 29. Vorlesung

Lemma: Gradientenverfahren sind Abstiegsverfahren. Armijoregel zur Schrittweitenbestimmung mit Lemma zur Wohldefiniertheit. Satz: Ist f stetig differenzierbar, so ist jeder Häufungspunkt des Gradientenverfahrens mit Armijoregel ein stationärer Punkt von f; bei (streng) konvexem f ergibt sich dann, dass jeder Häufungspunkt ein (strenges) globales Minimum ist.

5. Februar, 30. Vorlesung

Definition quadratischer Funktionen f:R^n nach R, die durch eine symmetrische positiv-definite Matrix gegeben sind, sowie Eigenschaften solcher Funktionen. Kantorovichungleichung. Satz: Für die obigen quadratischen Funktionen konvergiert das Gradientenverfahren bei geeigneter Wahl der Schrittweiten linear gegen das eindeutige (und strenge) globale Minimum der Funktion.
Send feedback concerning this page toaddress.gif
For spam control reasons, the e-mail address is only provided as an image.
Thus, you have to copy it manually. Sorry for any inconvenience.

Corrections (even minor ones) and suggestions for improvements are welcome.

Last update: Feb 6, 2020 Peter Philip.