Stichpunkte zur Vorlesung Numerik I

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

Organistorisches, Banach'scher Fixpunktsatz (19.04.2017)

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

Banach'scher Fixpunktsatz und lineare Iterationsverfahren (24.04.2017)

• Beweis Banach'scher Fixpunktsatz
• Differenzierbare Funktionen sind Lischitz-stetig
• Fixpunktiterationen für lineare Gleichungssysteme
• Jacobi- und Gauß-Seidel-Verfahren als Fixpunktiteration

Newton-Verfahren (26.04.2017)

• Konvergenzordung und superlineare Konvergenz
• Motivation des Newton-Verfahrens
• Affine invarianz des Newton-Verfahrens
• Lokal quadratische Konvergenz des Newton-Verfahrens
• Lokale Eindeutigkeit der Lösung

Globalisierung des Newton-Verfahrens, Bestapproximation, lineare Ausgleichsprobleme (03.05.2017)

• Globalisierungsstrategien
• Globalisierung durch Dämpfung
• Motivation: Bestapproximationsaufgaben
• Beispiele: Tschebyscheff- und \(L^2\)-Approximation
• Motivation: lineare Ausgleichsprobleme mit \(m\) Messpunkten

Bestapproximation in endlichdimensionalen Räumen (08.05.2017)

• 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 (10.05.2017)

• Definition: Skalarprodukt, Prähilbert-Raum
• Prähilbert-Räume sind strikt konvex
• Bestapproximationsaufgabe ist äquivalent zur Normalengleichung
• Definition: Projektion,, Orthogonalprojektion
• \(u\) ist Bestapproximation von \(f\) in \(U\) \(\Leftrightarrow\) \(u=Pf\) wobei \(P\) die Orthogonalprojektion mit \(R(P)=U\) ist

Orthogonalprojektionen, Berechnung von Bestapproximationen (15.05.2017)

• Für eine Projektion \(P\neq 0\) gilt \(\|P\| \geq 1\) und (\(\|P\|=1\) \(\Leftrightarrow\) \(P\) ist Orthogonalprojektion)
• 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

L2-Bestapproximation, lineare Ausgleichsprobleme, QR-Zerlegung (17.05.2017)

• \(L^2\)-Bestapproximation durch Polynomen
• \(L^2\)-Bestapproximation durch lineare finite Elemente
• Lineare Ausgleichsprobleme mit \(n\) Parametern und \(m\) Messpunkten
  • Eindeutige Lösung, falls \(n\leq m\)
  • 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
• Definition QR-Zerlegung

QR-Zerlegung, Givens-Rotationen (22.05.2017)

• Lösung von Ausgleichsproblemen durch QR-Zerlegung
• QR-Zerlegung ist stabil (im Gegensatz zu LR)
• QR-Zerlegung durch Givens-Rotationen
• Householder-Reflexionen

QR-Zerlegung mit Householder-Reflexionen, Interpolation (24.05.2017)

• QR-Zerlegung durch Householder-Reflexionen
• Klassische Polynominterpolation
  • Eindeutigkeit, Lagrange-Darstellung
  • Rekursionsformel für dividierte Differenzen
  • Newton-Darstellung
  • Fehler-Formel
• Taylor-Formel als Hermite-Interpolation

Interpolation, Hermite-Genochi-Formel (29.05.2017)

• Hermite-Genochi-Formel
  • Integral-Darstellung dividierter Differenzen
  • Verallgemeinerte dividierte Differenzierenzen
• Dividierte Differenzen hängen stetig von den Stützstellen ab
• Darstellung dividierte Differenzen durch Zwischenwerte von Ableitungen
• Rekursionsformel für verallgemeinerte dividierte Differenzen

Hermite-Interpolation (31.06.2017)

• Hermite-Interpolationsaufgabe
  • Problemstellung
  • Existenz und Eindeutigkeit
  • Newton-Darstellung
  • Fehler-formel

Approximationseigenschaften der Hermite-Interpolation (07.06.2017)

• Beispiel für Hermite-Interpolation
• 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 Interpolation und Spline-Interpolation (12.06.2017)

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

Kubische Splines (14.06.2017)

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

Approximationseigenschaften kubische Splines, Numerische Quadratur (19.06.2017)

• Nachtrag: Der Fehler der kubischen Spline-Interpolation ist in \(O(h^4)\)
• Relative Kondition der Integration
• Quadraturformeln
• Quadraturdurch globale Interpolation, Fehlerabschätzung

Summierte Quadraturformeln (21.06.2017)

• Quadratur durch stückweise Interpolation in \(\mathcal{P}_n\)
  • Knotenverteilung
  • Gewichte durch Lagrange-Polynome
  • Allgemeine Fehlerabschätzung für Quadraturformeln: Ordnung \(h^{n+1}\)
• Newton Cotes-Formeln
• relative Kondition der Quadraturaufgabe, Quadraturformeln von positivem Typ
• 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 (26.06.2017)

• 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
  • eindeutig bestimmt und optimal

Gauß-Lobatto-Quadraturformel, adaptive Multilevel-Quadratur (28.06.2017)

• Herleitung der Gauß-Lobatto-Formeln (Gauß-Formeln mit Randpunkten als Quadraturpunkten)
• Adaptiver Quadratur-Algorithmus
• Gitterverfeinerung auf Grundlage lokaler Fehlerschätzer

Adaptive Multilevel-Quadratur, gewöhnliche Differentialgleichungen (03.07.2017)

• 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 (03.07.2017)

• 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\).