Numerik - Cheatsheet.pdf

Direkte und iterative Lösungsverfahren

Definition:

Direkte Verfahren lösen Gleichungssysteme in endlich vielen Schritten. Iterative Verfahren approximieren die Lösung schrittweise.

Details:

• Matrixlösungen: \textbf{direkt}: \textit{LU-Zerlegung}, \textit{Cholesky-Zerlegung}, \textit{QR-Zerlegung}
• \textbf{Iterativ}: \textit{Jacobi-Verfahren}, \textit{Gauss-Seidel-Verfahren}, \textit{SOR-Verfahren}
• Effizienz: \textbf{direkt} für kleinere Systeme oder spezielle Matrizen (z.B. dichte Matrizen) gut; \textbf{iterativ} für große, spärliche Matrizen besser
• Konvergenz: Iterative Verfahren benötigen Konvergenzkriterien
• Ziel: Minimierung des Rechenaufwands und Speicherbedarfs

Rundungsfehler und deren Auswirkungen

Definition:

Rundungsfehler entstehen, wenn Zahlen bei der Darstellung oder Berechnung gerundet werden, da Computer nur eine begrenzte Anzahl von Dezimalstellen darstellen können.

Details:

• Rundungsfehler treten bei Fließkomma-Arithmetik auf.
• Kumulation von Rundungsfehlern führt zu Ungenauigkeiten.
• Bekannte Effekte: Numerische Instabilität, Verlust signifikanten Stellen, akkumulierte Fehler.
• Vermeidung: Algorithmenwahl, Mehrstellenarithmetik, Fehleranalyse und -korrektur
• Beispiel: Addition von sehr kleinen Zahlen zu großen Zahlen
• Maschinengenauigkeit (Maschinepsilon): Gibt an, wie genau ein Computer Zahlen darstellen kann (\texttt{float} und \texttt{double} in Programmiersprachen).

Least-Squares-Approximation

Definition:

Methode zur Anpassung eines Modells an gegebene Datenpunkte durch Minimierung der Summe der Quadrate der Abstände zwischen den Datenpunkten und dem Modell.

Details:

• Ziel: Minimierung der Fehlerquadrate \(\text{S}(\boldsymbol{x}) = \boldsymbol{r}(\boldsymbol{x})^T \boldsymbol{r}(\boldsymbol{x})\)
• Normalengleichung: \(\boldsymbol{A}^T \boldsymbol{A} \boldsymbol{x} = \boldsymbol{A}^T \boldsymbol{b}\)
• QR-Zerlegung: \(\boldsymbol{A} = \boldsymbol{Q} \boldsymbol{R}\), Lösung durch Rückwärtseinsetzen
• Anwendung: lineare Regression, Datenglättung

Numerische Lösung gewöhnlicher Differentialgleichungen (ODEs)

Definition:

Numerische Methoden zur Lösung von ODEs - Ansätze zur näherungsweisen Berechnung von Lösungen von gewöhnlichen Differentialgleichungen.

Details:

• Typische Methoden: Euler-Verfahren, Runge-Kutta-Verfahren
• Stabilität und Genauigkeit der Verfahren prüfen
• Euler-Verfahren: \[ y_{n+1} = y_n + h f(t_n, y_n) \]
• Runge-Kutta-Verfahren: \[ y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4) \] \( k_1 = f(t_n, y_n) \) \( k_2 = f(t_n + \frac{h}{2}, y_n + \frac{h}{2} k_1) \) \( k_3 = f(t_n + \frac{h}{2}, y_n + \frac{h}{2} k_2) \) \( k_4 = f(t_n + h, y_n + h k_3) \)
• Fehlerabschätzung und Konvergenz analysieren

Burnsidesches Lemma

Definition:

Das Burnsidesche Lemma hilft, die Anzahl der verschiedenen Orbits einer Gruppenaktion zu bestimmen.

Details:

• Nutze das Lemma für endliche Gruppen und endliche Mengen.
• Es besagt, dass die Anzahl der Orbits gleich dem Durchschnitt der Fixpunktanzahlen der Gruppenelemente ist.
• Formel: \( |X/G| = \frac{1}{|G|} \sum_{g \in G} |\text{Fix}(g)| \)
• \( |X/G| \) ist die Anzahl der Orbits.
• \( \text{Fix}(g) \) ist die Menge der Elemente in \( X \), die von \( g \) fixiert werden.

Finite-Differenzen-Methoden für partielle Differentialgleichungen (PDEs)

Definition:

Numerische Methode zur Approximation der Lösungen von partiellen Differentialgleichungen (PDEs); approximiert Ableitungen durch Differenzengleichungen.

Details:

• Diskretisierung des Problems: Zerlegen des kontinuierlichen Bereichs in ein Gitter.
• Approximation von Ableitungen: z.B. \( \frac{\partial u}{\partial x} \approx \frac{u(x+h,y) - u(x,y)}{h} \) für Vorwärtsdifferenzen
• Gitterpunkte: Punkte (Knoten), an denen Lösung berechnet wird.
• Stabilität und Konvergenz analysieren: Notwendige Bedingungen für die Genauigkeit der numerischen Lösung.
• Anwendung: Zeitabhängige und stationäre PDEs.

Kondition und Stabilität numerischer Verfahren

Definition:

Kondition und Stabilität numerischer Verfahren betreffen die Empfindlichkeit gegenüber Störungen und die Fähigkeit, Fehler während der Berechnung zu kontrollieren.

Details:

• Kondition (condition number): Maß für die Empfindlichkeit der Lösung eines Problems gegenüber Änderungen in den Eingangsdaten.
• Ist ein Problem gut konditioniert, führt eine kleine Eingangsänderung zu einer kleinen Änderung im Ergebnis.
• Konditionszahl \( \text{cond}(A) \): \[ \text{cond}(A) = \frac{\text{maximaler Eigenwert von } A}{\text{minimaler Eigenwert von } A} \]
• Stabilität: Ein numerisches Verfahren ist stabil, wenn es Fehler, die während der Berechnung auftreten, nicht vergrößert.
• Ein Verfahren kann numerisch stabil oder instabil sein; dies hängt von seiner Fehlerverstärkung ab.
• Vorwärtsfehler: Unterschied zwischen der exakten Lösung und der numerischen Lösung.
• Rückwärtsfehler: Unterschied zwischen den tatsächlichen Eingangsdaten und den durch das Verfahren angenommenen Daten, die die numerische Lösung produzieren würden.