Numerisches Programieren - Cheatsheet.pdf

Numerische Lösung linearer Gleichungssysteme

Definition:

Numerische Methoden zur Approximation der Lösung von linearen Gleichungssystemen. Oftmals notwendig, wenn analytische Lösungen nicht praktikabel sind.

Details:

• Häufige Methoden: Gauss-Algorithmus, LU-Zerlegung, Jacobi-Verfahren, Gauss-Seidel-Verfahren
• Vorgehensweise: Transformiere Matrix in eine einfachere Form oder abstrahiere über iterative Verfahren
• Fehleranalyse und Konvergenz sind kritische Punkte
• Matrix-Vektor-Multiplikationen im Fokus zur Reduktion von Rechenlast
• Spezielle Algorithmen für große und dünn besetzte Matrizen
• Anwendung in verschiedenen Bereichen wie Simulationen, Datenanalyse

Fehleranalyse, insbesondere Rundungsfehler und Fehlerfortpflanzung

Definition:

Fehleranalyse untersucht, wie Fehler in numerischen Berechnungen entstehen und sich ausbreiten. Konzentriere Dich vor allem auf Rundungsfehler und deren Auswirkungen.

Details:

• Rundungsfehler: Entstehen durch Begrenzung der Stellenanzahl im Computer, z. B. bei der Darstellung von Gleitkommazahlen.
• Absolute Fehler: \[ E_A = | x - x' | \]
• Relative Fehler: \[ E_R = \frac{| x - x' |}{| x |} \]
• Fehlerfortpflanzung: Analyse, wie Eingabefehler das Endergebnis beeinflussen.
• Fehlerfortpflanzung in Addition/Subtraktion: \[ E_{(A+B)} \approx E_A + E_B \]
• Fehlerfortpflanzung in Multiplikation/Division: \[ E_{(A \times B)} \approx E_A + E_B \]
• Schätzwert für die Fehlerfortpflanzung bei komplexen Algorithmen durch Varianten der Fehleranalyse.

Polynomiale und Spline-Interpolation

Definition:

Polynomiale und Spline-Interpolation sind numerische Methoden zur Annäherung von Funktionen durch Polynomien bzw. Splines.

Details:

• Polynomiale Interpolation verwendet ein Polynom n-ten Grades zur Durchgang durch n+1 gegebene Punkte.
• Generelle Form: P(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n.
• Vorteile: Einfach zu implementieren, glatte Funktion.
• Nachteile: Runge-Phänomen bei hohen Graden.
• Spline-Interpolation unterteilt Intervall in kleinere Stücke und verwendet Niedriggrad-Polynome.
• Kubische Splines sind Standard: S_i(x) = a_i + b_i (x - x_i) + c_i (x - x_i)^2 + d_i (x - x_i)^3.
• Vorteile: Bessere Stabilität und Genauigkeit, keine Oszillationen.
• Notwendige Bedingungen für Kubische Splines: Stetigkeit der ersten und zweiten Ableitung.

Least-Squares-Approximation

Definition:

Least-Squares-Approximation dient zur Minimierung der Summe der Quadrate der Differenzen zwischen den beobachteten und den geschätzten Werten.

Details:

• Ziel: Bestimme die Koeffizientenvektoren \(\beta\), die die Fehlerquadrate minimieren
• Formel: \[ \beta = (X^TX)^{-1}X^Ty \]
• Fehlerquadratsumme: \(\text{RSS} = \text{min} \sum_{i=1}^n (y_i - (\beta_0 + \beta_1 x_i + ... + \beta_p x_i^p))^2 \)
• Anwendung in Regressionsanalyse
• Für lineare Modelle: \(\beta = (X^TX)^{-1}X^Ty\)
• Matrixnotation: \(\text{RSS} = (y - X\beta)^T(y - X\beta)\)

Numerische Differentiationsmethoden und Fehlerquellen

Definition:

Numerische Differentiationsmethoden dienen zur Approximation der Ableitung einer Funktion, wenn die analytische Berechnung schwierig oder unmöglich ist.

Details:

• Zentrale Differenzenmethode: \[ f'(x) \approx \frac{f(x+h) - f(x-h)}{2h} \]
• Vorwärtssatzdifferenzenmethode: \[ f'(x) \approx \frac{f(x+h) - f(x)}{h} \]
• Rückwärtssatzdifferenzenmethode: \[ f'(x) \approx \frac{f(x) - f(x-h)}{h} \]
• Fehlerquellen: Rundungsfehler und Abschätzfehler
• Optimierung von h: Balance zwischen Rundungs- und Abschätzfehler

Numerische Integrationstechniken wie Trapezformel und Simpsons Regel

Definition:

Numerische Integrationstechniken wie Trapezformel und Simpsons Regel werden verwendet, um Integrale von Funktionen näherungsweise zu berechnen, wenn eine analytische Integration schwierig oder unmöglich ist.

Details:

• Trapezformel: Approximiert das Integral durch Aufteilung des Intervalls in kleinere Trapeze.
• Formel der Trapezregel: \[ \int_{a}^{b} f(x) \, dx \approx \frac{b-a}{2} \left[ f(a) + f(b) \right] \]
• Simpsons Regel: Näherung durch die Summe von Parabeln über Unterintervalle.
• Formel der Simpsons Regel: \[ \int_{a}^{b} f(x) \, dx \approx \frac{b-a}{6} \left[ f(a) + 4f \left( \frac{a+b}{2} \right) + f(b) \right] \]
• Beide Methoden erfordern die Unterteilung des Integrationsintervalls und die Summation der Einzelergebnisse.

Explizite und implizite Methoden zur Lösung von Differentialgleichungen

Definition:

Explizite und implizite Methoden zur numerischen Lösung von Differentialgleichungen; unterscheiden sich in der Behandlung des Zeitpunkts der Berechnung

Details:

• Explizite Methoden: Berechnung der nächsten Zeitstufe nur auf Basis bekannter Informationen
• Implizite Methoden: Einbindung zukünftiger Werte in die Berechnung, oft durch Lösung eines Gleichungssystems
• Explizit: z.B. Euler-Verfahren: \( y_{n+1} = y_n + h f(t_n, y_n) \)
• Implizit: z.B. Rückwärts-Euler: \( y_{n+1} = y_n + h f(t_{n+1}, y_{n+1}) \)
• Stabilität: Implizite Methoden oft stabiler, für steife Gleichungen geeignet
• Rechenaufwand: Implizite Methoden meist rechenintensiver

Konvergenz und Stabilität numerischer Verfahren

Definition:

Konvergenz bezieht sich darauf, dass numerische Verfahren eine Lösung immer näher an die exakte Lösung bringen, wenn die Schrittweite verkleinert wird. Stabilität bedeutet, dass Fehler nicht exponentiell wachsen.

Details:

• Konvergenzbedingung: Ein Verfahren konvergiert, wenn \(\forall \epsilon > 0, \exists h_0 > 0 \) so dass \(|x_n - x| < \epsilon\) für \(h < h_0\).
• Stabilitätsbedingung: Ein Verfahren ist stabil, wenn kleine Anfangsfehler nicht zu drastischen Fehlern während der Iteration führen.
• Consistency: Ein Verfahren ist konsistent, wenn der lokale Fehler \( \tau(h) \) für \( h \to 0 \) verschwindet.