Stichpunkte zur Vorlesung Numerik I

Dies sind die Stichpunkte zur Vorlesung Numerik I im Sommersemester 2015. Sie sollen einen kurzen Überblick über die Themen der einzelnen Vorlesungen und wichtige Begriffe und Aussagen verschaffen.

Organistorisches, Banach'scher Fixpunktsatz (15.04.2015)

• Nichtlineare Probleme
• Kontraktion, Selbstabbildung,
• Banach'scher Fixpunktsatz

Banach'scher Fixpunktsatz und Fixpunktiteration (20.04.2015)

• Beweis Banach'scher Fixpunktsatz
• Differenzierbare Funktionen sind Lischitz-stetig
• Fixpunktiterationen für lineare Gleichungssysteme

Lineare Iterationsverfahren, Newton-Verfahren (22.04.2015)

• Jacobi- und Gauß-Seidel-Verfahren als Fixpunktiteration
• Konvergenzordung und superlineare Konvergenz
• Motivation des Newton-Verfahrens

Konvergenz des Newton-Verfahrens (27.04.2015)

• Lokal quadratische Konvergenz des Newton-Verfahrens
• Lokale Eindeutigkeit der Lösung

Globalisierung Newton-Verfahren (29.04.2015)

• Affine invarianz des Newton-Verfahrens
• Globalisierungsstrategien
• Globalisierung durch Dämpfung

Bestapproximation in endlichdimensionalen Räumen (04.05.2015)

• Bestapproximationsaufgaben in endlich-diemnsionalen normierten Räumen
• Beispiele: Tschebyscheff- und \(L^2\)-Approximation
• Bestapproximationsaufgabe hat eine Lösung
• Lösung ist im Allgemeinen nicht eindeutig
• Lösung ist eindeutig in strikt-konvexen Räumen.

Bestapproximation in endlichdimensionalen Hilbert-Räumen (06.05.2015)

• Definition: Skalarprodukt, Prähilbert-Raum
• Prähilbert-Räume sind strikt konvex
• Bestapproximationsaufgabe ist äquivalent zur Normalengleichung
• Definition: Projektion,, Orthogonalprojektion
• Für eine Projektion \(P\neq 0\) gilt \(\|P\| \geq 1\) und (\(\|P\|=1\) \(\Leftrightarrow\) \(P\) ist Orthogonalprojektion)
• \(u\) ist Bestapproximation von \(f\) in \(U\) \(\Leftrightarrow\) \(u=Pf\) wobei \(P\) die Orthogonalprojektion mit \(R(P)=U\) ist

Berechnung von Bestapproximationen (11.05.2015)

• Durch Wahl einer Basis führt die Normalengleichung auf ein LGS mit Gramscher Matrix
• Beispiel: Legendre-Polynome als \(L^2\)-orthogonale Basis von \(\mathcal{P}_n\)
• Tschebyscheff-Approximation stetiger Funktionen, Tschebyscheff-Polynome
• \(L^2\)-Approximation stetiger Funktionen

Finite Elemente, Ausgleichsprobleme (13.05.2015)

• Approximation durch lineare finite Elemente
• Motivation: Ausgleichsprobleme mit \(m\) Messpunkten
• Lineare Ausgleichsprobleme mit \(n\) Parametern
• Lineares Ausgleichsproblem hat eine eindeutige Lösung, falls \(n\leq m\)

Lineare Ausgleichsprobleme (18.05.2015)

• Lösungsdarstellung durch Normalengleichung
• Für die Systemmatrix \(A^T A\) der Normalengleichung gilt \(\kappa(A^T A) = \kappa(A)^2\)
• Beispiel mit fast-Rangdefekt
• Orthogonalisierungsverfahren
• Givens-Reflexionen sind orthogonal

QR-Zerlegung (20.05.2015)

• QR-Zerlegung durch Givens-Rotationen
  • Aufwand ist etwa 4-mal so groß wie LR-Zerlegung
• QR-Zerlegung durch Householder-Reflexionen
  • Aufwand ist etwa 2-mal so groß wie LR-Zerlegung
• QR-Zerlegung ist stabil (im Gegensatz zu LR)

Interpolation, Hermite-Genochi-Formel (27.05.2015)

• Klassische Polynominterpolation
  • Eindeutigkeit, Lagrange-Darstellung
  • Rekursionsformel für dividierte Differenzen
  • Newton-Darstellung
  • Fehler-Formel
• Taylor-Formel als Hermite-Interpolation
• Hermite-Genochi-Formel
  • Integral-Darstellung dividierter Differenzen
  • Verallgemeinerte dividierte Differenzierenzen

Hermite-Interpolation I (01.06.2015)

• Dividierte Differenzen hängen stetig von den Stützstellen ab
• Darstellung dividierte Differenzen durch Zwischenwerte von Ableitungen
• Rekursionsformel für verallgemeinerte dividierte Differenzen
• Hermite-Interpolationsaufgabe
  • Problemstellung
  • Existenz und Eindeutigkeit
  • Newton-Darstellung
  • Fehler-formel

Hermite-Interpolation II (03.06.2015)

• Schülerbesuch
• Forsetzung: Existenzbeweis für Hermite-Interpolation

Approximation und Interpolation (08.06.2015)

• Interpolationsfehler geht gegen Null, falls \(f\) glatt genug
• Interpolationsfehler kann gegen Unendlich gehen
• Abschätzung des Interpolationsfehlers mit Lebesgue-Konstante und Approximationsfehler
• Approximationsfehler geht für jedes stetige \(f\) gegen Null
• Lebegue-Konstante geht immer gegen Unendlich
• Tschebyscheff-Knoten ergeben fast optimale Lebesgue-Konstante

Stückweise und Spline-Interpolation (10.06.2015)

• Interpolation durch stückweise lineare finite Elemente
• Fehlerabschätzung für lineare finite Element Interpolation und unterschiedliche Glattheit von \(f\)
• stückweise Polynominterpolation
• Spline-Interpolationsaufgabe
• Kubische Splines

Kubische Splines (15.06.2015)

• Physikalische Interpretation kubischer Splines durch Planken
• Volständige Randbedingen für kubische Splines
• Extremaleigenschaft kubischer Splines
• Existenz und Eindeutigkeit der kubischen Spline-Interpolation
• Natürliche und periodische Randbedingungen
• Darstellung der Taylor-Koeffizienten kubischer Spline
• Berechnung der kubischen Spline-Interpolation

Numerische Quadratur (17.06.2015)

• Nachtrag: Der Fehler der kubischen Spline-Interpolation ist in \(O(h^4)\)
• Relative Kondition der Integration
• Quadraturformeln
• Quadratur durch stückweise Interpolation in \(\mathcal{P}_n\)
  • Knotenverteilung
  • Gewichte durch Lagrange-Polynome
  • Allgemeine Fehlerabschätzung für Quadraturformeln: Ordnung \(h^{n+1}\)

Summierte Newton Cotes-Formeln (22.06.2015)

• relative Kondition der Quadraturaufgabe
• Fehlerabschätzung von summierten Newton-Cotes-Formeln für gerades \(n\): Ordnung \(h^{n+2}\)
• Ist \(\widehat{I}\) exakt auf \(\mathcal{P}_l\) mit \(l\geq n\), so ist die Ordnung der zu \(\widehat{I}\) gehörigen summierten Quadraturformel \(h^{l+1}\).

Gauß-Quadraturformeln (24.06.2015)

• Ist \(\widehat{I}\) zu Quadraturpunkten \(z_i\) exakt auf \(\mathcal{P}_{2n+1}\), so steht \(p_{n+1}(z) = \prod_{i=0}^n (z-z_i)\) orthogonal auf \(\mathcal{P}_n\).
• Es gibt ein (bis auf Normierung) eindeutiges \(p_{n+1} \in \mathcal{P}_{n+1}\), dass auf \(\mathcal{P}_n\) orthogonal steht (Legendre-Polynom).
• Steht \(\mathcal{P}_n\) orthogonal steht (Legendre-Polynom), so hat \(p_{n+1}\) \(n+1\) verschiedene Nullstellen im Quadraturintervall.
• Sind die \(z_i\) die Nullstellen des Orthogonalpolynoms \(p_{n+1}\), so ist \(\widehat{I}\) exakt auf \(\mathcal{P}_{2n+1}\).
• Summierte Gauß-Formel
  • Quadraturformel zu diesen Nullstelle (des Legendre-Polynoms)
  • Ordnung: \(h^{2n+2}\)
  • immer vom positiven Typ
  • diese Wahl der Knoten ist Optimal

Adaptive Multilevel-Quadratur (29.06.2015)

• Adaptiver Quadratur-Algorithmus
• Gitterverfeinerung auf Grundlage lokaler Fehlerschätzer
• Fehlerschätzer durch Quadraturformel höherer Ordnung
• Ist die Saturationsbedingung immer erfüllt, so läßt sich der exakte Fehler nach oben und unten durch den Schätzer beschränken.
• Adaptive Quadratur mit Trapez- und Simpson-Regel

Anfangswertprobleme für gewöhnliche Differentialgleichungen (01.07.2015)

• Autonome Anfangswertprobleme sind translationsinvariant.
• Jedes Anfangswertproblem kann in ein autonomes Anfangswertproblem umformuliert werden.
• Satz von Picard/Lindelöf: Eindeutigkeit und Existenz von Lösungen von Anfangswertproblemen für beliebige Startwerte bei Lipschitz-stetigem \(f\).
• Flussoperator
  • Definition
  • Halbgruppeneigenschaften
  • Abschätzung der Kondition mit Hilfe des Gronwall-Lemmas

Einführung zu Lösungsverfahren für Anfangswertprobleme (06.07.2015)

• Euler-Verfahren (explizit/implizit) als Ergebnis einer linearen Approximation des Flussoperators
• Konsistenz von Einschrittverfahren
  • Definition Konsistenzfehler, Konsistenz, Konsistenzordnung
  • Konsistenzordnung \(p=1\) für das explizite Euler-Verfahren
  • Taylor-Methode zur Konstruktion von Verfahren höherer Ordnung
• Runge-Kutta-Verfahren
  • allgemeine Definition
  • Darstellung im Butcher-Schema

Runge-Kutta-Verfahren (08.07.2015)

• Herleitung von Bedingungen an konsistente Runge-Kutta-Verfahren durch Taylor-Entwicklung des Konsistenzfehlers
• Diskrete Kondition/Lipschitz-Stetigkeit diskreter Flussoperatoren expliziter Runge-Kutta-Verfahren
• Optimale Störungsempfindlichkeit für konsistente s-stufige explizite Runge-Kutta-Verfahren mit nicht-negativen Koeffizienten
• Stabilität und Konvergenz expliziter Runge-Kutta-Verfahren